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

0 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 1 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 2 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 AXX \ gọi là phần bù của A trong X. Ta có: AAC = X hay XAA  ; AAC =  hay  AA  3 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} 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. N A .2 .10 .8 .4 .6 2 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: BABA   BABA   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  ni n i AAAA ... 21 1    = nn AAAA   )... ( 121  A1A2 A3 = (A1A2)A3  ni n i AAAA ... 21 1    = nn AAAA   )... ( 121 b.Mở rộng tính chất 3 Cho các tập hợp X, A1, A2,, An ta có: 3   i n i i n i AXAX         11    i n i i n i AXAX         11  c.Mở rộng tính chất 4 Cho các tập hợp X, A1, A2,, An ta có:  i n i i n i AA 11     i n i i n i AA 11    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 =   nnni n i AaAaaaA   ,,/,, 111 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ếu A1 = A2 = = An thì ký hiệu n i n i AA  1 và gọi là luỹ thừa đề các bậc n của tập hợp 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| 4 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ó: | {ai} B| = n vì AB = )}({ 1 Bai m i    và các tập {a1} B; {a2} B; ; {am} B đô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   m m AAAA  . Các nhóm gồm m phần tử 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ì {(a,b) , }R 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ệ. 5 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 6 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      yRxxyxx R | 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ó:       yxxy  và    yxxRy   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à:    ZkkR  |30 các số chia hết cho 3    ZkkR  |131 các số chia cho 3 dư 1    ZkkR  |232 các số chia cho 3 dư 2 Vậy Z =       RRR 2,1,0 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, ). 7 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) = 2 A ( 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<-2 4. Tam giác cân có 2 góc bằng nhau 5. H2O là một axit. Các mệnh đề 2, 4 có giá trị chân lý “đúng” hay là các mệnh đề đúng. Các mệnh đề 1, 3, 5 có giá trị chân lý “sai” hay là các mệnh đề sai. Ví dụ 2: Các phát biểu sau đây không phải là các mệnh đề vì tính đúng sai của chúng không xác định. 1. Hãy đóng cửa sổ lại! 2. Ai đang đọc sách? 3. Cô ấy rất thông minh 4. Cho x là một số nguyên dương. 5. x là một số lẻ 6. x + y = z 8 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<3  p : 5 3 Giá trị chân lý của p là 0 Giá trị chân lý của p là 1 Ví dụ 2: Chỉ ra rằng p và p luôn có cùng giá trị chân lý: Giải: lập bảng giá trị chân lý của mệnh đề (p) p p p 0 1 0 1 0 1 Qua bảng giá trị chân lý của mệnh đề ta nhận thấy rằng p và p luôn có cùng giá trị