Bài giảng Toán rời rạc - Chương 1: Cơ sở Logic

Ờ Ạ

TOÁN R I R C

(Discrete Mathematics)

ươ

Ch

ng 1

C s Logic

ề

ơ ở ệ Logic m nh đ Logic v tị ừ

ộ

N i dung chính

ệ

ạ ề

 Khái ni m m nh đ ề ệ  Các phép toán logic  D ng m nh đ ệ  Các quy t c suy di n ễ ắ  Các ph ứ ươ ng pháp ch ng minh  V t ượ hóa và l

ị ừ ừ ng t

ệ

ị

ề 1. Đ nh nghĩa m nh đ :

ệ

ễ

ạ

ị

 M nh đ (Proposition) ề ặ ị

ạ ừ

ể ừ

ộ ư

: là m t di n đ t có giá tr chân lý (chân i v a

ạ

ệ

ễ

ặ ờ

ệ

t Nam ệ

ủ ề

mi n b c vi

t nam

ị tr ) xác đ nh (đúng ho c sai nh ng không th v a đúng l sai). ụ ề Ví d 1.1: Các di n đ t sau, di n đ t nào là m nh đ ? ấ ặ ờ  M t tr i quay quanh trái đ t  3+1 = 5 ấ  Trái đ t quay quanh m t tr i,…  x + 2 = 8 ờ ồ ấ  M y gi r i? ỹ ề ể ả  ph i hi u k đi u này. ủ ộ  Hà n i là th đô c a Vi ắ ằ ở  Sài gòn n m ế  x+1=5 n u x=1

ệ

ề

M nh đ (tt)

Kí hi u:ệ ặ ặ

ị ị

ệ

1 (ho c T): Chân tr đúng. 0 (ho c F): Chân tr sai. ề P, Q, R,… dùng cho kí hi u các m nh đ .

ộ

ủ

ệ

t Nam ị

ệ

ự

ủ

ề

ộ

ỉ

ệ

t Nam.

ụ Ví d 1.2: ủ P: Hà N i là Th Đô c a Vi ộ ỉ Q: Quy Nh n thu c t nh Bình Đ nh ộ t Nam thu c châu Á R: Vi S: Long An là t nh thu c khu v c mi n trung c a Vi …

2. Các phép toán logic

ủ ị

Phép ph đ nh (Negation operator)

ố ề

Phép n i li n (Conjunction operator)

ố ờ

Phép n i r i (Disjunction operator)

Phép kéo theo (Implication operator)

Phép kéo theo hai chi u (Biconditional operator) ề

ủ ị

ủ

ệ

ề

ọ

ủ ị ệ

2.1. Phép ph đ nh (Negation operator)  Ph đ nh c a m nh đ P (kí hi u ¬P: đ c là “Không P”) là ế

ế

ị

ệ ề m nh đ có chân tr 1 n u P có chân tr 0 và có chân tr 0 n u P có chân tr 1. ◊B ng chân tr ị

¬P

ả

ủ

ộ

ệ

“Hà n i là th đô c a Vi

t Nam”

ủ

ộ

ệ

t Nam”

“Hà n i không ph i là th đô c a Vi ả

◊Ví d 2.1: ụ P:(cid:0) (cid:0) P:(cid:0)

(cid:0)

Q: (cid:0) (cid:0) Q:(cid:0)

“14 = 8” ” 14 (cid:0)

8”

(cid:0)

ố ề

2.2. Phép n i li n (Conjunction Operator)  Phép n i li n hai m nh đ P và Q (kí hi u P ố ề ệ ệ

ề ệ

ề

ế ả ộ ệ ế ề ặ ị

ị

P(cid:0) Q

ả (cid:0) Q: đ c là “P ọ ị ị và Q”) là m nh đ có chân tr 1 n u c P và Q có chân tr 1 ấ ho c có chân tr 0 n u ít nh t m t trong 2 m nh đ P hay Q có chân tr 0.  B ng chân tr : ị

ố ề

ụ ề

Ví d v phép n i li n

ụ Ví d 2.2:

ủ ậ và ngày mai là th 7” ứ

“Hôm nay là ch nh t ệ

ộ

ị

ề là m t m nh đ có chân tr 0.

ổ

ằ

ộ

Ví d 2.2ụ

o : “T ng các góc trong m t tam giác b ng 180 ề ệ ộ o” là m nh đ

và trong tam giác vuông có m t góc 90 có chân tr 1ị

ộ

ằ

ạ

Ví d 2.3ụ

: “Trong m t tam giác cân có 2 c nh b ng ệ

ấ

ộ

ặ ờ nhau và m t tr i quay quanh trái đ t” là m t m nh ị ề đ có chân tr 0.

ố ờ

2.3. Phép n i r i (Disjunction Operator)

 Phép n i r i k t h p hai m nh đ P,Q (kí hi u P ề

(cid:0) ệ ề (cid:0) Q: đ c ọ

ế

ặ

ị

ệ ế ả ị 0 n u c P và Q có ị

ố ờ ế ợ ệ là “P hay Q”) là m nh đ có chân tr chân tr 0 ho c có chân tr 1 n u P có chân tr 1 hay Q có chân tr 1.

ả

ị ị  B ng chân tr : ị

P(cid:0) Q 0

2.4 Phép kéo theo (Implication Operator)  M nh đ “N u P thì Q” (kí hi u P ọ Q: đ c là P kéo theo ề ầ ủ

(cid:0) ề ệ

ế ề

ệ ủ ủ ị ệ ề ị

ế ườ ị ệ Q, hay P là đi u ki n đ c a Q hay Q là đi u c n c a P) là m nh đ có chân tr 0 n u P có chân tr 1 và Q có chân tr 0, có chân tr 1 trong các tr ị ạ ợ ng h p còn l i.

ả

 B ng chân tr : ị

P(cid:0) Q 1

ụ ề

Ví d v phép kéo theo

: ế ể ố Ví d 2.4ụ P:(cid:0) c” ướ ướ i n

ộ Q:(cid:0)

