Giáo trình Tập hợp và logic toán | Trường Đại học Kỹ thuật Y tế Hải Dương

UBND TỈ NH HẢI DƯƠNG TRƯỜNG ĐẠI H ỌC HẢI DƯƠNG GIÁO TRÌNH TẬP HỢ P VÀ LOGIC TOÁN TS. Phạm Ngọc Hoa TS. Nguyễ n Thị Thu Hà LỜI GIỚI THIỆU Hải Dương - 2024 MỤC LỤC
MỤC LỤC ............................................................................................................ 1
LỜI GIỚI THIỆU ................................................................................................ 4
Chương 1 .............................................................................................................. 5
Logic ...................................................................................................................... 5
1.1. Mệnh đề và phép toán ................................................................................ 5
1.1.1. Khái niệm mệnh đề .............................................................................. 5
1.1.2. Phép phủ định ....................................................................................... 6
1.1.3. Phép hội .................................................................................................. 7
1.1.4. Phép tuyển ............................................................................................. 8
1.1.6. Phép kéo theo ........................................................................................ 9
1.1.7. Phép tương đương .............................................................................. 11
1.2. Công thức mệnh đề, tương đương logic ............................................... 12
1.2.1. Công thức mệnh đề và thứ tự ưu tiên của các toán tử logic ....... 12
1.2.3. Tương đương logic ............................................................................. 16
1.2.4. Dịch câu thành biểu thức logic ........................................................ 20
1.3. Vị từ và các phép toán vị từ ..................................................................... 21
1.3.1. Hàm mệnh đề ...................................................................................... 21
1.3.2. Lượng từ và vị từ ................................................................................ 22
1.3.3. Phủ định của vị từ .............................................................................. 24
1.3.4. Trật tự của các lượng từ ..................................................................... 26
1.3.5. Dịch các vị từ có sự tham gia của các lượng từ lồng nhau.......... 27
1.3.6. Dịch câu thành biểu thức logic ........................................................ 28
1.3.7. Phủ định các vị từ chứa lượng từ lồng nhau ................................. 29
1.4. Hệ quả logic và quy tắc suy luận ............................................................ 30 1
1.4.1. Hệ quả logic ......................................................................................... 31
1.4.2. Các quy tắc suy luận ............................................................................... 32
1.4.3. Những suy luận hợp thức ................................................................. 35
1.4.4. Ngụy biện ............................................................................................. 37
1.5. Một số phương pháp chứng minh Toán học ....................................... 37
1.5.1. Phương pháp chứng minh trực tiếp ................................................ 37
1.5.2. Phương pháp chứng minh gián tiếp ............................................... 40
1.5.3. Phương pháp chứng minh quy nạp ................................................ 41
1.5.4. Một số sai lầm trong chứng minh ................................................... 43
Câu hỏi, bài tập Chương 1 .............................................................................. 44
Chương 2 ............................................................................................................ 54
Tập hợp và Ánh xạ ........................................................................................... 54
2.1. Tập hợp ........................................................................................................ 54
2.1.1. Tập hợp và phần tử ............................................................................ 54
2.1.2. Cách xác định tập hợp ........................................................................ 55
2.1.3. Tập hợp con. Tập hợp bằng nhau.................................................... 57
2.1.4. Các phép toán trên các tập hợp ........................................................ 59
2.2. Quan hệ hai ngôi ....................................................................................... 67
2.2.1. Tích đề các ............................................................................................ 67
2.2.2. Quan hệ hai ngôi ................................................................................ 67
2.2.3. Quan hệ tương đương........................................................................ 70
2.2.4. Quan hệ thứ tự .................................................................................... 72
2.3. Ánh xạ .......................................................................................................... 73
2.3.1. Định nghĩa và ví dụ ........................................................................... 73
2.3.2. Ảnh và tạo ảnh .................................................................................... 74
2.3.3. Các ánh xạ đặc biệt ............................................................................. 75
2.3.4. Hợp thành của các ánh xạ .................................................................. 76
2.3.5. Ánh xạ ngược của một song ánh ...................................................... 77
2.3.6. Thu hẹp và mở rộng ........................................................................... 77 2
Bài tập chương 2 ............................................................................................... 77
Chương 3 ............................................................................................................ 83
Tổ hợp ................................................................................................................. 83
3.1. Một số phương pháp đếm cơ bản ........................................................... 83
3.1.1. Nguyên lý cộng ................................................................................... 83
3.1.2. Nguyên lý nhân ................................................................................... 84
3.1.3. Nguyên lý bù trừ ................................................................................ 85
3.2. Một số cấu hình tổ hợp ............................................................................. 87
3.2.1. Chỉnh hợp và chỉnh hợp lặp ............................................................. 87
3.2.2. Tổ hợp và tổ hợp lặp .......................................................................... 88
3.2.3. Hoán vị và hoán vị có lặp .................................................................. 92
3.3. Nguyên lý Dirichlet .................................................................................. 95
3.3.1. Nguyên lý Dirichlet cổ điển ............................................................. 95
3.3.2. Nguyên lý Dirichlet suy rộng .......................................................... 97
3.3.3. Một vài ứng dụng thú vị của nguyên lý Dirichlet ....................... 97
Bài tập Chương 3 .............................................................................................. 98
TÀI LIỆU THAM KHẢO .............................................................................. 103 3 LỜI GIỚI THIỆU
Lý thuyết tập hợp và lôgic toán là cơ sở nền tảng của toán học nói chung và
của các môn toán học trong chương trình đào tạo đại học nói riêng. Lôgic toán mà
chủ yếu là các quy luật cơ bản của lôgic hình thức xuất hiện và phát triển từ rất
sớm, khoảng 300 năm trước công nguyên.
Tuy nhiên trong quá trình phát triển, khi mà toán học chuyển từ phạm vi “bất
biến, hữu hạn” sang phạm vi “vận động, vô hạn và liên tục” thì các cơ sở lý luận-
lôgic hình thức ban đầu ấy tỏ ra không đủ đáp ứng được nữa. Để khắc phục những
khó khăn về cơ sở lý luận- lôgic hình thức, vào cuối thế kỷ 19 Cantor đã xây dựng
lý thuyết tập hợp. Tuy rằng, trong quá trình phát triển của toán học, lý thuyết tập
hợp của Cantor xây dựng về căn bản đã cung cấp một nền tảng thống nhất cho việc
xây dựng về căn bản đã cung cấp một nền tảng thống nhất cho việc xây dựng và
phát triển hầu như toàn bộ ngành toán học.
Đồng thời với việc khắc phục, loại bỏ các nghịch lý trong lý thuyết tập hợp mà
Cantor đã xây dựng bằng hạn chế ngoại diên của khái niệm tập hợp, quy định
những điều làm được và những điều không thể làm được đối với các đối tượng và
quan hệ cơ bản của lý thuyết tập hợp, người ta cũng đề nghị tiên đề hóa lý thuyết
cơ sở về lôgic nhằm xây dựng một nền tảng vững chắc cho toán học.
Giáo trình này gồm 3 chương, được viết chi tiết theo từng chương theo
chương trình của học phần Tập hợp và lôgic toán học, bao gồm: Chương 1. Logic:
Các khái niệm và tính chất cơ bản về Đại số mệnh đề, Đại số vị từ. Chương 2.Tập
hợp và Ánh xạ: Định nghĩa và tính chất cơ bản về tập hợp, quan hệ, ánh xạ; Phân
loại được quan hệ hai ngôi cơ bản, tìm lớp tương đương, tập thương, tìm phân tử
tối đại, tối tiểu, phân loại ánh xạ, tìm ảnh tạo ảnh. Chương 3. Tổ hợp: Lý thuyết tổ
hợp bao gồm các bài toán đếm, các quy tắc đếm cơ bản và bài toán tồn tại. Một số
phương pháp đếm cơ bản; Một số cấu hình tổ hợp; Nguyên lý Dirichlet.
Hệ thống kiến thức cơ bản được lựa chọn một cách tối thiểu, các mệnh đề
được chứng minh tỉ mỉ, chi tiết cùng hệ thống các ví dụ minh họa trực quan và bài
tập phong phú sau mỗi chương tạo điều kiện thuận lợi cho sinh viên tự học môn
này ở năm thứ nhất. Hy vọng rằng với cách trình bày như vậy, giáo trình sẽ góp
phần nâng cao hiệu quả học tập cho sinh viên.
Cuối cùng, có thể việc biên soạn của các tác giả vẫn còn thiếu sót, chúng tôi
mong muốn tiếp tục nhận được các ý kiến đóng góp phê bình của các bạn sinh viên và đồng nghiệp. Các tác giả 4
TẬP HỢP VÀ LOGIC TOÁN Chương 1 Logic
Trong thế giới của toán học, logic đóng vai trò như nền tảng vững
chắc để xây dựng các lý thuyết và phát triển các tư duy phê phán. Trong
chương I của giáo trình "Tập hợp và Logic Toán", chúng ta sẽ khám phá
những nguyên lý cơ bản của logic, từ khái niệm mệnh đề đến các phép toán
logic, từ các quy tắc suy luận đến những phương pháp chứng minh. Logic
toán học không chỉ là công cụ để giải quyết các bài toán toán học mà còn là
phương tiện để rèn luyện khả năng tư duy logic, phân tích và tổng hợp
thông tin. Những kỹ năng này không chỉ cần thiết trong toán học mà còn
trong nhiều lĩnh vực khác của cuộc sống và công việc.
Trong chương này, chúng ta sẽ học cách xác định và phân loại các
mệnh đề, hiểu và áp dụng các phép toán logic như phủ định, hội, tuyển và
kéo theo. Chúng ta cũng sẽ được giới thiệu về hệ quả logic và các quy tắc
suy luận, từ đó phát triển khả năng chứng minh các mệnh đề toán học một
cách chặt chẽ và chính xác. chương này sẽ giới thiệu về các phương pháp
chứng minh, một trong những kỹ năng quan trọng nhất mà mỗi người học
toán cần phải nắm vững. Chúng ta sẽ tìm hiểu về các phương pháp chứng
minh khác nhau như chứng minh phản chứng, chứng minh quy nạp và
chứng minh bởi đối lập. Mỗi phương pháp đều có những đặc điểm và ứng
dụng riêng, giúp chúng ta lựa chọn và áp dụng phù hợp với từng bài toán cụ thể.
1.1. Mệnh đề và phép toán
1.1.1. Khái niệm mệnh đề
Khi nói hoặc viết, ta đều diễn đạt bằng những câu, chẳng hạn như những câu sau:
a) Mỗi tứ giác có 4 cạnh. b) Số 15 chia hết cho 6.
c) Ngày thứ 5 trời nắng.
d) Hà Nội là thủ đô của Việt Nam.
e) Hình vuông có bốn cạnh bằng nhau.
Các câu trên khẳng định một sự kiện nào đó. Những khẳng định này
có thể đúng hoặc sai. Những câu như vậy người ta gọi là mệnh đề. 5
Định nghĩa 1. Mệnh đề (proposition) là một câu khẳng định có thể xác định
được tính đúng hoặc sai. Một mệnh đề luôn có giá trị chân lý (truth value)
rõ ràng: đúng (true) hoặc sai (false).
Các mệnh đề được ký hiệu bằng các chữ cái: A, B, C, p, q, r, ...
Khi mệnh đề A đúng, ta nói A nhận giá trị đúng và viết A = T (True).
Khi mệnh đề B sai, ta nói B nhận giá trị sai và viết B = F (False). Các giá trị
T, F được gọi là giá trị chân lý của các mệnh đề.
Ví dụ 1. Các phát biểu sau là mệnh đề. a) 1+1=2 (đúng) ; b) 2+ 2 bằng 5 (sai);
c) Bảng đen có dạng hình chữ nhật (đúng).
Ví dụ 2. Các câu sau không là mệnh đề.
a) Hôm nay là thứ mấy? (Không là mệnh đề vì là câu hỏi).
b) Nhớ làm hết các bài tập! (Không là mệnh đề vì là câu mệnh lệnh).
c) x  1  3 (không là mệnh đề vì không xác định được tính đúng/sai).
Trong toán học, khi có hai số, người ta dùng các phép toán số học
(cộng, trừ, nhân, chia,...) tác động vào chúng để nhận được những số mới.
Tương tự, khi có mệnh đề, người ta dùng các phép lôgic tác động vào chúng
để nhận được những mệnh đề mới, các mệnh đề này còn được gọi là các
mệnh đề phức hợp hay các biểu thức mệnh đề. Dưới đây trình bày định nghĩa
và các tính chất cơ bản của các phép toán này.
1.1.2. Phép phủ định
Định nghĩa 2. Cho P là một mệnh đề. Phát biểu “Không phải P” là một
mệnh đề mới gọi là phủ định của mệnh đề P, kí hiệu là P , P đúng khi P sai và sai khi P đúng.
Bảng 1. Bảng giá trị chân lí của phép phủ định P P T F F T
Ví dụ 3. Nếu P = "Paris là thủ đô của nước Pháp" thì mệnh đề phủ định P có thể diễn đạt như sau: 6
P = "Không phải Paris là thủ đô của nước Pháp".
hoặc P = "Paris không phải là thủ đô của nước Pháp".
Ở đây P= T, còn P =F.
Ví dụ 4. Nếu B = "15 lớn hơn 30" thì mệnh đề phủ định B có thể diễn đạt như sau:
B = "Không phải 15 lớn hơn 30"
hoặc B = "15 không lớn hơn 30"
hoặc B = "15 nhỏ hơn hoặc bằng 30"
Ở đây B= F, còn B = T.
Ví dụ 5. Nếu C = "Chuyến tàu TN1 hôm nay bãi bỏ" thì mệnh đề phủ định
C có thể diễn đạt như sau:
C = "Chuyến tàu TN1 hôm nay không bãi bỏ". 1.1.3. Phép hội
Định nghĩa 3. Cho A và B là hai mệnh đề. Hội của hai mệnh đề A, B được
phát biểu “A và B”, kí hiệu A Λ B (hoặc A.B), mệnh đề A Λ B nhận giá trị
đúng khi cả hai mệnh đề A, B cùng đúng và sai trong các trường hợp còn lại.
Bảng 2. Bảng giá trị chân lí của phép hội A B A Λ B F F F T F F F T F T T T
Chú ý: Để thiết lập mệnh đề hội của hai mệnh đề A, B ta ghép hai mệnh đề
đó bởi liên từ "và" hay một liên từ khác cùng loại. Những liên từ đó là: mà,
nhưng, song, đồng thời, vẫn, cùng,... hoặc dùng dấu phảy mà không dùng liên từ gì. Ví dụ 6.
"Lúc 8 giờ sáng nay Hà có mặt ở Hà Nội và thành phố Hồ Chí Minh" là
hội của hai mệnh đề A = "Lúc 8 giờ sáng nay Hà có mặt ở Hà Nội" và B = 7
"Lúc 8 giờ sáng nay Hà có mặt ở thành phố Hồ Chí Minh". Vì hai mệnh đề
này không thể cùng đúng, nên A Λ B = F. Ví dụ 7.
"Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước nhưng
không phải là thủ đô" là hội của hai mệnh đề A = "Thành phố Hồ Chí Minh
là thành phố lớn nhất trong cả nước" và B = "Thành phố Hồ Chí Minh
không phải là thủ đô". Rõ ràng là A Λ B = T. Ví dụ 8.
"Số π lớn hơn 2 song nhỏ hơn 3".
"Chị Nga nói thạo tiếng Pháp mà không biết tiếng Anh".
"ABC là tam giác vuông cân" là hội của của hai mệnh đề a = "ABC là
tam giác vuông" và b = "ABC là tam giác cân".
"Không những trời nắng to mà còn gió tây".
"Chồng cày, vợ cấy, con trâu đi bừa".
Chú ý: Đôi khi trong mệnh đề có liên từ "và" nhưng không có nghĩa của
mệnh đề hội. Chẳng hạn:
"Số lẻ và số chẵn là hai tập con rời nhau của tập số tự nhiên".
"Hùng đạt được tất cả 20 điểm 9 và 10". 1.1.4. Phép tuyển
Định nghĩa 4. Tuyển của hai mệnh đề A, B là một mệnh đề đọc là “A hoặc B”,
kí hiệu là A ν B (hoặc A+B). Mệnh đề A ν B nhận giá trị sai khi cả hai mệnh
đề A, B cùng sai và đúng trong các trường hợp còn lại. A B A ν B F F F T F T F T T T T T
Phép tuyển trên còn được gọi là phép tuyển không loại trừ.
Chú ý: Để thiết lập mệnh đề tuyển của hai mệnh đề A, B ta ghép hai
mệnh đề đó bởi liên từ "hoặc" (hay một liên từ khác cùng loại). Ví dụ 8. 8
"Tháng 12 có 31 ngày hoặc 2 + 2 = 4" là tuyển của hai mệnh đề A =
"Tháng 12 có 31 ngày" và B = "2 + 2 = 4". Trường hợp này do B = T nên A ν B = T. Ví dụ 9.
"3 nhỏ hơn hoặc bằng 4" là mệnh đề đúng.
"Số lẻ là số có chữ số tận cùng bằng 1, 3, 5, 7 hoặc 9" là mệnh đề đúng.
"20 là số lẻ hoặc chia hết cho 3" là mệnh đề sai.
1.1.5. Phép tuyển loại
Chú ý: Trong thực tế, liên từ "hoặc" thường được dùng với hai nghĩa
"loại trừ" và "không loại trừ".
Định nghĩa 5. Tuyển loại của hai mệnh đề A, B là một mệnh đề đọc là "Hoặc A
hoặc B nhưng không cả hai" là mệnh đề chỉ đúng khi có một trong hai mệnh
đề A, B là đúng và sai trong các trường hợp còn lại, ký hiệu là A XOR B hoặc AB. Ví dụ 10.
"Hôm nay là ngày Chủ nhật hoặc ngày lễ" là phép tuyển không loại trừ.
"20 là số lẻ hoặc nó chia hết cho 2" là phép tuyển loại trừ. 1.1.6. Phép kéo theo
Định nghĩa 6. Cho A và B là hai mệnh đề, phát biểu " A kéo theo B" là một
mệnh đề mới, kí hiệu là A  B, mệnh đề A  B chỉ sai khi A đúng và B sai
và đúng trong các trường hợp còn lại.
Bảng 4. Bảng giá trị chân lí của phép kéo theo A B A  B T T T T F F F T T F F T
Chú ý: Mệnh đề “A kéo theo B” thường được diễn đạt dưới nhiều hình thức khác nhau, chẳng hạn: "Nếu A thì B" 9 ''A chỉ nếu B" "Có B khi có A" "Từ A suy ra B"
"A là điều kiện đủ để có B"
"B là điều kiện cần (ắt có) để có A" .............. Ví dụ 11.
"15 có chữ số tận cùng bằng 5 suy ra 15 chia hết cho 5" mệnh đề đúng.
"Nếu dây tóc bóng đèn có dòng điện chạy qua thì bóng đèn sáng" mệnh đề đúng.
Chú ý 1: Trong lôgic, khi xét giá trị chân lí của mệnh đề “A  B” người ta
không quan tâm đến mối quan hệ về nội dung của hai mệnh đề A, B, cũng
không phân biệt trường hợp A có phải là nguyên nhân để có B hay không,
mà chỉ quan tâm đến tính đúng, sai của chúng. Ví dụ 12.
"Nếu mặt trời quay quanh trái đất thì Việt Nam nằm ở Châu Âu" là
mệnh đề đúng. Vì ở đây hai mệnh đề A = "mặt trời quay quanh trái đất" và
B = "Việt Nam nằm ở Châu Âu" đều sai.
"Nếu tháng 12 có 31 ngày thì mỗi năm có 13 tháng" là mệnh đề sai.
Chú ý 2. Theo bảng chân lí trên, ta thấy:
Nếu A sai thì A  B luôn đúng.
Nếu A đúng thì A  B đúng khi B đúng.
Chú ý 3. Nếu ta coi A  B là mệnh đề thuận thì B  A là mệnh đề đảo, A  B
là mệnh đề phản nghịch đảo và B  A là mệnh đề phản đảo.
Chú ý 4. Trong văn học, mệnh đề kéo theo còn được diễn đạt bằng nhiều
hình thức phong phú. Chẳng hạn:
"Bao giờ bánh đúc có xương,
Bấy giờ dì ghẻ mới thương con chồng" hoặc
"Chuồn chuồn bay thấp thì mưa,
Bay cao thì nắng bay vừa thì râm". 10
1.1.7. Phép tương đương
Định nghĩa 7. Cho A, B là hai mệnh đề, phát biểu “A tương đương B” là một
mệnh đề, kí hiệu là A  B, mệnh đề này đúng khi cả hai mệnh đề A và B
cùng đúng hoặc cùng sai.
Bảng 5. Bảng giá trị chân lí của mệnh đề tương đương A B A  B T T T T F F F T F F F T Chú ý:
1. Trong thực tế, mệnh đề "A tương đươngB" thường được diễn đạt dưới
nhiều hình thức khác nhau. Chẳng hạn: "A khi và chỉ khi B" "A nếu và chỉ nếu B"
"A và B là hai mệnh đề tương đương"
"A là điều kiều kiện cần và đủ để có B"
2. Hai mệnh đề A, B tương đương với nhau hoàn toàn không có nghĩa là nội
dung của chúng như nhau, mà nó chỉ nói lên rằng chúng có cùng giá trị
chân lí (cùng đúng hoặc cùng sai).
3. Một cách khác, người ta cũng nói rằng A tương đương B khi và chỉ khi cả
hai mệnh đề A  B và B  A cùng đúng. Vì vậy để chứng minh mệnh đề A
 B ta chứng minh hai mệnh đề A  B và B  A.
