TOÁN RỜI RẠC (DiscreteMathematics)

Vị từ là một khẳng định có dạng p(x,y,z,…) trong đó x, y, z,… là các biến lấy giá trị trong các tập hợp A, B, C,… cho trước sao cho: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ỳ ý a A, bB, c C,… ta được mệnh đề p(a,b,c,…).x, y, z,… gọi là các biến tự do
Nội dung trích xuất từ tài liệu:
TOÁN RỜI RẠC (DiscreteMathematics)TOÁN RỜI RẠC(DiscreteMathematics) GV:CAOTHANHTÌNH. Chương 1CƠSỞLOGIC Logicvịtừ • LêĐứcSang • VõVănTịnh4.Logicvịtừ4.1Vịtừ: Địnhnghĩa4.1: Vịtừlàmộtkhẳngđịnhcódạngp(x,y,z,…)trongđóx, y,z,…làcácbiếnlấygiátrịtrongcáctậphợpA,B,C, …chotrướcsaocho:  p(x,y,z,…)khôngphảilàmệnhđề  Nếuthayx,y,z,…bởicácphầntửcốđịnhnhưngtuỳý a ∈A,b∈B,c∈C,…tađượcmệnhđềp(a,b,c,…). x,y,z,…gọilàcácbiếntựdo 4.Logicvịtừ(tt) Chon ∈N,p(n)=“nchiahếtcho3.” p(n):Khôngphảilàmệnhđề.Nhưng: p(10):làmệnhđềcóchântrị0 p(15):làmệnhđềcóchântrị1 p(n)làmộtvịtừtheobiếnn∈N.Vídụ4.2: p(x,y)=“x2+y2>5”làmộtvịtừtheo2biếnx,y∈R. p(n)=“nlàsốnguyêntố”làvịtừtheobiếnn,n∈N 4.Logicvịtừ(tt) Địnhnghĩa4.2:Chop(x),q(x)làcácvịtừtheomộtbiếnx∈A. i)Phépphủđịnh:Phủđịnhp(x),kíhiệu¬p(x)làmộtvịtừsaocho với x=a∈Acốđịnhnhưngtùyýthì¬p(a)làphủđịnhcủap(a). ii)Phépnốiliền(tươngứngnốirời,kéotheo,kéotheo2chiều)củap(x) vàq(x),kíhiệup(x)∧q(x)(tươngứngp(x)∨q(x),p(x)→q(x),p(x)↔q(x))là vịtừtheobiếnxmàkhithayxbởia∈Acốđịnhnhưngtùyýthìđược mệnhđềp(a)∧q(a)(tươngứngp(a)∨q(a),p(a)→q(a),p(a)↔q(a)) 4.Logicvịtừ(tt)4.2Lượngtừ:Chovịtừp(x),x∈A.Có3trườnghợpxảyra:o Vớimọia∈A,mệnhđềp(a)đúng.Kíhiệu“ ∀a∈A,p(a)”o Vớimộtsốgiátrịa∈A(khôngcầnphảitấtcả),mệnhđềp(a) đúng.Kíhiệu:”∃ a∈A,p(a)”o Vớimọia∈A,mệnhđềp(a)sai.KÍhiệu: “ ∀a∈A,¬p(a)”Địnhnghĩa:Cácmệnhđề“ ∀x∈A,p(x)”Và:”∃ x∈A,p(x)”gọilàlượngtừhóacủap(x)bởilượngtừphổdụng ∀vàlượngtừtồntại∃ .4.Logicvịtừ(tt) Tómtắtýnghĩacủacáclượngtừ: Mệnh Đúng khi: Sai khi: đề ∀x, p(x) p(x) đúng với mọi x Có một giá trị x, p(x) sai ∃ x, p(x) Có một giá trị x, p(x) đúng p(x) sai với mọi x Địnhlý: Phủđịnhcủamệnhđềlượngtừhóacủavịtừp(x,y,z,…)bởicáclượng từlàmộtmệnhđềcóđượcbằngcáchthaylượngtừ∀bằnglượngtừ ∃ và thaylượngtừ∃ bằnglượngtừ∀vàthayvịtừp(x,y,z,…)bằngvịtừ¬p(x,y,z,…) Vídụ:¬(∀x∃ y,p(x,y))⇔∃ x∀y,¬p(x,y) Mệnh đề Mệnh đề tương đương Đúng khi: ¬∀x, p(x) ∃ x, ¬p(x) Có một giá trị x, p(x) sai ¬∃ x, p(x) ∀x, ¬p(x) p(x) sai với mọi x4.Logicvịtừ(tt)BảngtómtắtýnghĩacáclượngtừhaibiếnMệnh đề Đúng khi: Sai khi:∀x ∀y, p(x,y) P(x,y) đúng với mọi cặp Có một cặp x, y mà p(x,y) sai x,y∀x ∀y, p(x,y)∀x ∃ y, p(x,y) Với mọi x có một y để Có một x để p(x,y) sai với p(x,y) đúng mọi y∃ x ∀y, p(x,y) Có một x để p(x,y) đúng Với mọi x có một y để p(x,y) với mọi y sai∃ x ∃ y, p(x,y) Có một cặp x, y để p(x,y) P(x,y) sai với mọi cặp x,y đúng∃ y ∃ x, p(x,y) 4.Logicvịtừ(tt)Vídụ4.3:Tìmchântrịcủacácmệnhđề: a)∀x∈(0,1),x3+4x21=0 b)∃ x∈(0,1),x3+4x21=0Vídụ4.4:Vớix∈R,xétcácvịtừ: p(x):x ≥ 0 q(x):x2 ≥ 0 r(x):x2–4x–5=0 s(x):x2–3≥ 0Xétxemcácmệnhđềsaulàđúnghaysai? α) ∃ x, p(x)∧r(x) e)∀x,r(x)→p(x) β) ∀x,p(x)→r(x) f)∃ x,r(x)→q(x) χ) ∀x,p(x)→q(x) δ) ∀x,q(x)→s(x)4.Logicvịtừ(tt) Địnhlý: Chop(x,y)làvịtừtheo2biếnx,y.Cácmệnhđềsaulàhằng đúng: i)[∀x∈A,∀y∈B,p(x,y)] ↔[∀y∈B,∀x∈A,p(x,y)] ii)[∃ x∈A,∃ y∈B,p(x,y)] ↔[∃ y∈B,∃ x∈A,p(x,y)] iii)[∃ x∈A,∀y∈B,p(x,y)] →[∀y∈B,∃ x∈A,p(x,y)] Quytắcđặcbiệthóaphổdụng: ∀x∈A,p(x)đúngthìp(a)đúngvớia∈A,acốđịnhnhưngbất kỳ. Quytắctổngquáthóaphổdụng: Nếup(a)đúngvớia∈Abấtkỳthìmệnhđề:∀x∈A,p(x)đúng.4.Logicvịtừ(tt)  Mệnhđề: Trongmệnhđềlượngtừhóacủavịtừp(x,y,z,…). Nếutahoánvị2lượngtừliềnkềthìtađược:  Mệnhđềmớitươngđươngvớimệnhđềcũnếu2 lượngtừđượchoánvịcócùngloại.  Mệnhđềmớilàhệquảlogiccủavớimệnhđềcũ nếu2lượngtừđượchoánvịcódạng∃ ∀. 4.Logicvịtừ(tt)Vídụ4.5:ChoA={xlàsinhviên} p(x):“xlàsinhviênkhoacntt” q(x):“xphảihọctoánrờirạc”.Coilýluận: MọisinhviênkhoaCNTTđềuphảihọctoánrờirạc MàCườnglàsinhviênkhoaCNTT,nênCườngphảihọctoánrờirạcViếtdạnglogicvịtừ: Gọia:≡ “Cườnglàmộtsinhviên”(a∈A) Do ∀x∈A,p(x)→q(x) (tiênđề) ...