(cid:0) ”.

ế ơ ế R:(cid:0) c thì cá bi ướ ướ i n t b i”:

ể ặ S:(cid:0)

“N u 3<5 thì Cá không th s ng d ị Có chân tr ……..? ổ ế “N u 2+1=4 thì t ng các góc trong m t tam giác b ng ằ ị Có chân tr ……..? ố “N u cá s ng d ị Có chân tr ……..? ế “N u chúng ta không còn gì đ ăn thì sáng mai m t m c”ọ ờ ẽ tr i s ị Có chân tr ……..?

2.5. Phép kéo theo 2 chi uề

ệ

ề

ệ

ượ ạ c l

 M nh đ “N u P thì Q và ng ế ặ

i”, kí hi u P ỉ

ỉ ế

Q (còn đ c ọ ặ

ế ệ ầ

ề

ệ

ị

ế ả ườ

ủ ể ị

là “P n u và ch n u Q” ho c “P khi và ch khi Q” ho c “P là đi u ki n c n và đ đ có Q”) có chân tr 1 n u c 2 m nh đ P ị và Q có cùng chân tr , có chân tr 0 trong các tr

ợ ng h p còn l

ề ạ i.

(cid:0) (cid:0)

ả

ị:

 B ng chân tr

P(cid:0) Q

ệ

ạ

ề

3. D ng m nh đ

Tóm t

ị ng Logic

t: ắ ị ả ươ ệ

ắ

ế

ứ

 Đ nh nghĩa  B ng chân tr ươ  T ng đ ả  H qu Logic  Các quy t c thay th ậ  Các lu t logic ươ  Các ph

ng pháp ch ng minh

ệ

ạ

ề

3.1. D ng m nh đ

ị

ộ

 Đ nh nghĩa

ứ ề ượ

ể ệ

ề ề

ở

ệ

ế

ề

ệ

ạ ệ : D ng m nh đ là m t bi u th c Logic ế ệ ằ ồ (bao g m các h ng m nh đ , bi n m nh đ đ ế ợ k t h p b i các phép toán logic). ề ạ ụ Ví d 1: Cho d ng m nh đ theo 2 bi n m nh đ p, q:

(cid:0)

E(p,q)=(p(cid:0) ả ư

ả ế (cid:0) q)(cid:0) ệ ệ ế ề ế ệ

ề ề

ả

ế

ị

 B ng chân tr cho bi

ị ủ ạ ệ

ế

ị

ệ ề t chân tr c a d ng m nh đ ề ủ theo chân tr xác đ nh c a các bi n m nh đ .

(cid:0) p  B n thân E(p,q): Ch a ph i là m nh đ . ề  N u thay bi n m nh đ p b i m nh đ P và bi n m nh đ ề ề ở ệ ị ệ ệ ở q b i m nh đ Q. Khi đó E(P, Q) là m nh đ (có chân tr ị xác đ nh)

ề

ệ

ạ

3.1. D ng m nh đ (tt)

ệ

ậ

ả

Ví d 3.1ụ

ề : L p b ng chân tr c a d ng m nh đ :

ị ủ ạ (cid:0) q)(cid:0)

(cid:0) p

E(p,q)=(p(cid:0)

(cid:0)

(cid:0) (cid:0) p p(cid:0) q p(cid:0) q(cid:0) (cid:0) p p q

0 0 1 0 1

0 1 1 0 1

1 0 0 0 1

1 1 0 1 0

ề

ạ

ệ D ng m nh đ (tt)

ề

ậ

ả

ạ

ệ

i thành d ng m nh đ là l p b ng chân tr cho

ế ạ t l

ế

ạ

ị ổ

c phép đi xe máy n u b n trên 16 tu i và có

c phép đi xe máy.

q(cid:0)

(cid:0) r

q(cid:0)

(cid:0) r(cid:0) p

ứ

ạ

: Vi Ví d 3.2ụ ạ ễ ạ ượ di n đ t: “B n đ ỏ ố ứ s c kh e t t”. ạ ượ G i:ọ p: B n đ ổ ạ q: B n trên 16 tu i. ỏ ố ạ r: B n có s c kh e t ệ ạ ễ D ng m nh đ cho di n đ t trên: q(cid:0)

ề (cid:0) r(cid:0) p.

ả

ị

B ng chân tr :

ươ

ả

3.2 T

ng đ

ệ ng logic & h qu logic

 Hai d ng m nh đ

ạ ệ ế n u chúng ng đ

(cid:0) (cid:0)

ả ươ ị ớ ặ ươ ng logic ọ F (còn đ c là “E ươ ươ ớ ng logic v i F” ho c “F t ng đ ng đ ng Logic v i

ề E và F t ươ ệ có cùng b ng chân tr . Kí hi u E ươ t E”). ạ ề ọ ằ ế h ng đúng (tautology) n u nó luôn

có chân tr 1.

 D ng m nh đ g i là ệ ị  D ng m nh đ g i là ệ

ạ ằ ẩ h ng sai (mâu thu n

ị Contradiction) n u nó luôn có chân tr 0.

 E và F t đúng.

ươ ỉ ộ ằ ề ọ ế ươ ng đ ng logic khi và ch khi E (cid:0) F là m t h ng

 F là h qu logic c a E (kí hi u E

(cid:0) (cid:0) ủ ệ ệ ả (cid:0) F) n u E ế F là h ng ằ

đúng.

ươ

ả

ng đ

ệ ng logic & h qu logic (tt)

ề

(cid:0) (p(cid:0) q)](cid:0) p

ả

(cid:0) (p(cid:0) q) (cid:0) ứ Ví d 3.3ụ : Ch ng minh ệ ạ Xét d ng m nh đ E(p,q)= [ ị ủ B ng chân tr c a E:

p q p(cid:0) q (cid:0) (p(cid:0) q)

[(cid:0) (p(cid:0) q)](cid:0) p

0 0

0 1

1 0

1 1

ệ ề (cid:0) (p(cid:0) q)](cid:0) p luôn là 1.

