Thông Tin IT Share: Các phép toán lôgic cơ bản

Trong toán học, khi có hai số, người ta dùng các phép toán số học (cộng, trừ, nhân, chia,...) tác động vào chúng để nhận được những số mới. Tương tự, khi có mệnh đề, người ta dùng các phép lôgic tác động vào chúng để nhận được những mệnh đề mới. Dưới đây ta trình bày định nghĩa và các tính chất cơ bản của các phép toán này.
Phép phủ định Phủ định của mệnh đề a là một mệnh đề, kí hiệu là

\overline{a}

, đúng khi a sai và sai khi a đúng.
Bảng giá trị chân lí của phép phủ định


a	$\overline{a}$
1	0
0	1

Ví dụ 1:
Nếu a = "Paris là thủ đô của nước Pháp" thì mệnh đề phủ định

\overline{a}

có thể diễn đạt như sau:

$\overline{a}$ = "Không phải Paris là thủ đô của nước Pháp"
hoặc $\overline{a}$ = "Paris không phải là thủ đô của nước Pháp".

Ở đây G(a) = 1 còn G(

\overline{a}

) = 0.
Ví dụ 2:
Nếu b = "15 lớn hơn 30" thì mệnh đề phủ định

\overline{b}

có thể diễn đạt như sau:

$\overline{b}$ = "Không phải 15 lớn hơn 30"
hoặc $\overline{b}$ = "15 không lớn hơn 30"
hoặc $\overline{b}$ = "15 nhỏ hơn hoặc bằng 30"

Ở đây G(b) = 0 còn G(

\overline{b}

) = 1.
Ví dụ 3:
Nếu c = "Chuyến tàu TN1 hôm nay bãi bỏ" thì mệnh đề phủ định

\overline{c}

có thể diễn đạt như sau:

\overline{c}

= "Chuyến tàu TN1 hôm nay không bãi bỏ".

Nếu qua xác minh mệnh đề c đúng (hoặc sai) thì mệnh đề phủ định

\overline{c}

sẽ sai (hoặc đúng).
Chú ý: Mệnh đề phủ định a thường được diễn đạt là "không phải a".

Phép hội

Hội của hai mệnh đề a, b là một mệnh đề, đọc là a và b, kí hiệu a Λ b (hoặc a.b), đúng khi cả hai mệnh đề a, b cùng đúng và sai trong các trường hợp còn lại.

**Bảng giá trị chân lí của phép hội**
a	b	a Λ b
1	1	1
1	0	0
0	1	0
0	0	0

Chú ý: Để thiết lập mệnh đề hội của hai mệnh đề a, b ta ghép hai mệnh đề đó bởi liên từ "và" hay một liên từ khác cùng loại. Những liên từ đó là: mà, nhưng, song, đồng thời, vẫn, cùng,... hoặc dùng dấu phảy hoặc không dùng liên từ gì.
Ví dụ 1:
"Lúc 8 giờ sáng nay Hà có mặt ở Hà Nội và thành phố Hồ Chí Minh" là hội của hai mệnh đề a = "Lúc 8 giờ sáng nay Hà có mặt ở Hà Nội" và b = "Lúc 8 giờ sáng nay Hà có mặt ở thành phố Hồ Chí Minh". Vì hai mệnh đề này không thể cùng đúng, nên G(a Λ b) = 0.
Ví dụ 2:
"Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước nhưng không phải là thủ đô" là hội của hai mệnh đề a = "Thành phố Hồ Chí Minh là thành phố lớn nhất trong cả nước" và b = "Thành phố Hồ Chí Minh không phải là thủ đô". Rõ ràng là G(a) = 1 và G(b) = 1 nên G(a Λ b) = 1.
Ví dụ 3:

"Số π lớn hơn 2 song nhỏ hơn 3".
"Chị Nga nói thạo tiếng Pháp mà không biết tiếng Anh".
"ABC là tam giác vuông cân" là hội của của hai mệnh đề a = "ABC là tam giác vuông" và b = "ABC là tam giác cân".
"Không những trời nắng to mà còn gió tây".
"Chồng cày, vợ cấy, con trâu đi bừa".

