Cơ Sở Logic toán học

Ch

ươ

ng 1: C S Logic ơ ở

Biên so n: Nguy n Vi

t H ng

ễ

ạ

ế ư

Tài li u tham kh o

ệ

ả

ễ

ữ

ờ ạ

Toán r i r c, Gs.Ts Nguy n H u Anh Michael P.Frank ‘s slides Nguy n Minh Trung ‘s slides Toán r i r c, Ts. Tr n Ng c H i ộ

ễ ờ ạ

ầ

ọ

C S LOGIC

Ơ Ở

ọ

ộ

ệ

ợ

ụ ể ứ ạ

ể

ệ

ế

hay

gia mao ể ệ

ủ

Logic toán h c là m t công c đ làm vi c v i báo cáo h p ch t ph c t p. Nó bao ấ ớ g m:ồ th hi n chúng. M t ngôn ng đ ể ệ ữ ộ t ng n g n cho h . M t ký hi u vi ọ ọ ắ ộ ng pháp khách quan lý lu n v M t ph ề ươ ộ ậ h . s th t c a ậ ọ ự ủ Nó là n n t ng cho th hi n b ng ch ng ứ ằ ề ả chính th c trong t t c các chi nhánh c a ấ ả ứ toán h c. ọ

̉ ̣

Logic m nh đ

ệ

ề

ấ

ề

ệ

ủ

c xây d ng t

ừ

ự

ợ ả

ằ

ử ụ

t ử

ậ

George Boole (1815-1864)

ươ

ế

ấ

Logic là m nh đ logic c a báo cáo h p ch t báo cáo đ n gi n b ng đ ơ ượ cách s d ng cái g i là connectives Boolean. ọ M t s ng d ng trong khoa h c máy tính: ộ ố ứ ọ ụ Thi thu t s . k t k m ch đi n ạ ế ố ỹ ệ ế ng trình. Đi u ki n th hi n trong các ch ể ệ ệ ề Truy v n đ n c s d li u & công c tìm ụ ơ ở ữ ệ ki mế .

Chrysippus of Soli (ca. 281 B.C. – 205 B.C.)

M nh đ và chân tr ị ề

ệ

ệ ơ ả

ệ c đ nh nghĩa mà ch đ ủ ỉ ượ

ọ ắ

ề

ệ

ọ

Khái ni m v m nh đ : ề ề ệ M nh đ toán h c là khái ni m c b n c a ọ ề c toán h c không đ ị ượ mô t ệ ộ

ề ẳ

ị

ể ừ

ị

t là m nh đ ) là M nh đ toán h c(g i t m t kh ng đ nh có giá tr chân lý xác ị đ nh(đúng ho c sai, nh ng không th v a ặ đúng v a sai). ừ

ọ .ả

M nh đ và chân tr ị ề

ệ

Ví d : ụ

ố ề

c ệ ủ ế ố ồ ủ ướ

t Nam” là m t m nh đ sai. ộ ề

ỏ ộ

ả ỏ ề ộ

“S 123 chia h t cho 3” là 1 m nh đ đúng “Thành ph H Chí Minh là th đô c a n Vi ệ “B n có kh e không ? ” không ph i là m t m nh đ toán h c vì đây là m t câu h i không th ph n ánh m t đi u đúng hay m t đi u sai ệ ạ ệ ể ọ ộ ề ề ả ộ

Examples of Propositions

“It is raining.” (In a given situation.) “Beijing is the capital of China.” • “1 + 2 = 3”

But, the following are NOT propositions: “Who’s there?” (interrogative, question) “La la la la la.” (meaningless interjection) “Just do it!” (imperative, command) “Yeah, I sorta dunno, whatever...” (vague) “1 + 2” (expression with a non-true/false value)

M nh đ và chân tr ị ề

ệ

ẳ

ị

ể ệ

ề

ệ

Ki m tra xem các kh ng đ nh sau có là m nh đ không? N u có, đó là m nh đ ề ế đúng hay sai?

ắ ờ ạ ộ

Môn Toán r i r c là môn b t bu c chung cho ngành tin h c.ọ 97 là s nguyên t ố ố N là s nguyên t ố ố

M nh đ và chân tr ị ề

ệ

Ký hi u m nh đ : ệ i ta th

ề ng dùng các ký hi u : P, Q, R,

ệ ườ

ườ ệ

ệ

ự

ượ

ợ ệ

ừ “không”

Ng …

Chú ý: M nh đ ph c h p là m nh đ ề ệ ề ứ các m nh đ khác nh c xây d ng t đ ờ ề ừ liên k t c a chúng l i b ng các liên t (và, ạ ằ hay, n u…thì…) ho c tr ng t ừ ạ ặ t thì tôi đi d o. ạ

ế ủ ế ụ

Ví d : N u tr i t ờ ố ế

M nh đ và chân tr ị ề

ệ

ề

ệ

ị ủ

ệ ể

ặ ề ỉ ờ ừ ừ

ề i ta nói p có ệ c l ượ ạ

c ký hi u chân trị sai. ẽ ượ ệ ị

Chân tr c a m nh đ : Theo khái ni m, m t m nh đ ch có th đúng ệ ộ ho c sai, không th đ ng th i v a đúng v a ể ồ sai. Khi m nh đ p đúng ta nói p có chân tr ị đúng, ng Chân tr đúng và chân tr sai s đ ị l n l t là 1 và 0 ầ ượ

Phép tính m nh đệ

ề

ủ ứ

M c đích c a phép tính m nh đ : ề ệ

ệ ộ ệ

ị ủ

ề ề ơ ề ứ ả ể

ụ Nghiên c u chân tr c a m t m nh đ ph c h p t chân tr c a các m nh đ đ n gi n ợ ừ h n và các phép n i nh ng m nh đ này bi u ữ ơ hi n qua liên t ạ ệ

ệ “không” ho c tr ng t ị ủ ố ừ ặ ừ

Operators / Connectives

An operator or connective combines one or more operand expressions into a larger expression. (E.g., “+” in numeric exprs.) Unary operators take 1 operand (e.g., −3); binary operators take 2 operands (eg 3 · 4).

Propositional or Boolean operators operate on propositions or truth values instead of on numbers.

Some Popular Boolean Operators

Formal Name Nickname Arity Symbol

Negation operator NOT Unary ¬

(cid:217) Conjunction operator AND Binary

(cid:218) Disjunction operator OR Binary

¯ Exclusive-OR operator XOR Binary

ﬁ

Implication operator Biconditional operator IMPLIES Binary Binary IFF ↔

Phép tính m nh đệ

ề

Phép tính m nh đ

ệ

ề

ế

ủ ị

ổ lý

c a ủ

ế

Nhà đi u hành ph đ nh nguyên phân "¬" ủ ị (NOT) bi n đ i m t prop. thành ph đ nh ộ h p nó. ợ VD: N u p = "Tôi có mái tóc màu nâu." sau đó ¬ p = "Tôi không có mái tóc nâu".

Phép tính m nh đệ

ề

p (cid:216) p T F F T

Phép tính m nh đệ

ề

Phép n i li n(phép h i; phép giao):

ố ề

ệ ệ ượ

c ), là m nh ệ

