Đại số Mệnh đề

Ks. Từ Nghĩa

* Một số khái niệm tóm lược

               1. Mệnh đề và chân trị.

               2. Phép tính mệnh đề: phép phủ định, phép hội, phép tuyển, phép tuyển chọn, phép kéo theo, phép tương đương.

               3. Mệnh đề phức hợp.

               4. Hằng đúng, mâu thuẫn.

               5. Tương đương logic, chứng minh hằng đúng/hằng sai (dùng bảng chân trị, dùng tương đương logic).

               6. Các quy tắc suy diễn: Quy tắc Modus Ponens, Modus Tollens, Tam đoạn luận, Tam đoạn luận tuyển (rời), mâu thuẫn, phản ví dụ.

======

1) Mệnh đề và chân trị

        Mỗi câu phát biểu là đúng hay sai được gọi là một mệnh đề.

        Chân trị của mệnh đề đúng là T (true), chân trị của mệnh đề sai là F (false)

2) Phép tính mệnh đề

        + Phép phủ định (Negation): Cho P là một mệnh đề. Mệnh đề “không phải P” là một phủ định của P

                * Ký hiệu: ㄱP hoặc

        + Phép hội (Conjunction): Hội của hai mệnh đề (P và Q) chỉ đúng khi cả hai mệnh đề đúng.

                * Ký hiệu: P ∧ Q

        + Phép tuyển (Disjuntion): Tuyển của hai mệnh đề (P và Q) chỉ sai khi cả hai mệnh đề sai.

                * Ký hiệu: P ∨ Q

        + Phép tuyển chọn (xor): Phép xor của hai mệnh đề (P và Q) chỉ đúng khi P và Q khác nhau.

                * Ký hiệu: P ⊕ Q

        + Phép kéo theo (Implication): Nếu P thì Q là mệnh đề kéo theo với P là giả thuyết và Q là kết luận chỉ sai khi giả thuyết (P) đúng nhưng kết luận (Q) sai.

                * Ký hiệu: P ⟶ Q

        + Phép tương đương (Biconditional): P nếu và chỉ nếu Q là mệnh đề tương đương của P và Q chỉ đúng khi P và Q có cùng chân trị

                * Ký hiệu: P ⇔ Q = (P ⟶ Q) ∧ (Q ⟶ P)

3) Mệnh đề phức hợp

        + Cho P, Q, R … là các mệnh đề. Nếu các mệnh đề này liên kết với nhau bằng các phép toán thì ta được một mệnh đề phức hợp.

4) Hằng đúng, mâu thuẫn

a) Hằng đúng

        + Hằng đúng là mệnh đề luôn có chân trị là đúng.

        + Hằng đúng là mệnh đề phức hợp (biểu thức mệnh) luôn có chân trị là đúng bất chấp sự lựa chọn chân trị của biến mệnh đề.

b) Mâu thuẫn

        + Để chứng minh mệnh đề P là đúng, ta giả sử ngược lại P là sai. Hay ㄱP là đúng để dẫn đến kết luận Q sao cho ㄱP ⟶ Q phải đúng. Khi đó ta chỉ ra được Q là một mâu thuẫn.

5) Tương đương logic

        + Mệnh đề P và Q là tương đương logic nếu P ⇔ Q là hằng đúng

Một số luật tương đương:

        a) Luật nuốt (Domination Laws):

                + P ∨ T = T

                + P ∧ F = F

        b) Luật đồng nhất (Identity Laws):

                + P ∧ T = P

                + P ∨ F = P

        c) Luật luỹ đẳng (Idempotent Laws):

                + P ∧ P = P

                + P ∨ P = P

        d) Luật phủ định kép (Double Negation Law):

                + ㄱㄱP = P

        e) Luật bù trừ (Cancellation Laws):

                + P ∨ ㄱP = T

                + P ∧ ㄱP = F

        f) Luật giao hoán (Commutative Laws):

                + P ∧ Q = Q ∧ P

                + P ∨ Q = Q ∨ P

        g) Luật kết hợp (Associative Laws):

                + P ∧ (Q ∧ R) = (P ∧ Q) ∧ R

                + P ∨ (Q ∨ R) = (P ∨ Q) ∨ R

        h) Luật phân phối (Distributive Laws):

                + P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)

                + P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

        i) Luật De Morgan (De Morgan’s Laws):

                + ㄱ(P ∧ Q) = ㄱP ∨ ㄱQ

                + ㄱ(P ∨ Q) = ㄱP ∧ ㄱQ

        j) Luật théo theo (Implication Laws):

                + P ⟶ Q = ㄱP ∨ Q

        Ví dụ: Cho S1 = P ⟶ Q, S2 = ㄱ(P ∧ Q) . Xét hai mệnh đề trên có tương đương logic không?

        Cách 1: Dùng bảng chân trị

        Thông qua bảng chân trị, ta thấy S1 và S2 không tương đương logic

        Cách 2: Dùng tương đương logic

                    P  ⟶ Q ⇔ ㄱ(P ∧ Q)

                =  ㄱP ∨ Q ⇔ ㄱP ∨ ㄱQ

                ⇒ Không tương đương