ị ủ ạ ấ Ta th y chân tr c a d ng m nh đ [ V y: [ậ (cid:0) (p(cid:0) q)](cid:0) p

ng đ

ươ ụ

ệ ươ ng logic & h qu logic (tt) ả

ị ể ứ

(q(cid:0) r(cid:0) q) (cid:0) ệ

ả

(cid:0)

ả T Ví d 3.4: Dùng b ng chân tr đ ch ng minh: ((cid:0) q (cid:0) (cid:0) r (cid:0) p) (cid:0) r(cid:0) q) (cid:0) ề

ị ủ ạ B ng chân tr c a d ng m nh đ : (q

((cid:0) q (cid:0) (cid:0) r (cid:0) p)

(cid:0) q (cid:0) r

(cid:0) q (cid:0) (cid:0) r (cid:0) p

r q(cid:0) r(cid:0) q 0

ự

ứ

ề

ị ả D a vào b ng chân tr , ta ầ suy ra đ u c n ch ng minh?

ắ

ế 3.3. Các quy t c thay th :

ắ

 Quy t c thay th th nh t ế ứ ấ

ề ươ ề ớ ẫ ươ

ế ộ ươ ươ

ng đ ng đ

ể ng logic ng logic

ề

ạ

q) (cid:0)

¬p (cid:0) q nên theo quy t c thay th th ế ứ

ộ ạ ề ế ệ Trong m t d ng m nh đ , n u thay th m t bi u ở ệ ộ ạ ứ th c con b i m t d ng m nh đ t ệ ượ ạ c d ng m nh đ m i v n t thì đ ầ ệ ạ d ng m nh đ ban đ u. Ví d 3.5ụ ệ : Cho d ng m nh đ : (p q (cid:0) Do p (cid:0) ắ ấ nh t, ta có:

(p (cid:0)

q) (cid:0)

r (cid:0)

(¬p (cid:0) q ) (cid:0)

(cid:0)

ế

ắ 3.3. Các quy t c thay th (tt)

ắ

 Quy t c thay th th 2:

ằ

ầ

ậ ượ ạ

(cid:0) ệ Ví d 3.6ụ

ế 1, p2,…) là h ng đúng, n u thay ề ấ ỳ ệ ộ ạ ở i trong E b i m t d ng m nh đ b t k ằ ả ề ế ệ c d ng m nh đ k t qu là h ng đúng. ((cid:0) p (cid:0) q) (cid:0) q) (cid:0) : Cho d ng m nh đ : E(p,q)=(p ằ

ệ

ế ứ ề ệ ả ử ạ Gi s d ng m nh đ E(p ế th thành ph n p thì cũng nh n đ ạ ứ Ta đã ch ng minh đ Thay p b i rở (cid:0) s, ta đ

c E(p,q) là h ng đúng. ề c d ng m nh đ : [(cid:0) (r(cid:0) s) (cid:0) q]

ề ượ ượ ạ E’(r,s,q)= [(r(cid:0) s)(cid:0) q] (cid:0) ế ứ ắ Theo quy t c thay th th 2, ta có E’(r,s,q) cũng là

ằ h ng đúng.

ậ

ề

ệ

ế

ươ

3.4. Các qui lu t logic  V i p,q,r và s là các bi n m nh đ . Ta có các t

ớ ươ

ng logic sau: ủ ị

ủ

đ ủ ị 1. Ph đ nh c a ph đ nh (Double negation)

2. Quy t c De Morgan (DeMorgan’s Rules)

(cid:0)

¬p (cid:0) ¬q ¬p (cid:0) ¬q 3. Lu t giao hoán (Commutative Rules)

¬¬p (cid:0) ắ ¬(p (cid:0) q) (cid:0) ¬(p (cid:0) q) (cid:0) ậ p (cid:0) q (cid:0) p (cid:0) q (cid:0)

q (cid:0) p q (cid:0) p

(cid:0)

ậ

Qui lu t logic (tt)

ậ ế ợ

ố

4. Lu t k t h p (Associative Rules) (p (cid:0) q) (cid:0) r (p (cid:0) q) (cid:0) r 5. Lu t phân ph i (Distributive Rules)

(p (cid:0) q) (cid:0) (p (cid:0) r) (p (cid:0) q) (cid:0) (p (cid:0) r) ẳ

dempotent Rules)

p (cid:0) (q (cid:0) r) (cid:0) p (cid:0) (q (cid:0) r) (cid:0) ậ p (cid:0) (q (cid:0) r) (cid:0) p (cid:0) (q (cid:0) r) (cid:0) ậ p (cid:0) p (cid:0) p (cid:0) p (cid:0)

6. Lu t lũy đ ng (I p p

ậ

Qui lu t logic (tt)

7. Lu t trung hòa

8. Lu t ph n t

bù (Negation rules)

ị 9. Lu t th ng tr

ậ p (cid:0) 1 (cid:0) p (cid:0) 0 (cid:0) ậ p (cid:0) ¬p (cid:0) p (cid:0) ¬p (cid:0) ậ p (cid:0) 0 (cid:0) p (cid:0) 1 (cid:0)

p p ầ ử 0 1 ố 0 1 ậ ấ 10. Lu t h p th ( p (cid:0) (p (cid:0) q) (cid:0) p (cid:0) (p (cid:0) q) (cid:0)

ụ absorption rules) p p

ễ

ắ

3.5 Các quy t c suy di n

 Ph

q) (cid:0) p] (cid:0) ạ ế