ộ M nh đ n i li n c a hai m nh đ P, Q đ ề ố ề ủ kí hi u b i P ọ ở ệ đ đ ề ượ ị P (cid:217) Q đúng (cid:219)

c đ nh b i : ề (cid:217) Q (đ c là “P và Q” ở

P và Q đ ng th i đúng ồ ờ

Phép tính m nh đệ

ề

ẹ

ề

ụ

ệ ẹ

ả

ượ

ấ

ả ệ

ỉ

Ví d : M nh đ “Hôm nay, cô y đ p và ấ ệ c xem là m nh đ thông minh ” ch đ ề ỉ ượ đúng khi c hai đi u ki n “cô y đ p” và ấ ệ ề c “cô y thông minh” đ u x y ra. Ng ề i, ch 1 trong 2 đi u ki n trên sai thì l ề ạ m nh đ trên s sai. ệ

ề

ẽ

Phép tính m nh đ

ệ

ề

Meänh ñeà “Hoâm nay, An giuùp meï lau nhaø vaø röûa cheùn” chæ ñuùng khi hoâm nay An giuùp meï caû hai coâng vieäc lau nhaø vaø röûa cheùn. Ngöôïc laïi, neáu hoâm nay An chæ giuùp meï moät trong treân, hoaëc hai coâng vieäc khoâng giuùp meï caû hai thì meänh ñeà treân sai.

The Conjunction Operator

(cid:217) NDND

(cid:217)

The binary conjunction operator “(cid:217) ” (AND) combines two propositions to form their logical conjunction. E.g. If p=“I will have salad for lunch.” and q=“I will have steak for dinner.”, then p(cid:217) q=“I will have salad for lunch and I will have steak for dinner.”

Remember: “(cid:217)

(cid:217) ” points up like an “A”, and it means “ ” points up like an “A”, and it means “(cid:217)

(cid:217) NDND””

Conjunction Truth Table

Operand columns

(cid:217) … (cid:217) pn

p(cid:217) q F F F T

q F T F T

Note that a p conjunction F p1 (cid:217) p2 F of n propositions T will have 2n rows in its truth table. T Also: ¬ and (cid:217) operations together are suffi- cient to express any Boolean truth table!

Phép tính m nh đệ

ề

Phép tính m nh đệ

ề

Phép n i r i(phép tuy n; phép h p)

ể

ố ờ

ệ ệ ượ

c ), là m nh ệ

