Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 5', 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ả | 164 TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC Từ 2 và 4 theo quy tắc bắc cầu ta nhận được D K Vx Tương tự từ 2 b có D X K K Vx X c D K Cõng thức ị- JAaJa X X _ X KWA 5 6 7 X nhận dược từ 3 6 và quy tắc bắc cầu. Từ 5 và 7 áp dụng bổ đề 1 ta có công thức cần chứng minh K - X D - A A X K - A . X Định ỉý 18 I- X D A A X K - A X D A V X K - A Chứng minh Theo 3 c ta có - A - C - B C w A V B Q Ghép giả thiết trong công thức này ta được I- A C A B O - AvB - C 1 Trong 1 thay A bởi X D thay B bởi X K c thay bởi A ta được công thức cần chứng minh. Định lý 19 Với mọi công thức A ta luôn có Ị- A V A . Chứng mình Theo 3 a ta có -A- Avà 1 Theo 4 a ta có p A A V à - Avà - à 2 Từ 1 2 theo quy tắc dần xuất ta có Ị-Avà à 3 Theo 3 b Phẩn II. LÔGIC VÀ ỨNG DỤNG 165 Ị- A - A V A 4 và theo 4 a ta có - à - A V à - AvÃ- à 5 Từ 4 và 5 theo quy tắc dẫn xuất ta có ị- Av A A 6 Theo 4 c thì A A 7 Từ 6 7 ta có AvÃ- A 8 Từ 3 8 theo bổ đề 1 ta có - Avà - Aaà 9 Theo định lý 12 thì - AaĂ - K 10 Từ 9 10 theo quy tắc bắc cầu ta có pAvà - K 11 Theo 4 a thì - Avà K - K Avà 12 Từ 11 12 theo quy tắc dân xuất la được ị-K Avà 13 Theo 4 c ta có - Avà - Avà 14 Từ 12 14 theo quy tắc bắc cầu la có -K- Avà 15 Theo dinh nghĩa công thức sai thì ị- K 16 Từ 15 16 dùng quy tắc dản xuất ta có ị-AvA. Định lý được chứng minh. 166 TOẨN rời rạc ứng dụng trong tin học Định lý 20 - X D V X K . Chứng minh Theo định lý 15 thì - X D X Theo định lý 16 thì ị- X K X Từ 1 theo định lý 7 ta có -X X D Mặt khác theo 3 a thì - X D X D V X K Từ 3 4 theo quy tắc bắc cầu thì -x4 X-D v X K Từ 2 theo định lý 7 ta có Ị- X X K Theo 3 b ta có Ị- X K X D V X K Từ 6 và 7 theo quy tắc bắc cầu ta có ị- X - X D V X K Từ 5 8 theo bổ đề 2 ta được X V X - X D V X K Theo định lý 19 thì -Xv X Từ 9 10 theo quy tắc dẫn xuất ta có ị- X D V X K 1 2 3 4 5 6 7 8 9 10 Định lý được chứng minh. Định lý 21 Chứng minh Theo định lý 15 ta có K ÌA X X D A A X K A
