Bài giảng Toán rời rạc: Chương 1.1 - Nguyễn Viết Hưng, Trần Sơn Hải

Bài giảng Toán rời rạc: Chương 1.1 - Vị từ và lượng từ cung cấp cho các bạn những kiến thức về định nghĩa vị từ và lượng từ; định lý trong vị từ và lượng từ. Bài giảng phục vụ cho các bạn chuyên ngành Toán học và những ngành có liên quan.
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.1 - Nguyễn Viết Hưng, Trần Sơn Hải Vịtừvàlượngtừ• Địnhnghĩa: Cho A là một tập hợp khác rỗng. Giả sử,ứngvớimỗix=a Atacómộtmệnh đềp(a).Khiđó,tanóip=p(x)làmộtvịtừ theomộtbiến(xácđịnhtrênA) Vịtừvàlượngtừ• Địnhnghĩa: Tổng quát, cho A1, A2, A3…là n tập hợpkháctrống.Giảsửrằng ứngvớimỗi (x1,x2,.,xn) = (a1,a2,.,an) A1 A2 ... An, ta có một mệnh đề p(a1,a2,.,an). Khi đó ta nói p = p(x1,x2,.,xn) là một vị từ theo n biến(xácđịnhtrênA1 A2 ... An) Vịtừvàlượngtừ• Vídụ1: Xét p(n) = “n > 2” là một vị từ một biến xác địnhtrêntậpcácsốtựnhiênN. Tathấyvớin=3;4tađượccácmệnhđềđúng p(3),p(4),cònvớin=0,1tađượcmệnhđềsai p(0),p(1) Vịtừvàlượngtừ• Vídụ2 Xétp(x,y)=“x2+y=1”làmộtvịtừtheohaibiến xác định trên R2, ta thấy p(0,1) là một mệnh đề đúng,trongkhip(1,1)làmộtmệnhđềsai. Vịtừvàlượngtừ• Định nghĩa: Cho trước các vị từ p(x), q(x) theo mộtbiếnx A.Khiấy, – Phủđịnhcủamệnhđềpkíhiệulà plàvịtừmàkhi thayxbởi1phầntửcốđịnhcủaAthìtađượcmệnh đề (p(a)) – Phépnốiliền(tươngứngnốirồi,kéotheo…)củapvà qđượckýhiệubởip q(tương ứnglàp q,p q)làvị từ theo biến x mà khi thay x bới phần tử cố định a củaAtađượcmệnhđềp(a) q(a)(tương ứnglàp(a) q(a),p(a) q(a)) Vịtừvàlượngtừ• Địnhnghĩa: Chop(x)làmộtvịtừtheomộtbiếnxácđịnhtrênA.Ta địnhnghĩacácmệnhđềlượngtừhóacủap(x)nhưsau: – Mệnhđề“VớimọixthuộcA,p(x)”,kíhiệubởi“ x A,p(x)”, là mệnh đề được định bởi “ x A, p(x)” đúng khi và chỉ khi p(a)luônđúngvớimọigiátrịa A – Mệnh đề “Tồn tại(ít nhất )(hay có (ít nhất) một x thuộc A, p(x))”kíhiệubởi:“ x A,p(x)”,làmệnhđềđượcđịnhbởi “ x A,p(x)”đúngkhivàchỉkhicóítnhấtmộtgiátrịx=a0 nàođósaochomệnhđềp(a0)đúng.• Chú ý: Các mệnh đề lượng từ hóa ở trên đều là các mệnhđềcóchântrịxácđịnhchứkhôngcònlàcácvịtừ theobiếnxnữa. Vịtừvàlượngtừ1)Mệnh đề“ x R,x2 +3x+1 0”làmộtmệnh đềsai hayđúng?Mệnhđềsaivìtồntạix0=1 Rmàx02+3x0+1 02)Mệnhđề“ x R,x2+3x+1 0”làmộtmệnhđềđúnghaysai? Mệnhđềđúngvìtồntạix0=–1 Rmàx02+3x0+1 0. VịtừvàlượngtừMệnhđề“ x R,x2+1 2x”làmộtmệnhđềđúnghaysai?Mệnhđềđúngvìvới x R,,taluônluôncóx22x+1 0Mệnhđề“ x R,x2+1 Vịtừvàlượngtừ• Địnhnghĩa:Cho p(x, y) laø moät vò töø theo hai bieán x, y xaùc ñònh treân A B. Ta ñònh nghóa caùc meänh ñeà löôïng töø hoùa cuûa p(x, y) nhö sau: “ x A, y B, p(x, y)” =“ x A, ( y B, p(x, y))” “ x A, y B, p(x, y)” =“ x A, ( y B, p(x, y))” “ x A, y B, p(x, y)” =“ x A, ( y B, p(x, y))” “ x A, y B, p(x, y)” =“ x A, ( y B, p(x, y))” VịtừvàlượngtừXétvịtừp(x,y)=“x+2y VịtừvàlượngtừMệnhđề“ x R, y R,x+2y VịtừvàlượngtừChop(x,y)làmộtvịtừtheohaibiếnx,yxác định trênA B.Khiđó:1)“ x A, y B,p(x,y)” “ y B, x A,p(x,y)”2)“ x A, y B,p(x,y)” “ y B, x A,p(x,y)”3)“ x A, y B,p(x,y)” “ y B, x A,p(x,y)”Chiềuđảocủa3)nóichungkhôngđúng. Vịtừvàlượngtừ• Chứngminh3)Giảsử“ x A, y B, p(x, y)” làđúng.Khiđó,tồntạia A sao cho “ y B, p(x, y)”làđúng,nghĩalànếuthayy=b Bbấtkỳthìp(a,b)đúng.Nhưvậy,y=b B tuỳchọnthìtacóthểchọnx=ađể“ x A, p(x, y)” làđúng.Dođó,“ y B, x A, p(x, y)” làmệnhđềđúng.Vídụthểhiệnchiềuđảocủa3làchưachắcđúng:• Gọip(x,y)làvịtừtheo2biếnthực p(x,y)=“x+y=1”,• Nếuthayytuỳýthìx=1yđểchox+y=1 nênmệnhđề x A, p(x, y) làđúng. Nênmệnhđề“ y B, x A, p(x, y)” làđúng.• Ngượclại,nếuchọnx=atuỳý,tacóthểchọn y=ađể“ y B, p(x, y)” làsai. Điều này chứng tỏ, “ x A, y B, p(x, y)” là sai.• Dođó,phépkéotheosaulàsai: “ y B, x A, p(x, y)” ->“ x A, y B, p(x, y)” Vịtừvàlượngtừ• Trongmộtmệnhđềlượngtừhoátừmột vị từ theo nhiều biến độc lập, nếu ta hoánvịhailượngtừđứngcạnhnhauthì: 1. Mệnh đề mới vẫn còn tương đương logic vớimệnhđềcũnếuhailượngtừnàycùng loại. 2. Mệnh đề mới này sẽ là một hệ quả logic củamệnhđềcũnếuhailượngtừtrướckhi hoánvịcódạng VịtừvàlượngtừĐịnhlý:a) Vôùi p(x) laø moät vò töø theo moät bieán xaùc ñònh treân A, ta coù: A, p ( x ) ∀x �� ∃x �A, p ( x ) ...