Bài giảng môn học Toán học rời rạc

Chia sẻ: Photocopy Xứ Lạng | Ngày: | Loại File: PDF | Số trang:93

Thêm vào BST

Báo xấu

116
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng môn học Toán học rời rạc cung cấp cho các bạn những kiến thức chính về: Tập hợp và logic mệnh đề, giải thuật và các phương pháp đếm, lý thuyết đồ thị và cây. Để hiểu rõ hơn về bài giảng mời các bạn cùng tham khảo tài liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng môn học Toán học rời rạc

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH -------------o0o------------ BÀI GIẢNG MÔN HỌC TOÁN HỌC RỜI RẠC HỆ ĐẠI HỌC Số tín chỉ: 3TC Hệ đào tạo: ĐHCQ Ngành: CNTT, HTTTQL, TMĐT. Bộ môn giảng dạy: Bộ môn KHMT – Khoa CNTT. Thái Nguyên, năm 2015 0
MỤC LỤC Mục Trang Chương 1: TẬP HỢP VÀ LOGIC MỆNH ĐỀ……………………………… 2 1.1 Tập hợp và các phép toán trên tập hợp………………………………….. 2 1.2. Quan hệ…………………………………..……………………………... 5 1.3. Logic mệnh đề………………………………….. …………………….. 8 1.4. Suy luận toán học và các phương pháp chứng minh…………………… 16 Chương 2: GIẢI THUẬT VÀ CÁC PHƯƠNG PHÁP ĐẾM………………. 22 2.1. Thuật toán và các đặc trưng cơ bản của thuật toán……………………… 22 2.2. Thuật toán đệ quy…………………………………..……………………. 28 2.3. Thuật toán quay lui………………………………….. …………………. 33 2.4. Các nguyên lý đếm cơ bản………………………………….. ………… 37 2.5. Hoán vị và tổ hợp…………………………………..…………………… 40 Chương 3: LÝ THUYẾT ĐỒ THỊ VÀ CÂY………………………………… 50 3.1. Đồ thị và các khái niệm cơ bản trong đồ thị ……………………………. 50 3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị………………….. 54 3.3. Các phương pháp duyệt đồ thị…………………………………………... 57 3.4. Một số đơn đồ thị đặc biệt………………………………….. …………. 59 3.5. Đồ thị Euler…………………………………..…………………………. 63 3.6. Đồ thị Hamilton………………………………………………………… 68 3.7. Thuật toán tìm đường đi ngắn nhất. ………………………………….. 73 3.8. Cây và cây khung của đồ thị……………………………………………. 80 TÀI LIỆU THAM KHẢO…………………………………………………… 90 1
CHƯƠNG 1 TẬP HỢP & LOGIC MỆNH ĐỀ 1.1.Tập hợp 1.1.1 Khái niệm chung về tập hợp Tập hợp là một trong những khái niệm quan trọng nhất của toán học, nó là gốc rễ của các ngành toán học khác nhau. Vào nửa đầu thế kỷ 19, nhà toán học người Đức Geory Cautar (1845 – 1918) đã nghiên cứu các tập hợp và ứng dụng của chúng như là nền tảng của các ngành toán học (các công trình được công bố vào những năm từ 1871 – 1883) . Lý thuyết tập hợp sau khi xuất hiện đã thống nhất được nhiều quan niệm toán học và đã xây dựng nên các cơ sở logic của nhiều ngành toán học khác nhau. Tập hợp được coi là 1 cấu trúc rời rạc bao gồm nhiều đối tượng được nhóm lại với nhau, thông thường các đối tượng trong một tập hợp có một vài tính chất tương tự nhau. Các đối tượng trong tập hợp được gọi là các phần tử của tập hợp đó. Trật tự của các các phần tử trong tập hợp là không quan trọng, quan trọng là phần tử đó có mặt trong tập hợp hay không. Ví dụ: Tập hợp các số tự nhiên N. Tập N+ các số tự nhiên khác 0 Tập các số nguyên Z Tập các số hữu tỷ Q Tập các số thực R Ký hiệu: Phần tử tập hợp dùng chữ in thường. Tập hợp dùng chữ in hoa. Để ký hiệu x là phần tử của tập A, ta viết: xA (x thuộc A hay x là phần tử của A). Nếu x không là phần tử của tập A thì ta viết: xA (x không thuộc A). 1.1.2.Một số tập hợp đặc biệt a.Tập con Cho 2 tập hợp A và B. Nếu mọi phần tử của A đều là phần tử của B thì ta viết: AB hoặc BA và gọi là A là tập con của B (A được chứa trong B; A được bao hàm trong B; A là bộ phận của B; B bao hàm A…). Ví dụ: N*NZQR Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B Nếu AB và AB thì ta nói A là tập con thực sự của B, ký hiệu A  B. Nếu A không là tập con thực sự của B thì ta viết AB b.Tập hợp rỗng:Tập hợp không chứa phần tử nào gọi là tập rỗng. Tập rỗng được ký hiệu là .Với mọi tập A ta có A.Tập rỗng là duy nhất. c.Tập hợp các tập con của một tập hợp: Cho X là một tập hợp. Tập hợp các tập con của tập X ký hiệu là P(X) hay 2X. P(X) = {A | AX} Ví dụ: X =  thì P(X) = {} X = {a, b} thì P(X) = {, {a}, {b}, {a,b}} d. Tập hợp bù: Với mỗi AX đặt AC = X\A hay X  X \ A gọi là phần bù của A trong X. Ta có: AAC = X hay A  A  X ; AAC =  hay A  A   2
Theo tính chất ta có: (AB)C = ACBC (AB)C = ACBC 1.1.3 Cách xác định tập hợp a. Liệt kê các phần tử của tập hợp trong cặp ngoặc {…} Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó: A = {a, e, o, i, u}: tập tất cả các nguyên âm (của bảng chữ cái Aab) A = {1, 2, 3, 5, 7} Khi không liệt kê hết ta dùng dấu … A = {0, 1, 2, …, 99}: Tập tất cả các số tự nhiên từ 0 đến 99. B = {0, 2, 4, 6, …}: Tập tất cả các số tự nhiên chẵn. b. Chỉ ra thuộc tính đặc trưng của các phần tử trong tập hợp bằng một mệnh đề (x) nào đó. Nếu A là tập gồm các phần tử x của tập X có tính chất P(x) thì ta viết: A = {xX | P(x)} Ví dụ : A = {xR | x2 – 4x + 3 = 0} B = {nN | n là ước của 20} C = {nN* | xn + yn = zn có nghiệm nguyên dương} c. Dùng giản đồ Venn Qui ước:  Tập hợp vũ trụ U: tập chứa tất cả các phần tử đang xét, được biểu diễn bằng một hình chữ nhật.  Bên trong hình chữ nhật, dùng hình tròn, hình elip để biểu diễn cho các tập hợp.  Các điểm được dùng để biểu diễn cho các phần tử của tập hợp. Ví dụ : U = N A = {2, 4, 6, 8, 10} N A .2 .10 .8 .4 .6 1.1.4 Phép toán trên tập hợp a. Phép hợp: Cho hai tập hợp A, B. Ta gọi A hợp B là tập gồm các phần tử thuộc A hoặc thuộc B. Ký hiệu là AB, như vậy AB = {a | aA hoặc aB}. b. Phép giao: Cho hai tập hợp A, B. Ta gọi A giao B là tập gồm các phần tử vừa thuộc A vừa thuộc B. Ký hiệu là AB, như vậy AB = {a | aA và aB}. Nếu không có phần tử nào vừa thuộc A vừa thuộc B thì AB = . Trong trường hơp này ta nói A và B rời nhau hoặc không giao nhau. c. Phép hiệu: Cho hai tập hợp A, B. Ta gọi A trừ B (hay hiệu của A và B) là tập gồm các phần tử thuộc A nhưng không thuộc B. Ký hiệu là A\B. 3
A\B = {a | aA và aB}. Lưu ý: A\B khác B\A. d. Phép hiệu đối xứng: Cho hai tập hợp A, B. Ta gọi hiệu đối xứng của A và B là tập gồm các phần tử chỉ thuộc A hoặc chỉ thuộc B, không đồng thời thuộc cả A và B. Ký hiệu là AB. A  B = {(A\B) (B\A)}. Ví dụ 1: Cho A ={0, 1, 2, 4, 6} B = {1, 3, 5, 6} AB = {0, 1, 2, 3, 4, 5, 6} AB = {0,6} A\B = {1, 2, 4} B\A = {3, 5} AB = {1, 2, 4, 3, 5} Ví dụ 2: A = {xN | x chia hết cho 2}; B = {xN | x chia hết cho 3} AB = {xN | x chia hết cho 2 và chia hết cho 3} 1.1.4 Các tính chất trên tập hợp Với A, B, C là các tập hợp bất kỳ ta có: 1.Tính chất giao hoán: AB = BA và AB = BA 2.Tính chất kết hợp: (AB)C = A(BC) (AB)C = A(BC) 3.Tính chất phân phối: A(BC) = (AB)(AC) A(BC) = (AB)(AC) 4.Luật đối ngẫu Demorgan: A  B  A  B A B  A B 5.Luật nuốt: nếu AB thì AB = B, AB = A Chứng minh: Các tính chất 1, 2, 5 là hiển nhiên. Các tính chất còn lại được chứng minh tương tự nhau. Chứng minh tính chất 3: A(BC) = (AB)(AC) Thật vậy với aA(BC)  aA hoặc aBC  aA hoặc aB và aC  aA hoặc aB và aA hoặc aC  aAB và aAC  a (AB)(AC) Tức là có tính chất 3. Lưu ý: Vì A và AA với A nên: A = A, A = , AA = A, AA = A 1.1.5 Mở rộng các phép toán tập hợp a. Mở rộng tính chất 2 Với các tập A1, A2,…, An ta có:  A1A2 A3 = (A1A2)A3 n   Ai  A1  A2  ... An = ( A1  A2  ... An1 )  An i 1  A1A2 A3 = (A1A2)A3 n   Ai  A1  A2  ... An = ( A1  A2  ... An1 )  An i 1 b.Mở rộng tính chất 3 Cho các tập hợp X, A1, A2,…, An ta có: 2
 X    Ai     X  Ai  n n  i 1  i 1  X    Ai     X  Ai  n n  i 1  i 1 c.Mở rộng tính chất 4 Cho các tập hợp X, A1, A2,…, An ta có: n n   Ai   Ai i 1 i 1 n n   Ai   Ai i 1 i 1 1.1.7 Tích đề các a. Tích đề các của 2 tập hợp Cho A, B là 2 tập hợp. Với mỗi aA, bB. Ta gọi (a, b) là một cặp. Hai cặp (a, b) và (c, d) gọi là bằng nhau nếu a = c và b = d. Ta gọi tích đề các của A và B là tập AB gồm các cặp (a, b) với aA, bB AB = {(a,b) | aA, bB} Tích đề các AA ký hiệu là A2 (Bình phương đề các) Ví dụ: = {1, 2, 3}; B = {a, b} thì: AB = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)} BA = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)} AA = A2 = {(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)} BB = B2 = {(a,a); (a,b); (b,a); (b,b)} b.Tích đề các của n tập hợp Cho n tập hợp A1, A2,…, An. Khi đó tích đề các của n tập hợp này ký hiệu là A1 A2 … An =  Ai  a1 ,, a n  / a1  A1 ,, a n  An  n i 1 Hai bộ (a1, a2, …, an) và (b1,b2, …, bn) gọi là bằng nhau nếu: a1 = b1; a2 = b2 ; …; an = bn n Nếu A1 = A2 = … = An thì ký hiệu  Ai  A n và gọi là luỹ thừa đề các bậc n của tập hợp i 1 A. 1.1.8 Tập hợp hữu hạn a. Bản số của tập hữu hạn Tập A được gọi là hữu hạn nếu nó là tập  hoặc liệt kê được tất cả các phần tử của tập A, như vậy tập A là hữu hạn nếu:  A=  A = {a1, a2, …, an) với các ai là khác nhau ( i = 1,..,n). Trong trường hợp 1 ta nói A có bản số 0. Trong trường hợp 2 ta nói A có bản số n. Kí hiệu: A=0; hay N(A)=0; A=n; hay N(A)=n Nhận xét: Bản số của một tập hữu hạn chính là số phần tử của tập đó. Hai tập hữu hạn cùng bản số  có cùng số phần tử. b.Tính chất của bản số hữu hạn Định lý 1: Cho A, B là hai tập hữu hạn, khi đó: 1. |AB| = |A| + |B| – |AB| 2. |A\B| = |A| – |AB| 3
