Giáo trình Logic toán (Phần 1) - Trịnh Huy Hoàng
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.
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.
57 trang
09/11/2022
4500
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 hãy click vào nút Download ở trên.
File đí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ộ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