Đ c th hi n b i h ng đúng: [(p Ví d 3.7ụ

ả ố

ươ

ậ

ẳ

(cid:0) ươ ượ

t (ph

ng pháp kh ng

ệ

t”

(cid:0) q

ươ

ẳ

ị

ị đ nh). ế ằ t b ng kí hi u logic: ọ p: “Tôi h c chăm”; ả ố ạ ế q: “Đ t k t qu t p(cid:0) p (cid:0) q

(ph

ng pháp kh ng đ nh)

ẳ ị ng pháp kh ng đ nh (Modus Ponens) ở ằ ể ệ q ả ố ọ ế : N u tôi h c chăm thì tôi đ t k t qu t ọ Mà tôi h c chăm ạ ế V y: Tôi đ t k t qu t

ắ

ễ

ọ

¬p ả ố t

ươ

ủ ị

3.5 Các quy t c suy di n  Ph ắ (quy t c Modus Tollens) q) (cid:0) ¬q] (cid:0) [(p (cid:0) ở ằ ể ệ Th hi n b i h ng đúng: ạ ế ế Ví d 3.8ụ : N u tôi h c chăm thì tôi đ t k t qu t ả ố ạ ế t Mà tôi không đ t k t qu t ọ V y: Tôi không chăm h c (ph

ng pháp ph đ nh).

ệ

ậ t b ng kí hi u logic:

t”

(cid:0) q

ươ ủ ị ng pháp ph đ nh

ươ

ủ ị

ế ằ ọ p: “Tôi h c chăm”; ả ố ạ ế q: “Đ t k t qu t p(cid:0) ¬ q ¬ p

(ph

ng pháp ph đ nh)

(cid:0)

ễ

ắ

3.5 Các quy t c suy di n

ở ằ

ượ

ạ ể ệ

 Tam đo n lu n ậ Đ c th hi n b i h ng đúng:

(p (cid:0)

q) (cid:0) (q (cid:0)

Ví d 3.9ụ

nhà

[(p (cid:0) ọ : N u An đi h c thì Dũng ở

ậ

r)] (cid:0) ở nhà thì Dũng làm bài t p

ế ậ

ế

ậ

ọ

ủ ủ ộ

ụ

ệ

ầ

ế N u Dũng V y: N u An đi h c thì Dũng làm bài t p ấ Ví d 3.10: A, B và C là 3 c u th c a đ i bóng. Hu n luy n viên

ượ

ấ

c tham gia

ượ

ậ

ấ

ượ

ậ N u A tham gia tr n đ u thì B không đ c tham gia tr n đ u thì C cũng không đ N u B không đ

ị quy đ nh: ế ế tham gia ậ

ế

ậ

ấ

ượ

V y: N u A tham gia tr n đ u thì C không đ

c tham gia.

ễ

ắ

3.5 Các quy t c suy di n

 Tam đo n lu n r i ậ ờ ạ [(p (cid:0) q) (cid:0) ¬p] (cid:0) q ả ử ộ

ườ ề s cu c thi đi n kinh có 2 ng i tham gia A

ả ạ ả ấ i nh t

ậ ả i nh t hay B ph i đ t gi ạ ả ạ ụ Ví d : Gi và B. ấ ả ạ A ph i đ t gi ả mà: A không đ t gi ả V y: B ph i đ t gi ấ i nh t ấ i nh t

ễ

ắ

Các quy t c suy di n (tt)

ươ

ứ ả ẩ (ph n ch ng)

ng logic q] (cid:0)

(cid:0)

 Quy t c mâu thu n ắ ươ Ta có t ng đ (cid:0) p2 (cid:0) … (cid:0) pn) (cid:0) [(p1

[(p1

(cid:0) p2 (cid:0) … (cid:0) pn (cid:0) ¬q) (cid:0) 0]

ườ ở ể ệ ợ : Th hi n b i

 Quy t c ch ng minh theo tr ứ

ng h p

ắ ằ h ng đúng:

[(p(cid:0)

r) (cid:0) (q(cid:0)

r)] (cid:0)

[(p (cid:0) q) (cid:0)

(cid:0) (cid:0) (cid:0)

ụ

ộ ố M t s ví d

ạ ễ : Cho di n đ t:

ượ ế ạ ọ ọ c x p h ng cao trong h c

ạ c x p h ng cao.

ượ ế ọ ươ

ủ ị ư ễ ộ ng pháp ph đ nh). t m t cách hình th c cho suy di n trên nh sau:

ụ Ví d 3.11 ế N u An h c chăm thì An đ t pậ Mà An không đ ậ V y An không h c chăm (Ph ứ ế Vi ọ G i p: “An h c chăm”

ạ ọ ậ q: “An đ

Ta có:

(cid:0) ủ ị ọ ượ ế p (cid:0) q (cid:0) q (cid:0) p c x p h ng cao trong h c t p” ề ề (ti n đ ) ề (cid:0) ề (ti n đ ) ươ ng pháp ph đ nh) (Ph

(cid:0) (cid:0)

ộ ố M t s ví d (p(cid:0) q)(cid:0)

ụ ((cid:0) p(cid:0) q)

(cid:0) ụ Ví d 3.12 Ta có: (cid:0) ((cid:0) p(cid:0) q)

(cid:0) (cid:0)

(cid:0) (cid:0) ậ (lu t De Morgan) (cid:0) [(p (cid:0) q) (cid:0) (cid:0) q] (lu t phân ph i) ố ậ ụ ậ ấ (cid:0) [(p (cid:0) (cid:0) q) (cid:0) (q (cid:0) (cid:0) q)] (lu t h p th , phân

(cid:0) (cid:0) ầ ử bù)

(cid:0) (cid:0) (cid:0) [(p (cid:0) (cid:0) q) (cid:0) 0] (cid:0) (p (cid:0) (cid:0) q)

(cid:0) (cid:0) : Rút g nọ (p(cid:0) q)(cid:0) (cid:0) q) (cid:0) (p(cid:0) (p(cid:0) q)(cid:0) [(p (cid:0) q) (cid:0) p](cid:0) p(cid:0) ph i)ố p(cid:0) p(cid:0) p ậ (lu t ph n t ậ (lu t trung hòa) ụ ậ ấ (lu t h p th )

ụ

ộ ố M t s ví d

 T nh n xét trên, ta có 2 đo n ch

ạ ươ ươ ng trình trên là t ng

if ((p || q) && (!(!p && q)))

if (p)

{

ự

ệ

ự

ệ

Th c hi n S;

}

ừ ậ ươ ng: đ

 Ví d 3.8b: Ch ng minh [(p

(cid:0) ứ ụ (cid:0) q)(cid:0) r] (cid:0) [p (cid:0) (q (cid:0) r)]

ụ

ộ ố M t s ví d

 T nh n xét trên, ta có 2 đo n ch

ạ ươ ươ ng trình trên là t ng

if (p)

if (p && q)

if (q)

z=0;

for (int i=1; i<=10; i++)

{

x = i+2;

{

x = i+2;

y=i1;

if (x>=10)

if ((x>=10) && (y<=8))

if (y<=8))

z+=1;

(b)

z+=1;

}

(a)

ừ ậ ươ ng: đ

ụ

ộ ố M t s ví d

ụ Ví d 3.13

(r(cid:0) q) (s(cid:0) t)

Ta có:

ố ề nên

(r(cid:0) q)

Và Nên

ứ : Ch ng minh: p(cid:0) q p(cid:0) r(cid:0) (cid:0) s (cid:0) t p(cid:0) q p p (cid:0) r (cid:0) q ề ề (ti n đ ) ả ơ (Đ n gi n n i li n) ề ề (ti n đ ) ị ẳ (kh ng đ nh)

ụ

ộ ố M t s ví d

ố ề

ề

(s(cid:0) t)

(ti n đ )

ẳ ề

r r(cid:0) s(cid:0) t (cid:0) s (cid:0) t

ả (đ n gi n n i li n) ề ị (kh ng đ nh) ề (ti n đ ) ậ ờ ạ (tam đo n lu n r i) ả ử ộ ộ s

: a,b,c,d và e là 5 thành viên trong m t đ i bóng. Gi

ệ

ấ

Suy ra ơ ữ H n n a nên Mà Nên ụ Ví d 3.14 ấ hu n luy n viên có các quy đ nh nh sau: ế ế ế ế

ủ

ề

ầ

ậ

ấ ấ i c 2 c u th d và e đ u không tham

ị  N u b không tham gia vào tr n đ u thì a cũng không tham gia. ậ  N u b tham gia vào tr n đ u thì c cũng tham gia ậ  N u c tham gia vào tr n đ u thì d cũng tham gia ậ  N u trong tr n đ u s p t ấ ắ ớ ả gia thì a có tham gia không? c có tham gia không?

i:ả

(cid:0) b (cid:0) a bc cd (cid:0) d (cid:0) e ?a ?c

ủ ị

ề ề (ti n đ ) ề ề (ti n đ ) ươ ng pháp ph đ nh) (ph ề ề (ti n đ ) ươ ng pháp ph đ nh) (ph

ề

ươ

ẳ

ị

Ta có Và Nên Ta có Nên Và Nên

cd (cid:0) d (cid:0) c bc (cid:0) b (cid:0) b (cid:0) a (ti n đ ) ề (cid:0) a

(ph

ng pháp kh ng đ nh)

4. Logic v tị ừ

ị

là m t kh ng đ nh có d ng p(x,y,z,…) trong đó x, y, z,

: ẳ ộ ế ấ

ậ

ợ

ị

c sao cho:

ế

ỳ

A, b(cid:0) B, c(cid:0)

ượ ế ự

ọ

(cid:0)

ị ừ : 4.1 V t  Đ nh nghĩa 4.1 ị ạ ị ừ V t … là các bi n l y giá tr trong các t p h p A, B, C,… cho ướ tr  p(x,y,z,…) không ph i là m nh đ ề ệ  N u thay x,y,z,… b i các ph n t ầ ử ố ị ư c đ nh nh ng tu ý ề ệ c m nh đ p(a,b,c,…). do

ả ở a(cid:0) C,… ta đ x, y, z,… g i là các bi n t

ị ừ

4. Logic v t

(tt)

Ví d 4.1ụ

ế

:  Cho n(cid:0)

ệ

ề

ộ ị ừ

ế

(cid:0) N, p(n)=“ n chia h t cho 3.” ư ả p(n): Không ph i là m nh đ . Nh ng: ị ệ ề p(10): là m nh đ có chân tr 0 ị ề ệ p(15): là m nh đ có chân tr 1 (cid:0) N. p(n) là m t v t

theo bi n n

R. (cid:0) N

ộ ị ừ ố

ố

ụ Ví d 4.2: p(x,y)=“x2+y2>5” là m t v t p(n)=“n là s nguyên t ” là v t

ế theo 2 bi n x, y ế ị ừ theo bi n n, n

(cid:0)

ị ừ

4. Logic v t

(tt)

Cho p(x), q(x) là các v t

 Đ nh nghĩa 4.2:

ế ị ừ ộ theo m t bi n

ủ ị

(cid:0) ố ị ủ ị ớ ư A c đ nh nh ng tùy ý thì ệ (cid:0) p(x) là m t v t ộ ị ừ (cid:0) p(a) là ph ủ

ươ ứ ố ề

ươ ứ ề

ệ q(x)) là v t ư

ươ ứ

ị x(cid:0) A. i) Phép ph đ nh: Ph đ nh p(x), kí hi u sao cho(cid:0) v i x=a ủ ị đ nh c a p(a). ố ờ ng ng n i r i, kéo theo, kéo theo 2 ii) Phép n i li n (t (cid:0) q(x) (t ủ chi u) c a p(x) và q(x), kí hi u p(x) p(x)(cid:0) q(x), p(x)(cid:0) q(x), p(x)(cid:0) ị ừ thay x b i a ở (cid:0) A c đ nh nh ng tùy ý thì đ ố ị p(a)(cid:0) q(a) (t ng ng p(a)

ng ng ế theo bi n x mà khi ề ệ ượ c m nh đ q(a)) (cid:0) q(a), p(a)(cid:0) q(a), p(a)(cid:0)

ị ừ

4. Logic v t

(tt)

ườ ả ợ (cid:0) A. Có 3 tr

ề ệ

ượ 4.2 L ị ừ Cho v t ớ o V i m i a

ừ: ng t ng h p x y ra: p(x), x ệ (cid:0) ọ (cid:0) A, m nh đ p(a) đúng. Kí hi u “

(cid:0) a (cid:0) A, p(a)

”

ả ấ ả ớ ị ề ệ t c ), m nh đ ộ ố o V i m t s giá tr a

(cid:0) A (không c n ph i t ầ A, p(a) ”

ớ ệ

ị

ủ ở ượ ừ ng t

p(a) đúng. Kí hi u:”ệ (cid:0) a (cid:0) ọ (cid:0) A, m nh đ p(a) sai. KÍ hi u: ề o V i m i a (cid:0) a (cid:0) “(cid:0) Đ nh nghĩa: Và :”(cid:0) x(cid:0) A, p(x)” g i là l ng t ệ A, ¬p(a) ” (cid:0) x(cid:0) ề (cid:0) ệ A, p(x)” Các m nh đ “ ừ ượ ọ hóa c a p(x) b i l ng t ừ ồ ạ (cid:0) ượ t n t i ổ ụ (cid:0) ph d ng và l .

ừ

ượ

ng t

ị ừ (tt) ủ t ý nghĩa c a các l

Sai khi:

Đúng khi:

ớ

ọ

ộ

ị

Có m t giá tr x, p(x) sai

ị

ọ

ớ p(x) sai v i m i x

ị

Đ nh lý:

ừ

ệ

ị ừ ủ hóa c a v t ượ

ng t

ừ (cid:0)

ị ừ

ượ

ủ ị ộ ng t

ừ (cid:0)

ở p(x,y,z,…) b i các ượ ằ b ng l ng t ị ừ ằ

ừ (cid:0) p(x,y,z,…) b ng v t

4. Logic v t ắ Tóm t M nh ệ đề (cid:0) x, p(x) p(x) đúng v i m i x (cid:0) x, p(x) Có m t giá tr x, p(x) ộ đúng ề ượ ủ ng t Ph đ nh c a m nh đ l ượ ệ ừ ượ ằ ề c b ng cách thay l l ng t là m t m nh đ có đ ừ (cid:0) ằ ượ và thay v t b ng l ng t và thay l (cid:0) p(x,y,z,…)

Ví d :ụ (cid:0)

((cid:0) x (cid:0) y, p(x,y)) (cid:0)

(cid:0) x (cid:0) y, (cid:0) p(x,y)

ề ươ

ươ

ng đ

Đúng khi:

(cid:0)

ộ

ị

Có m t giá tr x, p(x) sai

(cid:0)

ọ

ề ệ M nh đ (cid:0) x, p(x) (cid:0) x, p(x)

ệ M nh đ t (cid:0) x, (cid:0) p(x) (cid:0) x, (cid:0) p(x)

ớ p(x) sai v i m i x

(cid:0)

ị ừ

4. Logic v t

(tt)

ả

ắ

ượ

ừ

B ng tóm t

t ý nghĩa các l

ng t

ế hai bi n

ề

Sai khi:

ọ ặ

ớ

ộ ặ

ệ Đúng khi: M nh đ (cid:0) x (cid:0) y, p(x,y) P(x,y) đúng v i m i c p

x,y

Có m t c p x, y mà p(x,y) sai

ọ

ớ

ộ

ể

ớ

ộ Có m t x đ p(x,y) sai v i m i yọ

ể

ọ

ớ

ộ

ớ

ể V i m i x có m t y đ p(x,y) sai

ể

ọ ặ

ớ P(x,y) sai v i m i c p x,y

đúng

(cid:0) y (cid:0) x, p(x,y) (cid:0) x (cid:0) y, p(x,y) V i m i x có m t y đ ể p(x,y) đúng (cid:0) x (cid:0) y, p(x,y) Có m t x đ p(x,y) đúng ộ ọ v i m i y (cid:0) x (cid:0) y, p(x,y) Có m t c p x, y đ p(x,y) ộ ặ (cid:0) y (cid:0) x, p(x,y)

(tt)

ệ

ị ừ 4. Logic v t ề ị ủ Ví d 4.3: Tìm chân tr c a các m nh đ :

ụ a) (cid:0) x(cid:0) [0,1], x3+4x25=0 b) (cid:0) x(cid:0) [0,1], x3+4x25=0