3. |AB| = |A| + |B| – 2|AB| Chứng minh: 1.Giả sử |A| = m; |B| = n. A = {a1, a2, …, am} và B = {b1, b2, …, bn} Xét trường hợp AB = : AB = {a1, a2, …, am, b1, b2, …, bn} do đó |AB| = m + n = |A| + |B| Trường hợp AB có k phần tử. Đặt AB = {a1, a2, …, ak}. Khi đó: A = {a1, a2, …, ak, ak+1, …, am}; B = {b1, b2, …, bk, bk+1,…, bn} Vì AB = {a1, a2, …, ak, ak+1, …, am, bk+1,…, bn} nên: |AB| = m + (n – k) = m + n – k = |A| + |B| – |AB| 1.Do A = (A\B)  (AB) mà (A\B)  (AB) =  nên theo (1) ta có: |A| = |A\B| + |AB|  |A\B| = |A| – |AB| 2.Vì (A\B)(B\A) =  nên áp dụng (1) và sau đó áp dụng (2) ta có: |AB| = |(A\B)(B\A)| = |A\B| + |B\A| = |A| – |AB| + |B| – |BA| = |A| + |B| – 2|AB| Lưu ý theo tính chất (2) nếu BA thì |A\B| = |A| – |B| Các tập hợp A1, A2,…, An gọi là đôi một rời nhau nếu 2 tập bất kỳ trong chúng đều rời nhau, tức là AiAj = . Với ij. Theo định lý 1, nếu A1A2 =  thì |A1A2|= |A1| + |A2| Áp dụng tính chất (1) (n-1) lần, ta có: Định lý 2: Cho A1, A2,…, An là các tập đôi một rời nhau. Khi đó, |A1A2… An| = |A1| + |A2| + …+ |An| Định lý 3: Với  tập hợp A, B ta có: |AB| = |A|.|B| Chứng minh: Giả sử A = {a1, a2, …, am}  |A| = m B = {b1, b2, …, bn}  |B| = n Với ai, ta có: m | {ai} B| = n vì AB = ({ai } B) và các tập {a1} B; {a2} B; …; {am} B i 1 đôi một rời nhau nên theo định lý 2 ta có: |AB| = |{a1} B| + |{a2} B| + … + |{am}B | = m  n = |A|.|B| Định lý 4: Cho A1, A2,…, An là các tập hợp bất kỳ. Khi đó |A1A2… An| = |A1|  |A2|  … |An| 1.2.Quan Hệ 1.2.1 Khái niệm về quan hệ Trong thực tế, ta thường gặp mối quan hệ giữa các phần tử của tập hợp này với các phần tử của tập hợp khác, hoặc ngay trong cùng một tập hợp. Nếu gọi A là tập các đối tượng (phần tử) mà ta đang xét thì mỗi nhóm gồm m phần tử có quan hệ với nhau là một phần tử của Am   A    A   A . Các nhóm gồm m phần tử m như vậy tạo thành một tập con của Am. Ta có các định nghĩa: a. Quan hệ 2 ngôi: Một quan hệ 2-ngôi từ tập A đến tập B là tập con của tích đề các A x B. Nếu R là một quan hệ 2-ngôi từ A đến B thì R  {(a,b) a  A, b  B } . Nếu (a, b)  R hay aRb thì ta nói a,b có R-quan hệ với nhau. Nếu (a, b)  R thì ta nói a,b không có R-quan hệ với nhau. Trong trường hợp A=B thì quan hệ R được gọi là quan hệ 2 ngôi trên chính tập A. Quan hệ 2-ngôi được gọi tắt là quan hệ. 4
b. Tương tự ta có khái niệm về quan hệ m-ngôi: Một quan hệ m-ngôi trên tập hợp A là tập con của tích đề các Am. Nếu R là một quan hệ m-ngôi trên A thì khi (a1, a2, …, am)  R ta nói a1, a2, …, am có R-quan hệ với nhau. Ví dụ: Cho A: Tập các nước; B: Tập các thủ đô R  A  B = {(a, b) | nếu a có thủ đô là b} Ta có: (Việt Nam, Hà nội)  R; (Lào, Viêng chăn)  R (Thái Lan, Băng cốc)  R; (Singapo, Hà nội)  R Ví dụ 2: A: Tập các cán bộ trong khoa CNTT R = {(a, b) | a, b  A và a, b có cùng tuổi}  A  A  R là một quan hệ trên A. 1.2.2 Tính chất của quan hệ Cho quan hệ R trên A. Nếu (x,y)R thì ta nói x có R quan hệ với y (x có quan hệ với y) viết là : xRy hay (x, y)  R. Nếu (x, y)  R thì hiểu là x không có quan hệ với y. Quan hệ R trên tập A có các tính chất sau: i.Tính chất phản xạ nếu với xA ta có xRx ii.Tính chất đối xứng nếu: vớix, yA: xRy thì yRx. iii.Tính chất phản đối xứng nếu : vớix, yA: xRy  yRx thì x=y. iv.Tính chất bắc cầu nếu: vớix, y, zA: xRy  yRx thì xRz. Ví dụ 1 : + Xét trong tập số tự nhiên N: Quan hệ xRy nếu x  y là quan hệ có tính chất phản xạ, phản đối xứng, bắc cầu. + Xét tập các tam giác, quan hệ R: đồng dạng, có tính chất phản xạ, đối xứng, bắc cầu. Ví dụ 2: Cho tập A={1, 2, 3, 4} Quan hệ R trên tập hợp A được định nghĩa a, bA :aRb  a+b =2k kZ, khi đó: 1. R có tính chất phản xạ: aA ta có a+a=2a  aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA và a+b=2k thì cũng có b+a=2k hay nếu có aRb thì cũng có bRa 3. R có tính chất bắc cầu : a, b,c A nếu a+b=2k, b+c=2k’ thì a+c=(2k-b)+(2k’-b)= 2k+2k’-2b=2k’’ hay (a,c)R 1.2.3 Quan hệ tương đương a.Định nghĩa Một quan hệ R trên tập A gọi là quan hệ tương đương nếu R có các tính chất phản xạ, đối xứng, và bắc cầu. Nếu R là quan hệ tương đương thì thay cho cách viết xRy ta viết xy (x tương đương y). Vậy  là một quan hệ tương đương trên A nếu với x, y, zA ta có:  xx (tính phản xạ)  xy  yx (tính đối xứng)  xy  yz  xz (tính bắc cầu) b. Ví dụ : Cho tập A={1, 2, 3, 4, 5, 6, 7} Quan hệ R trên tập hợp A được định nghĩa a, bA :aRb  a-b =3k kZ, khi đó R là quan hệ tương đương, thực vậy: 1. R có tính chất phản xạ: aA ta có a-a=0=3.0  aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA và a-b=3k b-a=3(-k)=3k’ bRa 5
3. R có tính chất bắc cầu : a, b,c A nếu a-b=3k, b-c=3k’ thì a-c= 3k+b+3k’-b=3(k+k’)=3k’’ hay (a,c)R c.Lớp tương đương Cho A là một tập và R là một quan hệ tương đương trên A. Với xA, tập xR  x  y  x | yRx gọi là lớp tương đương chứa x. Định lý 1: Các lớp tương đương là  , hoặc bằng nhau, hoặc rời nhau. Chứng minh: Xét lớp tương đương bất kỳ [x]:  Vì xRx nên x [x]  [x]  .  Để chứng minh phần còn lại ta giả sử 2 lớp x  và  y  có x    y  =  ta chỉ cần chứng minh x  =  y . Chọn z  x    y  vì z  x  nên xRz, vì z   y  nên zRy.  t  x   tRx  tRy  t   y  . Vậy x  =  y  . Từ định lý ta có:  y  x   x    y  và xRy  x    y   Các lớp tương đương chia A thành các tập con rời nhau (các phân hoạch tập A).  Tập hợp mà mỗi phần tử là 1 lớp tương đương của tập A theo quan hệ tương đương R () gọi là tập thương của A theo quan hệ R (). Ký hiệu là X/R  X/. Vậy X/R = {[x] | x  X}. Ví dụ: Trên tập Z các số nguyên xét quan hệ aRb nếu a – b  3. Ta có R là một quan hệ tương đương trên Z. Thật vậy: x, y, z  Z: a/x – x = 0  3  aRa suy ra R có tính chất phản xạ. b/xRy  x – y  3  –(y – x)  3 hay yRx suy ra R có tính chất đối xứng. c/ xRy  x – y  3 và yRz  x – y  3  (x – z)  3 suy ra R có tính chất bắc cầu. Ta xét các lớp tương đương theo quan hệ này ta có xRy  x – y  3  x và y chia cho 3 có cùng số dư. Khi chia cho 3 số dư có thể là 0, 1, 2. Do đó ta có các lớp tương đương đúng là: 0R  3k | k  Z  các số chia hết cho 3 1R  3k  1 | k  Z  các số chia cho 3 dư 1 2R  3k  2 | k  Z  các số chia cho 3 dư 2 Vậy Z = 0R , 1R , 2R  Quan hệ tương đương trên gọi là quan hệ đồng dư theo modul 3, ký hiệu là ab (mod 3). 1.2.4 Quan hệ thứ tự a. Định nghĩa quan hệ thứ tự Một quan hệ R trên tập A gọi là quan hệ thứ tự nếu R có các tính chất phản xạ, phản đối xứng và bắc cầu. Nếu R là quan hệ thứ tự trên A thì thay cho cách viết xRy ta viết xy (x nhỏ hơn hay bằng y). Vậy  là một quan hệ thứ tự trên A nếu với x, y, z  A, ta có: 1.x  x (tính phản xạ) 2.x  y  y  x thì x = y (tính phản đối xứng) 3.x  y  y  z thì x  z (tính bắc cầu) Ký hiệu x < y có nghĩa là x  y và x  y: đọc là x nhỏ hơn y. Tập A cùng với một quan hệ thứ tự  trên nó gọi là tập được sắp thứ tự, khi đó ký hiệu là (A, ). 6
Ví dụ 1: Trong N, Z, Q, R quan hệ  thông thường là quan hệ thứ tự. Ví dụ 2: Quan hệ bao hàm (  ) trong tập P(A) = 2A ( tập các tập con của tập A) là quan hệ thứ tự. Thật vậy: 1. X  P(A): A  A   có tính chất phản xạ. 2. X, Y  P(A): A  B  B  A  A = B nên  có tính chất phản đối xứng. 3. X, Y, Z  P(A): A  B  B  C  A C nên  có tính chất bắc cầu. b. Quan hệ thứ tự toàn phần và bộ phận Cho A là một tập hợp được sắp thứ tự. Nếu với x, y  A ta có x  y hoặc y  x thì ta nói x và y so sánh được với nhau. Nếu mọi x, y  A đều so sánh được với nhau thì ta nói A là tập sắp thứ tự toàn phần (sắp thứ tự tuyến tính). Trong trường hợp ngược lại, nói rằng A là tập sắp thứ tự bộ phận. Ví dụ :  Quan hệ  thông thường trên N, Z, Q, R là quan hệ thứ tự toàn phần.  Quan hệ “chia hết” trong N* là quan hệ thứ tự bộ phận (2 và 3 không so sánh được với nhau). c.Phần tử lớn nhất, nhỏ nhất, tối đại và tối thiểu Cho A là một tập được sắp thứ tự:  Phần tử a  A gọi là phần tử lớn nhất (nhỏ nhất) nếu với x  A đều có x  a (a  x).  Phần tử a  A gọi là phần tử tối đại (tối thiểu) nếu với x  A đều có a  x  a = x ( x  a kéo theo x = a). Ví dụ : Trong tập N với quan hệ  ta có 0 là phần tử nhỏ nhất; 0 là phần tử tối thiểu. Không có phần tử lớn nhất, phần tử tối đại.  Trong tập P(A) với quan hệ  có  là phần tử nhỏ nhất, A là phần tử lớn nhất. 1.3.Logic mệnh đề 1.3.1.Khái niệm mệnh đề và giá trị chân lý Một mệnh đề là một câu đúng hoặc sai, không thể vừa đúng vừa sai. Giá trị đúng hoặc sai của một mệnh đề được gọi là giá trị chân lý của mệnh đề. Về ký hiệu, ta thường dùng các chữ cái như p, q, r… để ký hiệu cho các biến nhận giá trị đúng hoặc sai. Giá trị chân lý “đúng – true” thường được viết là 1 hoặc T và giá trị chân lý “sai – false” được viết là 0 hoặc F. Ví dụ 1: Các phát biểu sau đây là các mệnh đề 1. 6 là một số nguyên tố 2. 5 là số lẻ 3. 4
Mệnh đề có hai loại: (1)Mệnh đề sơ cấp (elementary): mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là nó không thể phân tích được thành một hay nhiều (từ 2 trở lên) mệnh đề thành phần đơn giản hơn. (2) Mệnh đề phức hợp (compound): mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không” dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, vv … Ví dụ : xét các mệnh đề sau: p: “15 chia hết cho 3” ; q: “2 là một số nguyên tố và là một số lẻ” Ta có: p là mệnh đề sơ cấp, q là mệnh đề phức hợp, vì q được tạo thành từ 2 mệnh đề: p1 : “2 là một số nguyên tố” ; P2: “2 là một số lẻ” nhờ vào liên kết logic “và”. 1.3.2.Các phép toán mệnh đề Khi có các mệnh đề phức hợp theo các mệnh đề sơ cấp thì việc tính toán giá trị chân lý sẽ được thực hiện như thế nào? Để trả lời được cần có các phép toán logic, các phép toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như từ “không”, “và”, “hay”, “hoặc”, “suy ra”, “nếu … thì …”, “nếu và chỉ nếu…” Các phép toán logic được định nghĩa bằng bảng giá trị chân lý (truth table). a.Phép phủ định Ký hiệu là:  Giả sử p là một mệnh đề, phủ định của p được ký hiệu là  p hay p . Bảng giá trị chân lý của phép phủ định được cho bởi bảng: p p 0 1 1 0 Ví dụ 1: Cho mệnh đề p: 5
Ví dụ 1: Cho các mệnh đề p: “5>2” ; q: “6 là số nguyên tố” r: “Một tam giác đều cũng là tam giác cân” Giá trị chân lý của p, q, r là 1, 0, 1. Khi đó ta có: pq = 0; pr = 1 qr = 0; Ví dụ 2: Bằng cách lập bảng giá trị chân lý ta có: 1.Các mệnh đề p và pp luôn có cùng giá trị chân lý. 2.Mệnh đề p  p luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai) c.Phép tuyển Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề p hoặc q (p hay q) là pq. Phép tuyển hay phép hoặc được định nghĩa bởi bảng chân lý sau: p q pq 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có: pq = 1; pr = 1 Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề p  p là luôn đúng. Nhận xét: Một mệnh đề phức hợp mà luôn đúng bất kể các giá trị chân lý của các mệnh dề thành phần của nó được gọi là hằng đúng. Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn. Một mệnh đề không phải hằng đúng, cũng không phải mâu thuẫn được gọi là tiếp liên Ví dụ 3 : p  p là luôn đúng  nó là hằng đúng. p  p là luôn luôn sai  nó là mâu thuẫn. Phép loại trừ ký hiệu là XOR. p XOR q được định nghĩa bởi bảng chân lý sau: p q p XOR q 0 0 0 0 1 1 1 0 1 1 1 0  p XOR q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai. d.Phép kéo theo, ký hiệu là  Cho p và q là 2 mệnh đề. Mệnh đề p kéo theo q ký hiệu là p  q dùng để diễn đạt phát biểu: nếu p thì q và được định nghĩa bởi bảng chân lý sau: p q pq 0 0 1 0 1 1 1 0 0 1 1 1 9
Ví dụ : với nN, ta xét mệnhđề: p: n chia hết cho 5 q: n chia hết cho 9 Lúc đó mệnh đề p  q có giá trị xác định cụ thể: n = 45 p: 1 q: 1 p  q: 1 n = 15 p: 1 q: 0 p  q: 0 n = 16 p: 0 q: 0 p  q: 1 Xét mệnh đề p  q (1). Khi đó các mệnh đề sau đây gọi là các mệnh đề liên kết với (1) q  p (2) p  q (3) q  p (4) Mệnh đề (1) được gọi là mệnh đề thuận Mệnh đề (2) được gọi là mệnh đề đảo Mệnh đề (3) được gọi là mệnh đề phản Mệnh đề (4) được gọi là mệnh đề phản đảo Các mệnh đề liên kết chia thành 2 cặp tương đương:   i/  p  q   q  p  ii/ q  p   p  q với mệnh đề (1): Nếu có p thì có q do đó còn nói: p là điều kiện đủ để có q. Mệnh đề (1) tương đương mệnh đề (4) nghĩa là không q thì không p, do đó có thể nói: q là điều kiện cần để có p. e.Phép kéo theo hai chiều (phép tương đương). Ký hiệu là  Cho p, q là 2 mệnhđề. Mệnh đề p tương đương q dùng để diễn đạt phát biểu: p nếu và chỉ nếu q và được định nghĩa bởi bảng giá trị chân lý sau: P q pq 0 0 1 0 1 0 1 0 0 1 1 1 Mệnh đề p  q được đọc là: p nếu và chỉ nếu q hay còn được phát biểu dưới các dạng khác:  p khi và chỉ khi q  p là điều kiện cần và đủ cho q Độ ưu tiên của các toán tử logic 1.  2. ,  3. ,  Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Ví dụ :    1. x  y có nghĩa là x  y    2. x  y  p  q có nghĩa x  y   p  q 1.3.3.Biểu thức logic (công thức logic) Trong đại số ta có các biểu thức số học được xây dựng từ các hằng số, các biến số và các phép toán số học. Khi thay thế các biến trong một biểu thức số học bởi các hằng số 10
thì kết quả thực hiện các phép toán trong biểu thức là một hằng số. Trong đại số mệnh đề ta có biểu thức logic cũng được xây dựng như sau: a.Định nghĩa: Các mệnh đề chưa xác định p, q, r… gọi là các biến mệnh đề. 1.Các biến mệnh đề là các biểu thức 2.Nếu P, Q là các (công thức) biểu thức logic thì P , P  Q , P  Q , P  Q , P  Q là các (công thức) biểu thức. 3.Mọi ký hiệu khác không được xác định theo 2 qui tắc 1, 2 đều không là các biểu thức.    Ví dụ: p(x, y, z) = x  p  q  r  là một biểu thức logic với các biến mệnh đề x, p, q, r. b.Sự tương đương logic Hai biểu thức logic E và F theo bộ biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn có cùng giá trị chân lý trong mọi trường hợp giá trị chân lý của bộ biến mệnh đề. Khi đó ta viết E  F hay E  F và đọc là “E tương đương với F”. Như vậy, để chứng minh 2 biểu thức logic là tương đương logic thì có thể lập bảng giá trị chân lý. Ví dụ: Chứng minh p  q  r   p  r   q  r  Giải: ta lập bảng giá trị chân lý như sau: p q r pq pr qr pq r  p  r   q  r  0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy: p  q  r   p  r   q  r  c.Phép biến đổi công thức (biểu thức): Để biến đổi biểu thức một cách thuận tiện, ta qui ước các điều sau: 1.Không viết dấu ngoặc ngoài cùng đối với mỗi công thức (biểu thức). 2.Thay ký hiện  bởi dấu . hoặc bỏ đi. 3.Các phép toán được thực hiện theo thứ tự: , , ,  4.Nếu có dấu phủ định trên một biểu thức thì bỏ dấu ngoặc hai đầu biểu thức đó. Ví dụ :  ( p  q  r ) được viết là p  q  r    p  q  r được viết là p  q  r d.Các luật của logic mệnh đề Biểu thức logic A gọi là hằng đúng nếu A nhận giá trị 1 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Biểu thức logic A gọi là hằng sai nếu A nhận giá trị 0 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Khi A là hằng đúng thì ta gọi A là một luật, ký hiện là = A. Khi A là hằng sai thì ta gọi A là một mâu thuẫn. Ví dụ : p  p  1 nên ta có một luật = p  p . Luật = p  p gọi là luật bài trung: Trong hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng. 11
Các luật logic cơ bản 1. Luật phủ định kép: p  p 2. Luật giao hoán: p  q  q  p , p  q  q  p 3. Luật kết hợp: p  (q  r )   p  q   r , p  (q  r )   p  q   r 4. Luật phân phối: p  (q  r )   p  q   q  r  , p  (q  r )   p  q   q  r  5. Luật Demorgan: p  q  p  q , p  q  p  q 6. Luật về mối liên hệ giữa p với chính nó, với p , với 0 và 1: p p  p p p  p p0  0 p0  p p 1  p p 1  1 p  p  0 p  p 1 7. Luật kéo theo: p  q  p  q 8. Luật tương đương: p  q   p  q    q  p  Nhận xét: Có thể dùng các luật logic để biến đổi tương đương các biểu thức logic, hay nói cách khác, để chứng minh 2 biểu thức logic tương đương ta có thể dùng phương pháp biến đổi logic. Ví dụ: Chứng minh p  q  r   p  r   q  r  Ta biến đổi vế trái về vế phải như sau: Vế trái  p  q  r  ( p  q)  r  ( p  r )  (q  r )  ( p  r )  (q  r )  Vế phải 1.3.4.Các dạng chính tắc a.Dạng chính tắc tuyển Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, …, pn được gọi là một biểu thức hội cơ bản nếu nó có dạng sau: F = q1 q2  … qn với qi = pi hoặc qi  pi (i = 1… n). Ví dụ: Biểu thức xyz hoặc x  y  z hoặc x  y  z là các biểu thức hội cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng chính tắc tuyển khi E có dạng: E = E1 E2  … Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức hội cơ bản theo các biến mệnh đề p1, p2, …, pn. Ví dụ : Các biểu thức sau đây có dạnh chính tắc tuyển.      Ex, y, z   x  y  z  x  y  z  x  y  z       F  p1 , p 2 , p3 , p 4   p1  p 2  p3  p 4  p1  p 2  p3  p 4  p1  p 2  p3  p 4  Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc tuyển duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong phép tuyển). Nói cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản {E1, E2, …, Em} sao cho biểu thức E (p1, p2, …, pm)  E1  E2  …  Em. Ví dụ : Tìm dạng chính tắc tuyển của biểu thức:   E  x, y , z   x  z   x  y  Ex, y, z   x  z   x  y   x  z  x  x  z  y   x  z   x  y  z  12
      x y y z  x yz   x  y  z   x  y  z   x  y  z   x  y  z   x  y  z  b. Dạng chính tắc hội Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, …, pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau: F = q1 q2  … qn với qi = pi hoặc qi  pi (i = 1… n). Ví dụ: Biểu thức x y z hoặc x  y  z hoặc x  y  z là các biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng chính tắc hội khi E có dạng: E = E1 E2  … Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức tuyển cơ bản theo các biến mệnh đề p1, p2, …, pn. Ví dụ : Các biểu thức sau đây có dạng chính tắc hội.    Ex, y, z   x  y  z  x  y  z  x  y  z         F  p1 , p 2 , p3 , p 4   p1  p 2  p3  p 4  p1  p 2  p3  p 4  p1  p 2  p3  p 4  Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc hội duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội). Nói cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, …, Em} sao cho biểu thức E (p1, p2, …, pm)  E1  E2  …  Em. Ví dụ 1: Tìm chính tắc hội của biểu thức sau: E  x, y, z , t    x  y  y  z  z  t      Ex, y, z, t   x  y  z z  t t x x  y  z  t t x x  y y  z  t  x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t  x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t   x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t x  y  z  t  x  y  z  t x  y  z  t  Ví dụ 2: Tìm chính tắc tuyển của biểu thức:  x  y   z  y  x  y   z  y   x  y  z   x  y  y   x z  y z  xy  y y  x z  y z  xy      x y  y z  x  x y z  xy z  z    xy z  x y z  x y z  x y z  xyz  xy z  x y z  x y z  x y z  x yz 1.3.5.Vị từ, lượng từ a.Vị từ (Hàm mệnh đề) P(x) là một hàm mệnh đề (một biến) xác định trên tập X nếu với mỗi xX thì P(x) là một mệnh đề. Hàm mệnh đề một biến còn được gọi là vị từ 1-ngôi. 13
