Bài giảng Toán rời rạc - Nguyễn Viết Hưng

Nội dung text: Bài giảng Toán rời rạc - Nguyễn Viết Hưng

1. ChươngChương 1:1: CơCơ SởSở LogicLogic BiênBiên soạnsoạn:: NguyễnNguyễn ViếtViết HưngHưng
2. TàiTài liệuliệu thamtham khảokhảo TốnTốn rờirời rạc,rạc, Gs.TsGs.Ts NguyễnNguyễn HữuHữu AnhAnh MichaelMichael P.FrankP.Frank ‘s‘s slidesslides NguyễnNguyễn MinhMinh TrungTrung ‘s‘s slidesslides TốnTốn rờirời rạc,rạc, Ts.Ts. TrầnTrần NgọcNgọc HộiHội
3. CƠCƠ SỞSỞ LOGICLOGIC LogicLogic tốntốn họchọc làlà mộtmột cơngcơng cụcụ đểđể làmlàm việcviệc vớivới báobáo cáocáo hợphợp chấtchất phứcphức tạptạp NĩNĩ baobao gồmgồm:: MộtMột ngơnngơn ngữngữ đểđể thểthể hiệnhiện chúngchúng MộtMột kýký hiệuhiệu viếtviết ngắnngắn gọngọn chocho họhọ MộtMột phươngphương pháppháp kháchkhách quanquan lýlý luậnluận vềvề sựsự thậtthật hayhay giagiả ̉ mạomạo củacủa họhọ NĩNĩ làlà nềnnền tảngtảng chocho thểthể hiệnhiện bằngbằng chứngchứng chínhchính thứcthức trongtrong tấttất cảcả cáccác chichi nhánhnhánh củacủa tốntốn họchọc
4. LogicLogic mệnhmệnh đềđề LogicLogic làlà mệnhmệnh đềđề logiclogic củacủa báobáo cáocáo hợphợp chấtchất đượcđược xâyxây dựngdựng từtừ báobáo cáocáo đơnđơn giảngiản bằngbằng cáchcách sửsử dụngdụng cáicái gọigọi làlà connectivesconnectives Boolean.Boolean. MộtMột sốsố ứngứng dụngdụng trongtrong khoakhoa họchọc máymáy tínhtính:: ThiếtThiết kếkế mạchmạch điệnđiện tửtử kỹkỹ thuậtthuật sốsố George Boole (1815-1864) ĐiềuĐiều kiệnkiện thểthể hiệnhiện trongtrong cáccác chươngchương trìnhtrình TruyTruy vấnvấn đếnđến cơcơ sởsở dữdữ liệuliệu && cơngcơng cụcụ tìmtìm kiếmkiếm Chrysippus of Soli (ca. 281 B.C. – 205 B.C.)
5. MệnhMệnh đềđề vàvà chânchân trịtrị KháiKhái niệmniệm vềvề mệnhmệnh đềđề:: MệnhMệnh đềđề tốntốn họchọc làlà kháikhái niệmniệm cơcơ bảnbản củacủa tốntốn họchọc khơngkhơng đượcđược địnhđịnh nghĩanghĩa màmà chỉchỉ đượcđược mơmơ tảtả MệnhMệnh đềđề tốntốn học(gọihọc(gọi tắttắt làlà mệnhmệnh đềđề)) làlà mộtmột khẳngkhẳng địnhđịnh cĩcĩ giágiá trịtrị chânchân lýlý xácxác định(đúngđịnh(đúng hoặchoặc saisai,, nhưngnhưng khơngkhơng thểthể vừavừa đúngđúng vừavừa saisai).).
6. MệnhMệnh đềđề vàvà chânchân trịtrị VíVí dụdụ:: ““SốSố 123123 chiachia hếthết chocho 3”3” làlà 11 mệnhmệnh đềđề đúngđúng ““ThànhThành phốphố HồHồ ChíChí MinhMinh làlà thủthủ đơđơ củacủa nướcnước ViệtViệt Nam”Nam” làlà mộtmột mệnhmệnh đềđề saisai ““BạnBạn cĩcĩ khỏekhỏe khơngkhơng ?? ”” khơngkhơng phảiphải làlà mộtmột mệnhmệnh đềđề tốntốn họchọc vìvì đâyđây làlà mộtmột câucâu hỏihỏi khơngkhơng thểthể phảnphản ánhánh mộtmột điềuđiều đúngđúng hayhay mộtmột điềuđiều saisai
7. ExamplesExamples ofof PropositionsPropositions ““ItIt isis raining.”raining.” (In(In aa givengiven situation.)situation.) “Beijing“Beijing isis thethe capitalcapital ofof China.”China.” •• “1“1 ++ 22 == 3”3” But,But, thethe followingfollowing areare NOTNOT propositions:propositions: “Who’s“Who’s there?”there?” (interrogative,(interrogative, question)question) “La“La lala lala lala la.”la.” (meaningless(meaningless interjection)interjection) “Just“Just dodo it!”it!” (imperative,(imperative, command)command) “Yeah,“Yeah, II sortasorta dunno,dunno, whatever ”whatever ” (vague)(vague) “1“1 ++ 2”2” (expression(expression withwith aa non-true/falsenon-true/false value)value)
8. MệnhMệnh đềđề vàvà chânchân trịtrị KiểmKiểm tratra xemxem cáccác khẳngkhẳng địnhđịnh sausau cĩcĩ làlà mệnhmệnh đềđề khơngkhơng?? NếuNếu cĩcĩ,, đĩđĩ làlà mệnhmệnh đềđề đúngđúng hayhay saisai?? MơnMơn TốnTốn rờirời rạcrạc làlà mơnmơn bắtbắt buộcbuộc chungchung chocho ngànhngành tintin họchọc 9797 làlà sốsố nguyênnguyên tốtố NN làlà sốsố nguyênnguyên tốtố
9. MệnhMệnh đềđề vàvà chânchân trịtrị KýKý hiệuhiệu mệnhmệnh đềđề :: NgườiNgười tata thườngthường dùngdùng cáccác kýký hiệuhiệu :: P,P, Q,Q, R,R, ChúChú ý:ý: MệnhMệnh đềđề phứcphức hợphợp làlà mệnhmệnh đềđề đượcđược xâyxây dựngdựng từtừ cáccác mệnhmệnh đềđề kháckhác nhờnhờ liênliên kếtkết củacủa chúngchúng lạilại bằngbằng cáccác liênliên từ(vàtừ(và,, hay,hay, nếunếu thìthì ) ) hoặchoặc trạngtrạng từtừ ““khơngkhơng”” VíVí dụdụ :: NếuNếu trờitrời tốttốt thìthì tơitơi điđi dạodạo
10. MệnhMệnh đềđề vàvà chânchân trịtrị ChânChân trịtrị củacủa mệnhmệnh đềđề:: TheoTheo kháikhái niệmniệm,, mộtmột mệnhmệnh đềđề chỉchỉ cĩcĩ thểthể đúngđúng hoặchoặc saisai,, khơngkhơng thểthể đồngđồng thờithời vừavừa đúngđúng vừavừa saisai KhiKhi mệnhmệnh đềđề pp đúngđúng tata nĩinĩi pp cĩcĩ chânchân trịtrị đúngđúng,, ngượcngược lạilại tata nĩinĩi pp cĩcĩ chânchân trịtrị saisai ChânChân trịtrị đúngđúng vàvà chânchân trịtrị saisai sẽsẽ đượcđược kýký hiệuhiệu lầnlần lượtlượt làlà 11 vàvà 00
11. PhépPhép tínhtính mệnhmệnh đềđề MụcMục đíchđích củacủa phépphép tínhtính mệnhmệnh đềđề:: NghiênNghiên cứucứu chânchân trịtrị củacủa mộtmột mệnhmệnh đềđề phứcphức hợphợp từtừ chânchân trịtrị củacủa cáccác mệnhmệnh đềđề đơnđơn giảngiản hơnhơn vàvà cáccác phépphép nốinối nhữngnhững mệnhmệnh đềđề nàynày biểubiểu hiệnhiện quaqua liênliên từtừ hoặchoặc trạngtrạng từtừ ““khơngkhơng””
12. OperatorsOperators // ConnectivesConnectives AnAn operatoroperator oror connectiveconnective combinescombines oneone oror moremore operandoperand expressionsexpressions intointo aa largerlarger expression.expression. ((E.g.E.g.,, “+”“+” inin numericnumeric exprs.)exprs.) UnaryUnary operatorsoperators taketake 11 operandoperand ((e.g.,e.g., −−3);3); binarybinary operatorsoperators taketake 22 operandsoperands ((egeg 33 4).4). PropositionalPropositional oror BooleanBoolean operatorsoperators operateoperate onon propositionspropositions oror truthtruth valuesvalues insteadinstead ofof onon numbers.numbers.
13. SomeSome PopularPopular BooleanBoolean OperatorsOperators Formal Name Nickname Arity Symbol Negation operator NOT Unary ¬ Conjunction operator AND Binary  Disjunction operator OR Binary  Exclusive-OR operator XOR Binary  Implication operator IMPLIES Binary Biconditional operator IFF Binary ↔
14. PhépPhép tínhtính mệnhmệnh đềđề
15. PhépPhép tínhtính mệnhmệnh đềđề NhàNhà điềuđiều hànhhành phủphủ địnhđịnh nguyênnguyên phânphân "¬""¬" (NOT)(NOT) biếnbiến đổiđổi mộtmột prop.prop. thànhthành phủphủ địnhđịnh hợphợp lýlý củacủa nĩnĩ VD:VD: NếuNếu pp == ""TơiTơi cĩcĩ máimái tĩctĩc màumàu nâunâu."." sausau đĩđĩ ¬¬ pp == ""TơiTơi khơngkhơng cĩcĩ máimái tĩctĩc nâunâu".".
16. PhépPhép tínhtính mệnhmệnh đềđề
17. PhépPhép tínhtính mệnhmệnh đềđề PhépPhép nốinối liền(phépliền(phép hộihội;; phépphép giaogiao):): MệnhMệnh đềđề nốinối liềnliền củacủa haihai mệnhmệnh đềđề P,P, QQ đượcđược kíkí hiệuhiệu bởibởi PP  QQ ((đọcđọc làlà “P“P vàvà Q”Q”),), llàà mệnhmệnh đềđề đượcđược địnhđịnh bởibởi :: PP  QQ đúngđúng PP vàvà QQ đồngđồng thờithời đúngđúng
18. PhépPhép tínhtính mệnhmệnh đềđề VíVí dụdụ:: MệnhMệnh đềđề ““HơmHơm nay,nay, cơcơ ấyấy đẹpđẹp vàvà thơngthơng minhminh ”” chỉchỉ đượcđược xemxem làlà mệnhmệnh đềđề đúngđúng khikhi cảcả haihai điềuđiều kiệnkiện ““cơcơ ấyấy đẹpđẹp”” vàvà ““cơcơ ấyấy thơngthơng minhminh”” đềuđều xảyxảy rara NgượcNgược lạilại,, chỉchỉ 11 trongtrong 22 điềuđiều kiệnkiện trêntrên saisai thìthì mệnhmệnh đềđề trêntrên sẽsẽ saisai
19. PhépPhép tínhtính mệnhmệnh đềđề MệnhMệnh đềđề ““HômHôm nay,nay, AnAn giúpgiúp mẹmẹ laulau nhànhà vàvà rửarửa chénchén”” chỉchỉ đúngđúng khikhi hômhôm naynay AnAn giúpgiúp mẹmẹ cảcả haihai côngcông việcviệc laulau nhànhà vàvà rửarửa chénchén NgượcNgược lạilại,, nếunếu hômhôm naynay AnAn chỉchỉ giúpgiúp mẹmẹ mộtmột trongtrong haihai côngcông việcviệc trêntrên,, hoặchoặc khôngkhông giúpgiúp mẹmẹ cảcả haihai thìthì mệnhmệnh đềđề trêntrên saisai
20. TheThe ConjunctionConjunction OperatorOperator TheThe binarybinary conjunctionconjunction operatoroperator ““”” ((ANDAND)) combinescombines twotwo propositionspropositions toto formform NDND theirtheir logicallogical conjunctionconjunction E.g.E.g. IfIf pp=“I=“I willwill havehave saladsalad forfor lunch.”lunch.” andand q=q=“I“I willwill havehave steaksteak forfor dinner.”,dinner.”, thenthen ppqq=“I=“I willwill havehave saladsalad forfor lunchlunch andand II willwill havehave steaksteak forfor dinner.”dinner.” Remember: “” points up like an “A”, and it means “ND”
21. ConjunctionConjunction TruthTruth TableTable Operand columns NoteNote thatthat aa conjunctionconjunction pp11  pp22   ppnn ofof nn propositionspropositions willwill havehave 22nn rowsrows inin itsits truthtruth table.table. Also:Also: ¬¬ andand  operationsoperations togethertogether areare suffi-suffi- cientcient toto expressexpress anyany BooleanBoolean truthtruth table!table!
22. PhépPhép tínhtính mệnhmệnh đềđề
23. PhépPhép tínhtính mệnhmệnh đềđề PhépPhép nốinối rời(phéprời(phép tuyểntuyển;; phépphép hợphợp)) MệnhMệnh đềđề nốinối rờirời củacủa haihai mệnhmệnh đềđề P,P, QQ đượcđược kíkí hiệuhiệu bởibởi PP  QQ ((đọcđọc làlà “P“P hayhay Q”Q”),), llàà mệnhmệnh đềđề đượcđược địnhđịnh bởibởi :: PP  QQ saisai PP vàvà QQ đồngđồng thờithời saisai
24. PhépPhép tínhtính mệnhmệnh đềđề VíVí dụdụ:: MệnhMệnh đềđề ““TơiTơi đangđang chơichơi bĩngbĩng đáđá hayhay bĩngbĩng rổrổ”.”. MệnhMệnh đềđề nàynày chỉchỉ saisai khikhi tơitơi vừavừa khơngkhơng đangđang chơichơi bĩngbĩng đáđá cũngcũng nhưnhư vừavừa khơngkhơng đangđang chơichơi bĩngbĩng rổrổ NgượcNgược lạilại,, tơitơi chơichơi bĩngbĩng đáđá hayhay đangđang chơichơi bĩngbĩng rổrổ hayhay đangđang chơichơi cảcả haihai thìthì mệnhmệnh đềđề trêntrên đúngđúng
25. TheThe DisjunctionDisjunction OperatorOperator NhàNhà điềuđiều hànhhành phânphân lyly nhịnhị phânphân (OR)(OR) kếtkết hợphợp haihai mệnhmệnh đềđề đểđể hìnhhình thànhthành phânphân lyly hợphợp lýlý củacủa họhọ xexe cĩcĩ độngđộng cơcơ xấuxấu qq == xexe củacủa tơitơi cĩcĩ mộtmột bìnhbình xăngxăng concon xấuxấu qq == HoặcHoặc làlà xexe củacủa tơitơi cĩcĩ mộtmột độngđộng cơcơ xấuxấu,, hayhay xexe củacủa tơitơi cĩcĩ mộtmột bìnhbình xăngxăng concon xấuxấu After the downward- pointing “axe” of “” splits the wood, you Meaning is like “and/or” in English. can take 1 piece OR the other, or both.
26. DisjunctionDisjunction TruthTruth TableTable NoteNote thatthat ppqq meansmeans thatthat pp isis true,true, oror qq isis true, or both are true! true, or both are true! Note So,So, thisthis operationoperation isis difference alsoalso calledcalled inclusiveinclusive or,or, from AND becausebecause itit includesincludes thethe possibilitypossibility thatthat bothboth pp andand qq areare true.true. ““¬¬”” andand ““”” togethertogether areare alsoalso universal.universal.
27. PhépPhép tínhtính mệnhmệnh đềđề
28. PhépPhép tínhtính mệnhmệnh đềđề ChúChú ýý :: CầnCần phânphân biệtbiệt “hay”“hay” vàvà ““hoặchoặc”.”. ĐưaĐưa rara phépphép tốntốn đểđể thểthể hiệnhiện trườngtrường hợphợp loạiloại trừtrừ KýKý hiệuhiệu :: PP QQ saisai PP vàvà QQ đồngđồng thờithời cùngcùng đúngđúng hoặchoặc cùngcùng saisai
29. TheThe ExclusiveExclusive OrOr OperatorOperator TheThe binarybinary exclusive-orexclusive-or operatoroperator ““”” ((XORXOR)) combinescombines twotwo propositionspropositions toto formform theirtheir logicallogical “exclusive“exclusive or”or” (exjunction?).(exjunction?). pp == “I“I willwill earnearn anan AA inin thisthis course,”course,” qq == “I“I willwill dropdrop thisthis course,”course,” pp  qq == “I“I willwill eithereither earnearn anan AA forfor thisthis course,course, oror II willwill dropdrop itit (but(but notnot both!)”both!)”
30. Exclusive-OrExclusive-Or TruthTruth TableTable NoteNote thatthat ppqq meansmeans thatthat pp isis true,true, oror qq isis true,true, butbut notnot bothboth!! ThisThis operationoperation isis calledcalled exclusiveexclusive or,or, Note becausebecause itit excludesexcludes thethe difference possibilitypossibility thatthat bothboth pp andand qq areare true.true. from OR. ““¬¬”” andand ““”” togethertogether areare notnot universal.universal.
31. PhépPhép tínhtính mệnhmệnh đềđề PhépPhép kéokéo theotheo:: MệnhMệnh đềđề PP kéokéo theotheo QQ củacủa haihai mệnhmệnh đềđề PP vàvà Q,Q, kíkí hiệuhiệu bởibởi PP Q(đọcQ(đọc làlà “P“P kéokéo theotheo Q”Q” hayhay ““NếuNếu PP thìthì Q”Q” hayhay “P“P làlà điềuđiều kiệnkiện đủđủ củacủa Q”Q” hayhay “Q“Q làlà điềuđiều kiệnkiện cầncần củacủa P”)P”) làlà mệnhmệnh đềđề đượcđược địnhđịnh bởibởi:: PP QQ saisai PP đúngđúng vàvà QQ saisai
32. PhépPhép tínhtính mệnhmệnh đềđề VíVí dụdụ:: XétXét mệnhmệnh đềđề sausau :: ““NếuNếu tơitơi đẹpđẹp traitrai thìthì tơitơi cĩcĩ nhiềunhiều bạnbạn gáigái”” TaTa cĩcĩ cáccác trườngtrường hợphợp sausau:: TơiTơi đẹpđẹp traitrai vàvà cĩcĩ nhiềunhiều bạnbạn gáigái :: MệnhMệnh đềđề rõrõ ràngràng đúngđúng TơiTơi đẹpđẹp traitrai vàvà khơngkhơng cĩcĩ nhiềunhiều bạnbạn gáigái :: MệnhMệnh đềđề rõrõ ràngràng saisai TơiTơi khơngkhơng đẹpđẹp traitrai màmà vẫnvẫn cĩcĩ nhiềunhiều bạnbạn gáigái :: MệnhMệnh đềđề vẫnvẫn đúngđúng TơiTơi khơngkhơng đẹpđẹp traitrai vàvà khơngkhơng cĩcĩ nhiềunhiều bạnbạn gáigái :: MệnhMệnh đềđề vẫnvẫn đúngđúng
33. PhépPhép tínhtính mệnhmệnh đềđề MệnhMệnh đềđề ““ChiềuChiều nay,nay, nếunếu rảnhrảnh tôitôi sẽsẽ ghéghé thămthăm bạnbạn”” chỉchỉ saisai khikhi chiềuchiều naynay tôitôi rảnhrảnh nhưngnhưng tôitôi khôngkhông ghéghé thămthăm bạnbạn NgượcNgược lạilại,, nếunếu chiềuchiều naynay tôitôi bậnbận thìthì dùdù tôitôi cócó ghéghé thămthăm bạnbạn hayhay khôngkhông,, mệnhmệnh đềđề trêntrên vẫnvẫn đúngđúng NgoàiNgoài rara,, tấttất nhiênnhiên nếunếu chiềuchiều naynay tôitôi cócó ghéghé thămthăm bạnbạn thìthì mệnhmệnh đềđề trêntrên đúngđúng ((dùdù tôitôi cócó rảnhrảnh hayhay khôngkhông!).!).
34. TheThe ImplicationImplication OperatorOperator antecedent consequent TheThe implicationimplication pp qq statesstates thatthat pp impliesimplies q.q. I.e.I.e.,, IfIf pp isis true,true, thenthen qq isis true;true; butbut ifif pp isis notnot true,true, thenthen qq couldcould bebe eithereither truetrue oror false.false. E.g.E.g.,, letlet pp == “You“You studystudy hard.”hard.” qq == “You“You willwill getget aa goodgood grade.”grade.” pp qq == “If“If youyou studystudy hard,hard, thenthen youyou willwill getget aa goodgood grade.”grade.” (else,(else, itit couldcould gogo eithereither way)way)
35. ImplicationImplication TruthTruth TableTable pp qq isis falsefalse onlyonly whenwhen pp isis truetrue butbut qq isis notnot true.true. pp qq doesdoes notnot saysay The thatthat pp causescauses qq!! only pp qq doesdoes notnot requirerequire False case! thatthat pp oror qq areare everever truetrue!! E.g.E.g. “(1=0)“(1=0) pigspigs cancan fly”fly” isis TRUE!TRUE!
36. ExamplesExamples ofof ImplicationsImplications ““IfIf thisthis lecturelecture ends,ends, thenthen thethe sunsun willwill riserise tomorrow.”tomorrow.” TrueTrue oror FalseFalse?? “If“If TuesdayTuesday isis aa dayday ofof thethe week,week, thenthen II amam aa penguin.”penguin.” TrueTrue oror FalseFalse?? “If“If 1+1=6,1+1=6, thenthen BushBush isis president.”president.” TrueTrue oror FalseFalse?? “If“If thethe moonmoon isis mademade ofof greengreen cheese,cheese, thenthen II amam richerricher thanthan BillBill Gates.”Gates.” TrueTrue oror FalseFalse??
37. PhépPhép tínhtính mệnhmệnh đềđề ChúChú ý:ý: LiênLiên hệhệ phépphép kéokéo theotheo vàvà cúcú pháppháp IfIf PP thenthen QQ trongtrong ngơnngơn ngữngữ lậplập trìnhtrình P,QP,Q làlà 22 mệnhmệnh đềđề P P làlà mệnhmệnh đềđề,, QQ làlà dãydãy dịngdịng lệnhlệnh NgơnNgơn ngữngữ hằnghằng ngàyngày,, cĩcĩ sựsự nhầmnhầm lẫnlẫn giữagiữa phépphép kéokéo theotheo vàvà phépphép kéokéo theotheo haihai chiềuchiều ““GiáoGiáo viênviên khoakhoa TốnTốn dạydạy nghiêmnghiêm túctúc””
38. PhépPhép tínhtính mệnhmệnh đềđề
39. PhépPhép tínhtính mệnhmệnh đềđề PhépPhép kéokéo theotheo haihai chiềuchiều:: MệnhMệnh đềđề PP kéokéo theotheo QQ vàvà ngượcngược lạilại củacủa haihai mệnhmệnh đềđề PP vàvà Q,Q, kýký hiệuhiệu bởibởi PP  QQ ((đọcđọc làlà “P“P nếunếu vàvà chỉchỉ nếunếu Q”Q” hayhay PP khikhi vàvà chỉchỉ khikhi Q”Q” hayhay “P“P làlà điềuđiều kiệnkiện cầncần vàvà đủđủ củacủa Q”),Q”), làlà mệnhmệnh đềđề đượcđược địnhđịnh bởibởi:: PP  QQ đúngđúng PP vàvà QQ cócó cùngcùng chânchân trịtrị,,
40. PhépPhép tínhtính mệnhmệnh đềđề
41. PhépPhép tínhtính mệnhmệnh đềđề
42. TheThe biconditionalbiconditional operatoroperator TheThe biconditionalbiconditional pp  qq statesstates thatthat pp isis truetrue ifif andand onlyonly ifif (IFF)(IFF) qq isis true.true. pp == “Bush“Bush winswins thethe 20042004 election.”election.” qq == “Bush“Bush willwill bebe I’m still presidentpresident forfor allall ofof here! 2005.”2005.” pp  qq == “If,“If, andand onlyonly if,if, BushBush winswins thethe2004 20042004 2005 election,election, BushBush willwill bebe presidentpresident forfor allall ofof 2005.”2005.”
43. BiconditionalBiconditional TruthTruth TableTable pp  qq meansmeans thatthat pp andand qq havehave thethe samesame truthtruth value.value. NoteNote thisthis truthtruth tabletable isis thethe exactexact oppositeopposite ofof ’s!’s! pp  qq meansmeans ¬(¬(pp  qq)) pp  qq doesdoes notnot implyimply pp andand qq areare true,true, oror causecause eacheach other.other.
44. BooleanBoolean OperationsOperations SummarySummary WeWe havehave seenseen 11 unaryunary operatoroperator (out(out ofof thethe 44 possible)possible) andand 55 binarybinary operatorsoperators (out(out ofof thethe 1616 possible).possible). TheirTheir truthtruth tablestables areare below.below.
45. SomeSome AlternativeAlternative NotationsNotations
46. DạngDạng mệnhmệnh đềđề MộtMột dạngdạng mệnhmệnh đềđề làlà mộtmột biểubiểu thứcthức đượcđược cấucấu tạotạo từtừ:: CácCác hằnghằng mệnhmệnh đềđề,, tứctức làlà cáccác mệnhmệnh đềđề đãđã xétxét ởở trtrênên CácCác biếnbiến mệnhmệnh đềđề,, tứctức làlà cáccác biếnbiến lấylấy giágiá trịtrị làlà cáccác mệnhmệnh đềđề,, thôngthông quaqua cáccác phépphép toántoán mệnhmệnh đềđề đãđã xétxét ởở mụcmục ttrênrên theotheo mộtmột trìnhtrình tựtự nhấtnhất địnhđịnh nàonào đóđó,, thườngthường đượcđược chỉchỉ rõrõ bởibởi cáccác dấudấu ngongoặcặc
47. DạngDạng mệnhmệnh đềđề VớiVới EE làlà mộtmột dạngdạng mệnhmệnh đềđề cáccác biếnbiến mệnhmệnh đềđề p,p, q,q, rr ứngứng vớivới mỗimỗi giágiá trịtrị cụcụ thểthể P,P, Q,Q, RR ((làlà cáccác mệnhmệnh đềđề)) củacủa p,p, q,q, rr thìthì tata cĩcĩ duyduy nhấtnhất mộtmột mệnhmệnh đềđề E(P,E(P, Q,Q, R).R). TaTa viếtviết EE == E(pE(p,, q,q, r).r). BảngBảng chânchân trịtrị làlà bảngbảng ghighi tấttất cảcả cáccác trườngtrường hợphợp chânchân trịtrị cĩcĩ thểthể xảyxảy rara đốiđối vớivới mệnhmệnh đềđề EE theotheo chânchân trịtrị củacủa cáccác biếnbiến mệnhmệnh đềđề p,p, q,q, r.r. NếuNếu cĩcĩ nn biếnbiến,, bảngbảng nàynày sẽsẽ cĩcĩ 2^n2^n dịngdịng,, chưachưa kểkể dịngdịng tiêutiêu đềđề
48. DạngDạng mệnhmệnh đềđề
49. TautologiesTautologies andand ContradictionsContradictions AA tautologytautology isis aa compoundcompound propositionproposition thatthat isis truetrue nono mattermatter whatwhat thethe truthtruth valuesvalues ofof itsits atomicatomic propositionspropositions are!are! Ex.Ex. pp  pp [What[What isis itsits truthtruth table?]table?] AA contradictioncontradiction isis aa compoundcompound propositionproposition thatthat isis falsefalse nono mattermatter what!what! Ex.Ex. pp  pp [Truth[Truth table?]table?] OtherOther compoundcompound props.props. areare contingenciescontingencies
50. LogicalLogical EquivalenceEquivalence CompoundCompound propositionproposition pp isis logicallylogically equivalentequivalent toto compoundcompound propositionproposition qq,, writtenwritten pp qq,, IFFIFF thethe compoundcompound propositionproposition ppqq isis aa tautology.tautology. CompoundCompound propositionspropositions pp andand qq areare logicallylogically equivalentequivalent toto eacheach otherother IFFIFF pp andand qq containcontain thethe samesame truthtruth valuesvalues asas eacheach otherother inin allall rowsrows ofof theirtheir truthtruth tables.tables.
51. ProvingProving EquivalenceEquivalence viavia TruthTruth TablesTables Ex.Ex. ProveProve thatthat ppqq ((pp  qq).). F T T T F T T F F T T F T F T T F F F T
52. DạngDạng mệnhmệnh đềđề 1.1. QuyQuy tắctắc thaythay thếthế thứthứ 1:1: TrongTrong dạngdạng mệnhmệnh đềđề E,E, nếunếu tata thaythay thếthế biểubiểu thứcthức concon FF bởibởi mộtmột dạngdạng mệnhmệnh đềđề tươngtương đươngđương logiclogic thìthì dạngdạng mệnhmệnh đềđề thuthu đượcđược vẫnvẫn cịncịn tươngtương đươngđương logiclogic vớivới E.E. 2.2. QuyQuy tắctắc thaythay thếthế thứthứ 2:2: GiảGiả sửsử dạngdạng mệnhmệnh đềđề E(p,q,rE(p,q,r ) ) làlà mộtmột hằnghằng đúngđúng NếuNếu tata thaythay thếthế nhữngnhững nơinơi pp xuấtxuất hiệnhiện trongtrong EE bởibởi mộtmột F(p’,q’,rF(p’,q’,r’)’) thìthì dạngdạng mệnhmệnh đềđề nhậnnhận đượcđược theotheo cáccác biếnbiến q,rq,r , ,p’,q’,rp’,q’,r’, ’, vẫnvẫn cịncịn làlà 11 hằnghằng đúngđúng
53. DạngDạng mệnhmệnh đềđề CácCác luậtluật logiclogic :: VớiVới p,p, q,q, rr làlà cáccác biếnbiến mệnhmệnh đềđề,, 11 làlà mộtmột hằnghằng đúngđúng vàvà 00 làlà mộtmột hằnghằng saisai,, tata cĩcĩ cáccác tươngtương đươngđương logiclogic sausau đâyđây:: 1)1) LuậtLuật lũylũy đẳngđẳng pp  pp pp vàvà pp  pp pp
54. DạngDạng mệnhmệnh đềđề
55. DạngDạng mệnhmệnh đềđề 16)16) LuậtLuật vềvề phépphép kéokéo theo:theo: pp qq pp  qq 17)17) LuậtLuật rútrút gọn:gọn: pp qq pp 1(*)1(*) pp (p(p q)q) pp qq pp  qq qq pp qq pp (p(p  q)q) 1(*)1(*)
56. EquivalenceEquivalence LawsLaws ExamplesExamples IdentityIdentity:: ppTT pp ppFF pp DominationDomination:: ppTT TT ppFF FF IdempotentIdempotent:: pppp pp pppp pp DoubleDouble negation:negation: pp pp Commutative:Commutative: ppqq qqpp ppqq qqpp Associative:Associative: ((ppqq))rr pp((qqrr)) ((ppqq))rr pp((qqrr))
57. MoreMore EquivalenceEquivalence LawsLaws DistributiveDistributive:: pp((qqrr)) ((ppqq))((pprr)) pp((qqrr)) ((ppqq))((pprr)) Augustus DeDe Morgan’sMorgan’s:: De Morgan (1806-1871) ((ppqq)) pp  qq ((ppqq)) pp  qq TrivialTrivial tautology/contradictiotautology/contradictio nn:: pp  pp TT pp  pp FF
58. DefiningDefining OperatorsOperators viavia EquivalencesEquivalences UsingUsing equivalences,equivalences, wewe cancan definedefine operatorsoperators inin termsterms ofof otherother operators.operators. ExclusiveExclusive or:or: ppqq ((ppqq))((ppqq)) ppqq ((ppqq))((qqpp)) Implies:Implies: pp qq pp  qq BiconditionalBiconditional:: ppqq ((pp qq))  ((qq pp)) ppqq ((ppqq))
59. AnAn ExampleExample ProblemProblem CheckCheck usingusing aa symbolicsymbolic derivationderivation whetherwhether ((pp  qq)) ((pp  rr)) pp  qq  rr ((pp  qq)) ((pp  rr)) [Expand[Expand definitiondefinition ofof ]] ((pp  qq))  ((pp  rr)) [Defn.[Defn. ofof ]] ((pp  qq))  ((((pp  rr))  ((pp  rr)))) [DeMorgan’s[DeMorgan’s Law]Law] ((pp  qq))  ((((pp  rr))  ((pp  rr)))) [associative[associative law]law] cont.cont.
60. ExampleExample Continued Continued ((pp  qq))  ((((pp  rr))  ((pp  rr)))) [[ commutes]commutes] ((qq  pp))  ((((pp  rr))  ((pp  rr)))) [[ associative]associative] qq  ((pp  ((((pp  rr))  ((pp  rr)))))) [distrib.[distrib.  overover ]] qq  ((((((pp  ((pp  rr))))  ((pp  ((pp  rr)))))) [assoc.][assoc.] qq  ((((((pp  pp))  rr))  ((pp  ((pp  rr)))))) [trivail[trivail taut.]taut.] qq  ((((TT  rr))  ((pp  ((pp  rr)))))) [domination][domination] qq  ((TT  ((pp  ((pp  rr)))))) [identity][identity] qq  ((pp  ((pp  rr)))) cont.cont.
61. EndEnd ofof LongLong ExampleExample qq  ((pp  ((pp  rr)))) [DeMorgan’s][DeMorgan’s] qq  ((pp  ((pp  rr)))) [Assoc.][Assoc.] qq  ((((pp  pp))  rr)) [Idempotent][Idempotent] qq  ((pp  rr)) [Assoc.][Assoc.] ((qq  pp))  rr [Commut.][Commut.] pp  qq  rr Q.E.D.Q.E.D. (quod(quod eraterat demonstrandum)demonstrandum) (Which was to be shown.)
62. DạngDạng mệnhmệnh đềđề ChứngChứng minhminh dạngdạng mệnhmệnh đềđề tata cĩcĩ 33 cáchcách sausau:: LậpLập bảngbảng chânchân trịtrị LậpLập bảngbảng chânchân trịtrị mởmở rộngrộng SửSử dụngdụng phépphép thaythay thếthế
63. QuiQui TắcTắc SuySuy DiễnDiễn TrongTrong cáccác chứngchứng minhminh tốntốn học,xuấthọc,xuất phátphát từtừ mộtmột sốsố khẳngkhẳng địnhđịnh đúngđúng p,p, q,q, r (r (tiêntiên đềđề),), tata ápáp dụngdụng cáccác quiqui tắctắc suysuy diễndiễn đểđể suysuy rara chânchân lílí củacủa mộtmột mệnhmệnh đềđề hh màmà tata gọigọi làlà kếtkết luậnluận NĩiNĩi cáchcách kháckhác,, dùngdùng cáccác quiqui tắctắc suysuy diễndiễn đểđể chứngchứng minhminh:: (( pp  qq  rr  ) ) hh làlà mộtmột khẳngkhẳng địnhđịnh đúngđúng
64. QuiQui TắcTắc SuySuy DiễnDiễn KhẳngKhẳng địnhđịnh (1)(1) cĩcĩ dạngdạng:: ((((tiêntiên đềđề 11))  ((tiêntiên đềđề 2)2)  ) ) kếtkết luậnluận DoDo đĩđĩ nếunếu chứngchứng minhminh đượcđược dạngdạng mệnhmệnh đềđề trêntrên làlà mộtmột hằnghằng đúngđúng thìthì khẳngkhẳng địnhđịnh (1)(1) chắcchắc chắnchắn làlà đúngđúng TaTa thườngthường mơmơ hìnhhình hĩahĩa (2):(2): tiêntiên đềđề (1)(1) tiêntiên đềđề(2)(2)  kếtkết luậnluận Aristotle (ca. 384-322 B.C.)
65. Aristotle (ca. 384-322 B.C.)
66. QuiQui TắcTắc SuySuy DiễnDiễn QUIQUI TẮCTẮC MODUSMODUS PONENS(PhươngPONENS(Phương pháppháp khẳngkhẳng địnhđịnh)) QuiQui tắctắc nàynày đượcđược thểthể hiệnhiện bằngbằng hằnghằng đúngđúng:: HoặcHoặc dướidưới dạngdạng sơsơ đồđồ
67. •Nếu An học chăm thì An học tốt. •Mà An học chăm Suy ra An học tốt •Hình vuơng là hình bình hành •Mà hình bình hành cĩ hai đường chéo cắt nhau tại trung điểm mỗi đường. Suy ra hình vuơng cĩ hai đường chéo cắt nhau tại trung điểm mỗi đường Aristotle (ca. 384-322 B.C.)
68. QuiQui TắcTắc SuySuy DiễnDiễn QUIQUI TẮCTẮC TAMTAM ĐOẠNĐOẠN LUẬN(SyllogismLUẬN(Syllogism)) QuiQui tắctắc nàynày đượcđược thểthể hiệnhiện bằngbằng hằnghằng đúngđúng:: HoặcHoặc dướidưới dạngdạng sơsơ đồđồ Aristotle (ca. 384-322 B.C.)
69. •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 ()
70. QuiQui TắcTắc SuySuy DiễnDiễn QUIQUI TẮCTẮC MODUSMODUS TOLLENSTOLLENS PHƯƠNGPHƯƠNG PHÁPPHÁP PHỦPHỦ ĐỊNHĐỊNH QuiQui tắctắc nàynày đượcđược thểthể hiệnhiện bằngbằng hằnghằng đúngđúng:: HoặcHoặc dướidưới dạngdạng sơsơ đồđồ Aristotle (ca. 384-322 B.C.)
71. Xét chứng minh Ta suy luận Aristotle (ca. 384-322 B.C.)
72. QuiQui TắcTắc SuySuy DiễnDiễn QUIQUI TẮCTẮC TAMTAM ĐOẠNĐOẠN LUẬNLUẬN RỜIRỜI QuiQui tắctắc nàynày đượcđược thểthể hiệnhiện bằngbằng hằnghằng đúngđúng:: ÝÝ nghĩanghĩa củacủa quiqui tắctắc:: nếunếu trongtrong haihai trườngtrường hợphợp cĩcĩ thểthể xảyxảy rara,, chúngchúng tata biếtbiết cĩcĩ mộtmột trườngtrường hợphợp saisai thìthì chắcchắc chắnchắn trườngtrường hợphợp cịncịn lạilại sẽsẽ đúngđúng
73. QuiQui TắcTắc SuySuy DiễnDiễn QUIQUI TẮCTẮC MÂUMÂU THUẪNTHUẪN CHỨNGCHỨNG MINHMINH BẰNGBẰNG PHẢNPHẢN CHỨNGCHỨNG TaTa cĩcĩ tươngtương đươngđương logiclogic TaTa cầncần chứngchứng minhminh vếvế tráitrái cũngcũng làlà mộtmột hằnghằng đúngđúng hayhay nĩinĩi cáchcách kháckhác chứngchứng minhminh khikhi thêmthêm phủphủ địnhđịnh củacủa qq vàovào cáccác tiềntiền đềđề tata đượcđược mộtmột mâumâu thuẫnthuẫn
74. VÍ DỤ Hãy chứng minh: Cm bằng phản chứng. Aristotle (ca. 384-322 B.C.)
75. QuiQui TắcTắc SuySuy DiễnDiễn CHỨNGCHỨNG MINHMINH THEOTHEO TRƯỜNGTRƯỜNG HỢPHỢP DựaDựa trêntrên hằnghằng đúngđúng:: ÝÝ nghĩanghĩa:: nếunếu từtừ pp vàvà qq cĩcĩ thểthể suysuy rara rr thìthì từtừ dạngdạng pp hayhay qq cũngcũng cĩcĩ thểthể suysuy rara r.r.
76. VÍ DỤ ChứngChứng minhminh rằng:rằng: Aristotle (ca. 384-322 B.C.)
77. MộtMột sốsố luậtluật thêmthêm pp RuleRule ofof Addition(Addition(PhépPhép thêmthêm))  ppqq ppqq PhépPhép đđơnơn giảngiản nốinối liềnliền  pp pp LuậtLuật vềvề phépphép nốinối qq  ppqq Aristotle (ca. 384-322 B.C.)
78. VÍVÍ DỤDỤ TỔNGTỔNG HỢPHỢP 1. Nếu nghệ sĩ Trương Ba p:Nghệ sĩ Trương Ba trình diễn. khơng trình diễn hay số q:số vé bán ra ít hơn 100. vé bán ra ít hơn 100 thì r:đêm diễn bị hủy bỏ. đêm diễn sẽ bi hủy bỏ và ơng bầu sẽ rất buồn. s: ơng bầu buồn. 2. Nếu đêm diễn bị hủy bỏ t:trả lại vé cho người xem thì vé phải trả lại cho người xem. 3. Nhưng vé đã khơng trả lại cho người xem. Vậy cĩ kết luân gì?
79. QuiQui TắcTắc SuySuy DiễnDiễn PHẢNPHẢN VÍVÍ DỤDỤ ĐểĐể chứngchứng minhminh mộtmột phépphép suysuy luậnluận làlà saisai hayhay khơngkhơng làlà mộtmột hằnghằng đúngđúng TaTa chỉchỉ cầncần chỉchỉ rara mộtmột phảnphản víví dụdụ
80. VÍVÍ DỤDỤ ƠngƠng MinhMinh nĩinĩi rằngrằng nếunếu p:ơngp:ơng MinhMinh đượcđược tăngtăng lươnglương khơngkhơng đượcđược tăngtăng lươnglương thìthì q:q: ơngơng MinhMinh nghỉnghỉ việcviệc ơngơng tata sẽsẽ nghỉnghỉ việcviệc MặtMặt r:vợ ơng Minh mất việc. kháckhác,, nếunếu ơngơng ấyấy nghỉnghỉ việcviệc r:vợ ơng Minh mất việc. vàvà vợvợ ơngơng ấyấy bịbị mấtmất việcviệc thìthì s:gias:gia đìnhđình phảiphải bánbán xexe phảiphải bánbán xe.Biếtxe.Biết rằngrằng nếunếu vợvợ t:vợt:vợ ơngơng hayhay điđi làmlàm trểtrể ơngơng MinhMinh hayhay điđi làmlàm trễtrễ thìthì trướctrước sausau gìgì cũngcũng sẽsẽ bịbị mấtmất việcviệc vàvà cuốicuối cùngcùng ơngơng MinhMinh s=0 đãđã đượcđược tăngtăng lươnglương t=1 SuySuy rara nếunếu ơngơng MinhMinh khơngkhơng p=1 bánbán xexe thìthì vợvợ ơngơng tata đãđã q=0 khơngkhơng điđi làmlàm trễtrễ r=1
81. FormalFormal ProofProof ExampleExample SupposeSuppose wewe havehave thethe followingfollowing premises:premises: “It“It isis notnot sunnysunny andand itit isis cold.”cold.” “Only“Only ifif WeWe willwill swimswim isis itit sunny.”sunny.” “If“If wewe dodo notnot swim,swim, thenthen wewe willwill canoe.”canoe.” “If“If wewe canoe,canoe, thenthen wewe willwill bebe homehome early.”early.” GivenGiven thesethese premises,premises, proveprove thethe theoremtheorem “We“We willwill bebe homehome early”early” usingusing inferenceinference rules.rules.
82. ProofProof ExampleExample cont.cont. LetLet usus adoptadopt thethe followingfollowing abbreviations:abbreviations: sunnysunny == “It“It isis sunny”sunny”;; coldcold == “It“It isis cold”cold”;; swimswim == “We“We willwill swim”swim”;; canoecanoe == “We“We willwill canoe”canoe”;; earlyearly == “We“We willwill bebe homehome early”early” Then,Then, thethe premisespremises cancan bebe writtenwritten as:as: (1)(1) sunnysunny  coldcold (2)(2) swimswim sunnysunny (3)(3) swimswim canoecanoe (4)(4) canoecanoe earlyearly
83. ProofProof ExampleExample contcont StepStep ProvedProved byby 1.1. sunnysunny  coldcold PremisePremise #1.#1. 2.2. sunnysunny SimplificationSimplification ofof 1.1. 3.3. swimswim sunnysunny PremisePremise #2.#2. 4.4. swimswim ModusModus tollenstollens onon 2,3.2,3. 5.5. swimswim canoecanoe PremisePremise #3.#3. 6.6. canoecanoe ModusModus ponensponens onon 4,5.4,5. 7.7. canoecanoe earlyearly PremisePremise #4.#4. 8.8. earlyearly ModusModus ponensponens onon 6,7.6,7.
84. QuiQui TắcTắc SuySuy DiễnDiễn
85. QuiQui TắcTắc SuySuy DiễnDiễn
86. QuiQui TắcTắc SuySuy DiễnDiễn
87. QuiQui TắcTắc SuySuy DiễnDiễn
88. QuiQui TắcTắc SuySuy DiễnDiễn