[Toán rời rạc/Chương I] Logic

CHƯƠNG I: LOGIC

I, Mệnh đề (Propositional logic)

- Mệnh đề là câu chỉ có đúng hoặc sai

* Mệnh đề ghép (Compound propositions): Cho p và q là 2 mệnh đề

    + Phủ đỉnh (Negation)

            \(\rightharpoondown\)p = not p, nếu p đúng thì \(\rightharpoondown\)p là sai 

                                   nếu p sai thì \(\rightharpoondown\)p là đúng

    + Giao hợp (Conjunction) ( Phép hội)

            p \(\wedge\) q = "p and q", mệnh đề đúng khi và chỉ khi p và q cùng đúng

    + Phân ly (Disjunction) ( Phép tuyển)

            p \(\vee\) q = "p or q", mệnh đề sai khi và chỉ khi p và q cùng sai, các TH còn lại là đúng

    + Phép tuyển loại (Exclusive or)

            p \(\oplus\) q = "only p or only q", mệnh đề này đúng khi chỉ hoặc p hoặc q là đúng

    + Phép kéo theo (suy ra) (Conditional statement)

            p \(\rightarrow\) q, mệnh đề chỉ sai khi p đúng và q sai

    + Phép tương đương (Biconditional statement)

            p \(\leftrightarrow\) q, mệnh đề đúng khi p và q cùng đúng hoặc cùng sai 

* Chú ý: Các cách đề thể hiện phép suy ra (Conditional statement)

+ if p then q                                     + p is suffcient for q

+ q if p                                              + q is a necessary condition for p

+ p only if q

Ví dụ: I watch LoL only if T1 play or I have no homework

           p = "I watch LoL"

           q = " T1 play"

           r = "I have homework"

Đáp án: p \(\rightarrow\) q \(\vee\) \(\rightharpoondown\)r

* Logic trên bit

- 1 bit chỉ có 2 giá trị là 0 và 1, với 1 là T(true) và 0 là F(false)

- Thông tin thường biểu diễn dưới dạng 1 dãy bit

Ví dụ: 1001100 \(\wedge\) 0011001 = 0001000

            1001100 \(\vee\) 0011001 = 1011101

            1001100 \(\oplus\) 0011001 = 1010101

II, Mệnh đề tương đương (Propositional Equivalences)

- 1 mệnh đề ghép được gọi là hằng đúng (tautology) khi nó luôn đúng

- 1 mệnh đề ghép được gọi là mâu thuẫn (contracdiction) khi nó luôn sai

- 2 mệnh đề p và q là tương đương logic (logically equivalent) nếu phép tương đương của p và q là p \(\leftrightarrow\) q là hằng đúng. Kí hiệu: p \(\equiv\) q

* 1 số tương đương logic:

* Lưu ý:

+ p \(\rightarrow\) q \(\equiv\) \(\rightharpoondown\) q \(\rightarrow\) \(\rightharpoondown\) p \(\equiv\) \(\rightharpoondown\)p \(\vee\) q

+ (p \(\rightarrow\) r) \(\wedge\) (q \(\rightarrow\) r) \(\equiv\) (p \(\vee\) q) \(\rightarrow\) r

+ (p \(\rightarrow\) r) \(\vee\) (q \(\rightarrow\) r) \(\equiv\) (p \(\wedge\) q) \(\rightarrow\) r

+ p \(\leftrightarrow\) q \(\equiv\) (p \(\rightarrow\) q ) \(\wedge\) (q \(\rightarrow\) p)

+ p \(\oplus\) q \(\equiv\) \(\rightharpoondown\)(p \(\leftrightarrow\) q)

III, Vị từ và Lượng từ (Predicates and Quantifiers)

* Vị từ (Predicate)

- Ví dụ: "x > 3 " không phải mệnh đề, nó sẽ trở thành mệnh đề nếu x có giá trị cụ thể 

            \(\Rightarrow\) "x > 3" được gọi là hàm mệnh đề (propositional function), được xác định bởi P(x), ví dụ: P(0) = F hay P(5) = T

            Lúc này, x gọi là biến, "> 3" gọi là vị từ

\(\Rightarrow\) 1 hàm mệnh đề có thể có nhiều biến

* Lượng từ (\(\forall,\exists\))

- Cho P(x) là 1 hàm mệnh đề với x nhận giá trị trong 1 khoảng xác định

+ Lượng từ với mọi (Universal quantification)

        KH: \(\forall\)xP(x) = Tất cả x trong tập xác định thì P(x) là T

+ Lượng từ tồn tại (Existential quantification)

        KH: \(\exists\)xP(x) = Tồn tại ít nhất 1 giá trị của x trong tập xác định để P(x) là T

+ Dạng phủ định của lượng từ (Negating quantified expressions)

* Tương đương logic: \(\forall\)x(Q(x)\(\wedge\)P(x)) \(\equiv\) \(\forall\)xQ(x) \(\wedge\) \(\forall\)x P(x)

IV, Vị từ lồng nhau (Nested quantifiers)

- \(\forall x \forall y\)P(x,y) = Với mọi x và với mọi y thì P(x,y) là T

- \(\forall x \exists y\)P(x,y) = Với mọi x và tồn tại y thì P(x,y) là T

- \(\exists x \forall y\)P(x,y) = Tồn tại x và với mọi y thì P(x,y) là T

- \(\exists x \exists y\)P(x,y) = Tồn tại x và tồn tại y thì P(x,y) là T

* Phủ định lượng từ lồng nhau (Negating nested quantifiers)

+ \(\rightharpoondown\) (\(\forall x \forall y\)P(x,y)) = \(\exists x \exists y\)\(\rightharpoondown\)P(x,y)

+ \(\rightharpoondown\) (\(\forall x \exists y\)P(x,y)) = \(\exists x \forall y\)\(\rightharpoondown\)P(x,y)

+ \(\rightharpoondown\) (\(\exists x \forall y\)P(x,y)) = \(\forall x \exists y\)\(\rightharpoondown\)P(x,y)

+ \(\rightharpoondown\) (\(\exists x \exists y\)P(x,y)) = \(\forall x \forall y\)\(\rightharpoondown\)P(x,y)

V, Quy tắc diễn giải (Rules inferences) 

* Ngụy biện - sai logic (fallacies)

+ [ (p \(\rightarrow\) q) \(\wedge\) q ] \(\rightarrow\) p (ngụy biện khẳng định kết luận)

+ [ (p \(\rightarrow\) q) \(\wedge\) \(\rightharpoondown\) p ] \(\rightarrow\) \(\rightharpoondown\) p (ngụy biện phủ nhận giả thuyết)

* Quy tắc diễn giải cho câu lượng từ

P/s: Bài tập và tài liệu nghiên cứu thêm (nếu cần) được tổng hợp ở link dưới sau:

https://drive.google.com/drive/folders/1SuvqESuJOgWo1bM7YrRkbi38xbwCplYy?usp=sharing