ợ ề (cid:218) Q (đ c là “P hay Q” ở

c đ nh b i :

M nh đ n i r i c a hai m nh đ P, Q đ ề ố ờ ủ kí hi u b i P ọ ở ệ đ đ ề ượ ị P (cid:218) Q sai (cid:219) P và Q đ ng th i sai ồ ờ

Phép tính m nh đệ

ề

ụ

ệ

ề

Ví d : M nh đ “Tôi đang ch i bóng đá hay bóng r ”.ổ

ỉ ề ừ

ư ừ ơ

ơ ơ

ề ệ

M nh đ này ch sai khi tôi v a không đang ệ ch i bóng đá cũng nh v a không đang ch i ơ bóng r .ổ i, tôi ch i bóng đá hay đang ch i c l Ng ượ ạ bóng r hay đang ch i c hai thì m nh đ trên ơ ả ổ đúng.

The Disjunction Operator

ị

ế

ề

ệ

ề ể

lý

c a ủ c ơ

x u ấ

ấ

có ủ ặ

ủ

ộ

ủ

ộ

Meaning is like “and/or” in English.

Nhà đi u hành phân ly nh phân (OR) k t h p hai m nh đ đ hình thành phân ly ợ h . h p ọ ợ xe đ ng ộ q = xe c a tôi có m t bình xăng con x u ộ q = Ho c là xe c a tôi có m t đ ng c ơ x u, hay xe c a tôi có m t bình xăng con ấ After the downward- x u. ấ (cid:218) ”” pointing “axe” of “(cid:218) splits the wood, you splits the wood, you can take 1 piece OR the can take 1 piece OR the other, or both. other, or both.

(cid:218) (cid:218)

Disjunction Truth Table

Note difference from AND

p q p(cid:218) q F F F F T T T F T T T T

Note that p(cid:218) q means that p is true, or q is true, or both are true! So, this operation is also called inclusive or, because it includes the possibility that both p and q are true. “¬” and “(cid:218) ” together are also universal.

Phép tính m nh đệ

ề

Phép tính m nh đệ

ề

ệ

ặ ể ể ệ

ườ

ng h p lo i ợ

ạ

Chú ý :

(cid:218)

ồ

P và Q đ ng th i cùng đúng ho c ờ

ặ

t “hay” và “ho c”. C n phân bi ầ Đ a ra phép toán đ th hi n tr ư tr ừ Ký hi u : ệ P Q sai (cid:219) cùng sai.

(cid:218)

The Exclusive Or Operator

The binary exclusive-or operator “¯ ” (XOR) combines two propositions to form their logical “exclusive or” (exjunction?).

p = “I will earn an A in this course,” q = “I will drop this course,” p ¯

q = “I will either earn an A for this

course, or I will drop it (but not both!)”

Exclusive-Or Truth Table

p q p¯ q F F F F T T T F T T T F Note

difference from OR.

Note that p¯ q means that p is true, or q is true, but not both! This operation is called exclusive or, because it excludes the possibility that both p and q are true. “¬” and “¯ ” together are not universal.

Phép tính m nh đệ

ề

Phép kéo theo:

ệ ệ ề

ﬁ ở ủ ọ

ệ

ủ ủ ệ ề ủ ệ ầ

ề c đ nh b i: ở

M nh đ P kéo theo Q c a hai m nh đ P và ề Q(đ c là “P kéo theo Q” Q, kí hi u b i P ệ hay “N u P thì Q” hay “P là đi u ki n đ c a ế Q” hay “Q là đi u ki n c n c a P”) là m nh đ đ ề ượ ị Q sai (cid:219) P ﬁ P đúng và Q sai

Phép tính m nh đệ

ề

ề ạ

ạ

ệ

ụ ế

ề ệ

ạ

ề ệ

ề

ẹ

ạ

ẫ

ề ẫ

ề

ẹ

ệ

ạ

Tôi đ p trai và có nhi u b n gái : M nh đ rõ ràng đúng Tôi đ p trai và không có nhi u b n gái : M nh đ rõ ràng sai ề Tôi không đ p trai mà v n có nhi u b n gái : M nh đ v n ề ẫ đúng Tôi không đ p trai và không có nhi u b n gái : M nh đ v n đúng

Ví d : Xét m nh đ sau : ề ệ “N u tôi đ p trai thì tôi có nhi u b n gái” ẹ ng h p sau: Ta có các tr ợ ườ ẹ ề ẹ

Phép tính m nh đệ

ề

Meänh ñeà “Chieàu nay, neáu raûnh toâi seõ gheù thaêm baïn” chæ sai khi chieàu nay toâi raûnh nhöng toâi khoâng gheù thaêm baïn. Ngöôïc laïi, neáu chieàu nay toâi baän thì duø toâi coù gheù thaêm baïn hay khoâng, meänh ñeà treân vaãn ñuùng. Ngoaøi ra, taát nhieân neáu chieàu nay toâi coù gheù

thaêm baïn thì meänh ñeà treân

ñuùng (duø toâi coù raûnh hay

khoâng!).

The Implication Operator

consequent q states that p implies q.

antecedent The implication p ﬁ I.e., If p is true, then q is true; but if p is not

true, then q could be either true or false.

E.g.,

let

p =

“You

study

hard.”

q = “You will get a good grade.”

p ﬁ

q = “If you study hard, then you will get

a good grade.” (else, it could go either way)

Implication Truth Table

q does not require

p q pﬁ q F F F T T F T T

T T F T

The only False case!

p ﬁ q is false only when p is true but q is not true. p ﬁ q does not say that p causes q! p ﬁ that p or q are ever true! E.g. “(1=0) ﬁ

pigs can fly” is TRUE!

Examples of Implications

is president.”

“If this lecture ends, then the sun will rise tomorrow.” True or False? “If Tuesday is a day of the week, then I am a penguin.” True or False? then Bush “If 1+1=6, True or False? “If the moon is made of green cheese, then I am richer than Bill Gates.” True or False?

Phép tính m nh đệ

ề

Chú ý:

ệ

ề

P,Q là 2 m nh đ <->P là m nh đ , Q là dãy dòng l nh..ệ

Liên h phép kéo theo và cú pháp If P then Q trong ngôn ng l p trình ệ ữ ậ ề

ữ ằ ữ ự ầ

“Giáo viên khoa Toán d y nghiêm túc”

ạ

Ngôn ng h ng ngày, có s nh m l n gi a ẫ phép kéo theo và phép kéo theo hai chi u.ề

Phép tính m nh đệ

ề

Phép tính m nh đệ

ề

Pheùp keùo theo hai chieàu:

Q”

P vaø Q coù cuøng Q ñuùng (cid:219)

Meänh ñeà P keùo theo Q vaø ngöôïc laïi cuûa hai meänh ñeà P vaø Q, kyù hieäu bôûi P « Q (ñoïc laø “P neáu vaø hay neáu chæ P khi vaø chæ khi Q” hay “P laø ñieàu kieän caàn vaø ñuû cuûa Q”), laø meänh ñeà ñöôïc ñònh bôûi: P « chaân trò,

Phép tính m nh đệ

ề

Phép tính m nh đệ

ề

The biconditional operator

The biconditional p « q states that p is true if and

only if (IFF) q is true.

p = “Bush wins the 2004 election.” q = “Bush will be president for all of 2005.” p « q = “If, and only if, Bush wins the 2004

I’m still here!

2004

2005

election, Bush will be president for all of 2005.”

Biconditional Truth Table

p q p « F F F T T F T T

T F F T

p « q means that p and q have the same truth value. Note this truth table is the exact opposite of ¯ ’s! q means ¬(p ¯ q) q does not imply

p « p and q are true, or cause each other.

p «

Boolean Operations Summary

We have seen 1 unary operator (out of the 4 possible) and 5 binary operators (out of the 16 possible). Their truth tables are below. p q (cid:216) p p(cid:217) q p(cid:218) q p¯ q pﬁ q p« q F F F T T F T T T T F F T T T F

F F F T

T F F T

F T T F

T T F T

Some Alternative Notations

Name:

not and or xor implies

iff

Propositional logic:

Boolean algebra:

(cid:216) (cid:217) (cid:218) ¯ ﬁ «

p pq +

C/C++/Java (wordwise): ! && || != C/C++/Java (bitwise): ^

~ &

Logic gates:

D ng m nh đ

ệ

ạ

ề

Moät daïng meänh ñeà laø moät bieåu thöùc ñöôïc caáu taïo töø:

Caùc haèng meänh ñeà, töùc laø caùc meänh ñeà ñaõ xeùt ôû trên. Caùc bieán meänh ñeà, töùc laø caùc bieán laáy giaù trò laø caùc meänh ñeà, thoâng qua caùc pheùp toaùn meänh ñeà ñaõ xeùt ôû muïc trên theo moät trình töï nhaát ñònh naøo ñoù, thöôøng ñöôïc chæ roõ bôûi caùc daáu ngo c. ặ

D ng m nh đ

ệ

ạ

ề

ớ ế ệ ệ

ỗ ề ị ụ ể

ấ ệ ộ

t E = E(p, q, r). ế

ấ ả ợ

t c các tr ệ

ườ ề ế ể ị ị ủ ả ế ẽ ư

V i E là m t d ng m nh đ các bi n m nh đ ộ ạ ề p, q, r ng v i m i giá tr c th P, Q, R (là các ớ ứ m nh đ ) c a p, q, r thì ta có duy nh t m t m nh ề ủ ệ đ E(P, Q, R). Ta vi ề B ng chân tr là b ng ghi t ng h p ả ị ả chân tr có th x y ra đ i v i m nh đ E theo ố ớ ể ả chân tr c a các bi n m nh đ p, q, r. N u có n ề ệ bi n, b ng này s có 2^n dòng, ch a k dòng ế tiêu đ .ề

D ng m nh đ

ệ

ạ

ề

Tautologies and Contradictions

A tautology is a compound proposition that is true no matter what the truth values of its atomic propositions are!

Ex. p (cid:218) (cid:216) p [What is its truth table?] A contradiction is a compound proposition that is false no matter what! Ex. p (cid:217) (cid:216) p [Truth table?]

Other compound props. are contingencies.

Logical Equivalence

Compound proposition p is

logically to compound proposition q, compound

p(cid:219) q,

equivalent written proposition p«

IFF the q is a tautology.

Compound propositions p and q are logically equivalent to each other IFF p and q contain the same truth values as each other in all rows of their truth tables.

Ex. Prove that p(cid:218) q (cid:219)

(cid:216) ((cid:216) p (cid:217) (cid:216) q).

Proving Equivalence via Truth Tables

(cid:216) qq (cid:216) (cid:216)

(cid:216) qq)) (cid:216)