6) Các quy tắc suy diễn

a) Quy tắc Modus Ponens (Khẳng định luận)

Nếu P thì Q => Có P thì có Q

Hằng đúng: (P ∧ (P ⟶ Q)) ⟶ Q

Vd: Nếu trời mưa thì chúng ta ở nhà

       => Trời mưa do đó chúng ta ở nhà hoặc ngược lại

b) Quy tắc Modus Tollens (Nghịch đoạn luận)

        Nếu P thì Q => Không P thì không Q

        Hằng đúng: (ㄱP ∧ (P ⟶ Q)) ⟶ ㄱQ

        Vd: Nếu trời mưa thì chúng ta ở nhà

              => Trời không mưa do đó chúng ta không ở nhà hoặc ngược lại

c) Quy tắc Tam đoạn luận

        Nếu P thì Q , nếu Q thì R => Có P thì có R

        Hằng đúng: ((P ⟶ Q) ∧ (Q ⟶ R))  ⟶ (P ⟶ R)

        Vd: Nếu trời mưa thì chúng ta ở nhà, nếu chúng ta ở nhà thì tổ chức tiệc

              => Trời mưa do đó tổ chức tiệc

d) Quy tắc Tam đoạn luận tuyển

        P hoặc Q => Không P thì Q

        Hằng đúng: ㄱQ ∧ (P ∨ Q) ⟶ P

        Vd:         Đậu hoặc thi lại

=> Thi lại do đó không đậu

e) Quy tắc mâu thuẫn

        Có P và Q và … thì suy ra có R 

=> Có P và Q và … và không R thì suy ra Sai        

        Hằng đúng: (P1∧P2 ∧ … ∧Pn) ⟶ Q ⇔ (P1∧P2∧ … ∧Pn ∧ ㄱQ) ⟶ 0

        Chứng minh bằng phản chứng

        Vd:         Nếu dậy sớm thì tập thể dục, nếu tập thể dục thì tắm

Chứng minh dậy sớm thì tắm là đúng?

        Giải:         Giả sử giậy sớm thì không tắm

Vì không tắm nên không tập thể dục, không tập thể dục nên không dậy sớm

Sai với giả thiết => Vậy dậy sớm thì tắm là đúng

f) Quy tắc phản ví dụ

        (P1 ∧ P2 ∧ … ∧ Pn) ⟶ Q là sai thì chỉ cần ∃Pi sai với i ∈ {1, 2, …, n}

        Vd:         Bạn mong muốn trở thành người lập trình Python giỏi, nhưng nếu muốn giỏi Python thì phải biết cấu trúc dữ liệu và tư duy lập trình, nhưng muốn giỏi tư duy lập trình thì cần biết đại số mệnh đề và đại số Boole.

Vậy theo quy tắc phản ví dụ khẳng định không biết đại số mệnh đề thì không giỏi Python là đúng!

Cảm ơn các bạn đã theo dõi!

Xem thêm Đại số Boole tại:

https://omomega.com/omdoc/article/toan-roi-rac/dai-so-boole/27/

Xem thêm Toán Rời Rạc tại: https://omomega.com/omdoc/article/toan-roi-rac/tong-hop/23/

* TÀI LIỆU THAM KHẢO

[1] Nguyễn Đức Nghĩa và Nguyễn Tô Thành, Toán rời rạc, NXB Giáo dục, 1997.

[2] Nguyễn Hữu Anh, Toán rời rạc, NXB Lao động Xã hội, 2006.