Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng

1. Giới thiệu:
Logic là khoa học xuất hiện rất sớm trong lịch sử. N ó xuất hiện vào thế kỷ thứ IV trước
công nguyên khi sự phát triển của khoa học nói riêng và tư duy nói chung đã đòi hỏi phải trả
lời câu hỏi: làm thế nào để đảm bảo suy ra được kết luận đúng đắn, chân thực từ các tiền đề
chân thực?
2. Định nghĩa logic học:
Từ “Logic” có nguồn gốc từ Hy lạp là từ “Logos”, từ này có rất nhiều nghĩa trong đó
có hai nghĩa thường dùng nhất là:
 Chỉ tính qui luật của sự tồn tại và phát triển của thế giới khách quan.
 Chỉ những qui luật đặc thù của tư duy.
Khi ta nói “trái đất quay quanh mặt trời”, ta đã sử dụng nghĩa thứ nhất. Còn khi nói
“anh ấy suy luận hợp logic”, ta đã sử dụng nghĩa thứ hai. 
pdf 57 trang hoanghoa 09/11/2022 4680
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfgiao_trinh_logic_toan_phan_1_trinh_huy_hoang.pdf

Nội dung text: Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng

  1. GiáotrìnhLogicToán  Mộtmệnhđềphức(compoundproposition)làmệnhđềđượctạothànhtừhaihay nhiềumệnhđềđơn.Việcnốikếtnàyđượcthựchiệnbởicácliêntừlogic. Vídụ: Xétcácmệnhđềsauđây. p="15chiahếtcho3". q="2làmộtsốnguyêntốvàlàmộtsốlẻ". Tacóplàmộtmệnhđềsơcấp.N hưngqlàmộtmệnhđềphứchợp,vìmệnhđềqđược tạothànhtừhaimệnhđề"2làmộtsốnguyêntố"và"2làmộtsốlẻ"nhờvàoliênkếtlogic "và". 3.Cácphéptoánlogiccơbản: Cácphéptoánlogicđượcđịnhnghĩabằng bảngchântrị(truthtable).Bảngchântrị chỉrarõràngchântrịcủamệnhđềphứchợptheotừngtrườnghợpcủacácchântrịcủacác mệnhđềsơcấptạothànhmệnhđềphứchợp.Bảngchântrịcủacácphéptoánlogictấtnhiên làphảnánhngữnghĩatựnhiêncủacáctừliênkếttươngứng.Vềmặttựnhiêncủangônngữ, trongnhiềutrườnghợpcùngmộttừnhưngcóthểcónghĩakhácnhautrongnhữngngữcảnh khácnhau.Dođó,bảngchântrịkhôngthểdiễnđạtmọinghĩacóthểcócủatừtươngứngvới kýhiệuphéptoán.Ðiềunầychothấyrằngđạisốlogiclàrõrànghoànchỉnhtheonghĩalànó chotamộthệthốnglogicđángtincậy.Ðạisốlogiccònđặcbiệtquantrọngtrongviệcthiếtkế mạchchomáytính. Bảngchântrịkhôngchỉdùngđểkêrasựliênhệchântrịgiữamệnhđềphứchợpvới chântrịcủacácmệnhđềsơcấpcấuthànhnó,màbảngchântrịcònđượcdùngvớimụcđích rộnghơn:liệtkêsựliênhệchântrịgiữacácmệnhvớicácmệnhđềđơngiảnhơncấuthành chúng. Phépphủđịnh: ¬ (không) Độưutiêncủacáctoántửlogic . Phéphội: ∧ (và) ¬ Phéptuyển: ∨ (hay) ∧,∨ Phépkéotheo: → (kéotheo) →,↔ Phépkéotheo2chiều: ↔(tươngđương) Cáctoántửcùngdòngcócùngđộưutiên. Vídụ: ¬p ∨qcónghĩalà(( ¬p) ∨q). ¬p ∨q →r ∧scónghĩalà((( ¬p) ∨q) →(r ∧s)). Gv:TrịnhHuyHoàng Trang11
  2. GiáotrìnhLogicToán ¬p ∨q∧rlàkhôngrõràngcầnphảidùngcácdấungoặcđểchỉrõnghĩa. Xéthaimệnhđềxvày,khiđótacó: Bảngchântrịcủacácphéptoánmệnhđề Mệnhđềp Phủđịnhp Mệnhđềp PhéptuyểnPhéphộiKéotheo Tươngđương x ¬x y x ∨y x ∧y x →y x ↔y 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 N goàiratacòncóthêmmộtphéptoánlogickháclà“phéptuyểnchọn”ứngvới2 mệnhđềsơcấppvàqkhácvớiphéptuyểnđãchoởtrênđượcviếtlàp+q,hayp ⊕qhaycó thểbiểudiễnnhưsau: Bảngchântrị x y xvy 1 1 0 1 0 1 0 1 1 0 0 0 4.Côngthứctrongđạisốlogic: 4.1/Côngthc: Từcácbiếnmệnhđềsơcấp,nhờcácphéptoánlogiccơbản,talậpđượccácmệnhđề phứchợp,chúngđượcgọilàcáccôngthức.TathườngkýhiệucôngthứcbởicácchữF,G, H,R, Vídụ: F=((x∧ y)→ z) G=(x→(y→ z)) R=(x∧ y)∨z) Gv:TrịnhHuyHoàng Trang12
  3. GiáotrìnhLogicToán 4.2/Côngthctươngđương: HaicôngthứcFvàGgọilàtươngđươnglogicnếuchúngnhậncùnggiátrịchânlývới mọigiátrịcủacácbiếnmệnhđềsơcấp.Kýhiệu F=G Vídụ: F=((x ∧ y) →z) G=(x →(y →z)) (chứngminhnhưbàitập) thìF=G ¬¬p ⇔p(luậtphủđịnhcủaphủđịnh) Cácluậtvềphépphủđịnh: ¬1 ⇔0 ¬0 ⇔1 Luậtgiaohoán p ∧q ⇔q ∧p p ∨q ⇔q ∨p Luậtkếthợp p ∧(q ∧r) ⇔(p ∧q) ∧r p ∨(q ∨r) ⇔(p ∨q) ∨r p ∧(q ∨r) ⇔(p ∧q) ∨(p ∧r) Luậtphânbố p ∨(q ∧r) ⇔(p ∨q) ∧(p ∨r) ¬(p ∧q) ⇔¬p ∨¬q LuậtDeMorgan ¬(p ∨q) ⇔¬p ∧¬q p ∨¬p ⇔1 Luậtvềphầntửbù p ∧¬p ⇔0 Luậtkéotheo p →q ⇔¬p ∨q Luậttươngđương p ↔q ⇔(p →q) ∧(q →p) Cácluậtđơngiảncủaphéptuyển Gv:TrịnhHuyHoàng Trang13
  4. GiáotrìnhLogicToán p ∨p ⇔p(tínhlũyđẳngcủaphéptuyển) p ∨1 ⇔1(luậtnàycònđượcgọilàluậtthốngtrị) p ∨0 ⇔p(luậtnàycònđượcgọilàluậttrunghòa) p ∨(p ∧q) ⇔p(luậtnàycònđượcgọilàluậthấpthụ) Cácluậtđơngiảncủaphéphội p ∧p ⇔p(tínhlũyđẳngcủaphéphội) p ∧1 ⇔p(luậtnàycònđượcgọilàluậttrunghòa) p ∧0 ⇔0(luậtnàycònđượcgọilàluậtthốngtrị) p ∧(p ∨q) ⇔p(luậtnàycònđượcgọilàluậthấpthụ) Mộtsốluậttrongcácluậttrìnhbàyởtrêncóthểđượcsuyratừcácluậtkhác.Cáccông thứctươngđươnglogickhác: x ⊕y=(¬x∧y)∨(x ∧¬y) x ⊕y=y⊕x (x ⊕y) ⊕z=x ⊕(y⊕z) x(y ⊕z)=xy⊕xz ¬x⊕1=x x ⊕1= ¬x x ⊕x=0 4.3/Cácquitcthayth: Dướiđâylàcácquitắcđểchotacóthểsuyranhữngbiểuthứclogicmớihaytìmra cácbiểuthứclogictươngđươngvớimộtbiểuthứclogicchotrước. Quitắc1: Gv:TrịnhHuyHoàng Trang14
  5. GiáotrìnhLogicToán TrongmộtbiểuthứclogicE,nếutathaythếmộtbiểuthứcconbởimộtbiểuthứclogic tươngđươngvớibiểuthứcconđóthìtasẽđượcmộtbiểuthứcmớiE'tươngđươngvớibiểu thứcE. Vídụ: ChobiểuthứclogicE=q ∨¬ p.ThaythếqtrongbiểuthứcEbởibiểuthức ¬¬ q (tươngđươngvớiq)tađượcmộtbiểuthứcmớiE'=¬¬ q ∨¬ p.Theoquitắcthaythế1ta có: q ∨¬ p ⇔¬¬ q ∨¬ p Quitắc2: GiảsửbiểuthứclogicElàmộthằngđúng.N ếutathaythếmộtbiếnmệnhđềpbởi mộtbiểuthứclogictuỳýthìtasẽđượcmộtbiểuthứclogicmớiE'cũnglàmộthằngđúng. Vídụ: TacóbiểuthứcE(p,q)=(p →q) ⇔( ¬ p ∨q)làmộthằngđúng.Thaythếbiếnq trongbiểuthứcEbởibiểuthứcq ∧rtađượcbiểuthứclogicmới: E'(p,q,r)=(p →(q ∧r)) ⇔( ¬ p ∨(q ∧r)) Theoquitắcthaythế2tacóbiểuthứcE'(p,q,r)cũnglàmộthằngđúng. Vídụápdụng:  Vídụ1: Chứngminhrằng (p →q) ⇔( ¬q →¬p). Chứngminh: (p →q)⇔¬p ∨q(luậtkéotheo) ⇔q ∨¬p(luậtgiaohoán) ⇔¬q ∨¬p(luậtphủđịnh) ⇔¬q →¬p(luậtkéotheo)  Vídụ2: Chứngminhrằngbiểuthứcsaulàmộthằngđúng. ((p →q) ∧p) →q Chứngminh. Gv:TrịnhHuyHoàng Trang15
  6. GiáotrìnhLogicToán ((p →q) ∧p) →q ⇔((p →q) ∧p) ∨q(luậtkéotheo) ⇔( ¬(p →q) ∨¬p) ∨q(luậtDeMorgan) ⇔¬(p →q) ∨( ¬p ∨q)(luậtkếthợp) ⇔¬(p →q) ∨(p →q)(luậtkéotheo) ⇔1(luậtvềphầntửbù) Vậybiểuthức((p →q) ∧p) →qlàhằngđúng.  Vídụ3: Chứngminhrằngbiểuthứcsaulàmộthằngđúng. p ∧q →p Chứngminh. p ∧q →p ⇔¬(p ∧q) ∨p(luậtkéotheo) ⇔( ¬p ∨¬q) ∨p(luậtDeMorgan) ⇔( ¬q ∨¬p) ∨p(luậtgiaohoán) ⇔¬q ∨( ¬p ∨p)(luậtkếthợp) ⇔¬q ∨1(luậtvềphầntửbù) ⇔1(luậtđơngiản) Vậymệnhđềp ∧q →plàhằngđúng.  Vídụ4: Chứngminhrằngbiểuthứcsaulàmộthằngđúng. p →p ∨ q Chứngminh. p →p ∨ q ⇔¬p ∨(p ∨q)(luậtkéotheo) ⇔( ¬p ∨p) ∨q(luậtkếthợp) ⇔1 ∨q(luậtvềphầntửbù) Gv:TrịnhHuyHoàng Trang16
  7. GiáotrìnhLogicToán ⇔1(luậtđơngiản) Vậymệnhđềp →p ∨ qlàhằngđúng. hậnxét: Cácvídụtrênchotathấymộtquanhệkhácgiữacácmệnhđềphứchợphaycác mệnhđề:quanhệ" suyra ".Khimệnhđềp →qlàhằngđúng,tanóirằngpsuyraq(vềmặt logic).Chúngtasẽdùngkýhiệu ⇒đểchỉquanhệ"suyra".Quanhệsuyranầycótínhtruyền (haybắccầu),nhưngkhôngcótínhchấtđốixứng. 5.Hệquảlogicvàtươngđươnglogic: N ếucôngthứcx →y=1thìmệnhđềyđượcgọilàhệquảlogiccủax. N ếuxlàhệquảlogiccủayvàyvàhệquảlogiccủaxthìxvàylàtươngđươnglogic. Vídụ:Nếu F1 =( x → y )( ∧ yz → ) G1 =( x → z ) F2 =( xz → )( ∧ yz → ) G2 =( xy ∨ ) → z KhiđóG1làhệquảlogiccủaF 1,G 2vàF 2làtươngđươnglogic 6.Côngthứcđốingẫu Cácphéptoánlogichộivàtuyểnđượcgọilàhaiphéptoánđốingẫucủanhau. HaicôngthứcFvàGđượcgọilàđốingẫucủanhaunếucôngthứcnàysuyratừcông thứckiabằngcáchthaymọiphéptoántuyểnvàhộibằngcácphéptoánđốingẫucủanó. KýhiệucôngthứcđốingẫucủacôngthứcFlàF * * Vídụ:N ếu F=( xx1 ∨ 2 ) ∧ x 3 thì F=( xx1 ∧ 2 ) ∨ x 3 7.Tínhđầyđủcủamộthệcácphéptoán Mộthệthống ∑ baogồmcácphéptoánlogicđượcgọilàmộthệđầyđủnếumọicông thứclogicđềucóthểbiểudiễnchỉgồmcácbiếnmệnhđềvớichỉcácphéptoánlogictrong hệ. Cáchệsaulàthểhiệntínhđầyđủcủacácphéptoán: ={ ∧ , ∨ , ¬ } , ={ ∧ , ¬ } , ={ ∨ , ¬ } , ={, ∧ ⊕ , ¬ } ∑0 ∑1 ∑2 ∑3 Gv:TrịnhHuyHoàng Trang17
  8. GiáotrìnhLogicToán 7.Ứngdụnglogicmệnhđềđểvẽmạchđiệntử Tacócáccổngcơbảnsauđểthiếtkếmạch: Cổnginverterthểhiệnphéptoánphủđịnh1biếnngõnhập CổngAN Dthểhiệnphéptoánhộigiữacácbiếnngõnhập. CngORthhinphéptoántuyngiacácbinngõnhp CổngXORthểhiệnchophéptoántuyểnchọn. F= xyz + xyz + xyz x xy y xyz z xyz+ x y z z x y z F x x y y x y z F=xyzt’+x’zt’+x’yz’t+xz’ Gv:TrịnhHuyHoàng Trang18
  9. GiáotrìnhLogicToán x y z t ⊕ ⊕ F=x’zt+xy’z’t+x’y’t+zt Gv:TrịnhHuyHoàng Trang19
  10. GiáotrìnhLogicToán ⊕ ⊕ x xt t xty’z⊕ z y’z y’ y F xy’ xy’z’ z‘ yz’ xy’z’yz’t’⊕ t‘ yz’t’ BÀITẬP 1. Chobiếtnhữngkhẳngđịnhnàodướiđâylàmệnhđề: a. 2làmộtsốnguyêndương. b. 2k–1làmộtchẵn. c. Trờilạnhquá! Gv:TrịnhHuyHoàng Trang20
  11. GiáotrìnhLogicToán d. N ếubiếttrướclàkhókhănsaoanhcòncốgắng? 2. Hãyviếtcácmệnhđềđãchodướiđâydướidạnghìnhthứccósửdụngphépnối: A:“Bìnhbiếtchạyxeđạp” B:“Bìnhkhôngbiếtchạyxemáy” a. Bìnhkhôngchạyđượcxemáynhưngchạyđượcxeđạp. b. Bìnhkhôngbiếtchạyxeđạplẫnxegắnmáy. c. N ếuBìnhbiếtchạyxemáythìbiếtchạyxeđạp. d. BìnhbiếtchạyxemáyvàxeđạphayBìnhchạyđượcxemáymàkhông chạyđượcxeđạp. 3. Chobiếtchântrịcácmệnhđềsau: 2 a. x ≤ 1và x +1 > 2 2 b. x−210 x +≤ → x = 1 2 c. x−210 x +≤ ↔ x = 0 2 d. x−430 x +≤→ x = 2 4. Lậpbảngchântrịvàchỉracácmệnhđềluônđúng: a. m→( n → p ) b. [(mn→∨→ )( nm )]( → mn ∧ ) c. [m→ ( np → )]( → np → ) d. [m→∨ ( np )][( → mpnp →∨→ )( )] 5. Ápdụngcácluậtlogicđểrútgọncácmệnhđềvàchỉrađâulàcôngthứchằng: a. (mn∨ ) ∨ [( mn ∧ ) ∨ n ] b. (m→ n ) ∧ [ n ∧ ( pn ∨ )] c. m∧( np ∨ )( ∧ mnp ∨∨ ) d. [[(mnp∧∧∨ ) ] [( mpp ∧∧ ) ]] ∨ n 6. Hãy F,F *, F* , F* (m ,, n p ,) q củacáccôngthứcsau: a. Fmn(,)(= mn ∨∨ )[( mn ∧∨ ) n ] Gv:TrịnhHuyHoàng Trang21
  12. GiáotrìnhLogicToán b. Fmnp(,,)= mn ∧ [ n ∧ ( p ∨ n )] c. Fmnp(,,)(= pn ∨∨ )[( mp ∧ ) ∨ n ] d. Fmnpq(,,,)= mq ∧∨ ( n p )( ∧ m ∨∨ n p ) 7. Hãybiểudiễncáccôngthứcsaudướitấtcáchệđầyđủcácphéptoán: a. Gn=∨( m ∧ ( mnp ∨∨ )) b. F= n ⊕( m ∨ p ) c. Gm= ↔( n ⊕ p ) d. G=( nm ⊕ )( ↔ mp ∨ ) 8. Mộtxạthủbắncungvàomộtmụctiêu,kếtquảđượcthểhiệntheocácmệnhđề sau: Pk ={Phátthứktrúngđích}k=1,2,3 Hãygiảithíchcácmệnhđềphứchợpsau: P∧ P ∧ P a. 1 2 3 b. P1∨ P 2 ∨ P 3 c. (PPP123∧∧ )( ∨ PPP1 ∧∧ 13 )( ∨ PPP 123 ∧∧ ) d. (PP12∧ )( ∨ PPP 123 ∧∧ )( ∨ PPP 123 ∧∧ ) 9. Cho4thísinhA,B,C,Dthamgiathiđấuxếphạng.Kếtquảxếphạngnhưthế nàonếu: N gườithứ1dựđoán:Bhạngnhì,Chạngba. N gườithứ2dựđoán:Ahạngnhì,Chạngtư. N gườithứ3dựđoán:Bhạngnhất,Dhạngnhì. Đượcbiếtlàmỗingườicóphầnđúngphầnsai. 10.Trongmộtchatroom,cótổngcông5ngườiAn,Bình,Chinh,Dung,Yếnđang thảoluậnvềđềtàilogictoánvớinhautrênmạng. Biếtrằng: HoặcAn,hoặcBìnhhoặclàcả2đangthảoluận. HoặcChinh,hoặcDung,nhưngkhôngphảicả2cùngthảoluận. Gv:TrịnhHuyHoàng Trang22
  13. GiáotrìnhLogicToán N ếuYếnđangthảoluậnthìChinhcũngvậy. DungvàAn,hoặccả2cùngthảoluận,hoặckhôngaithảoluận. N ếuBìnhđangthảoluậnthìYếnvàAncũngvậy. Hãygiảithíchxemnếutấtcảkhẳngđịnhtrênđềuđúngthìhiệntạiaiđangthảo luận? 11.Đểcóđủchứngcứbuộctộiđốivớithủphạmtrong1vụán,1cảnhsátđiềutrađi thuthậpbằngchứngtạimộttòabiệtthự.Anhtalầnlượthỏimộtsốngườisau rồicókhẳngđịnhsau: N ếungườiquảngianóithậtthìngườiđầubếpcũngvậy. N gườiđầubếpvàngườilàmvườnkhôngthểcùngnóithật. N gườilàmvườnvàngườihầukhôngthểcùngnóidối. N ếungườilàmvườnnóithậtthìngườiđầubếpnóidối. Hỏicóthểxácđịnhrõainóithậtainóidốikhông? 12.Mộtsinhviênlàmbàithigiữakỳmônlogictoángồm5câuhỏitrắcnghiệm đúng/saitrênmáytính,anhtakhôngbiếttrảlờichínhxácchobấtkỳcâuhỏinào nhưngbiếtrằng: Câu1vàcâu5cùngđòihỏitrảlờitráingượcnhau. Câu2vàcâu4cầntrảlờinhưnhau. Ítnhất1trong2câuhỏiđầucầntrảlờilàkhẳngđịnh. N ếucâu4trảlờilà“đúng”thìcâu5phảitrảlờilà“sai”. Kinhnghiệmchosinhviênnàythấyrằngmáyđặtcâuhỏi cần trả lời “đúng” nhiềuhơn“sai”. Hãyxácđịnhcácđápáncầnchọnlựa. 13.Saukhithugọn,hãytìmcácbộnghiệm(x,y,z,t)đểcáccôngthứchàmsauđạt giálà0: a. F=[( ytxz ∨→→ )( xt yz )][ → xyt →∨ ( yzxt )] b. F=[( xyzt ∨→∨ ) ( yzxt )] → [( xzyt ∨→ ) ( yz ∨ xt )] c. F=[( xyz ∨→→→ yt ) ( xt y z )] [( yt∨ xz) → xz y ] Gv:TrịnhHuyHoàng Trang23
  14. GiáotrìnhLogicToán BÀI3:LOGÍCTÍHTOÁ 1.Kháiniệm: 1.1/Dngtuynchun: Giảsửp 1,p 2, ,p nlàcácbiếnmệnhđề.MộtbiểuthứclogicFtheocácbiếnmệnhđề p1,p 2, ,p nđượcgọilàmộtbiểuthứchộicơbảnnếunócódạngsau: F=q 1∧∧∧q 2∧∧∧ ∧∧∧q n vớiq j=p jhoặcq j= ¬p j(j=1, ,n).  Vídụ: Biểuthứcx ∧¬y ∧zlàmộtbiểuthứchộicơbảntheo3biếnmệnhđềx,y,z. BiểuthứclogicE(p 1,p 2, ,p n)theocácbiếnmệnhđềp 1,p 2, ,p nđượcnóilàcó dạngtuyểnchuNnkhiEcódạng : E=E 1∨E 2∨ ∨E m TrongđómỗibiểuthứcconE iđềucódạngtuyểnchuNntheocácbiếnp 1,p 2, ,p n.  Vídụ:CácbiểuthứcsauđâycódạngtuyểnchuNn: E(x,y,z)=(x∧y ∧z) ∨( ¬x ∧y ∧z) ∨(x ∧y ∧z) F(p 1,p 2,p 3,p 4)=(p 1∧p 2∧p 3∧p 4) ∨(p 1∧¬p 2∧p 3∧¬ p4) Ðịnhlý: MọibiểuthứclogicE(p 1,p 2, ,p n)đềucóthểviếtdướidạngtuyểnchuNnduynhất, khôngkểsựsaikhácvềthứtựtrướcsaucủacácbiểuthứchộicơbảntrongphéptuyển).N ói mộtcáchkhác,tacóduynhấtmộttậphợpcácbiểuthứchộicơbản {E 1,E 2, ,E m}saocho biểuthứcE(p 1,p 2, ,p n)tươngđươnglogicvớibiểuthức (E1∨E 2∨ ∨E m.) 1.2/Dnghichun: Giảsửp 1,p 2, ,p nlàcácbiếnmệnhđề.MộtbiểuthứclogicFtheocácbiếnmệnhđề p1,p 2, ,p nđượcgọilàmộtbiểuthứctuyểncơbảnnếunócódạngsau: F=q 1∨ q2∨ ∨ qn vớiq j=p jho ặcq j= ¬ pj(j=1, ,n). Gv:TrịnhHuyHoàng Trang24
  15. GiáotrìnhLogicToán  Vídụ:Biểuthứcx ∨¬ y ∨ zlàmộtbiểuthứctuyểncơbảntheo3biếnmệnhđềx,y,z. BiểuthứclogicE(p 1,p 2, ,p n)theocácbiếnmệnhđềp 1,p 2, ,p nđượcnóilàcó dạnghộichuNnkhiEcódạng: E=E 1∧ E2∧ ∧ Em TrongđómỗibiểuthứcconE iđềucódạngtuyểnchuNntheocácbiếnp 1,p 2, ,p n.  Vídụ:CácbiểuthứcsauđâycódạnghộichuNn: E(x,y,z)=(x ∨¬ y ∨z) ∧ (¬ x ∨y ∨ z) ∧ (x ∨y ∨ z) F(p 1,p 2,p 3,p 4)=(p 1∨ p2∨p 3∨ p4) ∧(p 1∨¬ p2∨ p3∨¬ p 4) Ðịnhlý: MọibiểuthứclogicE(p 1,p 2, ,p n)đềucóthểviếtdướidạnghộichuNnduynhất, khôngkểsựsaikhácvềthứtựtrướcsaucủacácbiểuthứctuyểncơbảntrongphéphội).N ói mộtcáchkhác,tacóduynhấtmộttậphợpcácbiểuthứctuyểncơbản {E 1,E 2, ,E m}sao chobiểuthứcE(p 1,p 2, ,p n)tươngđươnglogicvớibiểuthức(E 1∧E2∧ ∧Em.) 2.Sốlogic: 2.1/Đnhnghĩa: ♦ SốlogiccủamộtbiếnnguyênthủyA,kíhiệu#Alàchântrịcủabiếnđóxéttrong khônggianlogicN chiềumàAthamgiabiểudiễn. ♦ Vídụ: Xéttrongkhônggianmộtbiếnthì#A=(1,0) Trongkhônggian2biến:AB. A B    1 1  1 0  Matrậnbiểudiễn: [A,B]   0 1    0 0  Xéttrongkhônggian3chiều:ABC Gv:TrịnhHuyHoàng Trang25
  16. GiáotrìnhLogicToán A B C    1 1 1  1 1 0    1 0 1  Matrậnbiểudiễn: [A,B,C] 1 0 0    0 1 1  0 1 0    0 0 1    0 0 0  ♦ Mỗikhônggianlogicđượcbiểudiễnbởimộtsốbiếnriêng.Sựtổhợpcácbiếnra mộtgiátrịcủacácbiếnnằmtrongkhônggianlogic. 2.2Hàmlogic: ♦ Hàmlogiclàmộtliênkếtgiữacácbiếnlogicbởicácphéptoánlogicnhư:hợp(+), giao(.),phủđịnh(),kéotheo( →),tươngđương( ↔), . ♦ N hậnxét:Mộthàmlogiccómộtsốlogictươngứng:f(A,B, ) ≅#f(A,B, ) Vídụ:trongkhônggian3biếnchof(A,B,C)= AB + BC ABCAB BC f(A,B,C) 000000 100000 010000 110101 001011 101011 011000 111101 Vậy#f(A,B,C)=#( AB + BC )=00011101 ♦ Hệquả:  Sốlogiccủamộtbiếnhợp(tổng)bằngtổngcácsốlogicthànhphần: #(A+B)=#A+#B hay#(A ∨B)=#A ∨#B Gv:TrịnhHuyHoàng Trang26
  17. GiáotrìnhLogicToán  Sốlogiccủamộttíchbằngtíchcácsốlogicthànhphần: #(A.B)=#A.#B hay#(A ∧B)=#A ∧#B  # A = # A  #(A ⇒ B)=#A ⇒ #B ♦ Vídụminhhọa:chứngminhphátbiểusau((A →B) ∧(B →C) ∧A)→C Cónhiềucáchđểchứngminhphátbiểutrên,chẳnghạn:  Cách1:dùngbảngchântrị A B C A→B B→C (A →B) ∧(B →C) ∧A ((A →B) ∧(B →C) ∧A)→C 0001 1 0 1 1000 1 0 1 0101 0 0 1 1101 0 0 1 0011 1 0 1 1010 1 0 1 0111 1 0 1 1111 1 1 1 N hậnxét:cáchnàykháphứctạpnếusốcácphépkếtnốilogiclớn  Cách2:dùngcácluậtlogiccủaVươnghạo(1962)đểchứngminh.Cáchnày khôngdễ.  Cách3:tínhsốlogiccủaphátbiểu,nếusốlogicbằngI(1111 1)thìphátbiểu trênlàđúng. Tacó#(((A →B) ∧(B →C) ∧A) →C) =(#(A →B) ∧#(B →C) ∧#A) →#C =((#A →#B) ∧(#B →#C) ∧#A) →#C =((01010101 →00110011) ∧(00110011 →00001111) ∧01010101) →00001111 =(10111011 ∧11001111 ∧01010101) →00001111 =11111111=I ⇒pháttriểntrênlàđúng. Gv:TrịnhHuyHoàng Trang27
  18. GiáotrìnhLogicToán 2.2Tươngđươnglogic:  Haicôngthứclogicf(A 1,A 2, ,A m)vàg(A 1,A 2, ,A n)đượcgọilàtươngđươngkhi vàchỉkhi#f=#gxéttrênkhônggianlớnnhấtchứafvàg.  Vídụ:chobiếtf(A,B)=A →Bvàg(A,B,C)= (C ∨ C)∧ (B → A)cótươngđương nhauhaykhông? • Tacó:#f=10111011.Ởđâyfcũngphảiđượcxéttrongkhônggian3biến vìnócầnphảisosánhvớigcó3biến • #g=10111011 Do#f=#g ⇒fvàglàtươngđươngnhau. 3.Thuậttoánbiểudiễnmộtcôngthứclogicdướidạngtuyểnchun: Sốlogiccủatíchcácbiến:GọiC ilàsốlogiccủamộttổhợpcácbiếnsaochoC ichỉnhậngiá trị1tạicộti,cáccộtcònlạinhậngiátrị0. Vídụ:trongkhônggian3biếnA,B,C;tacóbiểudiễnnhưsau: ABC 1 0 0 0 0 0 0 0 C1 ABC 0 1 0 0 0 0 0 0 C 2 ABC 0 0 1 0 0 0 0 0 C 3 ABC 0 0 0 1 0 0 0 0 C 4 ABC 0 0 0 0 1 0 0 0 C 5 ABC 0 0 0 0 0 1 0 0 C 6 ABC 0 0 0 0 0 0 1 0 C 7 ABC 0 0 0 0 0 0 0 1 C8 Thuậttoán: chocôngthứclogicf(A 1,A 2, ,A n). n Bước1:Tính#f.Giảsử#f=(i 1,i 2, ,i 2 ) k:=1 F:={} Bước2: Nếui k=1thìF:=F+C k. k:=k+1 Bước3:nếuk ≤2 nthìquaylạibước2,ngượclạidừng. Gv:TrịnhHuyHoàng Trang28