(cid:218) qq (cid:216) p q pp(cid:218) F F F T F T T F T T T T

(cid:216) pp (cid:216) T T F F

(cid:216) qq (cid:216) T F T F

(cid:216) pp (cid:217) T F F F

(cid:216) pp (cid:217) (((cid:216) F T T T

(cid:217) (cid:216) (cid:217)

D ng m nh đ

ệ

ạ

ề

1. Quy t c thay th th 1:

ế ứ ề

ng đ ề ươ c v n còn t

ứ ng logic ng ng đ ươ

ế ể ươ ươ

Trong d ng m nh đ E, n u ta thay th bi u th c ế ệ con F b i m t d ng m nh đ t ộ ạ ệ thì d ng m nh đ thu đ ượ ẫ ề ệ ạ logic v i E.ớ

ắ ạ ở

1. Quy t c thay th th 2:

ệ

ế

ộ

ộ ằ ở ế

ế ữ ệ

ạ

s d ng m nh đ E(p,q,r…) là m t h ng đúng. N u ta Gi thay th nh ng n i p xu t hi n trong E b i m t F(p’,q’,r’) ệ ấ c theo các bi n thì d ng m nh đ nh n đ q,r…,p’,q’,r’,… v n còn là 1 h ng đúng.

ơ ề ậ ượ ẫ

ằ

ắ ả ử ạ ế ứ ề

D ng m nh đ

ệ

ạ

ề

ậ

ề

ế ệ ộ ằ ng logic sau đây:

ớ ộ ằ ươ

Các lu t logic : V i p, q, r là các bi n m nh đ , 1 là m t h ng đúng và 0 là m t h ng sai, ta có các t ươ 1)

ng đ Luaät luõy ñaúng

p (cid:217) p (cid:219) p vaø p (cid:218) p (cid:219)

D ng m nh đ

ệ

ạ

ề

D ng m nh đ

ệ

ạ

ề

16) Lu t v phép kéo theo:

ậ ề q (cid:219) p ﬁ ậ

(cid:216) p (cid:218) q 17) Lu t rút g n: ọ p(cid:217) q ﬁ p (cid:219) 1(*) pﬁ (p(cid:217) q) (cid:219) p ﬁ pﬁ p (cid:218) q ﬁ q (cid:219) p ﬁ

q q 1(*)

(p (cid:218) q) (cid:219)

Equivalence Laws - Examples

p F p

p p(cid:218) F (cid:219) T p(cid:217) F (cid:219) p p(cid:217) p (cid:219)

p (cid:219) p q(cid:218) p p(cid:217) q (cid:219)

q(cid:217) p

p(cid:218) (q(cid:218) r)

Identity: p(cid:217) T (cid:219) Domination: p(cid:218) T (cid:219) Idempotent: p(cid:218) p (cid:219) Double negation: (cid:216) Commutative: p(cid:218) q (cid:219) Associative: (p(cid:218) q)(cid:218) r (cid:219) (p(cid:217) q)(cid:217) r (cid:219)

p(cid:217) (q(cid:217) r)

(cid:216)

More Equivalence Laws

(p(cid:218) q)(cid:217) (p(cid:218) r)

p(cid:217) (q(cid:218) r) (cid:219) (p(cid:217) q)(cid:218) (p(cid:217) r)

Distributive: p(cid:218) (q(cid:217) r) (cid:219) De Morgan’s: (cid:216) (p(cid:217) q) (cid:219) (cid:216) (p(cid:218) q) (cid:219) (cid:216) p (cid:218) (cid:216) q (cid:216) p (cid:217) (cid:216) q

Augustus De Morgan (1806-1871)

Trivial tautology/contradiction: p (cid:218) (cid:216) p (cid:219) F T p (cid:217) (cid:216) p (cid:219)

Using equivalences, we can define operators

Defining Operators via Equivalences

(cid:216)

(p(cid:217) q) p)

q)(cid:218) (q(cid:217)

in terms of other operators. (p(cid:218) q)(cid:217) Exclusive or: p¯ q (cid:219) (p(cid:217) p¯ q (cid:219) (cid:216) p (cid:218) q Implies: pﬁ q (cid:219) (pﬁ q) (cid:217) (qﬁ p) q (cid:219) Biconditional: p« (cid:216) (p¯ q) q (cid:219) p«

(cid:216) (cid:216)

An Example Problem

(cid:216) p (cid:218) q (cid:218) (cid:216) r.

(p ¯ r) (cid:219)

r) ] (cid:216)

