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

Chương 1 của bài giảng Toán rời rạc cung cấp những kiến thức về cơ sở Logic 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ừ và lượng từ hóa. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Chương 1: Cơ sở Logic TOÁNRỜIRẠC(DiscreteMathematics) Chương1 CơsởLogicLogicmệnhđềLogicvịtừNộidungchính  Kháiniệmmệnhđề  Cácphéptoánlogic  Dạngmệnhđề  Cácquytắcsuydiễn  Cácphươngphápchứngminh  Vịtừvàlượngtừhóa1.Địnhnghĩamệnhđề: Mệnhđề(Proposition):làmộtdiễnđạtcógiátrịchânlý(chân trị)xácđịnh(đúnghoặcsainhưngkhôngthểvừađúnglạivừa sai). Vídụ1.1:Cácdiễnđạtsau,diễnđạtnàolàmệnhđề?  Mặttrờiquayquanhtráiđất  3+1=5  Tráiđấtquayquanhmặttrời,…  x+2=8  Mấygiờrồi?  phảihiểukỹđiềunày.  HànộilàthủđôcủaViệtNam  Sàigònnằmởmiềnbắcviệtnam  x+1=5nếux=1Mệnhđề(tt)Kíhiệu: 1(hoặcT):Chântrịđúng. 0(hoặcF):Chântrịsai. P,Q,R,…dùngchokíhiệucácmệnhđề.Vídụ1.2: P:HàNộilàThủĐôcủaViệtNam Q:QuyNhơnthuộctỉnhBìnhĐịnh R:ViệtNamthuộcchâuÁ S:LongAnlàtỉnhthuộckhuvựcmiềntrungcủaViệtNam. …2.CácphéptoánlogicPhépphủđịnh(Negationoperator)Phépnốiliền(Conjunctionoperator)Phépnốirời(Disjunctionoperator)Phépkéotheo(Implicationoperator)Phépkéotheohaichiều(Biconditionaloperator)2.1.Phépphủđịnh(Negationoperator) PhủđịnhcủamệnhđềP(kíhiệu¬P:đọclà“KhôngP”)là mệnhđềcóchântrị1nếuPcóchântrị0vàcóchântrị0nếu Pcóchântrị1.◊Bảngchântrị P ¬P 0 1 1 0◊Vídụ2.1: P: “HànộilàthủđôcủaViệtNam” P: “HànộikhôngphảilàthủđôcủaViệtNam” Q: “14=8” Q: ”14 8”2.2.Phépnốiliền(ConjunctionOperator) PhépnốiliềnhaimệnhđềPvàQ(kíhiệuP Q:đọclà“P vàQ”)làmệnhđềcóchântrị1nếucảPvàQcóchântrị1 hoặccóchântrị0nếuítnhấtmộttrong2mệnhđềPhay Qcóchântrị0. Bảngchântrị: P Q P Q 0 0 0 0 1 0 1 0 0 1 1 1VídụvềphépnốiliềnVídụ2.2:“Hômnaylàchủnhậtvàngàymailàthứ7” làmộtmệnhđềcóchântrị0.Vídụ2.2:“Tổngcácgóctrongmộttamgiácbằng180o vàtrongtamgiácvuôngcómộtgóc90o”làmệnhđề cóchântrị1Vídụ2.3:“Trongmộttamgiáccâncó2cạnhbằng nhauvàmặttrờiquayquanhtráiđất”làmộtmệnh đềcóchântrị0.2.3.Phépnốirời(DisjunctionOperator) PhépnốirờikếthợphaimệnhđềP,Q(kíhiệuP Q:đọc là“PhayQ”)làmệnhđềcóchântrị0nếucảPvàQcó chântrị0hoặccóchântrị1nếuPcóchântrị1hayQcó chântrị1. Bảngchântrị: P Q PQ 0 0 0 0 1 1 1 0 1 1 1 12.4Phépkéotheo(ImplicationOperator) Mệnhđề“NếuPthìQ”(kíhiệuP Q:đọclàPkéotheo Q,hayPlàđiềukiệnđủcủaQhayQlàđiềucầncủaP)là mệnhđềcóchântrị0nếuPcóchântrị1vàQcóchântrị0, cóchântrị1trongcáctrườnghợpcònlại. Bảngchântrị: P Q P Q 0 0 1 0 1 1 1 0 0 1 1 1Vídụvềphépkéotheo Vídụ2.4: P: “Nếu32.5.Phépkéotheo2chiều Mệnhđề“NếuPthìQvàngượclại”,kíhiệuP Q(cònđọc là“PnếuvàchỉnếuQ”hoặc“PkhivàchỉkhiQ”hoặc“Plà điềukiệncầnvàđủđểcóQ”)cóchântrị1nếucả2mệnhđềP vàQcócùngchântrị,cóchântrị0trongcáctrườnghợpcònlại. Bảngchântrị: P Q P Q 0 0 1 0 1 0 1 0 0 1 1 13.Dạngmệnhđề Tómtắt:  Địnhnghĩa  Bảngchântrị  TươngđươngLogic  HệquảLogic  Cácquytắcthaythế  Cácluậtlogic  Cácphươngphápchứngminh3.1.Dạngmệnhđề Địnhnghĩa:DạngmệnhđềlàmộtbiểuthứcLogic (baogồmcáchằngmệnhđề,biếnmệnhđềđược kếthợpbởicácphéptoánlogic). Vídụ1:Chodạngmệnhđềtheo2biếnmệnhđềp, q: E(p,q)=(p q) p BảnthânE(p,q):Chưaphảilàmệnhđề. NếuthaybiếnmệnhđềpbởimệnhđềPvàbiếnmệnhđề qbởimệnhđềQ.KhiđóE(P,Q)làmệnhđề(cóchântrị xácđịnh) Bảngchântrịchobiếtchântrịcủadạngmệnhđề theochântrịxácđịnhcủacácbiếnmệnhđề.3.1.Dạngmệnhđề(tt)Vídụ3.1:Lậpbảngchântrịcủadạngmệnhđề: E(p,q)=(p q) p p q p pq pq p 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0Dạngmệnhđề(tt)Vídụ3.2:Viếtlạithànhdạngmệnhđềlàlậpbảngchântrịcho diễnđạt:“Bạnđượcphépđixemáynếubạntrên16tuổivàcó sứckhỏetốt”.Gọi: p:Bạnđượcphépđixemáy. q:Bạntrên16tuổi. p q r q r q r p r:Bạncósứckhỏetốt.Dạngmệnhđềchodiễnđạttrên: q r p.Bảngchântrị:3.2Tươngđươnglogic&hệquảlogic HaidạngmệnhđềEvàFtươngđươnglogicnếuchúng cócùngbản ...