Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 82 TOÁN RỦI RẠC ONG ĐỤNG TRONG TIN HỌC Ví dụ 2 Đối ngẳu của công thức A X V Y A z là công thức A X A Y V Z. Định íý l Giả sử A X x2 Xn là một cõng thức trong dó X i 1 n là các mênh đề sơ cấp trong A. Khi dó ta luôn có A Ã X . Chứng tninh Dựa vào định nghĩa đệ quy của công thức A. Để cho gọn ta viết A X thay cho A X X2 Xn . - Nếu A X ở đây X là mệnh dề sơ cấp thì hiển nhiên A X X-X hayA Ã X . - Giả sử công thức dã được chứng minh cho các công thức A và B tức tà A A X và B s B X . Ta chứng minh định lý cũng đúng cho các công thức A A B A V B Và A . Xét công thức A A B A A B 5 A V B A X V B X A aB X . Xét công thức A V B A V B A a B A X A B X A vB X . Xét công thức A Ã Ã Ã X Định lý được chứng minh. Ví dụ 3 Cho A s X V Y A z. Theo định lý thì Ã X Xv Ỹ aZ s X V Ỹ V z X A Y V z A . Cổn chú ý rằng nếu A B thì A B . . Luật thay thế Nếu A là một công thức chứa mệnh để sơ cấp X thì khi thay X bởi một công thức E nào dó ta được công thức mới ký hiệu là B. Với các ký hiệu đó ta có Định ỉý 2 Nếu -A thì B Chứng minh suy ra từ định nghĩa công thức đồng nhất đúng. Phán li. LOGIC VA ỨNG DỤNG 83 . Luột kếthjộn Định ỉý 3 Nếu A và A - B thì Ị B. Chứng mình bằng phương pháp phản chứng. 2. ĐIỂU KIỆN ĐỔNG NHÁT ĐÚNG hảng đúng ĐIỀU KIỆN ĐỔNG NHẨT SAI hãng sai . Tuyển và hội sơ câp Bài toán Cho công thức A bất kỳ. Có hay không một thuật toán mà sau hữu hạn các bước làm việc ta có thể biết công thức A có phải là công thức đổng nhất đúng hay không Đối với bài toán trên luôn có một thuật toán để biết công thức A có phải là công thức đồng nhất đúng hay không dó là thuật toán lập bảng. Phương pháp lập bảng sẽ gặp khó khăn khi sô các biến trong A quá-lớn. Để khắc phục nhược điểm trên ta cần xây dựng thuật toán khác tốt hơn đó là thuật toán tìm dạng chuẩn tắc tuyển và dạng chuẩn lắc hội của công thức A. Trước hết ta dưa vào các khái niệm sau Định nghĩa 5 1 Tuyển các mệnh dề sơ cấp và phủ định của nó gọi là tuyển sơ cấp TSC . 2 Hội các mênh đề sơ cấp và phủ định của nó gọi là hội sơ