Check using a symbolic derivation whether r) (cid:219) (p (cid:217) (cid:216) q) ﬁ (p ¯ (p (cid:217) (cid:216) q) ﬁ [Expand definition of ﬁ [Defn. of ¯ [DeMorgan’s Law] (cid:219) (cid:219)

(p (cid:217) (cid:216) q) (cid:218) (p ¯ (cid:216) (p (cid:217) (cid:216) q) (cid:218) ((p (cid:218) r) (cid:217) (cid:216) (p (cid:217) r)) ] (cid:219)

((cid:216) p (cid:218) q) (cid:218) ((p (cid:218) r) (cid:217) (cid:216) (p (cid:217) r)) [associative law] cont.

Example Continued...

((cid:216) p (cid:218) q) (cid:218) ((p (cid:218) r) (cid:217) (cid:216) (p (cid:217) r)) (cid:219)

(cid:219)

(cid:219) [(cid:218) commutes] (q (cid:218) (cid:216) p) (cid:218) ((p (cid:218) r) (cid:217) (cid:216) (p (cid:217) r)) [(cid:218) associative] q (cid:218) ((cid:216) p (cid:218) ((p (cid:218) r) (cid:217) (cid:216) (p (cid:217) r))) [distrib. (cid:218) over (cid:217) ] q (cid:218) ((((cid:216) p (cid:218) (p (cid:218) r)) (cid:217) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r)))

[assoc.] (cid:219) [trivail taut.] (cid:219) [domination] (cid:219) [identity] (cid:219) q (cid:218) ((((cid:216) p (cid:218) p) (cid:218) r) (cid:217) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r))) q (cid:218) ((T (cid:218) r) (cid:217) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r))) q (cid:218) (T (cid:217) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r))) q (cid:218) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r)) (cid:219) cont.

End of Long Example

q (cid:218) ((cid:216) p (cid:218) ((cid:216) p (cid:218) (cid:216) r)) q (cid:218) (((cid:216) p (cid:218) (cid:216) p) (cid:218) (cid:216) r) q (cid:218) ((cid:216) p (cid:218) (cid:216) r) (q (cid:218) (cid:216) p) (cid:218) (cid:216) r (cid:216) p (cid:218) q (cid:218) (cid:216) r

q (cid:218) ((cid:216) p (cid:218) (cid:216) (p (cid:217) r)) [DeMorgan’s] (cid:219) [Assoc.] (cid:219) [Idempotent] (cid:219) [Assoc.] (cid:219) [Commut.] (cid:219) Q.E.D. (quod erat demonstrandum)

(Which was to be shown.)

D ng m nh đ

ệ

ạ

ề

ạ

Ch ng minh d ng m nh đ ta có 3 cách ệ ứ sau:

ả ả

L p b ng chân tr . ị L p b ng chân tr m r ng. ị ở ộ S d ng phép thay th . ế ậ ậ ử ụ

Qui T c Suy Di n

ễ

ắ

ọ ứ

ị ẳ ấ ề

ắ ủ ộ

ễ ọ ề ệ ậ

ễ ắ

ứ

m t Trong các ch ng minh toán h c,xu t phát t ừ ộ s kh ng đ nh đúng p, q, r…(tiên đ ), ta áp d ng ụ ố các qui t c suy di n đ suy ra chân lí c a m t ể m nh đ h mà ta g i là k t lu n. ế Nói cách khác, dùng các qui t c suy di n đ ể ch ng minh: ( p (cid:217) q (cid:217) r (cid:217) …) ﬁ

là m t kh ng đ nh đúng. ẳ ộ ị

Qui T c Suy Di n

ễ

ắ

Kh ng đ nh (1) có d ng:

ị

ạ

ẳ ((tiên đ 1ề ) (cid:217) (tiên đ 2) ề ứ

ế

ộ

(cid:217) …) ﬁ k t lu n ậ ế Do đó n u ch ng minh đ c d ng m nh đ trên là m t ề ệ ượ ạ ị

ắ

ẳ

ắ

ườ

h ng đúng thì kh ng đ nh (1) ch c ch n là đúng. ằ ng Ta th mô hình hóa (2):

(1) (2) …

k t lu n

tiên đ ề tiên đề ế

ậ

Aristotle (ca. 384-322 B.C.)

(2)

p 1

p 2

p n

p 1 p 2 ... ... p q\

Aristotle (ca. 384-322 B.C.)

(cid:217) (cid:217) (cid:217) ﬁ

Qui T c Suy Di n

ễ

ắ

ng pháp ươ

Ắ ị ẳ

QUI T C MODUS PONENS(Ph kh ng đ nh) Qui t c này đ ắ ằ