Chú ý: Đôi khi trong mệnh đề có liên từ "và" nhưng không có nghĩa của mệnh đề hội. Chẳng hạn:

"Số lẻ và số chẵn là hai tập con rời nhau của tập số tự nhiên".
"Hùng đạt được tất cả 20 điểm 9 và 10".

Phép tuyển

Tuyển của hai mệnh đề a, b là một mệnh đề đọc là a hoặc b, kí hiệu là a ν b (hoặc a+b), sai khi cả hai mệnh đề cùng sai và đúng trong trường hợp còn lại.

**Bảng giá trị chân lí của phép tuyển**
a	b	a ν b
1	1	1
1	0	1
0	1	1
0	0	0

Phép tuyển trên còn được gọi là phép tuyển không loại trừ.
Phép tuyển loại trừ của hai mệnh đề a và b, chỉ đúng khi hoặc a, hoặc b đúng.
Chú ý: Để thiết lập mệnh đề tuyển của hai mệnh đề a, b ta ghép hai mệnh đề đó bởi liên từ "hoặc" (hay liên từ khác cùng loại).
Ví dụ 1:
"Tháng 12 có 31 ngày hoặc 2 + 2 = 4" là tuyển của hai mệnh đề a = "Tháng 12 có 31 ngày" và b = "2 + 2 = 4".
Ở đây G(a ν b) = 1.
Ví dụ 2:

"3 nhỏ hơn hoặc bằng 4" ← là mệnh đề đúng
"Số lẻ là số có chữ số tận cùng bằng 1, 3, 5, 7 hoặc 9" ← là mệnh đề đúng
"20 là số lẻ hoặc chia hết cho 3" ← là mệnh đề sai

Chú ý: Trong thực tế, liên từ "hoặc" thường được dùng với hai nghĩa "loại trừ" và "không loại trừ".

Phép tuyển "hoặc a hoặc b" là phép tuyển loại trừ để chỉ a hoặc b nhưng không thể cả a lẫn b.
Phép tuyển "a hoặc b" là phép tuyển không loại trừ để chỉ a hoặc b và có thể cả a lẫn b.

Chẳng hạn:

"Hôm nay là ngày Chủ nhật hoặc ngày lễ" ← là phép tuyển không loại trừ.
"20 là số lẻ hoặc nó chia hết cho 2" ← là phép tuyển loại trừ.

Phép kéo theo

a kéo theo b là một mệnh đề, kí hiệu là a

\Rightarrow

b, chỉ sai khi a đúng và b sai và đúng trong các trường hợp còn lại.

**Bảng giá trị chân lí của phép kéo theo**
a	b	a $\Rightarrow$ b
1	1	1
1	0	0
0	1	1
0	0	1

Chú ý: Mệnh đề a kéo theo b thường được diễn đạt dưới nhiều hình thức khác nhau, chẳng hạn:
"Nếu a thì b"
"Có b khi có a"
"Từ a suy ra b"
"a là điều kiện đủ để có b"
"b là điều kiện cần (ắt có) để có a"
.............. Ví dụ:

"15 có chữ số tận cùng bằng 5 suy ra 15 chia hết cho 5" ← mệnh đề đúng.
"Nếu dây tóc bóng đèn có dòng điện chạy qua thì bóng đèn sáng" ← mệnh đề đúng.

Chú ý:

1. Trong lôgic, khi xét giá trị chân lí của mệnh đề a

\Rightarrow

b người ta không quan tâm đến mối quan hệ về nội dung của hai mệnh đề a, b. Không phân biệt trường hợp a có phải là nguyên nhân để có b hay không, mà chỉ quan tâm đến tính đúng, sai của chúng.

Ví dụ:

"Nếu mặt trời quay quanh Trái Đất thì Việt Nam nằm ở Châu Âu" ← mệnh đề đúng. Vì ở đây hai mệnh đề a = "mặt trời quay quanh Trái Đất" và b = "Việt Nam nằm ở Châu Âu" đều sai.
"Nếu tháng 12 có 31 ngày thì mỗi năm có 13 tháng" ← mệnh đề sai.

