Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH

4

CHƯƠNG I
CÁC KIẾN THỨC CƠ SỞ

1.1. MỆNH ĐỀ
1.1.1. Định nghĩa mệnh đề
Một mệnh đề là một câu phản ánh một điều đúng hoặc sai, chứ không
thể vừa đúng vừa sai.
Ví dụ: Tất cả các câu sau đều là các mệnh đề
(1). 2 + 3 = 5
(2). 3 x 4 = 10
(3). Tam giác đều có 3 cạnh bằng nhau
(4). Thái Nguyên là thủ đô Kháng chiến
(5). Washington D.C. là thủ đô của Canada
Câu xác định "2 + 3 = 5", "Tam giác đều có 3 cạnh bằng nhau" và "Thái
Nguyên là thủ đô Kháng chiến" là các mệnh đề đúng. Các câu xác định "3 x 4
= 10" và "Washington D.C. là thủ đô của Canada" là các mệnh đề sai.
Như vậy, một mệnh đề có thể là mệnh đề đúng hoặc mệnh đề sai. Hay
nói cách khác, một mệnh đề chỉ có thể lựa chọn 1 trong 2 giá trị là đúng hoặc
là sai.
Một mệnh đề không thể vừa đúng vừa sai.
Ví dụ: Xét các câu sau
(1). Hôm nay là thứ mấy ?
(2). Hãy đọc kỹ đọan văn này
(3). x + 1 = 2
(4). x + y = z
Câu "Hôm nay là thứ mấy ? " và " Hãy đọc kỹ đoạn văn này" không
phải là mệnh đề vì chúng không phải là câu khảng định. Còn các câu "x+1=2"

Giả sử P và Q là hai mệnh đề. Mệnh đề "P và Q", được kí hiệu bởi
P∧Q, là đúng khi cả P và Q đều đúng, là sai trong các trường hợp còn lại.
Mệnh đề P∧Q được gọi là hội của P và Q.
Ví dụ: Cho 2 mệnh đề P và Q như sau
P = " 2 > 0 " là mệnh đề đúng
Q = " 2 = 0 " là mệnh đề sai
P ∧ Q = " 2> 0 và 2 = 0 " là mệnh đề sai.
Bảng chân trị
Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH

6

P Q
P ∧
∧∧
∧ Q
T T T
T F F
F T F
F F F
1.1.4. Tuyển của hai mệnh đề
Giả sử P và Q là hai mệnh đề. Mệnh đề "P hoặc Q" được kí hiệu P∨Q,
là sai khi cả P và Q đều sai, là đúng trong các trường hợp còn lại. Mệnh đề
P∨Q được gọi là tuyển của P và Q
Ví dụ : Cho 2 mệnh đề P và Q như sau
P = " 2 > 0 " là mệnh đề đúng
Q = " 2 = 0 " là mệnh đề sai
P ∨ Q = " 2 > 0 hoặc 2=0" là mệnh đề đúng.
Bảng chân trị
P Q

kéo theo này P được gọi là giả thiết còn Q được gọi là kết luận.
Trong các suy luận toán học phép kéo theo P → Q được dùng để diễn
đạt “Nếu P thì Q”
Ví dụ: Cho hai mệnh đề P và Q như sau
P = " tam giác T là đều "
Q = " tam giác T có một góc bằng 60
0
"
P → Q = " nếu tam giác T là đều thì tam giác T có một góc bằng 60
0
"

P Q
P → Q
T T T
T F F
F T T
F F T

1.1.7. Mệnh đề tương đương
Giả sử P và Q là hai mệnh đề. Mệnh đề tương đương, được kí hiệu bởi
P⇔Q, là đúng khi P và Q có cùng giá trị chân lí, là sai trong các trường hợp
còn lại. Mệnh đề P ⇔ Q còn được gọi là mệnh đề hai điều kiện.
Trong các suy luận toán học phép tương đương P ⇔ Q được dùng để
diễn đạt “P nếu và chỉ nếu Q” hay “P là cần và đủ đối với Q”

P Q
P ⇔ Q
T T T
T F F

Ví dụ: Tìm OR bit, AND bit và XOR bit đối với 2 xâu sau đây
01 1011 0110
11 0001 1101
11 1011 1111 OR bit
01 0001 0100 AND bit
10 1010 1011 XOR bit
Các kiến thức cơ sở Nguyễn Thế Vinh- ĐHKH

9

1.3. SỰ TƯƠNG ĐƯƠNG CỦA CÁC MỆNH ĐỀ
Định nghĩa: Các mệnh đề P và Q được gọi là tương đương logic nếu
P↔Q là hằng đúng. Kí hiệu P≡Q để chỉ P và Q là tương đương logic.
Một các để xác định hai mệnh đề có tương đương logic không là lập
bảng chân trị. Dựa vào bảng nếu các cột cho giá trị của chúng phù hợp với
nhau, từ đó kết luận rằng các mệnh đề đó là tương đương logic. Sau đây là ví
dụ minh họa
Ví dụ: Chứng minh rằng P→ Q và ¬Q→ ¬P là tương đương logic
P Q
P→ Q
¬P ¬Q
¬Q→ ¬P
T T T F F T
T F F F T F
F T T T F T
F F T T T T
Dựa vào bảng ta thấy cột 3 và cột 6 có các giá trị tương ứng phù hợp
với nhau. Vậy P→ Q và ¬Q→ ¬P là tương đương logic.(đpcm)
Ta nhận thấy rằng đối với một mệnh đề phức hợp việc lập bảng gặp
nhiều khó khăn vì nếu có n mệnh đề phải cần ít nhất 2