ﬁ (cid:217) ﬁ Ø ø c th hi n b ng h ng đúng: ằ ượ ( ể ệ ) º ß

p p

Ho c d i d ng s đ ặ ướ ạ ơ ồ ﬁ

ế

ọ ố

•N u An h c chăm thì An h c t ọ •Mà An h c chăm ọ t Suy ra An h c t ọ ố

ng chéo c t

ắ

ạ

ắ

•Hình vuông là hình bình hành •Mà hình bình hành có hai đ ườ i trung đi m m i đ ng. nhau t ỗ ườ ể Suy ra hình vuông có hai đ ng chéo c t ườ i trung đi m m i đ ng nhau t ỗ ườ ể

ạ

(

)

(

)

u t

(cid:217) ﬁ (cid:216) (cid:218)

(cid:217)

(

)

u t

Aristotle (ca. 384-322 B.C.)

\ (cid:216) (cid:218)

Qui T c Suy Di n

ễ

ắ

ượ ằ

(

ﬁ (cid:217) ﬁ ﬁ ﬁ Ø ø QUI T C TAM ĐO N LU N(Syllogism) Ậ Ạ Ắ Qui t c này đ c th hi n b ng h ng đúng: ằ ể ệ ắ ) ) ( ) ( º ß

Ho c d i d ng s đ ặ ướ ạ ơ ồ

ﬁ

q r

ﬁ

p q (

)

Aristotle (ca. 384-322 B.C.)

\ ﬁ

ạ

ề

ằ

ữ

ọ ằ

ằ

ạ

ằ

ề

ạ

ặ

ằ

ọ

•Hai tam giác vuông có c nh huy n và 1 c p góc nh n b ng nhau thì chúng ta có ặ m t c nh b ng nhau kèm gi a hai góc b ng ộ ạ nhau. •N u hai tam giác có c nh b ng nhau kèm ế gi a hai góc b ng nhau thì chúng b ng ữ nhau Suy ra hai tam giác vuông có c nh huy n và 1 c p góc nh n b ng nhau thì b ng nhau.

ộ

ự ẻ

ự

ế

ộ

•M t con ng a r là m t con ng a hi m •Cái gì hi m thì đ t ắ ế Suy ra m t con ng a r thì đ t ( ự ẻ ộ

ắ )

Qui T c Suy Di n

ễ

ắ

QUI T C MODUS TOLLENS Ắ

PH

ƯƠ

Ủ Ị

NG PHÁP PH Đ NH

Qui t c này đ ắ ằ

ﬁ (cid:217) (cid:216) ﬁ (cid:216) Ø ø c th hi n b ng h ng đúng: ằ ượ ( ể ệ ) º ß

Ho c d i d ng s đ ặ ướ ạ ơ ồ ﬁ

(cid:216)

Aristotle (ca. 384-322 B.C.)

\ (cid:216)

Xét ch ng minh ứ

ﬁ ﬁ

p r t

ﬁ (cid:218) (cid:216)

ﬁ (cid:216) (cid:218) Ta suy lu nậ r p s r t s u t

r s s t u u

(cid:216) (cid:216)

Aristotle (ca. 384-322 B.C.)

\ (cid:216) \ (cid:216)

Qui T c Suy Di n

ễ

ắ

QUI T C TAM ĐO N LU N R I Ắ Qui t c này đ ắ Ậ Ờ c th hi n b ng h ng đúng: ằ ằ Ạ ể ệ ượ

(

)

(

)

p q

(cid:218) (cid:217) (cid:216) ﬁ Ø ø (cid:218) (cid:217) (cid:216) ﬁ Ø ø º ß º ß

ủ ế

ng h p ng h p ợ ợ

i s đúng Ý nghĩa c a qui t c: n u trong hai tr ắ ườ t có m t tr có th x y ra, chúng ta bi ộ ườ ể ả sai thì ch c ch n tr ạ ẽ ắ ế ng h p còn l ợ ườ ắ

Qui T c Suy Di n

ễ

ắ

QUI T C MÂU THU N

Ắ

Ứ

Ả

Ẫ Ứ CH NG MINH B NG PH N CH NG Ằ

Ta có t ươ ươ

(

)

...

p n

p 1

p 2

p 1

p 2

p n

(cid:217) (cid:217) (cid:217) ﬁ (cid:219) (cid:217) (cid:217) (cid:217) (cid:217) (cid:216) ﬁ Ø ø Ø ø ng đ ) ng logic ( º ß º ß

ầ ứ ằ ộ

ứ ề ượ ủ ộ

Ta c n ch ng minh v trái cũng là m t h ng ế đúng hay nói cách khác ch ng minh khi thêm c m t mâu ph đ nh c a q vào các ti n đ ta đ ề ủ ị thu n. ẫ

VÍ DỤ

Hãy ch ng minh: ứ ph n ả

ﬁ Cm ch ng.ứ p b ng ằ r ﬁ

(cid:216) ﬁ (cid:216) ﬁ

(cid:216) ﬁ

(cid:216) \ (cid:216) ﬁ

Aristotle (ca. 384-322 B.C.)

Qui T c Suy Di n

ễ

ắ

NG H P Ứ ƯỜ Ợ

CH NG MINH THEO TR D a trên h ng đúng: ằ ự

(

)

(

)

(

)

p q

ﬁ (cid:217) ﬁ ﬁ (cid:218) ﬁ Ø ø Ø ø º ß º ß

d ng p và q có th suy ra r thì t ể ừ ạ

Ý nghĩa: n u t ế ừ p hay q cũng có th suy ra r. ể

VÍ DỤ

Ch ng minh r ng: ứ ằ

(

)

3 4

M 3

Aristotle (ca. 384-322 B.C.)

M t s lu t thêm

ộ ố ậ

p Rule of Addition(Phép thêm)

p(cid:218) q

ả

ậ ề

ố

p(cid:217) q Phép đ n gi n n i li n ố ề \ p Lu t v phép n i q p(cid:217) q \

Aristotle (ca. 384-322 B.C.)

VÍ D T NG H P

Ụ Ổ

Ợ

ng Ba trình di n.

ệ

ế

ươ

ễ

ươ

ố

1. N u ngh sĩ Tr ễ ơ

ủ

ồ

p:Ngh sĩ Tr ệ q:s vé bán ra ít h n 100. r:đêm di n b h y b . ễ ị ủ ỏ s: ông b u bu n. ồ ầ i vé cho ng t:tr l

i xem

ả ạ

ườ

ng Ba không trình di n hay s ố vé bán ra ít h n 100 thì đêm di n s bi h y b ỏ ẽ ễ và ông b u s r t bu n. ầ ẽ ấ ễ

ế

ị ủ ả ạ

2. N u đêm di n b h y b ỏ thì vé ph i tr l i cho ả i xem. ng

(cid:216) (cid:218) ﬁ (cid:217)

p q t

i xem.

3. Nh ng vé đã không tr ả ườ

ﬁ

ườ ư i cho ng V y có k t luân gì? ế

l ạ ậ

(cid:216)

Qui T c Suy Di n

ễ

ắ

Ụ

Ả ể ứ ậ ộ

p n

p 2

(cid:217) (cid:217) (cid:217) ﬁ PH N VÍ D Đ ch ng minh m t phép suy lu n là sai hay ...

p 1 ộ ằ

không là m t h ng đúng. Ta ch c n ch ra m t ỉ ầ ộ ỉ

ph n ví d . ụ ả

VÍ DỤ

tăng

ượ

ng.

ượ ẽ

ế

ợ

ỉ ệ ấ

ợ

ấ

ợ

p:ông Minh đ l ươ q: ông Minh ngh vi c. r:v ông Minh m t vi c. ệ s:gia đình ph i bán xe. ả t:v ông hay đi làm tr . ể q

ố c tăng l

ng.

ượ

ươ

(cid:216) ﬁ

(cid:217) ﬁ

Ông Minh nói r ng n u ế ằ c tăng l không đ ng thì ươ ông ta s ngh vi c. M t ặ ệ ỉ khác, n u ông y ngh vi c ỉ ệ ấ và v ông y b m t vi c thì ị ấ ệ t r ng n u ph i bán xe.Bi ế ế ằ ả v ông Minh hay đi làm tr ễ ợ c sau gì cũng s b thì tr ẽ ị ướ m t vi c và cu i cùng ông ệ ấ Minh đã đ Suy ra n u ông Minh không ế bán xe thì v ông ta đã ợ không đi làm trễ

s=0 t=1 p=1 q=0 r=1

p q r r t p

ﬁ

\ (cid:216) ﬁ (cid:216)

Formal Proof Example

the

and swim sunny if We will it is

theorem the

following premises: Suppose we have cold.” is is not “It sunny.” it “Only “If we do not swim, then we will canoe.” “If we canoe, then we will be home early.” these premises, prove Given “We will be home early” using inference rules.

Proof Example cont.

Let us adopt the following abbreviations:

cold (2) swim ﬁ

canoe (4) canoe ﬁ

early

sunny = “It is sunny”; cold = “It is cold”; swim = “We will swim”; canoe = “We will canoe”; early = “We will be home early”. Then, the premises can be written as: (1) (cid:216) sunny (cid:217) sunny (3) (cid:216) swim ﬁ

Proof Example cont.

(cid:217) cold Premise

(cid:216) sunny (cid:216) sunny of

swimﬁ sunny Proved Simplification Premise

(cid:216) swim

(cid:216) swimﬁ canoe

canoeﬁ early by #1. 1. #2. tollens on 2,3. Modus #3. Premise Modus ponens on 4,5. #4.

Step 1. 2. 3. 4. 5. 6. canoe 7. 8. early Premise Modus ponens on 6,7.

Qui T c Suy Di n

ễ

ắ

Qui T c Suy Di n