2. Theo bảng chân lí trên, ta thấy:

Nếu a sai thì a $\Rightarrow$ b luôn đúng.
Nếu a đúng thì a $\Rightarrow$ b đúng khi b đúng.

Vì vậy để chứng minh mệnh đề a

\Rightarrow

b đúng ta chỉ cần xét trường hợp a và b cùng đúng và phép chứng minh mệnh đề a $\Rightarrow$ b được tiến hành theo ba bước:

Bước 1. Giả sử a đúng.

Bước 2. Từ giả thiết a đúng, dùng lập luận và các mệnh đề toán học đã biết, suy ra b đúng.

Bước 3. Kết luận a $\Rightarrow$ b luôn đúng.

Trong mệnh đề a $\Rightarrow$ b ta gọi a là giả thiết, b là kết luận.

3. Nếu ta coi a

\Rightarrow

b là mệnh đề thuận thì b

\Rightarrow

a là mệnh đề đảo,

\overline{a}

\Rightarrow

\overline{b}

là mệnh đề phản và

\overline{b}

\Rightarrow

\overline{a}

là mệnh đề phản đảo.

4. Trong văn học, mệnh đề kéo theo còn được diễn đạt bằng nhiều hình thức phong phú. Chẳng hạn:
"Bao giờ bánh đúc có xương,
Bấy giờ dì ghẻ mới thương con chồng"

hoặc
"Chuồn chuồn bay thấp thì mưa,
Bay cao thì nắng bay vừa thì râm".

Phép tương đương

Bài chi tiết: Tương đương logic

a tương đương b là một mệnh đề, kí hiệu là a

\Leftrightarrow

b, nếu cả hai mệnh đề a và b cùng đúng hoặc cùng sai.

**Bảng giá trị chân lí của mệnh đề tương đương**
a	b	a $\Leftrightarrow$ b
1	1	1
1	0	0
0	1	0
0	0	1

Chú ý:

1. Trong thực tế, mệnh đề "a tương đương b" thường được diễn đạt dưới nhiều hình thức khác nhau. Chẳng hạn:
"a khi và chỉ khi b"
"a nếu và chỉ nếu b"
"a và b là hai mệnh đề tương đương"
"a là điều kiều kiện cần và đủ để có b"

2. Hai mệnh đề a, b tương đương với nhau hoàn toàn không có nghĩa là nội dung của chúng như nhau, mà nó chỉ nói lên rằng chúng có cùng giá trị chân lí (cùng đúng hoặc cùng sai).

Ví dụ:

"Tháng 12 có 31 ngày khi và chỉ khi Trái Đất quay quanh mặt trời" là mệnh đề đúng.
"12 giờ trưa hôm nay Tuấn có mặt ở Hà Nội nếu và chỉ nếu vào giờ đó anh đang ở thành phố Hồ Chí Minh" là mệnh đề sai.
"Hình vuông có một góc tù khi và chỉ khi 100 là số nguyên tố" là mệnh đề đúng.

3. Một cách khác, người ta cũng nói rằng a tương đương b khi và chỉ khi cả hai mệnh đề a

\Rightarrow

b và b

\Rightarrow

a cùng đúng. Vì vậy để chứng minh mệnh đề a

\Leftrightarrow

b ta chứng minh hai mệnh đề a

\Rightarrow

b và b

\Rightarrow

4. Các cặp mệnh đề thuận và phản đảo, đảo và phản là những cặp mệnh đề tương đương. Đây chính là cơ sở của phương pháp chứng minh gián tiếp trong toán học.

Sự tương đương lôgic và luật

Công thức

Trong phần trên ta đã xét năm phép toán trên các mệnh đề. Như vậy, nếu có các mệnh đề a, b, c,... khi dùng các phép toán lôgic tác động vào, chúng ta sẽ nhận được những mệnh đề ngày càng phức tạp hơn. Mỗi mệnh đề như thế và cả những mệnh đề xuất phát ta gọi là công thức. Hay nói cách khác:

a) Mỗi mệnh đề gọi là một công thức.

b) Nếu P, Q là những công thức thì

\overline{P}

, P Λ Q, P ν Q, P

\Rightarrow

Q, P

\Leftrightarrow

Q cũng đều là công thức.

c) Mọi dãy kí hiệu khác không xác định theo quy tắc a), b) đều không phải là công thức.

Mỗi công thức được tạo thành từ những mệnh đề dưới tác dụng của các phép toán lôgic. Như vậy ta gán cho mỗi mệnh đề có mặt trong công thức P một giá trị chân lí, dùng bảng chân lí của các phép lôgic ta khẳng định được công thức P là mệnh đề đúng hoặc sai. Nếu P là mệnh đề đúng (hoặc sai) thì ta nói công thức P có giá trị chân lí bằng 1 (hoặc 0).
Ví dụ:

$\overline{a \land \overline{a}}$ (1) là công thức có giá trị chân lí bằng 1 (với mọi mệnh đề a).

**Bảng giá trị chân lí của công thức (1)**
a	$\overline{a}$	a Λ $\overline{a}$	$\overline{a \land \overline{a}}$
0	1	0	1
1	0	0	1

$\overline{(a \Rightarrow b) \Leftrightarrow (\overline{b} \Rightarrow \overline{a})}$ (2) là một công thức có giá trị chân lí bằng 0 (với mọi mệnh đề a, b)

**Bảng giá trị chân lí của công thức (2)**
a	b	$\overline{a}$	$\overline{b}$	$a \Rightarrow b$	$\overline{b} \Rightarrow \overline{a}$	$(a \Rightarrow b) \Leftrightarrow (\overline{b} \Rightarrow \overline{a})$	$\overline{(a \Rightarrow b) \Leftrightarrow (\overline{b} \Rightarrow \overline{a})}$
1	1	0	0	1	1	1	0
1	0	0	1	0	0	1	0
0	1	1	0	1	1	1	0
0	0	1	1	1	1	1	0

Sự tương đương lôgic

Cho P và Q là hai công thức. Ta nói rằng hai công thức P, Q tương đương lôgic với nhau, kí hiệu là P ≡ Q, nếu với mọi hệ chân lí gán cho các mệnh đề có mặt trong hai công thức đó thì chúng luôn nhận giá trị chân lí như nhau.
Đặc biệt, hai mệnh đề a, b gọi là tương đương lôgic, kí hiệu là a ≡ b, nếu chúng cùng đúng hoặc cùng sai.
Chú ý:

1. Kí hiệu a ≡ b là để chỉ hai mệnh đề tương đương lôgic chứ không phải là hai mệnh đề bằng nhau.

2. Hai mệnh đề tương đương lôgic có thể về nội dung chúng hoàn toàn không có liên quan.

Chẳng hạn: "Tháng 2 có 31 ngày ≡ 2 + 2 = 11".

3. Quan hệ P ≡ Q còn được gọi là một đẳng thức.

Đẳng thức

Dưới đây là một số đẳng thức thường gặp trong lôgic mệnh đề:

Phủ định của phủ định

(1)

\overline{\overline{a}}

≡ a.

Luật Đờ Moócgăng

(2)

\overline{a \land b}

≡

\overline{a} \vee \overline{b}

(3)

\overline{a \vee b}

≡

\overline{a} \land \overline{b}

Tính chất kết hợp của các phép lôgic

(4) (a Λ b) Λ c ≡ a Λ (b Λ c)

(5) (a ν b) ν c ≡ a ν (b ν c)

Tính chất giao hoán của các phép lôgic

(6) a Λ b ≡ b Λ a

(7) a ν b ≡ b ν a

(8) a

\Leftrightarrow

b ≡ b

\Leftrightarrow

Tính chất phân phối

(9) a Λ (b ν c) ≡ (a Λ b) ν (a Λ c)

(10) a ν (b Λ c) ≡ (a ν b) Λ (a ν c)

Tính lũy đẳng

(11) a Λ a ≡ a

(12) a ν a ≡ a

