You're Reading a Free Preview
Pages 5 to 7 are not shown in this preview.
This Paper
A short summary of this paper
37 Full PDFs related to this paper
Download
PDF Pack
III DẠNG CHUẨN TẮC HỘI VÀ DẠNG CHUẨN TẮCTUYỂN CỦA MỆNH ĐỀ LÔ GIC• Ví dụ. A≡ x ∧ [x → y]A’ ≡ x ∧ [¬x ∨ y] là DCTHA’’ ≡ [x ∧ ¬x] ∨ [x ∧ y] là DCTT• Định lý 2. Mọi công thức bất kỳ đều có DCTT và DCTH.• Chứng minh. Giả sử A là mệnh đềề̀. Nếu A chứa phép → dùngđồng nhất thức X → Y ≡ ¬X ∨ Y. Vì vậy A chỉ chứa các ∨ , ∧ ,¬. Nếu phép ¬ chưa trực tiếp đối với mệnh đề sơ cấp trong Athì dùng các quy tắc De morgan để chuyển về phủ định của cácmđsc. Và dùng các quy tắc phân phốip ∨ [ q ∧ r ] ⇔ [p ∨ q] ∧ [p ∨ r]p ∧ [q ∨ r ] ⇔ [p ∧ q] ∨ [p ∧ r]• Khi đó A sẽ có DCTT hay DCTH. ĐLđcm26 III DẠNG CHUẨN TẮC HỘI VÀ DẠNG CHUẨN TẮCTUYỂN CỦA MỆNH ĐỀ LÔ GIC• Ví dụ 1. Tìm DCTT của công thức sau:• A ≡ p → [q→ p] ≡ ¬p ∨ [q → p] ≡ ¬p ∨ [¬q ∨ p]•≡ ¬p ∨ ¬q ∨ p ≡ [¬p∧ ¬p] ∨ [¬q ∧ ¬q] ∨ [p ∧ p] ≡ A’• Ví dụ 2. Tìm DCTH của công thức sau:• A ≡ [p → q] → [¬q → ¬p] ≡ ¬[¬ p ∨ q] ∨ [q ∨ ¬p]•≡ [ p ∧ ¬q] ∨ [q ∨ ¬p ] ≡ [p∨ q ∨ ¬p] ∧ [¬q ∨ q ∨ ¬p] ≡A’• Định lý 3.• 1. A ≡ T ↔ Trong DCTH mọi TSC chứa mô ôt mđsc nàođó đồng thời với phủ định của nó.• 2. A ≡ F ↔ Trong DCTT của A, mọi HSC chứa mô ôtmđsc nào đó đồng thời với phủ định của nó.27 III DẠNG CHUẨN TẮC HỘI VÀ DẠNG CHUẨN TẮCTUYỂN CỦA MỆNH ĐỀ LÔ GIC• Chứng minh phần 1.• a] Điều kiê ôn cần. Giả sử A ≡ T theo Đl 2 thì A có DCTH:A’≡ [TSC1] ∧ [TSC2] ∧ … ∧ [TSCn]• Vì A’ đồng nhất đúng thì TSCi [i=1,…,n] là đồng nhấtđúng. Theo Đl 1 thì trong mỗi TSC i [i=1,…,n] có chứamô ôt mđsc nào đó đồng thời với phủ định của nó.• b] Điều kiê ôn đủ. Giả sử A’≡ [TSC1] ∧ [TSC2] ∧ …∧ [TSCn]là DCTH của A với mỗi TSCi [i=1,…,n] có chứa mô ôtmđsc nào đó đồng thời với phủ định của nó. Theo Đl1thì mọi TSCi [i=1,…,n] đều là đúng, do đó A’ t.l A ≡ T,• Phần 2 chứng minh tương tự.28 III DẠNG CHUẨN TẮC HỘI VÀ DẠNG CHUẨN TẮCTUYỂN CỦA MỆNH ĐỀ LÔ GIC3. Thuâ ôt toán nhâ ôn biết hằng đúng, hằng sai và tiếp liênCho A là công thức bất kỳ.1. Khử phép → trong A được A1≡ A2. Đưa phép ¬ trong A1 về trực tiếp liên quan tới các mđsc,ta được A2 ≡ A13. Đưa A2 về DCTH bằng cách áp dụng công thứcp ∨ [ q ∧ r ] ⇔ [p ∨ q] ∧ [p ∨ r] ta được A3≡ A2 vớiA3≡ [TSC1]∧ [TSC2]∧ …∧ [TSCn] [n ≥ 1]+ Nếu trong mọi TSCi đều chứa mô ôt mđsc nào đó đồng thờivới pđịnh của nó thì A3 là hằng đúng hay A ≡ T; Kthuc TT+ Nếu có mô ôt TSC không chứa mô ôt mđsc nào đó đồng thờivới phủ định của nó thì A3 là không là hằng đúng thìchuyển sang bước 4.29 III DẠNG CHUẨN TẮC HỘI VÀ DẠNG CHUẨNTẮC TUYỂN CỦA MỆNH ĐỀ LÔ GIC• 4. Đưa A2 về DCTT bằng cách áp dụng công thứcp ∧ [q ∨ r ] ⇔ [p ∧ q] ∨ [p ∧ r] ta được A’3≡ A2 vớiA’3≡ [HSC1] ∨ [HSC2] ∨ … ∨ [HSCn] [n ≥ 1]+ Nếu trong mọi HSC đều chứa mô ôt mđsc cùng phủđịnh của nó thì A’3≡ F hay A ≡ F; KT Thuâ ôt tóan+ Ngược lại nếu tồn tại mô ôt HSC không chứa mô ôtmđsc cùng phủ định của nó thì A không là hằngđúng cũng không là hằng sai t.l A là một tiếp liên.30 III DẠNG CHUẨN TẮC HỘI VÀCHUẨN TẮC TUYỂN CỦA MỆNH ĐỀ LÔ GIC4. Các ví dụ.Ví dụ 1. Chứng minhF ≡ [ A → [ B → C ] → [[ A → B] → [ A → C ]] ≡ 1Thật vậy, dạng CTH của F :F ≡ A ∨ B ∨ C ∨ A ∨ B ∨ A ∨ C ≡ [ A ∧ B ∧ C ] ∨ [ A ∧ B] ∨ A ∨ C ≡≡ [ A ∧ B ∧ C ] ∨ [[ A ∨ A ∨ C ] ∧ [ B ∨ A ∨ C ]] ≡≡ [ A ∧ B ∧ C] ∨ [B ∨ A ∨ C] ≡≡ [ A ∨ B ∨ A ∨ C ] ∧ [ B ∨ B ∨ A ∨ C ] ∧ [C ∨ B ∨ A ∨ C ] ≡ DCTH ≡ 131 III DẠNG CHUẨN TẮC HỘI VÀCHUẨN TẮC TUYỂN CỦA MỆNH ĐỀ LÔ GICVí dụ 2. Chứng minhF ≡ [ A → B] → [[ A → C ] → [ A → [ B ∧ C ]]] ≡ 1F ≡ A ∨ B ∨ [ A ∨ C ∨ A ∨ [ B ∧ C ]] ≡≡ [ A ∧ B] ∨ [ A ∧ C ] ∨ A ∨ [ B ∧ C ] ≡≡ [ A ∨ [ A ∧ C ] ∨ A ∨ [ B ∧ C ]] ∧ [ B ∨ [ A ∧ C ] ∨ A ∨ [ B ∧ C ]] ≡≡ B ∨ [ A ∧ C] ∨ A ∨ [B ∧ C] ≡ B ∨ C ∨ [ A ∧ C] ∨ A ≡≡ [ B ∨ C ∨ A ∨ A] ∧ [ B ∨ C ∨ C ∨ A] ≡ DCTH ≡ 132 IV. CÁC QUY TẮC SUY DIỄN1. Các quy tắc suy diễn.Định lý là một phát biểu có thể chỉ ra được là đúng.Một lập luận chỉ ra được tính đúng đắn của một mệnh đề phátbiểu trong Định lý được gọi là một Chứng minh.Các quy tắc suy diễn trong lô-gic là cơ sở để biết một lập luậnhay một chứng minh là đúng hay là sai.Một chứng minh dựa trên các hằng đúng làm cơ sở gọi làchứng minh có lý hay suy luận đúng.A1Một PP chứng minh một mệnh đề toán họcA2là đúng thường lý luận với dẫn xuất sau:.Nếu A1 và A2 và…và An thì BAndựa trên hằng đúng :∴B[ A1 ∧ A2 ∧ ... ∧ An ] → B ≡ 133 IV. CÁC QUY TẮC SUY DIỄN• Hằng đúng [p∧ [p→ q]] → q - cơ sở của quy tắcsuy luận- luật tách rời.• Luật tách rời được viết như sau:p[giả thiết]p→ q[giả thiết].: q[kết luận]• Ví dụ 1. Giả sử mệnh đề kéo theo “nếu hôm naytuyết rơi, thì chúng ta sẽ đi trượt tuyết” và giả thiết“nếu hôm nay tuyết rơi” là đúng. Khi đó, theo luậttách rời, “chúng ta sẽ đi trượt tuyết” là đúng34 IV CÁC QUY TẮC SUY DIỄNVí dụ 2. Mệnh đề p→ q=“nếu n chia hết cho 3, khi đó n 2 chiahết cho 9 ” là đúng. Do vậy, p=“ n chia hết cho 3”, khi đótheo luật tách rời ta suy ra q= “n2 chia hết cho 9”.• Ví dụ 3. Quy tắc suy luận nào là cơ sở của suy diễn: “ Bâygiờ trời quá băng giá. Vậy thì bây giờ hoặc là trời quá bănggiá hoặc trời mưa”?Bài giải. Giả sửp = ” Bây giờ trời quá băng giá”q = “ bây giờ trời mưa”.Khi đó suy diễn trên có dạngp∴ pvqquy tắc cộng35 IV CÁC QUY TẮC SUY DIỄN• Ví dụ 4. Quy tắc suy luận nào là cơ sở của suy diễnsau: “ Bây giờ trời quá băng giá và đang mưa. Vậythì bây giờ trời quá băng giá”?• Bài giải.•Giả sử p =“Bây giờ trời quá băng giá” vàq = “ bây giờ trời mưa”.Suy diễn trên có dạng[p ∧ q] → p• Vậy là ta đã sử dụng quy tắc rút gọn.36