Ví d 4.4ụ

ề Xét xem các m nh đ sau là đúng hay sai?

f )

: V i xớ (cid:0) R, xét các v t ị ừ : p(x): x(cid:0) 0 (cid:0) 0 q(x):x2(cid:0) r(x): x2 – 4x – 5 = 0 s(x): x2 – 3 (cid:0) 0 ệ (cid:0) x, (cid:0) p(x) (cid:0) r(x) (cid:0) x, p(x) (cid:0) r(x) (cid:0) x, p(x)(cid:0) q(x) (cid:0) x, q(x)(cid:0) s(x) (cid:0) x, r(x)(cid:0) p(x) (cid:0) x, r(x)(cid:0) q(x)

(cid:0)

ị ừ

4. Logic v t

(tt)

 Đ nh lý ị

ị ừ ệ ế ề theo 2 bi n x, y. Các m nh đ sau là

(cid:0)

(cid:0) : Cho p(x,y) là v t ằ h ng đúng: i) [(cid:0) x(cid:0) A,(cid:0) y(cid:0) B, p(x,y)](cid:0) ii) [(cid:0) x(cid:0) A, (cid:0) y(cid:0) B, p(x,y)](cid:0) iii) [(cid:0) x(cid:0) A, (cid:0) y(cid:0) B, p(x,y)](cid:0) [(cid:0) y(cid:0) B,(cid:0) x(cid:0) A, p(x,y)] [(cid:0) y(cid:0) B, (cid:0) x(cid:0) A, p(x,y)] [(cid:0) y(cid:0) B, (cid:0) x(cid:0) A, p(x,y)]

 Quy t c đ c bi

