Toán học rời rạc - Logic mệnh đề

Các quy tắc của logic toán học chỉ rõ các phương pháp lập luận các câu lệnh toán học. Nhà triết học Hy Lạp, Aristotle, là người tiên phong của lý luận lôgic. Suy luận logic cung cấp cơ sở lý thuyết cho nhiều lĩnh vực toán học và do đó là khoa học máy tính. Nó có nhiều ứng dụng thực tế trong khoa học máy tính như thiết kế máy tính, trí tuệ nhân tạo, định nghĩa cấu trúc dữ liệu cho ngôn ngữ lập trình, v.v.

Propositional Logicliên quan đến các tuyên bố mà giá trị sự thật, "đúng" và "sai", có thể được chỉ định. Mục đích là để phân tích các tuyên bố này hoặc riêng lẻ hoặc theo cách tổng hợp.

Logic giới từ - Định nghĩa

Mệnh đề là tập hợp các câu lệnh khai báo có giá trị chân lý "true" hoặc giá trị chân lý "false". Mệnh đề bao gồm các biến mệnh đề và các phép liên kết. Chúng tôi biểu thị các biến mệnh đề bằng chữ in hoa (A, B, v.v.). Các phép nối kết nối các biến mệnh đề.

Dưới đây là một số ví dụ về Mệnh đề -

"Man is Mortal", nó trả về giá trị sự thật "TRUE"
"12 + 9 = 3 - 2", nó trả về giá trị sự thật "FALSE"

Sau đây không phải là một Đề xuất -

"A nhỏ hơn 2". Đó là bởi vì trừ khi chúng ta đưa ra một giá trị cụ thể của A, chúng ta không thể nói liệu tuyên bố đó là đúng hay sai.

Kết nối

Trong logic mệnh đề nói chung, chúng ta sử dụng năm kết nối là:

HOẶC ($ \ lor $)
VÀ ($ \ land $)
Phủ định / KHÔNG ($ \ lnot $)
Hàm ý / if-then ($ \ rightarrow $)
Nếu và chỉ khi ($ \ Leftrightarrow $).

OR ($\lor$) - Phép toán OR của hai mệnh đề A và B (viết là $ A \ l hoặc B $) là đúng nếu ít nhất bất kỳ biến mệnh đề A hoặc B nào là đúng.

Bảng sự thật như sau:

A	B	A ∨ B
Thật	Thật	Thật
Thật	Sai	Thật
Sai	Thật	Thật
Sai	Sai	Sai

AND ($\land$) - Phép toán AND của hai mệnh đề A và B (viết là $ A \ land B $) là đúng nếu cả biến mệnh đề A và B đều đúng.

Bảng sự thật như sau:

A	B	A ∧ B
Thật	Thật	Thật
Thật	Sai	Sai
Sai	Thật	Sai
Sai	Sai	Sai

Negation ($\lnot$) - Phủ định của mệnh đề A (viết là $ \ l không phải A $) là sai khi A đúng và đúng khi A sai.

Bảng sự thật như sau:

A	¬ A
Thật	Sai
Sai	Thật

Implication / if-then ($\rightarrow$)- Hàm ý $ A \ rightarrow B $ là mệnh đề “nếu A thì B”. Nếu A đúng và B sai. Các trường hợp còn lại là đúng.

Bảng sự thật như sau:

A	B	A → B
Thật	Thật	Thật
Thật	Sai	Sai
Sai	Thật	Thật
Sai	Sai	Thật

If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ là liên kết logic hai điều kiện đúng khi p và q giống nhau, tức là cả hai đều sai hoặc cả hai đều đúng.

Bảng sự thật như sau:

A	B	A ⇔ B
Thật	Thật	Thật
Thật	Sai	Sai
Sai	Thật	Sai
Sai	Sai	Thật

Tautologies

Tautology là một công thức luôn đúng với mọi giá trị của các biến mệnh đề của nó.

Example - Chứng minh $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ là một phép tính toán

Bảng sự thật như sau:

A	B	A → B	(A → B) ∧ A	[(A → B) ∧ A] → B
Thật	Thật	Thật	Thật	Thật
Thật	Sai	Sai	Sai	Thật
Sai	Thật	Thật	Sai	Thật
Sai	Sai	Thật	Sai	Thật

Như chúng ta có thể thấy mọi giá trị của $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ là "Đúng", nó là một phép tính toán.

Mâu thuẫn

Mâu thuẫn là một công thức luôn sai đối với mọi giá trị của các biến mệnh đề của nó.

Example - Chứng minh $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ là một mâu thuẫn

Bảng sự thật như sau:

A	B	A ∨ B	¬ A	¬ B	(¬ A) ∧ (¬ B)	(A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Thật	Thật	Thật	Sai	Sai	Sai	Sai
Thật	Sai	Thật	Sai	Thật	Sai	Sai
Sai	Thật	Thật	Thật	Sai	Sai	Sai
Sai	Sai	Sai	Thật	Thật	Thật	Sai

Như chúng ta có thể thấy mọi giá trị của $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ là "Sai", đó là một mâu thuẫn.

Dự phòng

Dự phòng là một công thức có cả một số giá trị đúng và một số giá trị sai cho mọi giá trị của các biến mệnh đề của nó.

Example - Chứng minh $ (A \ lor B) \ land (\ lnot A) $ một khoản dự phòng

Bảng sự thật như sau:

A	B	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
Thật	Thật	Thật	Sai	Sai
Thật	Sai	Thật	Sai	Sai
Sai	Thật	Thật	Thật	Thật
Sai	Sai	Sai	Thật	Sai

Như chúng ta có thể thấy mọi giá trị của $ (A \ lor B) \ land (\ lnot A) $ có cả “Đúng” và “Sai”, đó là một trường hợp dự phòng.

Tương đương mệnh đề

Hai câu lệnh X và Y tương đương về mặt logic nếu bất kỳ điều kiện nào sau đây giữ nguyên:

Các bảng chân trị của mỗi câu lệnh có cùng giá trị chân lý.
Câu lệnh hai điều kiện $ X \ Leftrightarrow Y $ là một phép tính toán.

Example - Chứng minh $ \ lnot (A \ lor B) và \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ là tương đương nhau

Kiểm tra bởi 1 ^st phương pháp (bảng sự thật Matching)

A	B	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
Thật	Thật	Thật	Sai	Sai	Sai	Sai
Thật	Sai	Thật	Sai	Sai	Thật	Sai
Sai	Thật	Thật	Sai	Thật	Sai	Sai
Sai	Sai	Sai	Thật	Thật	Thật	Thật

Ở đây, chúng ta có thể thấy các giá trị chân lý của $ \ lnot (A \ lor B) và \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ là như nhau, do đó các câu lệnh là tương đương nhau.

Kiểm tra bằng phương pháp ^{thứ 2} (Điều kiện sinh học)

A	B	¬ (A ∨ B)	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Thật	Thật	Sai	Sai	Thật
Thật	Sai	Sai	Sai	Thật
Sai	Thật	Sai	Sai	Thật
Sai	Sai	Thật	Thật	Thật

Vì $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ là một phép tính toán, các câu lệnh tương đương nhau.

Đảo ngược, Ngược lại và Ngược lại dương tính

Hàm ý / if-then $ (\ rightarrow) $ còn được gọi là câu lệnh điều kiện. Nó có hai phần -

Giả thuyết, tr
Kết luận, q

Như đã đề cập trước đó, nó được ký hiệu là $ p \ rightarrow q $.

Example of Conditional Statement- "Nếu bạn làm bài tập về nhà của bạn, bạn sẽ không bị phạt." Ở đây, "bạn làm bài tập về nhà" là giả thuyết, p, và "bạn sẽ không bị trừng phạt" là kết luận, q.

Inverse- Một câu điều kiện nghịch đảo là sự phủ định của cả giả thuyết và kết luận. Nếu câu lệnh là “Nếu p thì q”, thì nghịch đảo sẽ là “Nếu không p thì không phải q”. Do đó, nghịch đảo của $ p \ rightarrow q $ là $ \ lnot p \ rightarrow \ lnot q $.

Example - Ngược lại của “Nếu bạn làm bài tập về nhà, bạn sẽ không bị phạt” là “Nếu bạn không làm bài tập về nhà, bạn sẽ bị phạt”.

Converse- Ngược lại của câu điều kiện được tính bằng cách hoán đổi giữa giả thuyết và kết luận. Nếu câu lệnh là “If p, then q”, ngược lại sẽ là “If q, then p”. Converse của $ p \ rightarrow q $ là $ q \ rightarrow p $.

Example - Câu chuyện "Nếu bạn làm bài tập, bạn sẽ không bị phạt" là "Nếu bạn không bị phạt, bạn sẽ làm bài tập về nhà của mình".

Contra-positive- Tính trái dấu tích cực của điều kiện được tính bằng cách hoán đổi giả thuyết và kết luận của câu lệnh nghịch đảo. Nếu câu lệnh là "Nếu p, thì q", trái ngược dương sẽ là "Nếu không phải q, thì không phải p". Ngược lại của $ p \ rightarrow q $ là $ \ lnot q \ rightarrow \ lnot p $.

Example - Mặt trái tích cực của “Nếu bạn làm bài tập về nhà, bạn sẽ không bị phạt” là “Nếu bạn bị phạt, bạn đã không làm bài tập về nhà”.

Nguyên tắc đối ngẫu

Nguyên tắc đối ngẫu phát biểu rằng đối với bất kỳ phát biểu đúng nào, phát biểu đối ngẫu thu được bằng cách hoán đổi các hợp nhất thành các giao điểm (và ngược lại) và hoán đổi tập hợp Phổ thành tập Null (và ngược lại) cũng đúng. Nếu kép của bất kỳ câu lệnh nào là chính câu lệnh đó, nó được cho làself-dual tuyên bố.

Example - Bộ đôi của $ (A \ cap B) \ cup C $ là $ (A \ cup B) \ cap C $

Dạng bình thường

Chúng ta có thể chuyển đổi bất kỳ mệnh đề nào ở hai dạng bình thường -

Dạng chuẩn liên kết
Hình thức bình thường khó hiểu

Dạng chuẩn liên kết

Một câu lệnh ghép ở dạng chuẩn liên hợp nếu nó có được bằng cách vận hành AND giữa các biến (phủ định của các biến được bao gồm) được kết nối với OR. Về phương diện hoạt động tập hợp, nó là một câu lệnh ghép thu được bởi Giao điểm giữa các biến được kết nối với Unions.

Examples

$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ cup Q) \ cap (Q \ cup R) $

Dạng bình thường không kết nối

Một câu lệnh ghép ở dạng chuẩn tắc nếu nó được lấy bằng phép toán OR giữa các biến (phủ định của các biến được bao gồm) được kết nối với AND. Về mặt hoạt động tập hợp, nó là một câu lệnh ghép được Union thu được giữa các biến được kết nối với Giao điểm.

Examples