Nếu P(x) là một hàm mệnh đề xác định trên X thì x được gọi là biến tử, một phần tử cụ thể aX gọi là hằng tử, P(a) là một hàm mệnh đề hoàn toàn xác định. Tương tự ta có hàm mệnh đề m biến, hay vị từ m-ngôi với mN* b.Miền đúng của hàm mệnh đề Giả sử P(x) là một hàm mệnh đề trên X, khi đó miền đúng của P(x) là tập EP(x)={ aX P(a) là mệnh đề đúng} Ví dụ: 1. P(x): x2-6x+5=0 với x R có EP(x)={ 1,5} 2. P(x): x2-6x+50 với x R có EP(x)= (,1)  (5,) Hàm mệnh đề P(x) xác định trên X gọi là hằng đúng nếu EP(x)=X, gọi là hằng sai nếu EP(x)=, gọi là thực hiện được nếu EP(x) Ví dụ: 1. P(x): x2+1>0 là hằng đúng trên R 2. P(x): x2+1=0 là hằng sai trên R 3. P(x): 3x-4=0 là thực hiện được trên R nhưng không thực hiện được trên N Hai hàm mệnh đề P(x) và Q(x) cùng xác định trên tập X được gọi là tương đương logic, kí hiệu là P( x)  Q( x) hoặc P( x)  Q( x) khi và chỉ khi EP(x)= EQ(x) c.Phép toán trên các hàm mệnh đề Phép phủ định Cho P(x) là một hàm mệnh đề xác định trên X, ta gọi phủ định của P(x) là hàm mệnh đề P( x) xác định trên X, nhận giá trị 1 trên tập các phần tử a  X , P(a)  0 , nhận giá trị 0 trên miền đúng của P(x) Ta có: E P ( x )  X \ E P ( x ) EP( x) EP(x) Phép hội Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, hội của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX sao cho P(a)  1  Q(a)  1 , nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP ( x )Q( x )  EP( x )  EQ( x) 14
Phép tuyển Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, tuyển của P(x) và Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao cho P(a)  0  Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP ( x )Q( x)  EP ( x )  EQ( x) Phép kéo theo Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) kéo theo Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao cho P(a)  1  Q(a)  0 , nhận giá trị 1 trong các trường hợp còn lại. Ta có: EP( x)Q( x)  ( X \ EP( x) )  EQ( x) Phép tương đương Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) tương đương Q(x) là hàm mệnh đề P(x)  Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX sao cho P(a)  Q(a) , nhận giá trị 0 trong các trường hợp còn lại. Ta có: EP( x)Q( x)  ( X \ ( EP( x)  EQ( x) ))  ( EP( x)  EQ( x) ) d. Lượng từ Cho P(x) là hàm mệnh đề xác định trên X. Ta gọi xX P(x) hiểu là Với mọi xX, P(x) là mệnh đề đúng nếu EP(x)=X, sai trong các trường hợp khác. Ta gọi xX P(x) hiểu là tồn tại xX, P(x) là mệnh đề đúng nếu EP(x), sai trong các trường hợp khác. Ký hiệu  gọi là lượng từ phổ dụng (với mọi), ký hiệu  gọi là lượng từ tồn tại Như vậy: xX P(x) đúng  P(x) hằng đúng trên X xX P(x) đúng  P(x) thực hiện được trên X Ví dụ: 1. x  R ( x 2  1  0) là mệnh đề đúng 2. x  R (3x  1  0) là mệnh đề sai 3. x  R (3x  1  0) là mệnh đề đúng 4. x  N (3x  1  0) là mệnh đề sai e. Lượng từ trên các hàm mệnh đề nhiều biến Cho hàm mệnh đề 2 biến Px,y) xác định trên X x Y. Khi đó với mỗi y cố định xX P(x,y), xX P(x,y) là các mệnh đề, do đó ta được các hàm mệnh đề xX P(x,y), xX P(x,y) xác định theo yY. Ta có thể áp dụng các lượng từ với mọi và tồn tại lên các hàm mệnh đề này để được các mệnh đề xác định: xX yY P(x,y), xX yY P(x,y) , xX yY P(x,y) , xX yY P(x,y) f. Mối liên hệ giữa 2 mệnh đề phổ dụng và tồn tại Cho P(x) là hàm mệnh đề xác định trên X, khi đó ta có: 1. x  XP(x)  x  X P( x) ; 2. x  XP(x)  x  X P( x) 1.4 Suy luận toán học & các phương pháp chứng minh 1.4.1 Qui tắc suy luận Giả sử A1, A2, ..., An, B là các biểu thức logic. Ta nói B là hệ quả logic của A1, A2, ..., An nếu với mọi bộ giá trị chân lý có thể nhận của bộ biến mệnh đề có mặt trong trong các biểu thức đó mà A1, A2, ..., An đồng thời nhận giá trị 1 đều có B nhận giá trị 1. 15
Khi B là hệ quả logic của A1, A2, ..., An thì nói rằng có một qui tắc suy luận từ các tiên đề A1, A2, ..., An tới hệ quả logic B. A1 , A2 ,..., An Qui tắc suy luận trên được kí hiệu là: hay A1, A2, ..., An = B B Ta có A1, A2, ..., An đồng thời nhận giá trị 1 khi và chỉ khi A1  A2  ...  An nhận giá trị 1 Khi đó A1  A2  ...  An  B đúng  A1  A2  ...  An nhận giá 1 thì B cũng nhận giá trị 1 A1 , A2 ,..., An Hay có qui tắc suy luận  có luật A1  A2  ...  An  B B A , A ,..., An Như vậy để chứng minh qui tắc suy luận 1 2 ta có thể dùng một trong 2 phương B pháp sau: 1. Lập bảng giá trị chân lý, xét theo đúng định nghĩa 2. Chỉ ra mệnh đề A1  A2  ...  An  B là hằng đúng. p, p  q Ví dụ 1: Chứng minh qui tắc suy luận q Cách 1: Lập bảng giá trị chân lý p q pq 0 0 1 0 1 1 1 0 0 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có một bộ giá trị của p,q làm cho p,q nhận giá trị 1 p, p  q thì p  q cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy luận q p, p  q Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh q ( p  ( p  q))  q  1( hằng đúng) Thực vậy: ( p  ( p  q))  q  p  ( p  q)  q  ( p  p)  ( p  q)  q  p  q  q  p  q  q  1 (ĐPCM) p  q, q  r Ví dụ 2: Chứng minh qui tắc suy luận pr Cách 1: Lập bảng giá trị chân lý p q r pq qr pr 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 16
1 1 0 1 0 0 1 1 1 1 1 1 Nhìn vào bảng giá trị chân lý ta thấy có 4 bộ giá trị của p,q, r làm cho pq và qr đồng thời nhận giá trị 1 thì p  r cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy p  q, q  r luận pr p  q, q  r Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh pr (( p  q)  (q  r ))  ( p  r )  1 ( hằng đúng) Thực vậy: (( p  q)  (q  r ))  ( p  r )  ( p  q)  (q  r )  p  r  ( p  q)  p  (q  r )  r  q  q  p  r  1  p  r  1 (ĐPCM) 1.4.2 Các qui tắc suy luận cơ bản Trong suy luận toán học người ta thường dùng 28 qui tắc suy luận cơ bản sau, các qui tắc này đã được chứng minh theo 2 phương pháp trên. 2 ví dụ vừa xét là qui tắc suy luận số1 và qui tắc số 3. p  q, p p  q, q 1. 2. q p p  q, q  r p  q, q  r 3. 4. pr pr p  q, q  p p  q, p 5. 6. pq q p  r, q  r p  q, p  r 7. 8. pq r pqr p  q, r  s p  q, r  s 9. 10. pr qs pr  qs p  q, r  s p  q, r  s 11. 12. pr qs pr  qs p, q pq 13. 14. pq p p p p 15. 16. ; pq p p pq q p pq 17. ; 18. q p pq pq pqr p  q  r  pqr 19. 20. p  q  r  pqr pr 17