ố ị

(cid:0) A, a c đ nh nh ng b t k . ấ ỳ

ệ ắ ặ ổ ụ

ắ ổ t hóa ph d ng: (cid:0) x(cid:0) A, p(x) đúng thì p(a) đúng v i a ớ  Quy t c t ng quát hóa ph d ng:

ệ ổ ụ ấ ỳ ớ (cid:0) A b t k thì m nh đ : ề (cid:0) x(cid:0) A, p(x)

ế N u p(a) đúng v i a đúng.

ị ừ

4. Logic v t

(tt)

ừ ế ng t p(x,y,z,…). N u ta

ượ

ế

ớ

ừ

ng t

ủ ớ

ệ

ề

ệ

ế

ị

 M nh đ m i là h qu logic c a v i m nh đ cũ n u 2 ạ

(cid:0) (cid:0)

 M nh đ ề: ệ ề ượ ệ Trong m nh đ l ượ ng t hoán v 2 l  M nh đ m i t ề ớ ươ ệ ị ượ ề ớ ệ ừ ượ ượ đ l

ng t

ủ ị ừ hóa c a v t ượ ề ừ ề c: li n k thì ta đ ươ ề ệ ng v i m nh đ cũ n u 2 l ng đ ạ c hoán v có cùng lo i. ả ị c hoán v có d ng

