Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng
57 trang
2550
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- giao_trinh_logic_toan_phan_1_trinh_huy_hoang.pdf
Nội dung text: Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng
- Giáo trình Logic Toán MỤC LỤC BÀI 1: KHÁI QUÁT VỀ LOGÍC 3 1. Giới thiệu: 3 2. Định nghĩa logic học: 3 3. Sự hình thành và phát triển của logic học: 3 4. Ứng dụng của logic học: 4 5. Đôi nét về logic mờ 5 BÀI 2: LOGÍC MỆNH ĐỀ 9 1. Định nghĩa : 10 2. Phân tích : 10 3. Các phép toán logic cơ bản : 11 Bảng chân trị 12 4. Công thức trong đại số logic : 12 4.1/ Công thức : 12 4.2/ Công thức tương đương : 13 4.3/ Các qui tắc thay thế: 14 5. Hệ quả logic và tương đương logic: 17 6. Công thức đối ngẫu 17 7. Tính đầy đủ của một hệ các phép toán 17 7. Ứng dụng logic mệnh đề để vẽ mạch điện tử 18 BÀI 3: LOGÍC TÍNH TOÁN 24 1. Khái niệm: 24 1.1/ D ạng tuyển chuNn: 24 1.2/ Dạng hội chuNn: 24 2. Số logic : 25 2.1/ Định nghĩa : 25 2.2 Hàm logic: 26 2.2 Tương đương logic: 28 3. Thuật toán biểu diễn một công thức logic dưới dạng tuyển chu n: 28 4. Thuật toán biểu diễn một công thức logic dưới dạng hội chu n: 30 Bài 4: CÀI ĐẶT MIN H HỌA 33 1. Thuật toán tính số logic của một công thức: 33 2. Chương trình minh họa việc kiểm tra 2 công thức tương đương: 39 BÀI 5: SUY DIỄN LOGIC VÀ V N TỪ 42 1. Giới thiệu: 42 2. Định nghĩa qui tắc suy diễn: 42 3. Kiểm tra một qui tắc suy diễn: 44 4. Các qui tắc suy diễn cơ bản: 45 5. Các ví dụ áp dụng trong suy luận và chứng minh 48 6. Định nghĩa vị từ và ví dụ 50 6.1/ Ðịnh nghĩa: 50 6.2/ Các phép toán trên các vị từ 50 Gv: Trịnh Huy Hoàng Trang 1
- Giáo trình Logic Toán 6.3/ Qui tắc phủ định mệnh đề có lượng từ 51 6.4/ Một số qui tắc dùng trong suy luận: 53 BÀI 6: N GÔN N GỮ PROLOG 58 1. Tư duy lập trình và định nghĩa vấn đề trên Prolog 58 2. Các clause, cách giải thích các vấn đề trên Prolog 60 3. Thực thi chương trình. Đặt câu hỏi và nhận câu trả lời 62 4. Phép hợp nhất Cơ chế tìm câu trả lời của Prolog. 65 4.1/ Phép hợp nhất 65 4.2/ Cơ chế tìm câu trả lời của Prolog 66 5. Sự quay lui Khống chế số lượng lời giải Vị từ nhát cắt và fail 68 6. Lập trình đệ quy với Prolog 72 7. Danh sách trên Prolog 74 8. Lập trình đệ quy với danh sách trên Prolog 75 9. Danh sách hai chiều 78 BÀI 7: LOGIC MỜ 81 1. Một số khái niệm 81 1.1/ Tập mờ (Fuzzy Sets) 81 1.2/ Số mờ (Fuzzy N umbers) 85 1.3/ Số logic dạng hình khối 86 1.4/ Số logic dạng tam giác 87 1.5/ Số logic dạng hình thang 89 2. Áp dụng của logic mờ trong dự đoán 90 2.1/ Giá trị trung bình trong thống kê 90 2.2/ Các phép toán với số tam giác vá số hình thang 91 2.3/ Trung bình trong logic mờ 93 2.4/ Dự đoán bằng phương pháp Delphi kết hợp logic mờ 95 2.5/ Phương pháp Fuzzy Delphi có trọng số: 99 2.6/ Ứng dụng Fuzzy Pert trong việc quản lý các đề án 100 ĐỀ TÀI CỘN G ĐIỂM CUỐI KỲ 110 TÀI LIỆU THAM KHẢO 111 Gv: Trịnh Huy Hoàng Trang 2
- Giáo trình Logic Toán BÀI 1: KHÁI QUÁT VỀ LOGÍC 1. Giới thiệu: Logic là khoa học xuất hiện rất sớm trong lịch sử. N ó xuất hiện vào thế kỷ thứ IV trước công nguyên khi sự phát triển của khoa học nói riêng và tư duy nói chung đã đòi hỏi phải trả lời câu hỏi: làm thế nào để đảm bảo suy ra được kết luận đúng đắn, chân thực từ các tiền đề chân thực? 2. Định nghĩa logic học: Từ “Logic” có nguồn gốc từ Hy lạp là từ “Logos”, từ này có rất nhiều nghĩa trong đó có hai nghĩa thường dùng nhất là: Chỉ tính qui luật của sự tồn tại và phát triển của thế giới khách quan. Chỉ những qui luật đặc thù của tư duy. Khi ta nói “trái đất quay quanh mặt trời”, ta đã sử dụng nghĩa thứ nhất. Còn khi nói “anh ấy suy luận hợp logic”, ta đã sử dụng nghĩa thứ hai. 3. Sự hình thành và phát triển của logic học: N gười sáng lập ra logic học là nhà triết học Hy lạp vĩ đại Aristote(384 322 Tr.CN ). Ở thời cổ đại, logic học của Aristote được các học trò của ông tiếp tục phát triển sau khi ông mất nhưng học chỉ nêu ra một số qui tắc suy luận vớI tiền đề là phán đoán điều kiện và phán đoán lựa chọn nghiêm ngặt mà thôi. Các nhà triết học thuộc trường phái Megat và trường phái khắc kỷ đi xa hơn: họ nghiên cứu các quan hệ suy diễn. Để nghiên cứu vấn đề này, họ đưa ra quan hệ bao hàm (implication) và họ cũng đưa ra hình thức đầu tiên của định lý diễn dịch định lý làm cơ sở cho các phép chứng minh trong các hệ thống hình thức hóa: một suy luận được gọi là hợp logic khi và chỉ khi công thức biểu thị nó là một công thức hằng đúng. Các thành tựu quan trọng nhất ở thời La mã cổ đại là: hệ thống các thuật ngữ logic được sử dụng đến ngày nay: hình vuông logic (sau này được Boethius hoàn thiện); lý thuyết về tam đoạn luận phức hợp và tam đoạn luận với tiền đề là phán đoán quan hệ. Vào thời phục hưng, logic học truyền thống bị chỉ trích mạnh mẽ. Một số nhà tư tưởng tiến bộ của thời kỳ này buộc tội logic là chỗ dựa cho tư tưởng kinh viện. N hà triết học người Gv: Trịnh Huy Hoàng Trang 3
- Giáo trình Logic Toán Anh F. Bacon (1561 1626) cho rằng tam đoạn luận của Aristote hoàn toàn vô ích vì nó không cho phép tìm ra các thông tin mới từ các tiền đề đã có. Vậy nên khoa học sử dụng nó không thể phát hiện các qui luật mới thông qua việc nghiên cứu các sự kiện thực nghiệm đã biết. Ông xây dựng nên logic qui nạp mà về sau được một nhà triết học và logic học Anh khác là S.Mill (1806 – 1873) phát triển. Về phần logic diễn dịch thì mãi đến thế kỷ XVII mới được nhà toán học và triết học người Pháp R.Descates (1596 – 1650) thanh minh và bảo vệ. Ông muốn xây dựng nó thành phương pháp nhận thức tổng hợp. Công lao rất lớn trong việc phát triển logic diễn dịch vẫn thuộc về nhà toán học và logic học người Đức Leibniz (1646 – 1716). Ông được coi là người đầu tiên đặt nền tảng cho logic kí hiệu. Ông đưa ra tư tưởng sử dụng các kí hiệu và phương pháp toán học vào logic. Ông chỉ ra rằng khi sử dụng các kí hiệu thay cho lời nói, không những chúng ta làm cho tư tưởng được trở nên rõ ràng hơn, chính xác hơn mà còn làm cho tư tưởng trở nên đơn giản hơn. Ông muốn xây dựng logic học thành phép tính (calculus rationator) – ngôn ngữ nhân tạo tổng quát trong đó các suy luận được hình thức hoá giống như các phép tính được hình thức hoá trong đại số. Tư tưởng của Leibniz về sau được các nhà toán học và logic học J. Boole (1815 – 1864) và De Morgan phát triển, họ đã xây dựng các hệ đại số logic. Sự phát triển của logic hình thức trong thời hiện đại gắn liền với các tên tuổi của các nhà bác học lớn như G.Frege (1848 – 1925), Peano (1858 – 1932), B.Russel (1872 – 1970), . Quá trình phát triển của logic học kể từ thời Leibniz và đặc biệt là từ Russel trở về sau liên quan rất chặt chẽ đến toán học. N gày nay, logic hình thức bao gồm nhiều nhánh khác nhau như logic cổ điển, logic tình thái, logic thời gian, logic kiến thiết, logic relevant, logic không đơn điệu, logic mờ, 4. Ứng dụng của logic học: Cùng với sự phát triển của khoa học và công nghệ, logic học ngày càng được ứng dụng rộng rãi. Logic giúp giải quyết các vấn đề nan giải của toán học, của điều khiển học, của nhiều vấn đề trong khoa học máy tính N gười ta sử dụng logic vị từ để làm các ngôn ngữ lập trình cho trí tuệ nhân tạo (ví dụ ngôn ngữ PROLOG); ứng dụng logic mờ (Fuzzy logic) để phát triển công nghệ mờ Gv: Trịnh Huy Hoàng Trang 4
- Giáo trình Logic Toán 5. Đôi nét về logic mờ N gày nay khi nhìn lại lịch sử của logic mờ, người ta nhận thấy người đầu tiên đề cập tới logic mờ chính là Đức Phật (500 năm trước CN ). Triết lý Phật giáo dựa trên tư tưởng rằng thế giới đầy những mâu thuẫn, "sắc không không sắc", mọi thứ đề chứa một phần đối lập của nó. Bước chân vào mỗi ngôi chùa chúng ta đều thấy ở ngay gian trước là hai vị Thiện — Ác, là hình ảnh hai mặt tốt và xấu trong mỗi con người. N ói theo lý thuyết logic mờ nghĩa là sự vật có thể đồng thời là A và không A. Ở đây ta thấy có một mối liên hệ rõ ràng giữa triết lý Phật giáo và logic mờ hiện đại. Thuyết âm dương của người Trung Quốc cũng hàm chứa logic mờ! "Logo" bát quái thể hiện tư tưởng cốt yếu của thuyết: hình tròn thể hiện sự toàn vẹn của sự vật, trời đất; mỗi sự vật hiện tượng đều có hai mặt âm và dương đối lập nhau, cùng tồn tại, mặt này thịnh thì mặt kia suy (phần âm to ra thì phần dương nhỏ đi và ngược lại); dấu trắng trong phần đen và dấu đen trong phần trắng thể hiện trong âm có dương, trong dương có âm; dấu đen trong đầu to của phần trắng thể hiện khi dương cực thịnh thì chính là lúc trong lòng nó xuất hiện âm (và ngược lại). Sau đức Phật 200 năm, nhà bác học Hy lạp là Aristote phát triển logic nhị phân. Trái ngược với triết lý nhà Phật, Aristote cho rằng thế giới tạo bởi các đối nghịch, thí dụ nam nữ, nóng lạnh, khô ướt. Mọi thứ hoặc là A hoặc là không A, không thể cả hai. Logic nhị phân của Aristote trở thành nền tảng cho khoa học, nếu một thứ được chứng minh về mặt logic (nhị phân) thì nó được và vẫn sẽ được khoa học công nhận. Cho tới cuối thế kỷ 19, khi một nhà văn nhà toán học người Anh, Russel, phát hiện ra một nghịch lý của logic nhị phân . . . Russel (1872 1970), người khai sinh logic mờ Bá tước Bertrand Arthur William Russel sinh ra trong một gia đình quý tộc Anh năm 1872. Ông có một cuộc đời dài và đầy biến động. Thời trẻ tuổi, ông nghiên cứu toán học và sau đó, cùng với một nhà toán học khác, viết một cuốn sách về những cơ sở của toán học. Trong sách, họ dành cả một trang chỉ để chứng minh 1 + 1 = 2. Trong quá trình nghiên cứu, ông đã phát hiện ra một nghịch lý mà ngày nay gọi là nghịch lý tập của Russell : Trước hết chúng ta phân biệt hai loại tập: tập chứa chính nó và tập không chứa chính nó. Gv: Trịnh Huy Hoàng Trang 5
- Giáo trình Logic Toán Xét thí dụ: một quả lê thuộc tập các quả lê, nhưng tập các quả lê không thuộc về tập các quả lê do bản thân nó không phải là một quả lê! N ghĩa là tập các quả lê không phải là một thành viên của chính nó. Bây giờ ta xét một tập khác, tập mọi thứ không phải quả lê, gồm sách, chuột cống, hay cả tổng thống Bush nữa! Do trong tập này bạn tìm thấy mọi thứ không phải quả lê, nên bạn cũng có thể tìm thấy trong đó tập các quả lê và tập mọi thứ không phải quả lê ! N ghĩa là tập mọi thứ không phải quả lê là thành viên của chính nó. Russel đi sâu hơn và xem xét tập của mọi tập mà không chứa chính nó. Trong tập này, bạn sẽ tìm thấy tập các quả lê, tập các tổng thống, và nhiều tập khác nữa. N hưng bạn sẽ không tìm thấy tập mọi thứ không phải quả lê, do tập đó chứa chính nó và do vậy không thoả mãn tiêu chuNn đặt ra. Trong khi xem xét tập các tập không chứa chính nó này, Russell băn khoăn liệu nó có phải là một thành viên của chính nó? N ếu nó là một thành viên của chính nó, thì không thoả mãn định nghĩa. Mặt khác, nếu nó không phải là thành viên của chính nó, thì theo định nghĩa về tập đó, thì nó lại thoả mãn và như vậy nó là thành viên của chính nó! Vì vậy khi tìm ra nghịch lý này, Russell ngẫu nhiên chứng minh rằng logic nhị phân, mà ông nghĩ là cơ sở của toán học, không thể tự chứng minh nó. Tất nhiên ngày nay, chúng ta biết nghịch lý của Russell không phải là một trường hợp không giải được, nếu dùng logic mờ thì ta có câu trả lời ngay. Tuy nhiên, Russell không hề biết gì về logic mờ và đã vô cùng thất vọng với toán học. Ông từ bỏ toán học, những như thế không có nghĩa là ông đã dừng lại việc làm đảo lộn thế giới này. Trong suốt cuộc đời 97 năm, ông luôn truyền bá tư tưởng của mình; ông viết hàng tá sách, sách toán, triết luận, tiểu thuyết, thậm chí cả thứ sách lá cải nữa. Khi mất năm 1970, ông đã không chỉ khởi đầu một trang mới của logic học, mà còn đoạt cả một giải N obel văn học. Ông là một thí dụ điển hình cho thấy những người có tài năng lớn về toán học cũng có thể là những nhà văn lớn. Zadeh, cha đẻ của logic mờ hiện đại. N ăm 1964, giáo sư Zadeh bắt đầu suy nghĩ liệu có thứ logic tốt hơn nào dùng trong máy móc. Ông có ý tưởng liệu ta có thể bảo máy điều hoà làm việc nhanh hơn khi trời nóng lên, hay những vấn đề tương tự như thế, sẽ hiệu quả hơn việc đặt ra từng luật cho từng nhiệt Gv: Trịnh Huy Hoàng Trang 6
- Giáo trình Logic Toán độ. Đây chính là bước đi đầu tiên của logic mờ hiện đại như chúng ta hiểu và ứng dụng ngày nay. Phải mất một thời gian dài logic mờ mới được chấp nhận, mặc dù ngay từ đầu một số người đã rất quan tâm. Bên cạnh các kỹ sư, những nhà triết học, tâm lý học và xã hội học nhanh chóng áp dụng logic mờ vào ngành khoa học của mình. N ăm 1987, N hật Bản đã xây dựng hệ thống tàu điện ngầm đầu tiên làm việc với hệ thống điều khiển hoạt động tàu tự động dựa trên logic mờ. Đây là một thành công lớn và dẫn tới sự phát triển bùng nổ của logic mờ. Các trường đại học và các hãng công nghiệp đua nhau phát triển những ý tưởng mới. Đầu tiên là ở N hật Bản, do tôn giáo ở N hật thừa nhận rằng mọi thứ có thể chứa phần đối lập của chính nó, chứ không coi là một thứ "kinh khủng" như hầu hết những nơi khác trên thế giới. Và logic mờ cũng hứa hẹn đem lại nhiều tiền bạc cho các hãng công nghiệp, tất nhiên là điều này được đón chào. Logic mờ được công bố lần đầu tiên tại Mỹ vào năm 1965 do giáo sư Lotfi Zadeh. Kể từ đó, logic mờ đã có nhiều phát triển qua các chặng đường sau : phát minh ở Mỹ, áp dụng ở Châu Âu và đưa vào các sản phNm thương mại ở N hật. Ứng dụng đầu tiên của logic mờ vào công nghiệp được thực hiện ở Châu âu, khoảng sau năm 1970. Tại trường Queen Mary ở Luân Đôn – Anh, Ebrahim Mamdani dùng logic mờ để điều khiển một máy hơi nước mà trước đây ông ấy không thể điều khiển được bằng các kỹ thuật cổ điển. Và tại Đức, Hans Zimmermann dùng logic mờ cho các hệ ra quyết định. Liên tiếp sau đó, logic mờ được áp dụng vào các lĩnh vực khác như điều khiển lò xi măng, nhưng vẫn không được chấp nhận rộng rãi trong công nghiệp. Kể từ năm 1980, logic mờ đạt được nhiều thành công trong các ứng dụng ra quyết định và phân tích dữ liệu ở Châu âu. N hiều kỹ thuật logic mờ cao cấp được nghiên cứu và phát triển trong lĩnh vực này. Cảm hứng từ những ứng dụng của Châu Âu, các công ty của N hật bắt đầu dùng logic mờ vào kỹ thuật điều khiển từ năm 1980. N hưng do các phần cứng chuNn tính toán theo giải thuật logic mờ rất kém nên hầu hết các ứng dụng đều dùng các phần cứng chuyên về logic mờ. Một trong những ứng dụng dùng logic mờ đầu tiên tại đây là nhà máy xử lý nước của Fuji Electric vào năm 1983, hệ thống xe điện ngầm của Hitachi vào năm 1987. Gv: Trịnh Huy Hoàng Trang 7
- Giáo trình Logic Toán N hững thành công đầu tiên đã tạo ra nhiều quan tâm ở N hật. Có nhiều lý do để giải thích tại sao logic mờ được ưa chuộng. Thứ nhất, các kỹ sư N hật thường bắt đầu từ những giải pháp đơn giản, sau đó mới đi sâu vào vấn đề. Phù hợp với việc logic mờ cho phép tạo nhanh các bản mẫu rồi tiến đến việc tối ưu. Thứ hai, các hệ dùng logic mờ đơn giản và dễ hiểu. Sự “thông minh” của hệ không nằm trong các hệ phương trình vi phân hay mã nguồn. Cũng như việc các kỹ sư N hật thường làm việc theo tổ, đòi hỏi phải có một giải pháp để mọi người trong tổ đều hiểu được hành vi của hệ thống, cùng chia sẽ ý tưởng để tạo ra hệ. Logic mờ cung cấp cho họ một phương tiện rất minh bạch để thiết kế hệ thống. Và cũng do nền văn hóa, người N hật không quan tâm đến logic Boolean hay logic mờ; cũng như trong tiếng N hật , từ “mờ’ không mang nghĩa tiêu cực. Do đó, logic mờ được dùng nhiều trong các ứng dụng thuộc lĩnh vực điều khiển thông minh hay xử lý dữ liệu. Máy quay phim và máy chụp hình dùng logic mờ để chứa đựng sự chuyên môn của người nghệ sĩ nhiếp ảnh. Misubishi thông báo về chiếc xe đầu tiên trên thế giới dùng logic mờ trong điều khiển, cũng như nhiều hãng chế tạo xe khác của N hật dùng logic mờ trong một số thành phần. Trong lĩnh vực tự động hóa, Omron Corp. có khoảng 350 bằng phát minh về logic mờ. N goài ra, logic mờ cũng được dùng để tối ưu nhiều quá trình hóa học và sinh học. N ăm năm trôi qua, các tổ hợp Châu âu nhận ra rằng mình đã mất một kỹ thuật chủ chốt vào tay người N hật và từ đó họ đã nỗ lực hơn trong việc dùng logic mờ vào các ứng dụng của mình. Đến nay, có khoảng 200 sản phNm bán trên thị trường và vô số ứng dụng trong điều khiển quá trình – tự động hóa dùng logic mờ. Gv: Trịnh Huy Hoàng Trang 8
- Giáo trình Logic Toán BÀI 2: LOGÍC MỆ H ĐỀ Trong đời sống hàng ngày, người ta cần có những lý luận để từ các điều kiện được biết hay được giả định (các tiền đề premises) có thể suy ra các kết luận (conclusion) đúng. Hãy xét 2 lý luận sau : Lý luận (1) : Các tiền đề : + N ếu hôm nay trời đẹp thì tôi đi chơi. + N ếu tôi đi chơi thì hôm nay về trễ . Giả thiết : Hôm nay trời đẹp . Kết luận : Hôm nay tôi sẽ về trễ . Lý luận (2) : Các tiên đề : + N ếu hôm nay rạp hát không đóng cửa thi tôi sẽ xem phim. + N ếu tôi xem phim thì tôi sẽ không soạn kịp bài . Giả thiết : Hôm nay rạp hát không đóng cửa . Kết luận : Hôm nay tôi sẽ không soạn kịp bài. Hai lý luận trên là đúng và có cùng dạng lý luận. Chúng đúng vì có dạng lý luận đúng, bất kể ý nghĩa mà chúng đề cập đến. Còn lý luận sau : Lý luận (3) : Các tiền đề : + N ếu trời đẹp thì tôi đi chơi. + N ếu tôi đi chơi thì tôi sẽ về trễ. Giả thiết : Hôm nay tôi về trễ. Kết luận : Hôm nay trời đẹp . Là lý luận sai và mọi lý luận dạng như vậy đều sai . Logic toán học quan tâm đến việc phân tích các câu (sentences), các mệnh đề (propositions) và chứng minh với sự chú ý đến dạng (form) lược bỏ đi sự việc cụ thể. Gv: Trịnh Huy Hoàng Trang 9
- Giáo trình Logic Toán 1. Định nghĩa : Một phán đoán là một suy nghĩ muốn khẳng định hay phủ định một điều gì đó có tính chính đúng hoặc sai mà không thể vừa đúng lại vừa sai. Mệnh đề toán học là diễn đạt phán đoán bằng một câu ngữ pháp. Mệnh đề đúng có giá trị chân lý là 1, mệnh đề sai có giá trị chân lý là 0. Ví dụ : 4+3 > 2 là một mệnh đề có giá trị chân lý là 1 3+5 = 7 là một mệnh đề có giá trị chân lý là 0. Các phát biểu sau đây không phải là các mệnh đề (toán học) vì tính đúng sai của chúng không xác định: Ai đang đọc sách? (một câu hỏi) Cho n là một số nguyên dương. a là một số chính phương. 2. Phân tích : Phân tích lý luận (1) ta thấy nó sử dụng các mệnh đề cơ sở sau : • Hôm nay trời đẹp • Tôi đi chơi • Tôi sẽ về trễ. Mỗi mệnh đề (proposition) là một phát biểu đúng (true) hay sai (false). Biểu thị tượng trưng lần lượt các mệnh đề trên bởi các tên A, B, C, ta ghi lại dạng lý luận của (1) như sau : N ếu A thì B (4) N ếu B thì C Đây cũng là dạng lý luận của (2) . Có A kết luận được : C Thường một phát biểu sẻ gồm nhiều phát biểu nhỏ nối kết với nhau bằng các liên từ "và" , "hay" , "vì vậy " ,"kết quả là" Một mệnh đề đơn (simple proposition) là mệnh đề không chứa mệnh đề khác. Gv: Trịnh Huy Hoàng Trang 10
- Giáo trình Logic Toán Một mệnh đề phức (compound proposition) là mệnh đề được tạo thành từ hai hay nhiều mệnh đề đơn .Việc nối kết này được thực hiện bởi các liên từ logic. Ví dụ : Xét các mệnh đề sau đây. 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ột mệnh đề sơ cấp. N hưng q là một mệnh đề phức hợp, vì mệnh đề q được tạo thành từ hai mệnh đề "2 là một số nguyên tố" và "2 là một số lẻ" nhờ vào liên kết logic "và". 3. Các phép toán logic cơ bản : Các phép toán logic được định nghĩa bằng bảng chân trị (truth table). Bảng chân trị chỉ ra rõ ràng chân trị của mệnh đề phức hợp theo từng trường hợp của các chân trị của các mệnh đề sơ cấp tạo thành mệnh đề phức hợp. Bảng chân trị của các phép toán logic tất nhiên là phản ánh ngữ nghĩa tự nhiên của các từ liên kết tương ứng. Về mặt tự nhiên của ngôn ngữ, trong nhiều trường hợp cùng một từ nhưng có thể có nghĩa khác nhau trong những ngữ cảnh khác nhau. Do đó, bảng chân trị không thể diễn đạt mọi nghĩa có thể có của từ tương ứng với ký hiệu phép toán. Ðiều nầy cho thấy rằng đại số logic là rõ ràng hoàn chỉnh theo nghĩa là nó cho ta một hệ thống logic đáng tin cậy. Ðại số logic còn đặc biệt quan trọng trong việc thiết kế mạch cho máy tính. Bảng chân trị không chỉ dùng để kê ra sự liên hệ chân trị giữa mệnh đề phức hợp với chân trị của các mệnh đề sơ cấp cấu thành nó, mà bảng chân trị còn được dùng với mục đích rộng hơn: liệt kê sự liên hệ chân trị giữa các mệnh với các mệnh đề đơn giản hơn cấu thành chúng. Phép phủ định: ¬ (không) Độ ưu tiên của các toán tử logic . Phép hội: ∧ (và) ¬ Phép tuyển: ∨ (hay) ∧ , ∨ Phép kéo theo: → (kéo theo) →, ↔ Phép kéo theo 2 chiều: ↔ ( tương đương) Các toán tử cùng dòng có cùng độ ưu tiên. Ví dụ : ¬ p ∨ q có nghĩa là (( ¬ p) ∨ q). ¬ p ∨ q → r ∧ s có nghĩa là ((( ¬ p) ∨ q) → (r ∧ s)). Gv: Trịnh Huy Hoàng Trang 11
- Giáo trình Logic Toán ¬ p ∨ q ∧ r là không rõ ràng cần phải dùng các dấu ngoặc để chỉ rõ nghĩa. Xét hai mệnh đề x và y, khi đó ta có: Bảng chân trị của các phép toán mệnh đề Mệnh đề p Phủ định p Mệnh đề p Phép tuyển Phép hội Kéo theo Tương đương x ¬x y x ∨ y x ∧ y x → y x ↔ y 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 N goài ra ta còn có thêm một phép toán logic khác là “phép tuyển chọn” ứng với 2 mệnh đề sơ cấp p và q khác với phép tuyển đã cho ở trên được viết là p + q, hay p ⊕ q hay có thể biểu diễn như sau: Bảng chân trị x y x v y 1 1 0 1 0 1 0 1 1 0 0 0 4. Công thức trong đại số logic : 4.1/ Công th c : Từ các biến mệnh đề sơ cấp, nhờ các phép toán logic cơ bản, ta lập được các mệnh đề phức hợp, chúng được gọi là các công thức . Ta thường ký hiệu công thức bởi các chữ F, G, H, R, Ví dụ : F = ( (x ∧ y) → z) G = ( x→ (y → z) ) R = ( x ∧ y )∨ z ) Gv: Trịnh Huy Hoàng Trang 12
- Giáo trình Logic Toán 4.2/ Công th c tương đương : Hai công thức F và G gọi là tương đương logic nếu chúng nhận cùng giá trị chân lý với mọi giá trị của các biến mệnh đề sơ cấp. Ký hiệu F = G Ví dụ : F = ( (x ∧ y) → z) G = ( x → (y →z) ) (chứng minh như bài tập) thì F = G ¬ ¬ p ⇔ p (luật phủ định của phủ định) Các luật về phép phủ định: ¬ 1 ⇔ 0 ¬ 0 ⇔ 1 Luật giao hoán p ∧ q ⇔ q ∧ p p ∨ q ⇔ q ∨ p Luật kết hợp p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) Luật phân bố p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) ¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q Luật De Morgan ¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q p ∨ ¬ p ⇔ 1 Luật về phần tử bù p ∧ ¬ p ⇔ 0 Luật kéo theo p → q ⇔ ¬ p ∨ q Luật tương đương p ↔ q ⇔ (p → q) ∧ (q → p) Các luật đơn giản của phép tuyển Gv: Trịnh Huy Hoàng Trang 13
- Giáo trình Logic Toán p ∨ p ⇔ p (tính lũy đẳng của phép tuyển) p ∨ 1 ⇔ 1 (luật này còn được gọi là luật thống trị) p ∨ 0 ⇔ p (luật này còn được gọi là luật trung hòa) p ∨ (p ∧ q) ⇔ p (luật này còn được gọi là luật hấp thụ) Các luật đơn giản của phép hội p ∧ p ⇔ p (tính lũy đẳng của phép hội) p ∧ 1 ⇔ p (luật này còn được gọi là luật trung hòa) p ∧ 0 ⇔ 0 (luật này còn được gọi là luật thống trị) p ∧ (p ∨ q) ⇔ p (luật này còn được gọi là luật hấp thụ) Một số luật trong các luật trình bày ở trên có thể được suy ra từ các luật khác. Các công thức tương đương logic khác: x ⊕ y = (¬x∧y) ∨( x ∧¬y) x ⊕ y = y ⊕ x (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) x( y ⊕ z) = xy ⊕ xz ¬x ⊕ 1 = x x ⊕ 1 = ¬x x ⊕ x = 0 4.3/ Các qui t c thay th : Dưới đây là các qui tắc để cho ta có thể suy ra những biểu thức logic mới hay tìm ra các biểu thức logic tương đương với một biểu thức logic cho trước. Qui tắc 1: Gv: Trịnh Huy Hoàng Trang 14
- Giáo trình Logic Toán Trong một biểu thức logic E, nếu ta thay thế một biểu thức con bởi một biểu thức logic tương đương với biểu thức con đó thì ta sẽ được một biểu thức mới E' tương đương với biểu thức E. Ví dụ : Cho biểu thức logic E = q ∨¬ p. Thay thế q trong biểu thức E bởi biểu thức ¬ ¬ q (tương đương với q) ta được một biểu thức mới E' = ¬ ¬ q ∨¬ p. Theo qui tắc thay thế 1 ta có: q ∨ ¬ p ⇔ ¬ ¬ q ∨ ¬ p Qui tắc 2: Giả sử biểu thức logic E là một hằng đúng. N ếu ta thay thế một biến mệnh đề p bởi một biểu thức logic tuỳ ý thì ta sẽ được một biểu thức logic mới E' cũng là một hằng đúng. Ví dụ : Ta có biểu thức E(p,q) = (p → q) ⇔ ( ¬ p ∨ q) là một hằng đúng. Thay thế biến q trong biểu thức E bởi biểu thức q ∧ r ta được biểu thức logic mới: E'(p,q,r) = (p → (q ∧ r)) ⇔ ( ¬ p ∨ (q ∧ r)) Theo qui tắc thay thế 2 ta có biểu thức E'(p,q,r) cũng là một hằng đúng. Ví dụ áp dụng: Ví dụ 1: Chứng minh rằng (p → q) ⇔ ( ¬ q → ¬ p). Chứng minh : (p → q) ⇔ ¬ p ∨ q (luật kéo theo) ⇔ q ∨ ¬ p (luật giao hoán) ⇔ ¬ q ∨ ¬ p (luật phủ định) ⇔ ¬ q → ¬ p (luật kéo theo) Ví dụ 2: Chứng minh rằng biểu thức sau là một hằng đúng. ((p → q) ∧ p) → q Chứng minh. Gv: Trịnh Huy Hoàng Trang 15
- Giáo trình Logic Toán ((p → q) ∧ p) → q ⇔ ((p → q) ∧ p) ∨ q (luật kéo theo) ⇔ ( ¬ (p → q) ∨ ¬ p) ∨ q (luật De Morgan) ⇔ ¬ (p → q) ∨ ( ¬ p ∨ q) (luật kết hợp) ⇔ ¬ (p → q) ∨ (p → q) (luật kéo theo) ⇔ 1 (luật về phần tử bù) Vậy biểu thức ((p → q) ∧ p) → q là hằng đúng. Ví dụ 3: Chứng minh rằng biểu thức sau là một hằng đúng. p ∧ q → p Chứng minh. p ∧ q → p ⇔ ¬ ( p ∧ q) ∨ p (luật kéo theo) ⇔ ( ¬ p ∨ ¬ q) ∨ p (luật De Morgan) ⇔ ( ¬ q ∨ ¬ p) ∨ p (luật giao hoán) ⇔ ¬ q ∨ ( ¬ p ∨ p) (luật kết hợp) ⇔ ¬ q ∨ 1 (luật về phần tử bù) ⇔ 1 (luật đơn giản) Vậy mệnh đề p ∧ q → p là hằng đúng. Ví dụ 4: Chứng minh rằng biểu thức sau là một hằng đúng. p → p ∨ q Chứng minh. p → p ∨ q ⇔ ¬ p ∨ (p ∨ q) (luật kéo theo) ⇔ ( ¬ p ∨ p) ∨ q (luật kết hợp) ⇔ 1 ∨ q (luật về phần tử bù) Gv: Trịnh Huy Hoàng Trang 16
- Giáo trình Logic Toán ⇔ 1 (luật đơn giản) Vậy mệnh đề p → p ∨ q là hằng đúng. hận xét: Các ví dụ trên cho ta thấy một quan hệ khác giữa các mệnh đề phức hợp hay các mệnh đề : quan hệ " suy ra ". Khi mệnh đề p → q là hằng đúng, ta nói rằng p suy ra q (về mặt logic). Chúng ta sẽ dùng ký hiệu ⇒ để chỉ quan hệ "suy ra". Quan hệ suy ra nầy có tính truyền (hay bắc cầu), nhưng không có tính chất đối xứng. 5. Hệ quả logic và tương đương logic: N ếu công thức x → y =1 thì mệnh đề y được gọi là hệ quả logic của x. N ếu x là hệ quả logic của y và y và hệ quả logic của x thì x và y là tương đương logic. Ví dụ: Nếu F1 =( x → y )( ∧ yz → ) G1 =( x → z ) F2 =( xz → )( ∧ yz → ) G2 =( xy ∨ ) → z Khi đó G1 là hệ quả logic của F 1, G 2 và F 2 là tương đương logic 6. Công thức đối ngẫu Các phép toán logic hội và tuyển được gọi là hai phép toán đối ngẫu của nhau. Hai công thức F và G được gọi là đối ngẫu của nhau nếu công thức này suy ra từ công thức kia bằng cách thay mọi phép toán tuyển và hội bằng các phép toán đối ngẫu của nó. Ký hiệu công thức đối ngẫu của công thức F là F * * Ví dụ: N ếu F=( xx1 ∨ 2 ) ∧ x 3 thì F=( xx1 ∧ 2 ) ∨ x 3 7. Tính đầy đủ của một hệ các phép toán Một hệ thống ∑ bao gồm các phép toán logic được gọi là một hệ đầy đủ nếu mọi công thức logic đều có thể biểu diễn chỉ gồm các biến mệnh đề với chỉ các phép toán logic trong hệ. Các hệ sau là thể hiện tính đầy đủ của các phép toán: ={ ∧ , ∨ , ¬ } , ={ ∧ , ¬ } , ={ ∨ , ¬ } , ={, ∧ ⊕ , ¬ } ∑0 ∑1 ∑2 ∑3 Gv: Trịnh Huy Hoàng Trang 17
- Giáo trình Logic Toán 7. Ứng dụng logic mệnh đề để vẽ mạch điện tử Ta có các cổng cơ bản sau để thiết kế mạch: Cổng inverter thể hiện phép toán phủ định 1 biến ngõ nhập Cổng AN D thể hiện phép toán hội giữa các biến ngõ nhập. C ng OR th hi n phép toán tuy n gi a các bi n ngõ nh p Cổng XOR thể hiện cho phép toán tuyển chọn. F= xyz + xyz + xyz x xy y xyz z xyz+ x y z z x y z F x x y y x y z F = xyzt ’+ x’zt’ + x’yz’t + xz’ Gv: Trịnh Huy Hoàng Trang 18
- Giáo trình Logic Toán x y z t ⊕ ⊕ F = x’zt + xy’z’t + x’y’t + zt Gv: Trịnh Huy Hoàng Trang 19
- Giáo trình Logic Toán ⊕ ⊕ x xt t xt y’z⊕ z y’z y’ y F xy’ xy’z’ z‘ yz’ xy’z’ yz’t’⊕ t‘ yz’t’ BÀI TẬP 1. Cho biết những khẳng định nào dưới đây là mệnh đề: a. 2 là một số nguyên dương. b. 2k – 1 là một chẵn. c. Trời lạnh quá! Gv: Trịnh Huy Hoàng Trang 20
- Giáo trình Logic Toán d. N ếu biết trước là khó khăn sao anh còn cố gắng? 2. Hãy viết các mệnh đề đã cho dưới đây dưới dạng hình thức có sử dụng phép nối: A: “Bình biết chạy xe đạp” B: “Bình không biết chạy xe máy” a. Bình không chạy được xe máy nhưng chạy được xe đạp. b. Bình không biết chạy xe đạp lẫn xe gắn máy. c. N ếu Bình biết chạy xe máy thì biết chạy xe đạp. d. Bình biết chạy xe máy và xe đạp hay Bình chạy được xe máy mà không chạy được xe đạp. 3. Cho biết chân trị các mệnh đề sau: 2 a. x ≤ 1 và x +1 > 2 2 b. x−210 x +≤ → x = 1 2 c. x−210 x +≤ ↔ x = 0 2 d. x−430 x +≤→ x = 2 4. Lập bảng chân trị và chỉ ra các mệnh đề luôn đúng: a. m→( n → p ) b. [(mn→∨→ )( nm )]( → mn ∧ ) c. [m→ ( np → )]( → np → ) d. [m→∨ ( np )][( → mpnp →∨→ )( )] 5. Áp dụng các luật logic để rút gọn các mệnh đề và chỉ ra đâu là công thức hằng: a. (mn∨ ) ∨ [( mn ∧ ) ∨ n ] b. (m→ n ) ∧ [ n ∧ ( pn ∨ )] c. m∧( np ∨ )( ∧ mnp ∨∨ ) d. [[(mnp∧∧∨ ) ] [( mpp ∧∧ ) ]] ∨ n 6. Hãy F, F *, F* , F* (m ,, n p ,) q của các công thức sau: a. Fmn(,)(= mn ∨∨ )[( mn ∧∨ ) n ] Gv: Trịnh Huy Hoàng Trang 21
- Giáo trình Logic Toán b. Fmnp(,,)= mn ∧ [ n ∧ ( p ∨ n )] c. Fmnp(,,)(= pn ∨∨ )[( mp ∧ ) ∨ n ] d. Fmnpq(,,,)= mq ∧∨ ( n p )( ∧ m ∨∨ n p ) 7. Hãy biểu diễn các công thức sau dưới tất các hệ đầy đủ các phép toán: a. Gn=∨( m ∧ ( mnp ∨∨ )) b. F= n ⊕( m ∨ p ) c. Gm= ↔( n ⊕ p ) d. G=( nm ⊕ )( ↔ mp ∨ ) 8. Một xạ thủ bắn cung vào một mục tiêu, kết quả được thể hiện theo các mệnh đề sau: Pk = { Phát thứ k trúng đích} k = 1, 2, 3 Hãy giải thích các mệnh đề phức hợp sau: P∧ P ∧ P a. 1 2 3 b. P1∨ P 2 ∨ P 3 c. (PPP123∧∧ )( ∨ PPP1 ∧∧ 13 )( ∨ PPP 123 ∧∧ ) d. (PP12∧ )( ∨ PPP 123 ∧∧ )( ∨ PPP 123 ∧∧ ) 9. Cho 4 thí sinh A, B, C, D tham gia thi đấu xếp hạng. Kết quả xếp hạng như thế nào nếu: N gười thứ 1 dự đoán: B hạng nhì, C hạng ba. N gười thứ 2 dự đoán: A hạng nhì, C hạng tư. N gười thứ 3 dự đoán: B hạng nhất, D hạng nhì. Được biết là mỗi người có phần đúng phần sai. 10. Trong một chatroom, có tổng công 5 người An, Bình, Chinh, Dung, Yến đang thảo luận về đề tài logic toán với nhau trên mạng. Biết rằng: Hoặc An, hoặc Bình hoặc là cả 2 đang thảo luận. Hoặc Chinh, hoặc Dung, nhưng không phải cả 2 cùng thảo luận. Gv: Trịnh Huy Hoàng Trang 22
- Giáo trình Logic Toán N ếu Yến đang thảo luận thì Chinh cũng vậy. Dung và An, hoặc cả 2 cùng thảo luận, hoặc không ai thảo luận. N ếu Bình đang thảo luận thì Yến và An cũng vậy. Hãy giải thích xem nếu tất cả khẳng định trên đều đúng thì hiện tại ai đang thảo luận? 11. Để có đủ chứng cứ buộc tội đối với thủ phạm trong 1 vụ án, 1 cảnh sát điều tra đi thu thập bằng chứng tại một tòa biệt thự. Anh ta lần lượt hỏi một số người sau rồi có khẳng định sau: N ếu người quản gia nói thật thì người đầu bếp cũng vậy. N gười đầu bếp và người làm vườn không thể cùng nói thật. N gười làm vườn và người hầu không thể cùng nói dối. N ếu người làm vườn nói thật thì người đầu bếp nói dối. Hỏi có thể xác định rõ ai nói thật ai nói dối không? 12. Một sinh viên làm bài thi giữa kỳ môn logic toán gồm 5 câu hỏi trắc nghiệm đúng/sai trên máy tính, anh ta không biết trả lời chính xác cho bất kỳ câu hỏi nào nhưng biết rằng: Câu 1 và câu 5 cùng đòi hỏi trả lời trái ngược nhau. Câu 2 và câu 4 cần trả lời như nhau. Ít nhất 1 trong 2 câu hỏi đầu cần trả lời là khẳng định. N ếu câu 4 trả lời là “đúng” thì câu 5 phải trả lời là “sai”. Kinh nghiệm cho sinh viên này thấy rằng máy đặt câu hỏi cần trả lời “đúng” nhiều hơn “sai”. Hãy xác định các đáp án cần chọn lựa. 13. Sau khi thu gọn, hãy tìm các bộ nghiệm (x, y, z, t ) để các công thức hàm sau đạt giá là 0: a. F=[( ytxz ∨→→ )( xt yz )][ → xyt →∨ ( yzxt )] b. F=[( xyzt ∨→∨ ) ( yzxt )] → [( xzyt ∨→ ) ( yz ∨ xt )] c. F=[( xyz ∨→→→ yt ) ( xt y z )] [( yt∨ xz) → xz y ] Gv: Trịnh Huy Hoàng Trang 23
- Giáo trình Logic Toán BÀI 3: LOGÍC TÍ H TOÁ 1. Khái niệm: 1.1/ D ng tuy n chu n: Giả sử p 1, p 2, , p n là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p 2, , p n được gọi là một biểu thức hội cơ bản nếu nó có dạng sau: F = q 1 ∧∧∧ q 2 ∧∧∧ ∧∧∧ q n với q j = p j hoặc q j = ¬ p j (j = 1, , n). Ví dụ: Biểu thức x ∧ ¬ y ∧ z là một biểu thức hội cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức logic E(p 1, p 2, , p n) theo các biến mệnh đề p 1, p 2, , p n được nói là có dạng tuyển chuNn khi E có dạng : E = E 1 ∨ E 2 ∨ ∨ E m Trong đó mỗi biểu thức con E i đều có dạng tuyển chuNn theo các biến p 1, p 2, , p n. Ví dụ: Các biểu thức sau đây có dạng tuyển chuNn: E(x,y,z) = (x ∧ y ∧ z) ∨ ( ¬ x ∧ y ∧ z) ∨ (x ∧ y ∧ z) F(p 1,p 2,p 3,p 4) = (p 1 ∧ p 2 ∧ p 3 ∧ p 4) ∨ (p 1 ∧ ¬ p 2 ∧ p 3 ∧ ¬ p4) Ðịnh lý : Mọi biểu thức logic E(p 1, p 2, , p n) đều có thể viết dưới dạng tuyển chuNn 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 một 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 { E 1, E 2, , E m} sao cho biểu thức E(p 1, p 2, , p n) tương đương logic với biểu thức ( E1 ∨ E 2 ∨ ∨ E m.) 1.2/ D ng h i chu n: Giả sử p 1, p 2, , p n là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p 2, , p n được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau: F = q 1 ∨ q2 ∨ ∨ qn với q j = p j ho ặc q j = ¬ pj (j = 1, , n). Gv: Trịnh Huy Hoàng Trang 24
- Giáo trình Logic Toán Ví dụ:Biểu thức x ∨ ¬ y ∨ z là một biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức logic E(p 1, p 2, , p n) theo các biến mệnh đề p 1, p 2, , p n được nói là có dạng hội chuNn khi E có dạng: E = E 1 ∧ E2 ∧ ∧ Em Trong đó mỗi biểu thức con E i đều có dạng tuyển chuNn theo các biến p 1, p 2, , p n. Ví dụ: Các biểu thức sau đây có dạng hội chuNn: E(x,y,z) = (x ∨ ¬ y ∨ z) ∧ (¬ x ∨ y ∨ z) ∧ (x ∨ y ∨ z) F(p 1,p 2,p 3,p 4) = (p 1 ∨ p2 ∨ p 3 ∨ p4) ∧ (p 1 ∨ ¬ p2 ∨ p3 ∨ ¬ p 4) Ðịnh lý : Mọi biểu thức logic E(p 1, p 2, , p n) đều có thể viết dưới dạng hội chuNn 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 một 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 { E 1, E 2, , E m} sao cho biểu thức E(p 1, p 2, , p n) tương đương logic với biểu thức (E 1 ∧ E2 ∧ ∧ Em.) 2. Số logic : 2.1/ Đ nh nghĩa : ♦ Số logic của một biến nguyên thủy A , kí hiệu #A là chân trị của biến đó xét trong không gian logic N chiều mà A tham gia biểu diễn. ♦ Ví dụ: Xét trong không gian một biến thì #A =(1,0) Trong không gian 2 biến: AB. A B 1 1 1 0 Ma trận biểu diễn: [A,B] 0 1 0 0 Xét trong không gian 3 chiều: ABC Gv: Trịnh Huy Hoàng Trang 25
- Giáo trình Logic Toán A B C 1 1 1 1 1 0 1 0 1 Ma trận biểu diễn: [A,B,C] 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 ♦ Mỗi không gian logic được biểu diễn bởi một số biến riêng. Sự tổ hợp các biến ra một giá trị của các biến nằm trong không gian logic. 2.2 Hàm logic: ♦ Hàm logic là một liên kết giữa các biến logic bởi các phép toán logic như: hợp (+), giao (.), phủ định ( ), kéo theo ( →), tương đương ( ↔), . ♦ N hận xét: Một hàm logic có một số logic tương ứng: f(A,B, ) ≅ #f(A,B, ) Ví dụ: trong không gian 3 biến cho f(A,B,C) = AB + BC A B C AB BC f(A,B,C) 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1 Vậy #f(A,B,C) = #( AB + BC ) = 00011101 ♦ Hệ quả: Số logic của một biến hợp ( tổng) bằng tổng các số logic thành phần: #(A+B) = #A + #B hay #(A ∨ B) = #A ∨ #B Gv: Trịnh Huy Hoàng Trang 26
- Giáo trình Logic Toán Số logic của một tích bằng tích các số logic thành phần: #(A . B) = #A . #B hay #(A ∧ B) = #A ∧ #B # A = # A #(A ⇒ B) = #A ⇒ #B ♦ Ví dụ minh họa: chứng minh phát biểu sau ((A →B) ∧(B →C) ∧A) →C Có nhiều cách để chứng minh phát biểu trên, chẳng hạn: Cách 1: dùng bảng chân trị A B C A→B B→C (A →B) ∧(B →C) ∧A ((A →B) ∧(B →C) ∧A) →C 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 N hận xét: cách này khá phức tạp nếu số các phép kết nối logic lớn Cách 2: dùng các luật logic của Vương hạo (1962) để chứng minh. Cách này không dễ. Cách 3: tính số logic của phát biểu, nếu số logic bằng I(1111 1) thì phát biểu trên là đúng. Ta có #(((A →B) ∧(B →C) ∧A) →C) = (#(A →B) ∧#(B →C) ∧#A) →#C = ((#A →#B) ∧(#B →#C) ∧#A) →#C = ((01010101 →00110011) ∧(00110011 →00001111) ∧01010101) →00001111 = (10111011 ∧11001111 ∧01010101) → 00001111 = 11111111 = I ⇒ phát triển trên là đúng. Gv: Trịnh Huy Hoàng Trang 27
- Giáo trình Logic Toán 2.2 Tương đương logic: Hai công thức logic f(A 1,A 2, ,A m) và g(A 1,A 2, ,A n) được gọi là tương đương khi và chỉ khi #f = #g xét trên không gian lớn nhất chứa f và g. Ví dụ: cho biết f(A,B) = A →B và g(A,B,C) = (C ∨ C)∧ (B → A) có tương đương nhau hay không? • Ta có: #f = 10111011. Ở đây f cũng phải được xét trong không gian 3 biến vì nó cần phải so sánh với g có 3 biến • #g = 10111011 Do #f = #g ⇒ f và g là tương đương nhau. 3. Thuật toán biểu diễn một công thức logic dưới dạng tuyển chu n: Số logic của tích các biến: Gọi C i là số logic của một tổ hợp các biến sao cho C i chỉ nhận giá trị 1 tại cột i, các cột còn lại nhận giá trị 0. Ví dụ: trong không gian 3 biến A,B,C; ta có biểu diễn như sau: ABC 1 0 0 0 0 0 0 0 C1 ABC 0 1 0 0 0 0 0 0 C 2 ABC 0 0 1 0 0 0 0 0 C 3 ABC 0 0 0 1 0 0 0 0 C 4 ABC 0 0 0 0 1 0 0 0 C 5 ABC 0 0 0 0 0 1 0 0 C 6 ABC 0 0 0 0 0 0 1 0 C 7 ABC 0 0 0 0 0 0 0 1 C8 Thuật toán: cho công thức logic f(A 1,A 2, ,A n). n Bước 1: Tính #f. Giả sử #f = (i 1,i 2, ,i 2 ) k := 1 F := {} Bước 2: Nếu i k = 1 thì F := F + C k. k := k+1 Bước 3: nếu k ≤ 2 n thì quay lại bước 2, ngược lại dừng. Gv: Trịnh Huy Hoàng Trang 28
- Giáo trình Logic Toán Khi thuật toán dừng, F chính là biểu diễn dạng tuyển chuNn của công thức f đã cho ban đầu. Ví dụ minh họa: Tìm dạng tuyển chuNn của công thức logic sau: f(A,B,C) = (A →→→B) ∧∧∧ (B →→→C) Bước 1: #f = 10001011 k := 1 F := {} Bước 2: do i k = 1 ⇒ F := F + ABC (C 1); k:= k+1 = 2 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 0 ⇒ F = ABC ; k:= k+1 = 3 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 0 ⇒ F = ABC ; k:= k+1 = 4 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 0 ⇒ F = ABC ; k:= k+1 = 5 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 1 ⇒ F:= ABC + ABC k:= k+1 = 6 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 0 ⇒ F = ABC + ABC k:= k+1 = 7 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 1 ⇒ F = ABC + ABC + ABC k := k+1 = 8 Bước 3: do k ≤ 8(2 3) quay lại bước 2 Bước 2: do i k = 1 ⇒ F = ABC + ABC + ABC + ABC Gv: Trịnh Huy Hoàng Trang 29
- Giáo trình Logic Toán ⇒ Tuyển chuNn của f là F = ABC + ABC + ABC + ABC 4. Thuật toán biểu diễn một công thức logic dưới dạng hội chu n: Tích của các tổng : xét số 0 ở vị trí nào thì đưa tổ hợp tại vị trí đó vào. Các tổ hợp hội chuNn của 3 biển A,B,C: ABC+ + 11 1 1 1 110 D 8 ABC+ + 11 1 1 1 101 D 7 ABC+ + 1 1 11 1 011 D 6 ABC+ + 1 1 11 0 111 D 5 ABC+ + 1 1 10 1111 D 4 ABC+ + 11 01 1111 D 3 ABC+ + 1 0 11 1111 D 2 ABC+ + 01 11 11 11 D 1 Thuật toán xác định hội chu n: Cho công thức logic f(A 1,A 2, ,A n) n Bước 1: Tính #f. Giả sử #f = (i 1,i 2, ,i 2 ) k := 1; F := {} Bước 2: Nếu i k = 0 thì F := F + D k k := k+1 Bước 3: nếu k ≤ 2 n thì quay lại bước 2; ngược lại dừng. Khi thuật toán dừng, F chính là dạng hội chuNn của công thức đã cho ban đầu. Ví dụ minh họa: Tìm công thức hội chuNn của công thức sau: f(A,B,C) = (A ∧B) ∨ B ∨ C Bước 1: Tính #f = 11011111 k:=1 F := {} Bước 2: do i k = 1 ⇒ F = {} k := k+1 = 2 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Gv: Trịnh Huy Hoàng Trang 30
- Giáo trình Logic Toán Bước 2: do i k = 1 ⇒ F = {} k := k+1 = 3 Bước 3: do k ≤ 23 ⇒ quay lại bước 2 Bước 2: do i k = 0 ⇒ F = D 3 = ( A+ B + C ) k := k+1 = 4 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Bước 2: do C k = 0 ⇒ F = D 3 = ( A+ B + C ) k := k+1 = 5 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Bước 2: do C k = 1 ⇒ F = ( A+ B + C ) k := k+1 = 6 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Bước 2: do C k = 1 ⇒ F = ( A+ B + C ) k := k+1 = 7 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Bước 2: do C k = 1 ⇒ F = ( A+ B + C ) k := k+1 = 8 Bước 3: do k ≤ 2 3 ⇒ quay lại bước 2 Bước 2: do C k = 1 ⇒ F = ( A+ B + C ) k:= k+1 = 9 Bước 3: k > 2 3 ⇒ dừng Vậy: dạng hội chuNn của công thức ban đầu là F = A+ B + C N hận xét: tuỳ theo số logic của công thức f có số lượng số 0 hay số 1 ít hơn mà ta có thể đưa về dạng hội chuNn hay tuyển chuNn. Gv: Trịnh Huy Hoàng Trang 31
- Giáo trình Logic Toán Bài tập Chuyển tất cả các công thức sau thành dạng chuyển tuyển, chuNn hội, chuyển tuyển hoàn toàn và chuNn hội hoàn toàn: 1. (mn∨ )( ∧ n → p ) 2. [m→ ( np → )]( → np → ) 3. n∨( m ∧ ( mnp ∨∨ )) 4. [(mn→∨→ )( nm )]( → mn ∧ ) 5. (mn∨ ) ∨ [( mn ∧ ) ∨ n ] 6. (m→ n ) ∧ [ n ∧ ( pn ∨ )] 7. m∧( np ∨ )( ∧ mnp ∨∨ ) 8. [[(mnp∧∧∨ ) ] [( mpp ∧∧ ) ]] ∨ n 9. [m→∨ ( np )][( → mpnp →∨→ )( )] 10. n⊕( m ∨ p ) 11. m↔( n ⊕ p ) 12. (nm⊕ )( ↔ mp ∨ ) Gv: Trịnh Huy Hoàng Trang 32
- Giáo trình Logic Toán Bài 4: CÀI ĐẶT MI H HỌA 1. Thuật toán tính số logic của một công thức: Input: Chuỗi s chứa công thức logic f (có tối đa 5 biến logic) Output: Số logic tương ứng của f Thuật toán: unsigned long Tinh_sologic(char *s) { Bước 1: loại bỏ ngoặc thừa của chuỗi s Bước 2: sử dụng biểu thức hậu tố Balan để tìm phép toán chính của biểu thức s, các phép toán cùng cấp ưu tiên sẽ được tính từ trái sang phải. Giả sử vị trí của phép toán chính là t(t= 1 có nghĩa là biểu thức không còn phép toán chính) • N ếu t= 1: return #s • N gược lại: qua bước 3 Bước 3: Gọi s1 và s2 là 2 biểu thức bên trái và bên phải của phép toán chính của s t1 = Tinh_sologic(s1); t2 = Tinh_sologic(s2); switch(phép toán chính) { case '&': return t1 & t2; case 'v': return t1 v t2; case ' >': return t1 > t2; } } Chương trình hoàn chỉnh: #include #include #include #include Gv: Trịnh Huy Hoàng Trang 33
- Giáo trình Logic Toán #define MAX 8 int SOLG[MAX],n; char MD[8][5];// moi menh de co toi da 4 ki tu(gia su) /* */ char* Bo_ngoac_2phia_thua(char *s) { int l = strlen(s); if(s[0] != '(' || s[l 1] != ')') return s; int d = 1; for(int i = 1; i < l 1; i++) { if(s[i]=='(') d++; else if(s[i]==')') d ; if(d==0) return s; } char s1[100]; strcpy(s1,s+1); s1[l 2] = 0; return s1; } /* */ int Ktra_chua_ngoac_2phia(char *s) { int l = strlen(s); if(s[0] != '(' || s[l 1] != ')') return 0; int d = 1; for(int i = 1; i < l 1; i++) { if(s[i]=='(') d++; else if(s[i]==')') d ; Gv: Trịnh Huy Hoàng Trang 34
- Giáo trình Logic Toán if(d==0) return 0; } return 1; } /* */ void Chuan_hoa(char *mde) { for(int i=strlen(mde) 1;i>=0;i ) if(mde[i]==32) strcpy(mde+i,mde+i+1); } /* */ int Tim_phep_toan_chinh(char *bt) { int s[100]; int t = 0, l = strlen(bt); for(int i = 0 ; i &v()",bt[i])) { if(bt[i]==')' ) { while(bt[s[t 1]]!='(') t ; t ; } else s[t++] = i; } if(t==0) return 1; return s[t 1]; } /* */ void SX(char md[][5],int n) { Gv: Trịnh Huy Hoàng Trang 35
- Giáo trình Logic Toán for(int i = 0; i 0) { char s[5]; strcpy(s,md[i]); strcpy(md[i],md[j]); strcpy(md[j],s); } } /* */ int Tim_vt(int n,char *s) { for(int j = 0; j (",s[i]) && strchr("&v >(",s[i 1])) cs = i; else if((i==l || strchr("&v )",s[i])) && !strchr("&v >()",s[i 1])) { char s1[5]; strncpy(s1,s+cs,i cs); s1[i cs] = 0; if(Tim_vt(n,s1)== 1) strcpy(MD[n++],s1); Gv: Trịnh Huy Hoàng Trang 36
- Giáo trình Logic Toán } SX(MD,n);//sắp xếp để bảo đảm tính tăng của các biến nguyên thủy //điều này không quan trọng nhưng để khỏi bị hiểu nhầm return n; } /* */ void Tinh_mang_so( ) { int *bit; int hmn = pow(2,n); bit = new int [hmn]; bit[0]=1; for(int i = 1;i < hmn ; i++) bit[i] = bit[i 1]<<1; for( i = 0; i< n ; i++) { int t = 0,hmi = pow(2,i); for(int j = 0; j < hmn; j+= (hmi<<1)) for(int k = j; k < hmi+j;k++) t |= bit[k]; SOLG[i] = t; } delete []bit; } /* */ unsigned long Tinh_sologic(char *s) { s = Bo_ngoac_2phia_thua(s); int t = Tim_phep_toan_chinh(s); if(t== 1) if(s[0]==' ') return ~SOLG[Tim_vt(n,s+1)]; else return SOLG[Tim_vt(n,s)]; Gv: Trịnh Huy Hoàng Trang 37
- Giáo trình Logic Toán char ch = s[t]; char s1[100],s2[100]; strcpy(s1,s); strcpy(s2,s+t+1); s1[t] = 0; if(s1[t 1]==' ') s1[t 1] = 0; unsigned long t1 = Tinh_sologic(s1); unsigned long t2 = Tinh_sologic(s2); switch(ch) { case '&': return t1 & t2; case 'v': return t1 | t2; case '>': return (~t1)|t2; } return t; } /* */ void Xuat_so_np(long t) { int haimu = pow(2,n); for(int i=haimu 1;i>=0;i ) printf("%d",(t>>i)&1); } void main() { clrscr(); char s[100]; printf("N hap cong thuc logic(cac toan tu logic la ,&,v, >):"); gets(s); Chuan_hoa(s); n = Tim_cac_mde(s); Gv: Trịnh Huy Hoàng Trang 38
- Giáo trình Logic Toán Tinh_mang_so(); long t = Tinh_sologic(s); printf("So logic cua %s la:",s); Xuat_so_np(t); getch(); } 2. Chương trình minh họa việc kiểm tra 2 công thức tương đương: Thuật toán: Input: 2 công thức logic f(A 1,A 2, ,A m) và g(A 1,A2, ,A n) Ouput: True nếu f tương đương với g False nếu f không tương đương với g Phương pháp: Tính #f Tính #g nếu #f = #g thì kết quả:=True ngược lại kết quả:=False Chương trình hoàn chỉnh: #include #include #include #include #define MAX 8 int SOLG[MAX],n; char MD[8][5];// moi menh de co toi da 4 ki tu(gia su) Các hàm này đã được /* */ cài đặt trong phần tính char* Bo_ngoac_2phia_thua(char *s); số logic. /* */ int Ktra_chua_ngoac_2phia(char *s); /* */ void Chuan_hoa(char *mde); /* */ int Tim_phep_toan_chinh(char *bt); Gv: Trịnh Huy Hoàng Trang 39
- Giáo trình Logic Toán /* */ int Tim_vt(int n,char *s); /* */ void SX(char md[][5],int n); /* */ void Tinh_mang_so(); /* */ unsigned long Tinh_sologic(char *s); /* */ void Xuat_so_np(long t); /* */ void Xuat_cac_md(char md[][5],int n); /* */ void Tim_cac_mde(char *s,int &n) { int cs = 0; int l = strlen(s); for(int i = 1; i (",s[i]) && strchr("&v >(",s[i 1])) cs = i; else if((i==l || strchr("&v )",s[i])) && !strchr("&v >()",s[i 1])) { char s1[5]; strncpy(s1,s+cs,i cs); s1[i cs] = 0; if(Tim_vt(n,s1)== 1) strcpy(MD[n++],s1); } } Hàm tìm các mệnh đề có thay đổi so với phần tính số logic vì các mệnh đề ở đây là hội của các mệnh đề của f và g. void main() { clrscr(); Gv: Trịnh Huy Hoàng Trang 40
- Giáo trình Logic Toán char s1[100],s2[100]; printf("Chuong trinh so sanh 2 cong thuc logic tuong duong?\n"); printf("N hap cong thuc logic f(cac toan tu logic la ,&,v, >):"); gets(s1); printf("N hap cong thuc logic g(cac toan tu logic la ,&,v, >):"); gets(s2); Chuan_hoa(s1); Chuan_hoa(s2); n = 0; Tim_cac_mde(s1,n); Tim_cac_mde(s2,n); SX(MD,n);//khong quan trong nhung de bi hieu lam nen phai sap xep Tinh_mang_so(); unsigned long t1 = Tinh_sologic(s1); printf(" So logic cua f"); Xuat_cac_md(MD,n); printf(" = %s la:",s1); Xuat_so_np(t1); unsigned long t2 = Tinh_sologic(s2); printf("\n So logic cua g"); Xuat_cac_md(MD,n); printf(" = %s la:",s2); Xuat_so_np(t2); if(t1==t2){ printf("\nCong thuc f"); Xuat_cac_md(MD,n); printf(" = %s tuong duong voi cong thuc g",s1); Xuat_cac_md(MD,n); printf(" = %s",s2); } else printf("\nHai menh de khong tuong duong"); getch(); } Gv: Trịnh Huy Hoàng Trang 41
- Giáo trình Logic Toán BÀI 5: SUY DIỄ LOGIC VÀ VN TỪ 1. Giới thiệu: Một hệ thống toán học bao gồm các tiên đề, các định nghĩa, và những khái niệm không được định nghĩa. Các tiên đề được giả định là đúng. Các định nghĩa được sử dụng để xây dựng hay đưa ra những khái niệm mới trên cơ sở những khái niệm đã có. Một số thuật ngữ, khái niệm sẽ không được định nghĩa rõ ràng nhưng được ngầm định nghĩa bởi các tiên đề. Trong một hệ toán học chúng ta có thể suy ra được các định lý. Một định lý là một khẳng định được chứng minh là đúng. Một số loại định lý được xem là các bổ đề, các hệ quả. Một lập luận (hay lý luận) chỉ ra được tính đúng đắn của mệnh đề phát biểu trong định lý được gọi là chứng minh . Logic là một công cụ cho việc phân tích các chứng minh. Trong phần nầy chúng ta sẽ đề cập đến việc xây dựng một chứng minh toán học. Ðể thực hiện được một lập luận hay một chứng minh chúng ta cần hiểu các kỹ thuật và các công cụ được sử dụng để xây dựng một chứng minh. Thông thường một chứng minh sẽ bao gồm nhiều bước suy luận mà ở mỗi bước ta đi đến (hay suy ra) một sự khẳng định mới từ những khẳng định đã biết. Ví dụ về một bước suy diễn: 1/ N ếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì danh sách L là rỗng nên theo sự khẳng định trên ta không thể lấy ra phần tử đầu trong danh sách. 2/ N ếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì ta không thể lấy ra phần tử đầu trong danh sách L nên danh sách L là danh sách rỗng. Trong 2 suy diễn ở ví dụ trên thì suy diễn 2/ là một suy luận đúng, nhưng suy diễn 1/ là không đúng. Vậy làm thế nào để biết được một suy diễn là đúng hay sai ? Một bước suy luận như thế phải dựa trên một qui tắc suy diễn hợp lý nào đó để nó được xem là một suy luận đúng. Các qui tắc suy diễn là cơ sở để tay biết được một lập luận hay một chứng minh là đúng hay sai. Trong các mục tiếp theo chúng ta sẽ xem xét chi tiết hơn về các qui tắc suy diễn và giới thiệu một số qui tắc suy dễn cơ bản thường được dùng trong việc suy luận và chứng minh. 2. Định nghĩa qui tắc suy diễn: Tuy có nhiều kỹ thuật, nhiều phương pháp chứng minh khác nhau, nhưng trong chứng minh trong toán học ta thường thấy những lý luận dẫn xuất có dạng: N u p 1 và p 2 và . . . và p n thì q. Gv: Trịnh Huy Hoàng Trang 42
- Giáo trình Logic Toán Dạng lý luận nầy được xem là hợp lý (được chấp nhận là đúng) khi ta có biểu thức (p 1 ∧ p 2 ∧ . . . ∧ p n) → q là hằng đúng. Ta gọi dạng lý luận trên là một luật suy diễn và người ta cũng thường viết luật suy diễn trên theo các cách sau đây : Cách 1 : Biểu thức hằng đúng (p 1 ∧ p 2 ∧ . . . ∧ p n) → q ⇔ 1 Cách 2 : Dòng suy diễn (p 1 ∧ p 2 ∧ . . . ∧ p n) ⇒ q Cách 3 : Mô hình suy diễn p1 . . . . pn ∴∴∴ q Các biểu thức logic p 1, p 2, . . ., p n trong luật suy diễn trên được gọi là giả thiết (hay tiền đề), và biểu thức q được gọi là kết luận. Ở đây chúng ta cũng cần lưu ý rằng lý luận trên đúng không có nghĩa là ta có q đúng và cũng không khẳng định rằng p 1, p 2, . . ., p n đều đúng. Lý luận chỉ muốn khẳng định rằng nếu như ta có p 1, p 2, . . ., p n là đúng thì ta sẽ có q cũng phải đúng. Ví dụ : Giả sử p và q là các biến logic. Xác định xem mô hình sau đây có phải là một luật suy diễn hay không? p → q p ∴ q Giải: Lập bảng chân trị ta có: p q p→ q (p → q) ∧ p ((p → q) ∧ p) → q 1 1 1 1 1 1 0 0 0 1 Gv: Trịnh Huy Hoàng Trang 43
- Giáo trình Logic Toán 0 1 1 0 1 0 0 1 0 1 Bảng chân trị cho thấy biểu thức ((p → q) ∧ p) → q là hằng đúng. Do đó, mô hình suy luận trên đúng là một luật suy diễn. Thật ra, ta chỉ cần nhìn vào các cột chân trị của p, q, và p→ q trong bảng chân trị là ta có thể kết luận được rồi, vì từ bảng chân trị trên ta thấy rằng nếu các giả thiết p → q và p đúng (có giá trị bằng 1) thì kết luận q cũng đúng. Ta có thể khẳng định được mô hình suy luận trên là một luật suy diễn mà không cần lập bảng chân trị. Giả sử p → q và p đúng. Khi đó q phải đúng, bởi vì nếu ngược lại (q sai) thì p cũng phải sai (sẽ mâu thuNn với giả thiết). 3. Kiểm tra một qui tắc suy diễn: Ðể kiểm tra một qui tắc suy diễn xem có đúng hay không ta có thể sử dụng một trong các phương pháp sau đây: Phương pháp 1: Lập bảng chân trị. Theo phương pháp này, ta sẽ thiết lập biểu thức logic tương ứng của qui tắc suy diễn và lặp bảng chân trị của biểu thức đó để xem nó có phải là hằng đúng hay không. Trong trường hợp biểu thức logic là hằng đúng thì ta kết luận qui tắc suy diễn là đúng. N gược lại, ta kết luận qui tắc suy diễn là sai. Ví dụ: Ðể kiểm tra qui tắc suy diễn sau: (p → q) ∧ p ⇒ q ta lập bảng chân trị của biểu thức logic ((p → q) ∧ p) → q theo 2 biến logic p và q. Từ bảng chân trị ta sẽ thấy biểu thức logic là hằng đúng và ta đi đến kết luận rằng qui tắc suy diễn trên là đúng. Phương pháp 2: Chứng minh bằng cách sử dụng các luật logic. Theo phương pháp nầy, ta sẽ thiết lập biểu thức logic tương ứng của qui tắc suy diễn và chứng minh biểu thức là hằng đúng bằng cách áp dụng các luật logic và các qui tắc thay thế. Ví dụ: Kiểm tra qui tắc suy diễn sau đây: (p → q) ∧ p ⇒ q Giải: Thực hiện phép biến đổi tương đương logic, ta có: Gv: Trịnh Huy Hoàng Trang 44
- Giáo trình Logic Toán ( (p → q) ∧ p ) → q ⇔ ( ( ¬ p ∨ q) ∧ p ) → q (luật kéo theo) ⇔ ( ( ¬ p ∧ p) ∨ (q ∧ p) ) → q (luật phân bố) ⇔ ( 0 ∨ (q ∧ p) ) → q (luật về phần tử bù) ⇔ (q ∧ p) → q (luật đơn giản) ⇔ ¬ (q ∧ p) ∨ q (luật kéo theo) ⇔ ( ¬ q ∨ ¬ p) ∨ q (luật De Morgan) ⇔ ( ¬ q ∨ q ) ∨ ¬ p (luật giao hoán và kết hợp) ⇔ 1 ∨ ¬ p (luật về phần tử bù) ⇔ 1 (luật đơn giản) Vậy biểu thức ((p → q) ∧ p) → q là hằng đúng, nên ta có qui tắc suy diễn (p → q) ∧ p ⇒ q là đúng. Ghi chú: Ðể kiểm tra một qui tắc suy diễn ta còn có thể kết hợp 2 phương pháp trên và áp dụng cả những luật suy diễn đã biết trước. 4. Các qui tắc suy diễn cơ bản: Trong mục nầy chúng ta nêu lên một số qui tắc suy diễn (đúng) thường được sử dụng mà ta có thể kiểm tra chúng bằng các phương pháp đã được trình bày trong mục trước. Stt Qui tắc Mô hình suy diễn p → q Qui tắc khẳng định (Modus Ponens) p 1 [(p → q) ∧ p] → q = 1 −−−−−− ∴ q Qui tắc phủ định (Modus Tollens) p → q 2 ¬ q [(p → q) ∧ q → ¬ p] = 1 Gv: Trịnh Huy Hoàng Trang 45
- Giáo trình Logic Toán −−−−−− ∴ ¬ p p → q Tam đoạn luận giả thiết (Symlogism) q → r 3 [(p → q) ∧ (q → r) → (p → r)] = 1 −−−−− ∴ p → r Tam đoạn luận tuyển ¬ p [¬ p ∧ (p ∨ q)] → q = 1 p ∧ q 3 −−−−− ∴ q p ∧ q Qui tắc nối liền 4 −−−−− p ∧ q → p = 1 ∴ q (p → q) Qui tắc phản đảo 5 −−−−−−−−− (p → q) = (¬q → ¬ p) ∴ (¬q → ¬ p) Qui tắc chứng minh bằng phản chứng Qui tắc nầy cho phép ta chứng minh (p →¬ q ) → 0 thay cho p → q. N ói cách 4 [(p → q) → (p → ¬ q)] → 0 khác, nếu ta thêm giả thiết phụ vào tiền đề p mà chứng minh được có sự mâu thuẫn thì ta có thể kết luận q từ tiền đề p. p1 → q p → q Qui tắc chứng minh theo trường hợp 2 . . . (p → q) ∧ (p → q) ∧ . . . ∧ (p → q) ⇒ 5 1 2 n (p 1 ∨ p 2 ∨ . . . ∨ p n) → q pn → q −−−−−−−−−−− ∴∴∴∴ (p 1 ∨ p 2 ∨ . . . ∨ p n) → q Kiểm tra một phép suy luận cụ thể Gv: Trịnh Huy Hoàng Trang 46
- Giáo trình Logic Toán Ðể kiểm tra một suy luận cụ thể là đúng hay không, tức là có "hợp logic" hay không, ta có thể căn cứ vào các qui tắc suy diễn (luật suy diễn). Phép suy luận cụ thể có thể được xem như sự suy diễn trên các mệnh đề phức hợp. Các mệnh đề sơ cấp cụ thể (mà chân trị có thể đúng hoặc sai) trong phép suy luận sẽ được trừu tượng hóa (thay thế) bởi các biến logic. N hư thế phép suy luận được trừu tượng hóa thành một qui tắc suy diễn trên các biểu thức logic mà ta có thể kiểm tra xem qui tắc suy diễn là đúng hay không. Ðây chính là biện pháp để ta biết được một suy luận cụ thể là đúng hay sai. Ví dụ 1 : Xét sự suy luận sau đây: N ếu một danh sách L là khác rỗng thì ta có thể lấy ra phần tử đầu trong danh sách.Vì ta không thể lấy ra phần tử đầu trong danh sách L nên danh sách L là danh sách rỗng. Trong phép suy luận, ta có các mệnh đề sơ cấp "danh sách L là khác rỗng", "ta có thể lấy ra phần tử đầu (từ danh sách L)". Thay thế các mệnh đề sơ cấp nầy bởi các biến logic p, q tương ứng thì phép suy luận cụ thể trên sẽ được trừu tượng hóa thành một suy diễn trên các biểu thức logic như sau: p → q ¬q −−−−−−−− ∴ ¬ p Mô hình suy diễn nầy chính là qui tắc suy diễn Modus Tollens, đã được biết là đúng. Vậy phép suy luận trên là suy luận đúng. Ví dụ 2 : Xét xem suy luận sau đây có đúng hay không? N ếu là số hữu tĩ thì phương trình m 2 = 2n 2 có nghiệm nguyên dương m, n. N ếu phương trình m 2 = 2n 2 có nghiệm nguyên dương m và n thì ta có mâu thuẫn. Vậy là số vô tĩ. Trừu tượng hóa các mệnh đề sơ cấp " là số hữu tĩ", " phương trình m 2 = 2n 2 có nghiệm nguyên dương m, n " thành các biến logic p, q tương ứng thì phép suy luận trên có dạng mộ hình suy diễn p → q q → 0 −−−−−−− Gv: Trịnh Huy Hoàng Trang 47
- Giáo trình Logic Toán ∴∴∴ ¬ p Kiểm tra mô hình suy diễn nầy ta sẽ thấy là đúng. N hư thế phép suy luận trên là đúng. 5. Các ví dụ áp dụng trong suy luận và chứng minh Dưới đây ta trình bày chứng minh của một số mệnh đề mà không nêu lên một cách chi tiết về các qui tắc suy diễn đã được áp dụng. N gười đọc có thể tìm thấy các qui tắc suy diễn được sử dụng trong chứng minh một cách dễ dàng. Mệnh đề 1: Với mọi số nguyên n, n 3 + 2n chia hết cho 3. Suy nghĩ đầu tiên là ta thấy rằng không thể tìm thấy một thừa số 3 trong biểu thức n 3 + 2n. N hưng khi phân tích ra thừa số thì n 3 + 2n = n(n 2 + 2). Phát biểu "n 3 + 2n chia hết cho 3" sẽ đúng nếu n là bội số của 3. Còn các trường hợp khác thì sao?. Ta thử phương pháp phân chứng. Chứng minh: Ta có n 3 + 2n = n(n 2 + 2), và số tự nhiên n có một trong 3 dạng ứng với 3 trường hợp dưới đây: Trường hợp 1 : n = 3k, với k là một số nguyên. n 3 + 2n = 3k(9k 2 + 2) chia hết cho 3. Trường hợp 2 : n = 3k+1, với k là một số nguyên. n 3 + 2n = (3k+1)((3k+1) 2 + 2) = (3k+1)(9k 2 +6k+3) = (3k+1)3(3k 2 +2k+1) chia hết cho 3. Trường hợp 3: n = 3k+2, với k là một số nguyên. n 3 + 2n = (3k+2)((3k+2) 2 + 2) = (3k+1)(9k 2 +12k+6) = (3k+1)3(3k 2 +4k+2) chia hết cho 3. Trong mọi trường hợp (có thể có) ta đều có n 3 + 2n đều chia hết cho 3. Vậy ta kết luận n 3 + 2n chia hết cho 3 đối với mọi số nguyên n. Gv: Trịnh Huy Hoàng Trang 48
- Giáo trình Logic Toán hận xét : Chứng minh trên có thể được trình bày ngắn gọn hơn bằng cách sử dụng phép đồng dư modulo 3. Mệnh đề 2: N ếu n 2 là một số chẳn thì n cũng là một số chẳn. Suy nghĩ: Giả sử n 2 = 2k (là số chẳn). Ta thấy khó suy ra n là số chẳn. N ếu biết thông tin gì đó về n thì suy ra điều gì đó về n 2 thì dễ hơn. Ta thử phương pháp phản chứng. Chứng minh: Ta hãy chứng minh mệnh đề "N ếu n lẻ thì n 2 lẻ". Cho n là một số lẻ, ta có n = 2k+1 (k là một số nguyên). Do đó n 2 = (2k+1) 2 = 4k 2+4k+1 là một số lẻ. Mệnh đề trong cặp nháy kép là đúng nên mệnh đề phản đảo của nó cũng đúng. Vậy, nếu n2 là một số chẳn thì n cũng là một số chẳn. Mệnh đề 3: N ếu p > 3 và p nguyên tố thì p 2 1 chia hết cho 3. Chứng minh: Ta có (p 1), p, (p+1) là 3 số nguyên liên tiếp. Trong 3 số nguyên nầy có một số chia hết cho 3. N hưng số đó không phải là p vì p là số nguyên tố lớn hơn 3. Do đó (p 1) chia hết cho 3 hoặc (p+1) chia hết cho 3. Suy ra (p 1)(p+1) chia hết cho 3, tức là p 2 1 chia hết cho 3. Mệnh đề 4: Số lượng các số nguyên tố là vô hạn. Chứng minh: Giả sử phát biểu trong mệnh đề là sai. Tức là chỉ có một số hữu hạn, k, số nguyên tố (dương). Ký hiệu k số nguyên tố là p 1, p 2, . . ., p k, ở đây k là số nguyên dương. Ðặt n = p 1p2 . . . p k + 1. Số n lớn hớn tất cả k số nguyên tố nên n không nguyên tố. Do đó, từ định lý cơ bản của số học , n phải có một ước số nguyên tố p. p phải là một trong k số nguyên tố. Do đó p | ( p 1p2 . . . p k). Suy ra p | (n p 1p2 . . . p k), hay p | 1. N hư thế, ta có p là một số nguyên tố và p | 1. Ðiều nầy là không thể, hay nói cách khác, ta có một mâu thuNn. Vậy, Số lượng các số nguyên tố là vô hạn. Gv: Trịnh Huy Hoàng Trang 49
- Giáo trình Logic Toán 6. Định nghĩa vị từ và ví dụ 6.1/ Ð nh nghĩa: Một vị từ là một phát biểu p(x, y, ) phụ thuộc theo các biến x, y, lấy giá trị trên các miền xác định A, B, nào đó. Khi thay thế các biến trong vị từ bởi các giá trị cụ thể a, b, thuộc các miền xác định thì ta được một mệnh đề p(a, b, ) có chân trị đúng hoặc sai. Gọi B là tập hợp gồm có hai giá trị : Sai (ký hiệu bởi 0), và Ðúng (ký hiệu bởi 1). Một vị từ p(x, y, ) Ví dụ1: P(n) ≡ "n là một số nguyên tố" là một vị từ trên tập hợp các số tự nhiên (hoặc trên tập hợp các số nguyên). Ta có thể thấy rằng: P(1) = 0, tức là P(1) ≡ "1 là một số nguyên tố" là một mệnh đề sai. P(2) = 1, tức là P(2) ≡ "2 là một số nguyên tố" là một mệnh đề đúng. P(12) = 0, tức là P(12) ≡ "12 là một số nguyên tố" là một mệnh đề sai. P(17) = 1, tức là P(17) ≡ "17 là một số nguyên tố" là một mệnh đề đúng. Vị từ "n là một số nguyên tố" có thể được xem là một ánh xạ đi từ tập hợp các số tự nhiên vào tập hợp Boole B: P : → B Ví dụ2: p(m,n) ≡ "m là một ước số của n", với m và n là các biến số tự nhiên, cho ta một vị từ theo 2 biến m và n thuộc tập hợp các số tự nhiên. Ta có: p(2,4) = 1, p(3,4) = 0. 6.2/ Các phép toán trên các v t Cho p(x, y, ) là một vị từ theo các biến x, y, . Phủ định của p, ký hiệu là ¬p, là một vị từ mà khi thay các biến x, y, bởi các phần tử cụ thể a, b, tương ứng thì ta được mệnh đề ¬(p(a, b, )). N ói một cách khác, vị từ ¬p được định nghĩa bởi: (¬ p) (x, y, ) = ¬(p(x, y, )) Gv: Trịnh Huy Hoàng Trang 50
- Giáo trình Logic Toán Cho p(x, y, ) và q(x, y, ) là các vị từ theo các biến x, y, . Phép hội của p và q, ký hiệu là p → q, là một vị từ mà khi thay các biến x, y, bởi các phần tử cụ thể a, b, tương ứng thì ta được mệnh đề p(a, b, ) → q(a, b, ). N ói một cách khác, vị từ p ?q được định nghĩa bởi: (p ∧ q) (x, y, ) = p (x, y, ) ∧ q (x, y, ) Một cách tương tự, các phép toán tuyển, kéo theo và tương đương của 2 vị từ p và q có thể được định nghĩa như sau: (p ∨ q) (x, y, ) = p (x, y, ) ∨ q (x, y, ) (p → q) (x, y, ) = p (x, y, ) → q (x, y, ) (p ↔ q) (x, y, ) = p (x, y, ) ↔ q (x, y, ) 6.3/ Qui t c ph đ nh m nh đ có lư ng t Dựa vào cách xác định chân trị của các mệnh đề có lượng từ theo ngữ nghĩa tự nhiên của các phát biểu, ta có các qui tắc phủ định mệnh đề có lượng từ sau đây: ¬ ( ∀ x : P(x)) ≡ ∃ x : ¬ P(x) (1) ¬ ( ∃ x : P(x)) ≡ ∀ x : ¬ P(x) (2) Ví dụ 1 : Tìm phủ định của mệnh đề "tồn tại một số thực x sao cho x 2 < 0". Ðặt P(x) ≡ "x2 < 0". Mệnh đề đã cho được viết dưới dạng ký hiệu như sau: ∃ x : P(x) Áp dụng luật phủ định mệnh đề có lượng từ, ta có mệnh đề phủ định cần tìm có dạng : ∀ x : ¬ P(x). Vậy mệnh đề phủ định là: "Với mọi số thực x, x 2 ≥ 0". Ghi chú: Từ các qui tắc trên ta có thể nói chung về qui tắc phủ định mệnh đề có lượng từ như sau: N ếu trong một mệnh đề có lượng từ ta thay thế lượng từ ∀ bởi lượng từ ∃ , lượng từ ∃ bởi lượng từ ∀ , và biểu thức vị từ được thay thế bởi phủ định của nó thì ta sẽ được mệnh đề phủ định của mệnh đề có lượng từ ban đầu. Qui tắc nầy cũng áp dụng được cho các mệnh đề với nhiều lượng từ. Ví dụ 2 : Cho p(x, y, z) là một vị từ phụ thuộc vào biến bộ ba (x,y,z) ∈ AxBxC. Miền xác định là tích Ðê Cat của 3 tập hợp A, B, C. Trong trường hợp nầy ta nói vị từ p là một vị từ theo 3 biến Gv: Trịnh Huy Hoàng Trang 51
- Giáo trình Logic Toán x, y, z. Miền xác định tương ứng của 3 biến nầy là A, B, C. Hãy tìm phủ định của mệnh đề sau: ∀ x ∈ A, ∃ y ∈ B, ∃ z ∈ C : p(x,y,z) Theo qui tắc chung ta có : ¬ ( ∀ x ∈ A, ∃ y ∈ B, ∃ z ∈ C : p(x,y,z)) ≡ ∃ x ∈ A, ∀ y ∈ B, ∀ z ∈ C : ¬ p(x,y,z) Thật ra nếu thực hiện từng bước theo các qui tắc (1) và (2) ta cũng đạt được mệnh đề phủ định như trên: ¬ ( ∀ x ∈ A, ∃ y ∈ B, ∃ z ∈ C : p(x,y,z)) ≡ ∃ x ∈ A, ¬ ( ∃ y ∈ B, ∃ z ∈ C : p(x,y,z)) ≡ ∃ x ∈ A, ∀ y ∈ B, ¬ ( ∃ z ∈ C : p(x,y,z)) ≡ ∃ x ∈ A, ∀ y ∈ B, ∀ z ∈ C : ¬ p(x,y,z) Ví dụ 3 : Với một hàm số f xác định ở một lân cận của điểm a ∈ R (a là một số thực), ta có định nghĩa sự liên tục của f tại a như sau : f liên tục tại a nếu và chỉ nếu cho một số dương tùy ý, ta có một số dương δ sao cho | x a | 0, ∃ δ > 0 : ( ∀ x : | x a | 0, ∀ δ > 0 : ¬ ( ∀ x : | x a | 0, ∀ δ > 0 : ( ∃ x : ¬ (| x a | 0, ∀ δ > 0 : ( ∃ x : | x a | < δ ∧ ¬ ( | f(x) f(a) | < ε )) Gv: Trịnh Huy Hoàng Trang 52
- Giáo trình Logic Toán ≡ ∃ ε > 0, ∀ δ > 0 : ( ∃ x : | x a | 0, ∀ δ > 0, ∃ x : | x a | < δ ∧ | f(x) f(a) | ≥ ε N hư vậy ta có thể phát biểu mệnh đề phủ định như sau:: "Tồn tại một số dương ε sao cho ứng với số dương δ tùy ý có một số thực x thoả điều kiện | x a | < δ và | f(x) f(a) | ≥ ε ". Như v y ta có th phát bi u m nh đ ph đ nh như sau: "T n t i m t s dương ε sao cho ng v i m i s dương δ tùy ý ta có m t s th c x th a đi u ki n | x a | < δ và | f(x) f(a) | ≥ ε ". 6.4/ M t s qui t c dùng trong suy lu n: Thay đổi thứ tự lượng từ hóa của 2 biến Cho một vị từ p(x, y) theo 2 biến x, y. N ếu lượng từ hóa cả 2 biến x, y trong đó ta lượng từ hóa biến y trước và lượng từ hóa biến x sau thì sẽ được 4 mệnh sau đây: ∀ x, ∀ y : p(x,y) ∃ x, ∀ y : p(x,y) ∀ x, ∀ y : p(x,y) ∀ x, ∀ y : p(x,y) Tương tự ta cũng có 4 mệnh đề lượng từ hóa từ vị từ p(x, y) trong đó ta lượng từ hóa biến x trước và lượng từ hóa biến y sau: ∀ y, ∀ x : p(x,y) ∃ y, ∀ x : p(x,y) ∀ y, ∀ x : p(x,y) ∀ y, ∀ x : p(x,y) Ðịnh lý dưới đây cho ta một số tính chất liên quan đến thứ tự của việc lượng từ hóa các biến trong các mệnh đề có lượng từ. Ðịnh lý : Giả sử p(x, y) là một vị từ theo 2 biến x, y thì các mệnh đề sau là đúng (∀ x, ∀ y : p(x,y) ) ↔ ( ∀ y, ∀ x : p(x,y) ) (∃ x, ∃ y : p(x,y) ) ↔ ( ∃ y, ∃ x : p(x,y) ) Gv: Trịnh Huy Hoàng Trang 53
- Giáo trình Logic Toán (∃ x, ∀ y : p(x,y) ) → ( ∀ y, ∃ x : p(x,y) ) Qui tắc đặc biệt hóa phổ dụng Qui tắc: Giả sử một mệnh đề có lượng từ trong đó biến x với miền xác định là A, được lượng từ hóa và bị buộc bởi lượng từ phổ dụng ∀ , và mệnh đề là đúng. Khi đó nếu thay thế x bởi a ∈ A thì ta sẽ được một mệnh đề đúng. Ví dụ1: Biết rằng phát biểu "mọi số nguyên tố lớn hơn 2 đều là số lẻ" là một mệnh đề đúng. Cho a là một số nguyên tố lớn hơn 2 (cố định nhưng tùy ý). Hãy chứng minh rằng a là một số lẻ. Giải: Ðặt p(n) ≡ "n là số nguyên tố lớn hơn 2", và q(n) ≡ "n là số lẻ". Ta có p(n) và q(n) là các vị từ theo biến số tự nhiên n, và ta có mệnh đề đúng sau đây: ∀ n : p(n) → q(n) Theo qui tắc trên ta suy ra p(a) → q(a) = 1. Theo giả thiết ta cũng có p(a) = 1. Suy ra q(a) = 1 (qui tắc suy diễn Modus Ponens). Vậy ta có mệnh đề "a là một số lẻ" là đúng. Ví dụ 2 : Trong các định lý Toán học ta thường thấy các khẳng định là các mệnh đề lượng từ hóa phổ dụng. Ví dụ như các trường hợp bằng nhau của 2 tam giác bất kỳ. Khi áp dụng ta sẽ đặc biệt hóa cho 2 tam giác cụ thể. Qui tắc tổng quát hóa phổ dụng Qui tắc: N ếu ta thay thế biến x trong vị từ P(x) bởi một phần tử a cố định nhưng tùy ý thộc miền xác định của biến x mà mệnh đề nhận được có chân trị là đúng, tức là P(a) = 1, thì mệnh đề lượng từ hóa ∀ x : P(x) là một mệnh đề đúng. hận xét : N ếu xem vị từ P(x) như là một hàm lấy giá trị Bool trên miền xác định A của biến x thì ta có mệnh đề lượng từ hóa ∀ x : P(x) là một mệnh đề đúng khi và chỉ khi P là hàm hằng 1. Gv: Trịnh Huy Hoàng Trang 54
- Giáo trình Logic Toán Từ các qui tắc trên ta có thể chứng minh được một số tính chất suy diễn được phát biểu trong các mệnh đề sau đây: Mệnh đề 1 : Cho p(x) và q(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A), và a là một phần tử cố định tùy ý thuộc A. Khi ấy ta có qui tắc suy diễn sau đây: ∀ x : p(x) → q(x) p(a) −−−−−−−−−−−−−−−−− ∴∴∴ q(a) Mệnh đề 2 : Cho p(x), q(x) và r(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A). Ta có qui tắc suy diễn sau đây: ∀ x : p(x) → q(x) ∀ x : q(x) → r(x) −−−−−−−−−−−−−− ∴∴∴ ∀ x : p(x) → r(x) BÀI TẬP 1. Tìm chân trị của các vị từ ứng với các giá trị tương ứng sau: m(x): “x > 2” n(x): “ x 1 lẻ ” p(x): “ x < 0 ” a. m(2) b. n(2 10 ) c. m(− 1) ∨ n (3) d. m(0)∧ n (4) e. [m (7)→ n (1)] ∨ p (1) f. [m (−∨ 1) n ( − 1)] → p ( − 1) g. [m (3)↔ n (3)] ∨ p (3) h. m(1)→ [ n (1) → p (1)] 2. Xác định chân trị của vị từ sau: p(x,y) : “x là ước của y ” Gv: Trịnh Huy Hoàng Trang 55
- Giáo trình Logic Toán a. p(1,5) b. p(3,4) c. ∀x, p (, x x ) d. ∀y, p (, y y ) e. ∀x ∃ y, pxy (, ) f. ∀y ∃ x, pxy (, ) g. ∀∀xypxy,((,) ∧ pyx (,)) →= ( x y ) h. ∀∀∀xyzpxy,((,) ∧ pyz (,)) → pxz (,) 3. Xác định chân trị của các vị từ sau: m(x,y) : “2x > y 1” n(x,y): “y ( xz )] g. ∀∈∃∈∃∈xℤ, y ℤ , z ℤ ,[(2 xyz − =∧ )(2 xyz ++= 0)] h. ∃∈∀∈∃∈xRyRzRx, , ,[(2 = y 2 − z 2 ) ∧≥ ( xz )] 5. Xác định các suy luận đúng và cho biết qui tắc suy diễn đã được áp dụng: a. Mọi người đều quan tâm đến học vấn đều gia sức học tập để tích lũy kiến thức. Huy chẳng cố gắng học tập. Suy ra là Huy không quan tâm đến học vấn. b. N ếu Bình đi chơi thì Bình không học logic toán. N ếu Bình không học bài thì sẽ thi trượt môn logic toán. Mà Bình lại đi chơi nên Bình thi trượt môn logic toán. c. Mọi sinh viên lười học đều không chịu đến lớp học thường xuyên. Tân đã đến lớp học thường xuyên. Vì thế Vân là sinh viên không lười học. d. Minh khẳng định rằng, nếu không được lĩnh lương dạy kèm thì phải kiếm việc khác làm. Mặt khác, nếu Minh nghỉ dạy kèm mà mẹ Minh không gửi tiền trợ cấp thì phải bán máy tính để đóng tiền học anh văn buổi tối. Cuối cùng Minh vẫn được trả lương nên Minh vẫn được tiếp tục học anh văn vào buổi tối. Gv: Trịnh Huy Hoàng Trang 56
- Giáo trình Logic Toán e. Mọi sinh viên nghiêm túc đều không nộp bài chưa làm xong. Minh không nộp bài chưa làm xong. Vậy Minh là sinh viên nghiêm túc. f. Mọi công dân quan tâm đến môi trường đều bỏ riêng túi nhựa bỏ đi vào một chỗ. Hùng không quan tâm đến môi trường. Vậy Hùng không bỏ riêng túi nhưa bỏ đi vào một chỗ. 6. Hãy phủ định rồi sau đó rút gọn các mệnh đề lượng từ hóa sau: a. {(∀xpx )[()12 → px ()]( ∧∀ xpxpx )[ 34 () ∨ ()]( ∧∀ xpxpx )[() 13 ∨ ()]} → [ px 24 () → px ()] b. (∀xpx )[21 () → px ()]( ∧∀ xpxpx )[ 23 () ∨ ()]( ∧∀ xpx )[ 43 () → px ()]} →∀ ( xpxpx )[ 24 () ∨ ()] c. {(∀xpx )[21 () → px ()]( ∧∀ xpx )[ 23 () → px ()]( ∧∀ xpxpx )[ 43 () ∨ ()]}( ∨∀ xpxpx )[( 24 () ∧ ()] 7. Hãy chứng minh các công thức : n( n+ 1)(2 n + 1) a. 02+ 1 2 ++ n 2 = 6 n2( n + 1) 2 b. 03+ 1 3 ++ n 3 = 4 nn(+ 1)( n + 2)( n + 3) c. 1.2.3+ 2.3.4 ++ n .( n + 1)( n += 2) 4 1 1 1n ( n + 3) d. +++ = 1.2.3 2.3.4nn .(++ 1)( n 2) 4( n ++ 1)( n 2) 8. Tìm nguyên dương n . Biết rằng trong 3 mệnh đề sau chỉ có duy nhất 1 mệnh đề sai : A = {n+51 là một số chính phương} B = {n có số tận cùng là 1} C = {n 38 là một số chính phương} 9. Cho 2 số nguyên dương m và n. Biết rằng trong số 4 mệnh đề sau chỉ có duy nhất 1 mệnh đề sai: A = {m = 2n + 5} B = {m + 1 chia hết cho n} C = {m + n chia hết cho 3} D = {m + 7n là số nguyên tố} a. Hãy chỉ ra mệnh đề sai trong các mệnh đề trên. b. Hãy tìm tất các cặp (m, n) thõa các mệnh đề đúng còn lại. 10. Một giải cờ vua có n kỳ thủ tham dự thi đấu vòng tròn 1 lượt tính điểm. Trong mỗi trận thì người thắng được 2 điểm, hòa được 1 điểm, thua thì không có điểm. Các kỳ thủ có cùng số điểm sẽ xét thêm các chỉ số phụ nào đó. Khi kết thúc thì kỳ thủ hạng 1 được 8 điểm, kỳ thủ hạng 2 được 6 điểm và kỳ thủ hạng 3 được 5 điểm. Các kỳ thủ còn lại có số điểm khác nhau. Hãy cho biết có bao nhiêu kỳ thủ tham dự, và số điểm của họ bao nhiêu? Gv: Trịnh Huy Hoàng Trang 57