4. Các cặp mệnh đề thuận và phản đảo, đảo và phản nghịch đảo là những
cặp mệnh đề tương đương. Đây chính là cơ sở của phương pháp chứng minh
gián tiếp trong toán học. Ví dụ 13.
"Tháng 12 có 31 ngày khi và chỉ khi trái đất quay quanh mặt trời" là mệnh đề đúng.
"12 giờ trưa hôm nay Tuấn có mặt ở Hà Nội nếu và chỉ nếu vào giờ đó anh
đang ở thành phố Hồ Chí Minh" là mệnh đề sai. 11
"Hình vuông có một góc tù khi và chỉ khi 100 là số nguyên tố" là mệnh đề đúng.
1.2. Công thức mệnh đề, tương đương logic
Một bước quan trọng được dùng trong các lập luận toán học là thay
một mệnh đề này bằng một mệnh đề khác có cùng giá trị chân lý. Vì thế, các
phương pháp tạo ra các mệnh đề có cùng giá trị chân lý với một mệnh đề
phức hợp đã cho được dùng rất rộng rãi trong việc xây dựng các lập luận
toán học. Chúng ta sẽ bắt đầu bằng việc phân loại các mệnh đề phức hợp
theo các giá trị chân lý khả dĩ của chúng.
1.2.1. Công thức mệnh đề và thứ tự ưu tiên của các toán tử logic
Giả sử cho A, B, C là các mệnh đề nào đó. Ta có thể gọi A, B, C là các
biến mệnh đề vì chúng có thể nhận giá trị T hoặc F. Từ các mệnh đề sơ cấp
ta dùng các phép toán logic để có các mệnh đề phức tạp hơn như A , A  B, A  B, A  B,
A  B ,...(*). Từ các mệnh đề (*) ta lại áp dụng
các phép toán logic để có các mệnh đề phức tạp hơn nữa như
A  ( A  B),
( A  B)  C ,...(**) và ta gọi các dãy ký hiệu đó là công thức
của logic mệnh đề hay biểu thức mệnh đề. Sau đây ta đưa ra định nghĩa
hình thức của khái niệm biểu thức mệnh đề. Định nghĩa 1.
a) Các biến mệnh đề A, B, C,...là các biểu thức mệnh đề;
b) Nếu A, B là các biểu thức mệnh đề thì A , A  B , A  B , A  B ,
A  B, A  B là các biểu thức mệnh đề.
Ví dụ 1. Cho A: “Tứ giác ABCD là hình chữ nhật”
B: “Tứ giác ABCD là hình thoi”,
C: “Tứ giác ABCD là hình vuông”
Khi đó A  B  C là mệnh đề: “ Nếu tứ giác ABCD vừa là hình chữ nhật
vừa là hình thoi thì tứ giác ABCD là hình vuông”.
Ví dụ 2. Cho các mệnh đề A: “ Hà hiểu sâu lý thuyết”
B: “ Hà đọc kỹ đầu bài”
C: “ Hà làm được bài tập”.
Hãy phát biểu các mệnh đề sau:
a) A  B  C ;
b) A  B  C ; 12
c) C  A  B ;
d) A  B  C ;
e) A  B  C . Giải:
a) Nếu Hà hiểu sâu lý thuyết và đọc kỹ đề bài thì Hà làm được bài tập.
b) Nếu Hà hiểu sâu lý thuyết và đọc kỹ đề bài thì Hà làm được bài tập và ngược lại.
c) Nếu Hà làm được bài tập thì Hà hiểu sâu lý thuyết hoặc Hà đọc kĩ đề bài.
d) Nếu Hà không hiểu sâu lí thuyết mà Hà có đọc kĩ đề bài thì Hà vẫn
không làm được bài tập.
e) Nếu Hà không hiểu sâu lí thuyết và Hà không đọc kĩ đề bài thì Hà
không làm được bài tập. Chú ý:
1. Khái niệm biểu thức mệnh đề trong logic mệnh đề tương tự như khái
niệm biểu thức gặp trong đại số; ta có thể gọi công thức là biểu thức của
logic mệnh đề. Khi thay các biến mệnh đề A, B, C... bằng các mệnh đề cụ thể
thì công thức logic mệnh đề sẽ thành mệnh đề xác định.
2. Giá trị chân lý của biểu thức mệnh đề là kết quả nhận được từ sự kết hợp
các phép toán và giá trị chân lý của các biến mệnh đề sơ cấp.
Thứ tự ưu tiên các phép toán logic
Trong biểu thức mệnh đề, ta sẽ dùng dấu ngoặc để chỉ định thứ tự thực hiện
của các phép toán. Các toán tử nằm ở dấu ngoặc trong cùng sẽ được thực hiện
trước tiên, ngoài ra các toán tử trong cùng một dấu ngoặc sẽ có thứ tự ưu tiên là:
phủ định, hội, tuyển, tuyển loại, kéo theo, và tương đương.
Ví dụ 3. Lập bảng giá trị chân lý của các biểu thức mệnh đề sau:
a)  A  B  A  B .
b)  A  B  C  A  B Giải:
a)  A  B  A  B
Kết quả được cho trong bảng sau: Bảng 7 13
A B AB A  B B A  B  A  B  A  B F F T F T F T F T T F F F T T F F T T T T T T T F F F T
b)  A  B  C  A  B
Kết quả được cho trong bảng sau: Bảng 8
A B C A A  B A  B  C A  B  A  B  C  A  B F F F T F F F T F F T T F T F F F T F T T T F F F T T T T T F F T F F F F F F T T F T F F T F F T T F F F F T F T T T F F T T T
Ví dụ 4. Xác định giá trị chân lý của các mệnh đề sau:
a) ( A  B)  A ;
b)  A  B  C   A  C   (B  C) ;
c)  A  B  C   A  C   (B  C) . Giải:
a) ( A  B)  A ;
Kết quả được cho trong bảng sau: Bảng 9
A B B A  B ( A  B)  A F F T T F 14 F T F F T T F T T T T T F T T
b)  A  B  C   A  C   (B  C) ;
Kết quả được cho trong bảng sau: Bảng 10
A B C A  B  A  B  C A  C B  C  A  C  (B  C) BT F F F F F F F F T F F T F F F F F T F T F T F F F F T F T T T T F T T T T F F T F F F F T T F T T T T F T T T T F T F F F F T T T T T T T T T T
c)  A  B  C   A  C   (B  C) .
Kết quả được cho trong bảng sau: Bảng 11
A B C A  B  A  B  C A  C B  C  A  C  (B  C) BT F F F F F F F F T F F T F T T T T T F T F F F F T F T F T T F T T T T T T F F F F T F F T T F T F T T T T T T T F T T T T T T T T T T T T T T T
1.2.2. Phân loại các mệnh đề phức hợp 15
Chúng ta có một số thuật ngữ chuyên ngành sau: Định nghĩa 2.
Hằng đúng: Một mệnh đề phức hợp mà luôn luôn đúng bất kể các giá
trị chân lý của các mệnh đề thành phần của nó được gọi là hằng đúng.
Mâu thuẫn: Một mệnh đề mà luôn luôn sai thì được gọi là mâu thuẫn (hằng sai)
Tiếp liên: Một mệnh đề không là hằng đúng, cũng không là mâu thuẫn
được gọi là tiếp liên.
Ví dụ 5. A  A là hằng đúng còn A  A là một mâu thuẫn. Ta có thể kiểm
tra qua bảng giá trị chân lý sau: Bảng 15 A A A  A A  A F T T F T F T F
1.2.3. Tương đương logic
Như trên đã xét, từ các mệnh đề sơ cấp ta có thể dùng các phép toán
logic để tạo ra các mệnh đề phức hợp. Nói chung, giá trị chân lý của các
mệnh đề phức hợp phụ thuộc vào giá trị chân lý của các mệnh đề sơ cấp cấu
thành nên nó và phụ thuộc vào cấu trúc các phép toán logic của mệnh đề
phức hợp đó. Có những công thức luôn nhận giá trị đúng cho dù các mệnh
đề sơ cấp nhận bất kỳ một giá trị nào. Ví dụ A  A là luôn đúng. Ta có định nghĩa sau:
Định nghĩa 3. Cho công thức S(A, B, C...). Nếu mệnh đề biểu thị bởi công
thức S luôn luôn đúng với mọi bộ giá trị của các mệnh đề A, B, C bất kỳ thì ta gọi
S(A, B, C..) là một luật.
Định nghĩa 4. Các mệnh đề p và q được gọi là tương đương logic nếu mệnh
đề p  q là một hằng đúng.
Ký hiệu p  q để chỉ rằng p và q là tương đương logic.
Chú ý: ký hiệu  không phải là một phép toán logic, vì p  q không phải là
một mệnh đề phức hợp, mà chỉ để phát biểu rằng p  q là hằng đúng.
Để chứng minh một công thức n biến là một luật, ta tính giá trị của
công thức trong 2n trường hợp (ứng với tất cả các giá trị khác nhau của các 16
biến). Nếu trong mọi trường hợp công thức luôn nhận giá trị T thì công thức
là một luật. Nếu trái lại, thì công thức đó không là luật.
Ví dụ 6. Chứng minh A  A là một luật. A A A  A F F T T T T
Ví dụ 7. Chứng minh A  A là một luật. A A A  A F T T T F T
Ta có định lý sau đây:
Định lý 1. Cho A, B, C là các mệnh đề bất kỳ. Khi đó ta có:
(1) Luật giao hoán: A  B  B  A; A  B  B  A .
(2) Luật kết hợp: (A  )
B  C  A  (B  C); (A  )
B  C  A  (B  C) .
(3) Luật phân phối:
(A  B)  C  (A  C)  (B  C);
(A  B)  C  (A  C)  (B  C).
(4) Luật luỹ đẳng: A  A  A; A  A  . A
(5) Luật hấp thụ: A  (A  )
B  A; A  (A  ) B  . A
(6) Các luật De Morgan: A  B  A  ;
B A  B  A  . B
(7) Luật hai lần phủ định: A  . A
(8) Luật chứng minh phản chứng thứ nhất: A  B  B  A
(9) Luật chứng minh phản chứng thứ hai: (A  )
B  A  B .
(10) Luật đồng nhất: A  T  A; A  F  . A
(11) Luật trội: A  F  F; A  T  T. 17
(12) Luật phủ định: A  A  T; A  A  F.
Các luật trên đều có thể chứng minh được bằng phương pháp lập bảng giá trị chân lý.
Chú ý: Các luật trên cho ta các cặp mệnh đề tương đương logic. Tương tự
như vậy, ta có bảng tương đương logic sau:
Bảng 16. Các tương đương logic Tên gọi
Tương đương Luật giao hoán
A  B  B  A
A  B  B  A Luật kết hợp
( A  B)  C  A  (B  C)
( A  B)  C  A  (B  C) Luật phân phối
( A  B)  C  ( A  C)  (B  C)
( A  B)  C  ( A  C)  (B  C) Luật lũy đẳng
A  A  A
A  A  A Luật hấp thụ
A  ( A  B)  A
A  ( A  B)  A Luật De Morgan
( A  B)  A  B
( A  B)  A  B
Luật phủ định kép A  . A Luật bù
A  A  F
A  A  T Luật đồng nhất
A  T  A
A  F  A Luật trội
A  F  F
A  T  T
Ta cũng có các tương đương logic có sự tham gia của các mệnh đề kéo theo. 18
Bảng 17. Một số tương đương logic
có sự tham gia của các mệnh đề kéo theo (tiếp)
A  B  B  A (Luật chứng minh phản chứng thứ nhất)
A  B  A  B (Luật chứng minh phản chứng thứ hai)
A  B  ( A  B)  (B  ) A
A  B  A  B
A  B  A  B
A  B  A  B
( A  B)  ( A  C)  A  (B  C)
( A  C)  (B  C)  ( A  B)  C
( A  B)  ( A  C)  A  (B  C)
( A  C)  (B  C)  ( A  B)  C
Ví dụ 7. Dựa vào các tương đương logic trên, hãy phát biểu mệnh đề phủ
định của mỗi mệnh đề sau, với điều kiện không đặt liên từ ‘không’ ở đầu câu.
a) Nếu 30 chia hết cho 6 thì 30 cũng chia hết cho 2.
b) Nếu hôm nay là thứ 5 thì trời nắng.
c) Hôm nay là thứ 5 và trời nắng.
d) Nếu hai tam giác bằng nhau thì hai đường trung tuyến tương ứng bằng nhau.
e) 1+1 = 2 hoặc đội nhà sẽ thắng.
f) Nếu trời mưa thì đội nhà sẽ thắng . Giải:
Phủ định của các mệnh đề trên được phát biểu như sau:
a) 30 chia hết cho 6 mà 30 không chia hết cho 2 (theo luật chứng minh phản chứng thứ hai) ;
b) Hôm nay là thứ 5 nhưng trời vẫn không nắng (theo luật chứng minh phản chứng thứ hai) ;
c) Hôm nay không là thứ 5 hoặc trời không nắng (luật De Morgan) ; 19