ị ừ

(tt)

4. Logic v t Ví d 4.5ụ

: Cho A={x là sinh viên} p(x): “x là sinh viên khoa cntt” ờ ạ ả ọ q(x): “x ph i h c toán r i r c”.

Coi lý lu n:ậ ọ

ề

ả ọ

ườ

ả ọ

ị ừ :

(cid:0) A)

ộ “ C ng là m t sinh viên” (a q(x)

ổ ụ

(cid:0) x(cid:0) A, p(x) (cid:0) q(a)

ị

ề ề (ti n đ ) ệ ặ (đ c bi t hóa ph d ng) ề ề (Ti n đ ) ẳ (pp kh ng đ nh) ả ọ

ườ

ờ ạ M i sinh viên khoa CNTT đ u ph i h c toán r i r c ờ ạ Mà C ng là sinh viên khoa CNTT, nên C ng ph i h c toán r i r c ế ạ t d ng logic v t ườ G i a:ọ Do nên p(a) (cid:0) Mà p(a) nên: q(a) ờ ạ ườ Mà C ng là sinh viên khoa CNTT, nên C ng ph i h c toán r i r c

ườ

A: “C ng là sinh viên khoa CNTT”

(cid:0)

ị ừ

4. Logic v t

(tt)

ứ

Ví d 4.6ụ

q(x)] r(x)]

: Ch ng minh: (cid:0) x, [p(x) (cid:0) (cid:0) x, [q(x) (cid:0) (cid:0) x, [p(x) (cid:0)

r(x)]

Ta có:

ề ề

ề (ti n đ ) ề (ti n đ )

ớ

q(x)] r(x)] ố ị

ổ ụ ổ ụ

ổ ụ

ổ

(cid:0) x, [p(x) (cid:0) (cid:0) x, [q(x) (cid:0) ấ ỳ ư V i a b t k nh ng c đ nh ta có: p(a) (cid:0) q(a) q(a) (cid:0) r(a) p(a) (cid:0) r(a) V y: ậ (cid:0) x, [p(x) (cid:0)

r(x)]

ệ ặ (đ c bi t hóa ph d ng) ệ ặ (đ c bi t hóa ph d ng) ậ ạ (tam đo n lu n) (t ng quát hóa ph d ng)

(cid:0)

ị ừ

4. Logic v t

(tt)

Ví d 4.8ụ : Ch ng minh:

ằ

ứ A={Các tam giác} ạ p(x): x có 2 c nh b ng nhau q(x): x là tam giác cân r(x): x có 2góc b ng nhau

ế ậ ằ

ằ Lý lu n sau:”N u tam giác không có 2 góc b ng nhau thì tam ằ ạ giác này không có 2 c nh b ng nhau. Đúng hay sai?

5. Nguyên lý quy n p:ạ

(cid:0) N và n (cid:0) Đ ch ng minh p(n) đúng v i m i n n0. Ta có

ọ ư ớ ạ

 Ki m ch ng p(n

0) đúng

ể ứ ể th dùng nguyên lý quy n p nh sau: ể ứ

 N u p(n) đúng (n

(cid:0) ế n0 ) thì p(n+1) đúng

 K t lu n: p(n) đúng

(cid:0) ậ ế

p(n+1)

ử ụ n(cid:0) ễ n0 Nghĩa là s d ng suy di n sau:

p(n0) (cid:0) n > n0, p(n) (cid:0)

(cid:0) n (cid:0)

n0, p(n)

(cid:0)

ạ

ứ

ằ

5. Nguyên lý quy n p (tt) ụ Ví d 5.1: Ch ng minh r ng:

1.1! + 2.2!+…+n.n!=(n+1)!1

i:ả

p(n)=“1.1! + 2.2! + … + n.n! = (n+1)! 1”

ả ử

Đ t:ặ Ta có: p(1)=“1.1! = (1+1)! – 1” đúng s p(n) đúng v i n

ớ (cid:0) 1 đúng, ta ch ng minh p(n+1) cũng ứ

Gi đúng.

Do p(n) đúng nên:

(cid:0)

ạ

(cid:0) n(cid:0) 1, p(n)

1.1! + 2.2! + … + n.n! = (n+1)! – 1 1.1! + 2.2! + … + n.n!+(n+1).(n+1)! = (n+1)! – 1+(n+1).(n+1)! 1.1! + 2.2! + … + n.n!+(n+1).(n+1)! = (n+1)!(1+n+1) –1 1.1! + 2.2! + … + n.n!+(n+1).(n+1)! = (n+2)! –1 ậ V y p(n+1) cũng đúng. Theo nguyên lý quy n p, ta có: đúng.

(cid:0)

Bài t p ậ

 Bài 1: Cho bi

ổ

ế ệ

ế

c sôi

ộ oC

ề ằ

ằ

ộ

ị ủ t chân tr c a các m nh đ sau: a) (cid:0) =2 và t ng các góc trong m t tam giác b ng 180 ở ướ b) N u 2>3 thì n ổ