Biểu diễn phép kéo theo qua các phép lôgic khác

(13)

a \Rightarrow b

≡

\overline{a} \vee b

(14)

a \Rightarrow b

≡

\overline{a \land \overline{b}}

(15)

a \Rightarrow b

≡

\overline{b} \Rightarrow \overline{a}

(luật phản đảo)

Biểu diễn tương đương qua các phép lôgic khác

(16)

a \Leftrightarrow b

≡

(a \Rightarrow b) \land (b \Rightarrow a)

(17)

a \Leftrightarrow b

≡

\overline{a} \Leftrightarrow \overline{b}

Các đẳng thức về 0 và 1

Người ta còn dùng kí hiệu 1 (hoặc 0) để chỉ một mệnh đề luôn luôn đúng (hoặc luôn luôn sai). Ta có các đẳng thức sau về 0 và 1:

(18) a Λ 0 ≡ 0

(19) a ν 0 ≡ a

(20) a Λ 1 ≡ a

(21) a ν 1 ≡ 1

(22) a ν

\overline{a}

≡ 1 (luật bài trung)

(23) a Λ

\overline{a}

≡ 0 (luật mâu thuẫn)

Chứng minh đẳng thức

Để chứng minh một đẳng thức trong lôgic mệnh đề ta thường dùng phương pháp lập bảng giá trị chân lí.
Ví dụ 1: Chứng minh:

\overline{a \land b}

≡

\overline{a} \vee \overline{b}

**Bảng giá trị chân lí**
a	b	$\overline{a \land b}$	$\overline{a} \vee \overline{b}$
1	1	0	0
1	0	1	1
0	1	1	1
0	0	1	1

Nhìn cột 3 và 4 trong bảng trên ta thấy hai công thức

\overline{a \land b}

và

\overline{a} \vee \overline{b}

luôn nhận giá trị chân lí như nhau. Vậy ta có điều phải chứng minh.
Ví dụ 2: Chứng minh:

a \Rightarrow b

≡

\overline{b} \Rightarrow \overline{a}

**Bảng giá trị chân lí**
a	b	$a \Rightarrow b$	$\overline{b} \Rightarrow \overline{a}$
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

Nhìn cột 3 và 4 trong bảng trên ta thấy hai công thức

a \Rightarrow b

và

\overline{b} \Rightarrow \overline{a}

luôn nhận giá trị chân lí như nhau. Vậy ta có điều phải chứng minh.

Hàm mệnh đề. Các lượng từ tồn tại và tổng quát

Khái niệm về hàm mệnh đề

Ta xét các ví dụ sau:
Ví dụ 1: "Số tự nhiên n chia hết cho 5".
Về phương diện ngôn ngữ thì đây là một câu. Nhưng câu này chưa phản ánh tính đúng hoặc sai một thực tế khách quan nào, cho nên nó chưa phải là mệnh đề. Song nếu ta thay n bằng số tự nhiên cụ thể, chẳng hạn:

Thay n = 100 ta được mệnh đề đúng: "Số 100 chia hết cho 5".
Thay n = 101 ta được mệnh đề sai: "Số 101 chia hết cho 5".

Ví dụ 2: "x + 3 > 7".
Tương tự như trong ví dụ 1, x + 3 > 7 chưa phải là mệnh đề, song nếu ta thay x bởi một số thực cụ thể, chẳng hạn:

Thay x = 0 ta được mệnh đề sai: "0 + 3 > 7".
Thay x = 5 ta được mệnh đề đúng: "5 + 3 > 7".

Ví dụ 3: "Ông A là nhà toán học vĩ đại".
Câu trên chưa phải là mệnh đề. Nhưng nếu ta chọn "ông A" là "Gausơ" sẽ được mệnh đề đúng: "Gausơ là nhà toán học vĩ đại", nếu ta chọn "ông A" là "Đinh Bộ Lĩnh" thì sẽ được mệnh đề sai: "Đinh Bộ Lĩnh là nhà toán học vĩ đại".
Từ các ví dụ trên ta đi đến định nghĩa sau:
Những câu có chứa các biến mà bản thân nó chưa phải là mệnh đề nhưng khi ta thay các biến đó bởi các phần tử thuộc tập xác định X thì nó trở thành mệnh đề (đúng hoặc sai) ta sẽ gọi là hàm mệnh đề (hoặc vị từ, hàm phán đoán, mệnh đề không xác định, mệnh đề chứa biến). Tập X gọi là miền xác định của hàm mệnh đề đó.
Ta dùng kí hiệu: T(n), F(x),... để chỉ các hàm mệnh đề.
Chẳng hạn:

Hàm mệnh đề T(n): "Số tự nhiên n chia hết cho 5" có miền xác định là tập các số tự nhiên N. Tập các số tự nhiên có tận cùng bằng 0 hoặc 5 là miền đúng của T(n).
Hàm mệnh đề F(x) = "x + 3 > 7" có miền xác định là các số thực. Tập các số thực lớn hơn 4 ta gọi là miền đúng của hàm mệnh đề F(x).

Mệnh đề tồn tại

Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Tồn tại

x \in X

sao cho..." vào trước hàm mệnh đề T(x) ta được mệnh đề:

"Tồn tại $x \in X$ sao cho T(x)"

Ta gọi mệnh đề có cấu trúc như trên là mệnh đề tồn tại. Kí hiệu là:

\exists x \in X: T(x)

hoặc

\exists x\ T(x)

x \in X

Kí hiệu

\exists

gọi là lượng từ tồn tại.
Ví dụ:

"Tồn tại số thực x sao cho x + 4 > 7" là mệnh đề đúng.

Kí hiệu là:

\exists x: x + 4 > 7

"Tồn tại số tự nhiên n sao cho n chia hết cho 5" là mệnh đề đúng.

Kí hiệu là:

\exists n \in \mathbb{N}: n\ \vdots\ 5

"Tồn tại số thực x sao cho x² + 1 = 0" là mệnh đề sai.

Kí hiệu là:

\exists x: x^2 + 1 = 0

Chú ý:

1. Trong thực tế, mệnh đề tồn tại còn được diễn đạt dưới những dạng khác nhau, chẳng hạn:

"Tồn tại ít nhất một $x \in X$ sao cho T(x)".
"Có một $x \in X$ sao cho T(x)".
"Có ít nhất một $x \in X$ sao cho T(x)".
"Ít ra cũng có một người là nhà toán học".
"Một số người là nhà toán học".
"Có nhiều người là nhà toán học"
..................

2. Ta dùng kí hiệu

\exists ! x \in X: T(x)

với nghĩa "Tồn tại duy nhất một

x \in X

sao cho T(x)".

Mệnh đề tổng quát

Cho T(x) là hàm mệnh đề xác định trên miền X. Nếu ta đặt thêm cụm từ "Với mọi

x \in X

ta có..." vào trước hàm mệnh đề T(x) ta được mệnh đề:

"Với mọi $x \in X$ ta có T(x)"

Ta gọi mệnh đề có cấu trúc như trên là mệnh đề tổng quát (hoặc toàn thể, phổ biến, phổ cập,...). Kí hiệu là:

\forall x \in X,\ T(x)

hoặc

(\forall x \in X)\ T(x)

hoặc

\forall x \ T(x)

x \in X

Kí hiệu

\forall

gọi là lượng từ tổng quát (hay toàn thể, phổ biến, phổ cập,...)

Phủ định của mệnh đề tồn tại và tổng quát

Phủ định các mệnh đề tồn tại và tổng quát được thiết lập theo hai quy tắc dưới đây:

\overline{\exists x\in X: T(x)}\equiv\forall x \in X, \overline{T(x)}\ \ v \grave{a}\ \ \overline{\forall x \in X, T(x)}\equiv \exists x\in X: \overline{T(x)}

Như vậy, hai mệnh đề:

$\exists x\in X: T(x)$ và $\forall x \in X, \overline{T(x)}$ là phủ định của nhau.
$\forall x \in X, T(x)$ và $\exists x\in X: \overline{T(x)}$ là phủ định của nhau.