ệ ề ạ ị

(cid:0)

q (cid:0) q

100 N u ế (cid:0) =1 thì t ng các góc trong m t tam giác b ng 170 Bài 2:L p b ng chân tr cho các d ng m nh đ sau: ậ ả (cid:0) ((cid:0) p (cid:0) q) (cid:0) a) p(cid:0) (cid:0) ((cid:0) p (cid:0) q) (cid:0) b) p(cid:0) c) (p > q) > (q>p)

(cid:0)

Bài t pậ

ủ ị ứ ể

ằ ủ ữ ự ề ễ t d ng ph đ nh (b ng bi u th c logic và di n ạ nhiên) c a các d ng m nh đ sau:

ế ạ Bài 3: Vi ằ b ng ngôn ng t ế ế ệ a) N u P là hình ngũ giác thì P là hình đa giác ủ ủ b) N u Tom là cha c a Ann, thì Jim là chú c a Ann, Sue là

ủ ọ ủ

 Bài 4: Vi

ế

t 2 phát bi u khác nhau s d ng “phép kéo ớ ươ ề ọ ng v i phát bi u “H c C là đi u

ươ ế ể ọ ệ ầ ấ cô c a Ann và Mary là em h c a cô y. ử ụ ể ể ng đ t đ h c C++“ theo” có nghĩa t ki n c n thi

Bài t pậ

(cid:0)

ề (cid:0) p (cid:0) q) (cid:0) ề ệ ệ ọ ng

 Bài 5: Cho d ng m nh đ : ( ạ ạ ỉ ử ụ

(cid:0) ố (r (cid:0) (cid:0) q) bi n đ i ổ ế ề ươ ạ ng ch s d ng các phép n i logic và rút g n d ng m nh đ này thành d ng m nh đ t ươ đ

 Bài 6: Các phát bi u nào sau đây t

ể ươ

ệ và (cid:0) ươ ng đ ế ể ế

ế

ặ

ế

ặ

ế

ặ

b) N u n không chia h t cho 30 thì n không chia h t cho 2 ho c

ế

ế ế

ế

ặ

c) N u n chia h t cho 2 , cho 3 và cho 5 thì n chia h t cho 30. ặ d) N u n không chia h t cho 2 ho c không chia h t cho 3 ho c

ế

ế ế h t cho 3 ho c n chia h t cho 5 ế ế ặ không chia h t cho 3 ho c không chia h t cho 5 ế ế ế không chia h t cho 5 thì n không chia h t cho 30

ế ế ớ ng v i phát bi u “N u n chia h t cho 30 thì n chia h t cho 2, 3 và 5”: a) N u n không chia h t cho 30 thì n chia h t cho 2 ho c n chia

Bài t pậ

(cid:0) (cid:0) ươ ạ ề r) có t ng

 Bài 7: D ng m nh đ (p ệ

ệ ớ ạ đ r) (cid:0) (q (cid:0) ề ng logic v i d ng m nh đ :

(cid:0)

 Bài 8: Cho bi

ế ệ

ế t chân tr c a các m nh đ sau n u ố ả ị ủ ậ

ươ [((cid:0) p (cid:0) r) (cid:0) (p (cid:0) (cid:0) r)] (cid:0) [((cid:0) q (cid:0) r) (cid:0) (q (cid:0) (cid:0) r)] ề không gian kh o sát là t p các s nguyên:  (cid:0) n, (n2(cid:0) 0)  (cid:0) n(cid:0) m, (n (cid:0) < m2)  (cid:0) n (cid:0) m, (m+n = 0)  (cid:0) n (cid:0) m (n+m=4 (cid:0) nm =1 )  (cid:0) n (cid:0) m (cid:0) p (p=(m+n)/2)

Bài t pậ

 Bài 9: Xác đ nh giá tr chân lý c a các m nh đ sau:

ủ ề ệ ị ị

y+x

(2x3+3x1=0)

 (cid:0) x(cid:0) R, x2 = 2  (cid:0) x(cid:0) R (cid:0) y(cid:0) R, x+y (cid:0)  (cid:0) x(cid:0) R (cid:0) y(cid:0) R, (x+2y = 2)(cid:0) (2x+4y=5)  (cid:0) x(cid:0) R, 2x2+3x5 =0  (cid:0) x(cid:0) R, (3x2+4x+5 =0)(cid:0)  (cid:0) x(cid:0)

[0,5], 2/3.x3+2x>=2

(cid:0)

Bài t pậ

ề ớ ạ ủ

lim ố i h n c a dãy s : n

ớ

ể

ượ

ọ

ế ỉ ố ch s N(

c bé tùy ý, có th tìm đ (cid:0) ) thì |xna| < (cid:0) ề ớ

ệ

ị Bài 10: Ta có đ nh nghĩa v gi ọ ố ự (cid:0) >0 cho tr ướ n u v i m i s th c (cid:0) ) sao cho v i m i n> N( ớ ằ ế ạ ị t l

ệ i đ nh nghĩa trên b ng m nh đ v i các kí hi u

ủ ị

ủ

ệ

ề

ạ

a) Hãy vi logic b) Tìm d ng ph đ nh c a m nh đ trên

(cid:0) (cid:0) (cid:0)

Bài 11: Ta có đ nh nghĩa: Hàm s y=f(x) liên t c t

ụ ạ ố ị i x = a khi

ỉ và ch khi:

(cid:0) (cid:0) >0, (cid:0) |f(x)f(a)|<(cid:0)

(cid:0) >0, (cid:0) x(cid:0) D, |x – a| <(cid:0) (cid:0) ủ ị ề ệ ế ạ ủ t d ng ph đ nh c a m nh đ trên. Vi

Bài t pậ

ứ Bài 12) Ch ng minh:

(cid:0)

21 )

...

}0{\

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

nn ( 2 nn (

(cid:0) (cid:0)

2 1 )

...

2)(1 6

(cid:0) (cid:0) (cid:0) (cid:0)