Chương 3. Lôgic và suy luận toán học

Chương 3. LÔGIC VÀ SUY LUẬN TOÁN HỌC
I. ĐẠI SỐ MỆNH ĐỀ
1. Mệnh đề sơ cấp
Các phát biểu khẳng định không thể chia nhỏ được và có giá trị hoặc đúng (1, true, yes)
hoặc sai (0, false, no) được gọi là mệnh đề sơ cấp. Giá trị của mệnh đề sơ cấp được gọi là giá trị
chân lý. Kí hiệu các mệnh đề sơ cấp bởi các chữ cái X, Y, Z, ...
Trong bài giảng này để biểu thị giá trị chân lý "đúng", "sai" ta dùng 1 (true) và 0 (false).
Ví dụ 1:
 "3 là số nguyên tố" là một mệnh đề có giá trị chân lý là 1
 "x chia hết cho 3" không phải là mệnh đề vì nó chỉ trở thành khẳng định với x cụ thể
hoặc khi thêm các lượng từ với mọi, tồn tại vào trước mệnh đề.
 "Bao giờ cho đến tháng mười" không phải là một mệnh đề vì nó không phải là khẳng
định.
2. Mệnh đề, công thức mệnh đề
Các mệnh đề được thành lập từ các mệnh đề sơ cấp bằng các phép toán mệnh đề.
a. Phép toán
Các phép toán : hội (), tuyển (), phủ định (, _), kéo theo () . Bảng chân trị
X

Y

XY

XY

X

XY


0

1

1

0

0

0

1

1

1

Các phép toán trên tương đương với các liên từ "và", "hoặc", "không", "kéo theo"
Chú ý bảng chân trị của phép kéo theo  qua các câu sau đây :
 Vì mặt trời mọc ở hướng đông nên trái đất tròn
 Vì mặt trời mọc ở hướng tây nên trái đất tròn
 Vì mặt trời mọc ở hướng đông nên trái đất vuông
 Vì mặt trời mọc ở hướng tây nên trái đất vuông
Về mặt thực tế khó nói được tính đúng sai của 4 khẳng định dạng trên. Tuy nhiên áp dụng
hệ toán mệnh đề có thể thấy các câu i. ii. là đúng và câu iii. là sai và đặc biệt một câu vô nghĩa
như câu iv. lại là đúng.
b. Công thức mệnh đề
1


i. A  B  A  B
ii. (A  B)  A  B
iii. A  A
Bằng cách lập bảng chân trị ta dễ dàng chứng minh được các cặp công thức tương đương
sau :
Một số công thức tương đương
Tên gọi

Tương đương

Luật đồng nhất

A1A0A

Luật nuốt

A  1  1; A  0  0, A  A  1; A  A  0

Luật luỹ đẳng

AAAAA

Luật phủ định kép

A  A

Luật hấp thụ

A  (A  B)  A; A  (A  B)  A


:

A  (A  B)
:

(A  A)  (A  B)
:

0  (A  B)
:

(A  B)
Ví dụ 2 : Chứng minh A  (A  B) = A

(A  0)  (A  B)
:

A  (0  B)
:

A  (B  0)
:

A0
:

A
:

De Morgan

B

AB

AB

(A  B)  (A  B)

1

1

1

1

1
3


Chương 3. Lôgic và suy luận toán học

1

0

0

1


các đồng nhất đúng.
Chứng minh: bài tập.



Định lý này cho thấy mối quan hệ giữa tính tương đương và tính đồng nhất đúng.
Ví dụ 7:
 A  A vì cả A  A và A  A đều là các đồng nhất đúng.
 A  (B  A) là công thức đồng nhất đúng nhưng không thể khẳng định A  B  A, vì
(B  A)  A chỉ là tiếp liên.
5. Luật đối ngẫu
Giả sử A là một công thức chỉ chứa các phép toán , ,  mà không chứa phép toán .
Trong A đối chỗ vai trò hai phép toán ,  cho nhau và thay giá trị của cặp 1, 0 ta được công
thức A* gọi là công thức đối ngẫu của A. Từ định nghĩa dễ dàng thấy được nếu B là công thức
đối ngẫu của A thì A cũng là đối ngẫu của B
Ví dụ 8: Đối ngẫu của công thức X  (Y  X) là công thức X  (Y  X)
Định lý 2: Cho A(X) và B(X) là các công thức, trong đó X là bộ các mệnh đề sơ cấp
và B(X) là công thức đối ngẫu của A(X). Khi đó ta có :
i. A(X)  B(X) và B(X) = A(X)
ii. A(X)  B(X) và B(X)  A(X)
Chứng minh: Chứng minh theo định nghĩa đệ quy của công thức A và dùng luật De Morgan.
Ví dụ 9:
Cho
ta có :



A(X, Y, Z) = (X  Y)  (Y  Z)  A*(X, Y, Z) = (X  Y)  (Y  Z)
A*((X, Y, Z))


số bất kỳ vị trí X trong A bởi một công thức mệnh đề B nào đó ta sẽ nhận được công thức mệnh
đề mới kí hiệu A(X|B).
Định lý 4: Nếu A(X) là đồng nhất đúng thì A(X|B) cũng là đồng nhất đúng với mọi
công thức B bất kỳ.
Chứng minh: chứng minh theo định nghĩa của công thức đồng nhất đúng.



Ví dụ 11: (A  B)  A là đồng nhất đúng. Do đó thay A bởi (B  A) ta nhận được công thức
((B  A)  B)  (B  A) cũng là đồng nhất đúng.
7. Luật kết luận
Định lý 5: Nếu A và A  B là các công thức đồng nhất đúng thì B cũng là công thức
đồng nhất đúng
Chứng minh: Phản chứng.



II. BÀI TOÁN THOẢ ĐƯỢC
Một công thức mệnh đề A gọi là thoả được nếu tồn tại một bộ giá trị của các mệnh đề sơ
cấp sao cho công thức có giá trị đúng (1).
Như vậy một công thức A là không thoả được khi nó không phải là đồng nhất sai tức A
không phải là đồng nhất đúng. Do vậy để giải bài toán thoả được ta đưa về xét bài toán đồng nhất
đúng. Nếu A không là đồng nhất đúng thì A là thoả được.
Dễ thấy có tồn tại thuật toán tìm đồng nhất đúng. Ví dụ lập bảng chân trị. Tuy nhiên
phương pháp này có độ phức tạp lớn (O(2n)). Do vậy ta đưa ra một cách khác kiểm tra tính đồng
nhất đúng với độ phức tạp bé hơn.
Giả thiết cần kiểm tra một công thức A là đồng nhất đúng ? Giả sử A chứa 64 biến
mệnh đề sơ cấp. Nếu làm theo phương pháp liệt kê bảng chân trị ta sẽ thu được bảng
5


Để xây dựng dạng chuẩn tắc tuyển ta theo các bước :
 Khử 
 Dùng De Morgan và phân phối đưa về chỉ 3 phép toán , , .
 Đưa công thức về dạng chuẩn tắc
Ví dụ 12: X  (Y  X) = X  Y  X
là dạng chuẩn tắc tuyển với ba HSC là X, Y, X
là dạng chuẩn tắc hội với một TSC là X  Y  X nên là đồng nhất đúng.
III. VỊ NGỮ VÀ LƯỢNG TỪ
4. Vị ngữ
i.

Xét các câu có liên quan đến biến như :
P(x) := x > 3
6


Chương 3. Lôgic và suy luận toán học

ii. Q(x,y) := x = y + 3
iii. R(x,y,z) := x + y + z = 0
Các câu trên có giá trị (1, 0, 1, 0) chỉ khi x, y, z nhận giá trị cụ thể.
P, Q, R được gọi là các hàm mệnh đề, x, y, z là các biến và "tính chất", "ràng buộc" của x,
y, z là vị ngữ. Ví dụ đối với hàm mệnh đề P(x), x là biến và "lớn hơn 3" là vị ngữ.
Với các giá trị cụ thể của x, y, z thì P, Q, R có giá trị chân lý. Ví dụ P(1) = 0, P(4) = 1.
5. Lượng từ
Đề hàm mệnh đề nhận giá trị ta cần xét giá trị cụ thể của các biến. Tuy nhiên một hàm
mệnh đề cũng có thể được lượng từ hoá để nhận giá trị.
a. Lượng từ "với mọi"
xP(x) = 1  P(x) đúng với mọi x trong không gian.
Ví dụ 13: x. x  0 là một mệnh đề đúng. Hàm mệnh đề P(x) là x2  0.

Có thể tách thành 2 hàm mệnh đề : “mọi người đều có một người bạn tốt nhất” và
“mọi người đều có chỉ một người bạn tốt nhất”. Đây là 2 hàm mệnh đề có liên quan đến
nhau và có thể biểu diễn được bởi một hàm mệnh đề : B(x,y) = "y là bạn tốt nhất của x"
x y (B(x,y)  z(z  y  B(x,z))
Ví dụ 17: bài tập
 "Tất cả sư tử đều hung dữ"
 "Một số sư tử không uống cà phê"
 "Một số sinh vật hung dữ không uống càfê "

x(P(x)  Q(x))
x(P(x)  R(x))
x(Q(x)  R(x))

P(x) = "x là sư tử", Q(x) = "x hung dữ", R(x) = "x uống cà phê
Cần phân biệt x(P(x)  R(x)) và x(P(x)  R(x)) (bài tập)
IV. CÁC PHƯƠNG PHÁP CHỨNG MINH
1. Các qui tắc suy diễn
Định lý là một mệnh đề có thể chứng minh là đúng đắn. Để chứng minh tính đúng của
mệnh đề ta có thể xuất phát từ các mệnh đề được chấp nhận đúng ban đầu gọi là tiên đề và từ
nhiều phương pháp bằng nhiều qui tắc suy luận toán học ta rút ra các mệnh đề đúng tiếp theo kéo
thành dãy và kết thúc thành mệnh đề cần chứng minh. Trong thực tế ta thường xuất phát từ những
mệnh đề trung gian (hoặc các bổ đê) đã được chứng minh là đúng đắn.
Bảng sau là một số qui tắc suy luận quan trọng thường đặt trên cơ sở các đồng nhất đúng
trong lôgic mệnh đề và lôgic vị từ. Chúng ta có thể xây dựng rất nhiều các qui tắc suy diễn như
vậy dựa trên các đồng nhất đúng tuy nhiên ta chỉ xét các suy diễn tương đối đơn giản dễ nhớ và
dễ áp dụng.
Tên gọi

Đồng nhất đúng



pq,qrpr

Tam đoạn luận tuyển

((p  q)  p)  q

p  q , p  q

Các ví dụ :
 Mặt trời mọc ở hướng đông hoặc quả đất vuông là một định lý.
 Tam giác là đa giác có 3 cạnh và 3 góc. Do vậy tam giác là đa giác có 3 cạnh.
 Ta đã biết 2 định lý : 3 là số lẻ và nếu n là một số lẻ thì n+1 chia hết cho 2. Vậy 4 = 3+1
chia hết cho 2 vì 3 là một số lẻ.
 n là một số lẻ thì n+1 chia hết cho 2. 8+1 không chia hết cho 2 vậy 8 không phải là số lẻ.
8


Chương 3. Lôgic và suy luận toán học
 Đã biết : nếu năm chia chẵn cho 4 thì là năm nhuận và nếu năm nhuận thì tháng 2 có 29
ngày. Vậy tháng 2 năm 2000 có 29 ngày.
 Hiện nay trời đang mưa hoặc có nhiều mây. Nếu hiện nay trời không mưa thì có nhiều
mây.
Suy luận có cơ sở : Các suy luận dùng qui tắc suy diễn dựa trên công thức đồng nhất đúng.
Nguỵ biện : Các suy luận dùng qui tắc suy diễn dựa trên đồng nhất sai hoặc tiếp liên
Một suy luận có cơ sở có thể dẫn đến kết quả đúng hoặc sai tuỳ thuộc vào các giả thiết
đúng hoặc sai. Một nguỵ biện luôn luôn dẫn đến kết quả không được chấp nhận (luôn luôn sai).
Ví dụ về suy luận có cơ sở :
 Cắt chân cào cào, hô nhảy cào cào không nhảy vậy tai cào cào nằm ở chân.
 Nếu a = b thì a2 = ab  a2 - b2 = ab - b2 = b(a - b). Mặt khác a2 - b2 = (a - b)*(a + b).

Cách chứng minh này cũng có thể được quan niệm như chứng minh bằng phản chứng,
chứng minh bằng mâu thuẫn phụ thuộc vào cách trình bày. Chứng minh bằng phản chứng khi ta
quan niệm mệnh đề p  q như một mệnh đề p không cần phân chia. Chứng minh bằng mâu
thuẫn (hoặc cũng gọi là phản chứng) khi ta giả thiết p đúng và q đúng khi đó suy ra được p,
tức dẫn đến mâu thuẫn vì có p và p. Minh hoạ cho nhận xét này là chứng minh A  (B  A) là
hằng đúng :
 Phản chứng : giả thiết A  (B  A) = 0  A = 1 và B  A = 0  B = 1 và A = 0, như
vậy ta có A = 1 và A = 0 => mâu thuẫn
 Gián tiếp : xem p = A và q = B  A, giả thiết q tức B  A = 0  B = 1, A = 0 tức p
9


Chương 3. Lôgic và suy luận toán học
vậy p  q
 Mâu thuẫn : Giả thiết có p tức A = 1, và q tức B  A = 0 tức A = 0 dãn đến mâu
thuẫn.
c. Cần chứng minh (p1  p2  ...  pn)  q
Chứng minh từng trường hợp : (p1  q)  (p2  q)  ...  (pn  q).
Ví dụ : Nếu n không chia hết cho 3 thì n2  1 (mod 3). 1ách n thành 2 trường hợp chia 3 dư
1 và chia 3 dư 2.
d. Cần chứng minh p  q
Chứng minh p  q và q  p.
Ví dụ : Cho R là một quan hệ tương đương. Các điều sau đây là tương đương
i. aRb
ii. [a]R = [b]R
iii. [a]  [b]  
e. Cần chứng minh xP(x)
 Chứng minh bằng kiến thiết : Chỉ ra x. Ví dụ : với mọi n, tồn tại n số nguyên liên tiếp là
hợp số. Tức nx (x + i) là hợp số (i=1..n). Lấy x = (n + 1)! + 1.
 Trực tiếp hoặc phản chứng : Ví dụ x3 - 3x + 1 = 0 có nghiệm trên [0, 1]. Áp dụng định lý

vậy, theo quy nạp toán học, mọi người trong hàng đều biết điều bí mật. Một cách minh họa khác
là một dãy quân cờ đô-mi-nô có nhãn là 1,2,3,.. đang đứng trên mặt bàn. Giả sử P(n) là mệnh đề
“quân đô-mi-nô n bị đổ”. Nếu quân 1 bị đổ, tức là P(1) đúng, và nếu quân n đổ thì quân (n+1)
cũng đổ, tức là nếu P(n)  P(n+1) là đúng, thì khi đó tất cả các quân đô-mi-nô đều bị đổ.
b. Tính đúng đắn của phương pháp qui nạp
Để chứng minh phương pháp quy nạp toán học là đúng đắn ta cần giải thích chúng dựa trên
tiên đề sắp tốt của tập các số nguyên.
Tiên đề phát biểu : Mọi tập số nguyên không âm luôn có phần tử nhỏ nhất.
Giả sử ta đã chứng minh P(1) là đúng và mệnh đề P(n)  P(n+1) cũng đã được chứng minh
là đúng với mọi số nguyên dương n. Giả thiết có ít nhất một số nguyên dương sao cho P(n) là sai.
Khi đó tập S bao gồm các số nguyên dương n mà P(n) sai là không rỗng. Theo tiên đề sắp tốt, S
có phần tử nhỏ nhất, gỉa sử là k. Vì P(1) đúng nên k > 1. Do 0 < k-1 < k nên k-1 không thuộc S,
tức là P(k-1) đúng. Nhưng vì mệnh đề P(k-1)  P(k) là đúng, ta suy ra P(k) là đúng. Điều này vô
lý vì k thuộc S. Do vậy, P(n) là đúng với mọi n nguyên dương.
(Ví dụ về tiên đề sắp tốt : Chứng minh : nếu a là một số nguyên và d là một số nguyên
dương khi đó có duy nhất các số nguyên q và r sao cho 0  r < d và a = dq + r.
Chứng minh: Giả sử S là tập các số nguyên không âm dạng a - dq trong đó q là một số nguyên.
Tập này không rỗng vì -dq có thể lớn tùy ý bằng cách chọn q âm có trị tuyệt đối đủ lớn.
Theo tính được sắp tốt, S có số nhỏ nhất là r = a - dq0. Rõ ràng r < d, vì nếu ngược lại ta xét
số a - d(q0+1) = (a - dq0) - d = r - d  0 tức là a - d(q0+1) thuộc tập S mà lại nhỏ hơn r. Đó là
điều vô lý. Do vậy có các số nguyên q, r sao cho a = dq + r và 0  r < d. Tính duy nhất của
q và r cho có thể được chứng minh dễ dàng)
Chú ý : ở bước cơ sở thay cho 1 có thể là một k nào đó, khi đó ở bước qui nạp cần chứng
minh P(n)  P(n+1) với n  k.
c. Ví dụ
Ví dụ 1: 1 + 2 + ... + n = n(n+1)/2
Ví dụ 2: Mọi số nguyên lớn hơn 1 đều có thể phân tích thành tích của các thừa số ng. tố
Ví dụ 3: Số hạng dãy Fibonaci f(n) =



1
2



1
3

 . . . .

1
k

11


Chương 3. Lôgic và suy luận toán học

Ví dụ 7: Chứng minh rằng:

n

H2n  1

2

trong đó n là số nguyên không âm.

Chứng minh: Giả sử P(n) là mệnh đề “ H 2
Bước cơ sở : P(0) là đúng vì

1

1



2

3

 H2n 

 (1 

n
2

2

 (1 

2

1
2

n

1



1

 . . .
2

n1

1

 . . .
2

 (1 

n1

n

1

) 

2

2

n

1






Ak

k 1

2.

Chứng minh: Giả sử P(n) là đẳng thức cần chứng minh.
Bước cơ sở : Rõ ràng P(2) là đúng vì
ta đã chứng minh trong chương 1.

A1  A 2  A1  A 2

chính là định luật DeMorgan mà

n

Bước quy nạp : Giả sử P(n) là đúng, tức là :


k 1

n

Ak 




n1
 n



   Ak   An  1   Ak
 k 1

k 1



2. Dạng tổng quát của quy nạp toán học
12


Chương 3. Lôgic và suy luận toán học
a. Phương pháp
 Bước cơ sở : Chỉ ra mệnh đề P(k)  P(k+1)  …  P(k+m) là đúng.
 Bước quy nạp : Chứng tỏ [P(k)  P(k+1)  ...  P(n)]  P(n+1) là đúng với mọi n
nguyên dương, trong đó 1 k  n.
Việc chứng minh tính đúng đắn tương tự dạng nguyên thuỷ (bài tập).
b. Ví dụ
Ví dụ 1: Chỉ ra rằng nếu n là một số nguyên lớn hơn 1, khi đó n có thể viết dưới dạng tích của các
số nguyên tố.
Chứng minh: Gọi P(n) là mệnh đề “n có thể viết dưới dạng tích của các số nguyên tố”.
Bước cơ sở : P(2) là đúng vì 2 là tích của chính nó.
Bước quy nạp : Gỉa sử P(k) là đúng với k = 2, 3, .., n. Ta phải chứng minh P(n+1) là đúng.

không âm, chúng ta cho:
13


Chương 3. Lôgic và suy luận toán học
 Giá trị của hàm tại các giá trị ban đầu.
 Công thức tính giá trị của nó tại số nguyên n từ các giá trị của nó tại các số nguyên nhỏ
hơn.
a. Ví dụ về định nghĩa đệ qui
Ví dụ 1: Dãy Fibonaci

- f(1) = f(2) = 1

Ví dụ 2: Tập số chẵn

-2S

Ví dụ 3: Xâu

-  là một xâu - x là một xâu và c là chữ cái thì xc là một xâu.

Ví dụ 4: Độ dài xâu

- l() = 0

- f(n) = f(n - 1) + f(n - 2)

- Nếu x  S và y  S thì x + y  S.

- l(xc) = l(x) + 1


n 1

F ( n  1) 

a
k0



   a k   a n 1  F ( n )  a n 1
 k0

n

k

Ví dụ 7: Biểu thức lôgic :
 1, 0 và p, trong đó p là một biến mệnh đề, là biểu thức.
 (  p ), ( p  q ), ( p  q ), ( p  q ) là các biểu thức nếu p và q là các biểu thức.
Việc chứng minh các đại lượng được định nghĩa đệ quy thường bằng phương pháp qui
nạp thông qua cấu trúc đệ qui của chúng.
Ví dụ 8: Chỉ ra rằng

fn  

n2

, trong đó fn là số Fibonaci và





Ví dụ 9: Chứng minh l(xy) = l(x) + l(y), trong đó x và y là các xâu thuộc *.
Chứng minh: Ta chứng minh theo độ dài của y.
 Bước cơ sở : Dễ kiểm tra lại rằng trường hợp y =  khẳng định trên là đúng vì : l(x) =
l(x) = l(x) + 0 = l(x) + l() với mọi xâu x.
14


Chương 3. Lôgic và suy luận toán học
 Bước quy nạp : Giả sử l(xy) là đúng, ta phải chứng minh l(x(yc)) đúng với mọi c
tức là l(x(yc)) = l(x) + l(yc). Theo định nghĩa của xâu và độ dài xâu ta có:

 ,

l(x(yc)) = l(xyc) = l(xy) + 1, theogiả thiết quy nạp ta có
= l(x) + l(y) +1 = l(x) + l(yc).



2. Thuật toán đệ qui
Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán
ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn.
Ví dụ 10: Tìm thuật toán đệ quy tính giá trị n!
Định nghĩa đệ quy hàm UCLN của hai số nguyên a, b không âm cũng cho luôn thuật toán
thuật toán tính UCLN.
3. Đệ quy và lặp
Định nghĩa đệ quy biểu diễn giá trị của hàm tại một số nguyên qua giá trị của nó tại các số
nguyên nhỏ hơn. Điều này có nghĩa là ta có thể xây dựng một thuật tóan đệ quy tính giá trị của


Theo thuật toán này, để tìm fn ta biểu diễn fn = fn-1 + fn-2. Sau đó thay thế cả hai số này bằng
15


Chương 3. Lôgic và suy luận toán học
tổng của hai số Fibôna xi bậc thấp hơn, cứ tiếp tục như vậy cho tới khi f0 và f1 xuất hiện thì được
thay bằng các giá trị của chúng theo định nghĩa.
Bây giờ ta tính số các phép toán cần dùng để tính fn khi sử dụng phương pháp lặp.
Thuật toán này khởi tạo x như f0 = 0 và y như f1 = 1. Khi vòng lặp được duyệt qua tổng của
x và y được gán cho biến phụ z. Sau đó x được gán giá trị của y và y được gán giá trị của z. Vậy
sau khi đi qua vòng lặp lần 1, ta có x = f1 và y = f0+f1 = f2. Khi qua vòng lặp n-1 lần thì x = fn-1
còn y = fn. Như vậy chỉ có n-1 phép cộng được dùng để tìm fn khi n > 1.
Function Iteractive Fibonacci (n: nguyên không âm);
Begin
if n = 0 then return 0
else begin
x:=0; y:=1;
for i:=1 to (n-1) do
begin
z := x+y; x := y; y := z;
end;
Return y;
end;
End;

Chúng ta đã chỉ ra rằng số các phép toán dùng trong thuật toán đệ quy nhiều hơn khi dùng
phương pháp lặp. Tuy nhiên đôi khi người ta vẫn thích dùng thủ tục đệ quy hơn ngay cả khi nó tỏ
ra kém hiệu quả so với thủ tục lặp. Đặc biệt, có những bài toán chỉ có thể giải bằng thủ tục đệ quy
mà không thể giải bằng thủ tục lặp.

f. hoặc bạn bị cúm và bạn thi trượt kỳ thi cuối khoá hoặc bạn không thi trượt kỳ thi
cuối khoá và bạn được lên lớp 
2.

Cho p và q là 2 mệnh đề :
p: bạn lái xe với tốc độ trên 65 km/h

q: bạn bị phạt vì quá tốc độ cho phép

Viết các mệnh đề sau thành công thức mệnh đề :
a. Bạn không lái xe trên 65 km/h
b. Bạn lái xe trên 65 km/h nhưng bạn không bị phạt vì quá tốc độ cho phép
c. Bạn sẽ bị phạt vì quá tốc độ cho phép Nếu bạn lái xe trên 65 km/h.
d. Nếu bạn không lái xe với tốc độ trên 65 km/h thì bạn sẽ không bị phạt vì quá tốc độ cho
phép
e. Lái xe với tốc độ 65 km/h là đủ để bị phạt vì quá tốc độ cho phép
f. Bạn bị phạt vì quá tốc độ cho phép nhưng bạn không lái xe trên 65 km/h
g. Mỗi lần bị phạt vì quá tốc độ cho phép là bạn đã lái xe trên 65 km/h.
Chứng minh:

3.

a. p

b. p  q

c. p  q

e. p  q


c. Trời mưa nếu và chỉ nếu là ngày cuối tuần.
d. Bạn có thể nhìn thấy lão phù thuỷ nếu và chỉ nếu lão không ở trong đó.

5.

Lập bảng chân trị cho các công thức mệnh đề sau :
a. (p  q)  r

b. (p  q)  r

c. (p  q)  r

d. (p  q)  r

e. (p  q)  r

f. (p  q)  r

g. (p  q)  (q  r) h. (p  q)  (q  r)

Chứng minh:
p

q

r

(a)

(b)


1

1

1

1

0

1

1

1

0

1

0

1

0

1

0


0

1

0

1

1

0

1

1

1

0

0

1

1

1

1


1

0

0

1

1

0

1

1

0

0

0

0

0

1

0


h. (p  q)  (p  q)

i. (p  q)  (p  q)
18


Chương 3. Lôgic và suy luận toán học
Chứng minh:
a. (p  q)  (p  q)
p

q

pq

p  q

(a)

1

1

1

0

1


b. (p  q) | (q  r)

c. (p  q)  (q  r)

p

q

r

p  q

qr

qr

(c)

1

1

1

0

1

1


1

0

1

0

0

1

1

0

0

1

1

0

0

1

0


0

0

1

0

0

1

0

0

1

1

0

0

0

0

0


A | B

BC

(e)

AB

B | C

(f)

1

1

1

1

1

1

0

1

1


1

0

1

1

0

1

0

0

1

1

0

0

0

0

1


0

0

1

0

0

1

0

0

0

1

1

0

0

0

1


1

1

1

0


7.

Lập bảng chân trị để chứng minh các công thức tương đương đã học

8.

Dùng bảng chân trị để chứng minh các công thức tương đương sau :
19


Chương 3. Lôgic và suy luận toán học
a. p  q  (p  q)  (p  q)

b. p  p | p

c. p  p  p

d. p | q  (p  q)

e. p  q  (p  q)


1

1

0

1

0

1

1

0

1

1

0

0

0

0

0


1

1

0

0

0

0

0

0

0

1

0

0

0

0

1


1

1

1

1

1

1

Bằng các phép biến đổi tương đương chứng minh tính tương đương của các cặp công thức
sau :
a. p  q và q  p
b. p  q và p  q
c. (p  q) và p  q
d. (p  q) và p  q
e. p  q và (p | q) | (p | q)
f. p  q và (p | p) | (q | q)
g. p  q và (x  y)  (x  y)
h. p  q và (p  p)  (q  q)

Chứng minh:
a. Ta có p  q  p  q  q  p  (q)  (p)  q  p
b. Ta có p  q  (p  q)  (q  p)  (q  p)  (p  q)  p  q
c. Ta có (p  q)  ((p  q)  (p  q))  (p  q)  (p  q)  (p  q)  (q 
p)  p  q
d. Ta có (p  q)  (p  q)  (q  p)  (p  q)  (q  p) 
 (p  q)  (p  p)  (q  q)  (q  p)  (p  q)  (q  p)  p  q



13. Biểu diễn câu sau chỉ dưới dạng phép tuyển và phủ định : "Nếu CSDL danh bạ được mở thì
monitor được đặt ở trạng thái đúng, nếu hệ không ở trạng thái ban đầu của nó". Sau đó phát
biểu lại câu nói này theo công thức vừa tìm được.
Chứng minh: Đặt p = “hệ ở trạng thái ban đầu” , q = “CSDL danh bạ mở”, r = “monitor ở trạng
thái đúng”. Ta có công thức : A = p  (q  r)  p  (q  r) có nghĩa : hệ ở trạng thái
ban đầu của nó hoặc CSDL danh bạ là đóng hoặc monitor ở trạng thái đúng.

II. LÔGIC VỊ TỪ
14. Cho P(x) là câu “x học ở lớp hơn 5 giờ mỗi ngày trong tuần”, không gian là tập hợp các sinh
viên. hãy diễn đạt các biểu thức lôgic sau thành câu thông thường :
a. xP(x)

b. xP(x)

c. xP(x)

d. x P(x)

Chứng minh:
a. Có một sinh viên học ở lớp hơn 5 giờ mỗi ngày trong tuần
b. Mọi sinh viên đều học ở lớp hơn 5 giờ mỗi ngày trong tuần
c. Có một sinh viên không học ở lớp hơn 5 giờ mỗi ngày trong tuần
d. Mọi sinh viên học ở lớp không quá 5 giờ mỗi ngày trong tuần

15. Cho P(x, y) là câu “x đã học môn y”, với không gian của x là tập hợp sinh viên trong lớp,
không gian của y là tập hợp các môn học. Hãy diễn đạt các mệnh đề sau thành câu thông
thường
a. xy P(x,y) b. xy P(x,y) c. xy P(x,y)

f. y x L(x, y)
g. y(xL(x, y)  z (xL(x, z)  (z = y)))
h. y z ((y  z)  L(„Lynn‟, y)  L(„Lynn‟, z)  w (L(„Lynn‟, w)  (w = y  w = z)))
i. xL(x, x)
j. x(L(x, x)  y (y  x  L(x, y)))
Chú ý : Mệnh đề xy (L(x, y)  x = y)  xy (x  y  L(x, y)) vẫn thiếu L(x, x)



17. Dùng lượng từ diễn đạt các câu sau
a. Tất cả sinh viên tin học đều phải học môn toán học rời rạc
b. Có một sinh viên lớp này đã có máy vi tính
c. Tất cả sinh viên lớp này đã học ít nhất một môn tin học
d. Có một sinh viên lớp này đã học ít nhất một môn tin học
e. Mỗi sinh viên trong lớp này ở một nhà trong ký túc xá
f. Có một sinh viên lớp này đã ở tất cả các phòng của ít nhất một nhà trong kí túc xá
g. Tất cả sinh viên lớp này ít nhất đã ở một phòng trong tất cả các nhà của kí túc xá
Chứng minh:
22


Chương 3. Lôgic và suy luận toán học
a. xL(x,‟THRR‟) với x  {sinh viên tin học} và L(x, y) := x học môn y
b. xH(x, „vi tính‟) với x  {sinh viên lớp này} và H(x, y) := x có y
c. x y L(x, y) với x  {sinh viên lớp này}, y  {các môn tin học{, L(x, y) := x học
môn y
d. x y L(x, y) với x  {sinh viên lớp này}, y  {các môn tin học{, L(x, y) := x học
môn y
e. x y L(x, y) với x  {sinh viên lớp này}, y  {nhà của KTX{, L(x, y) := x ở trong
y

P(2,3)  P(3,3)) 
19. Chứng minh rằng xP(x)  xQ(x) và x (P(x)  Q(x)) là không tương đương.
Chứng minh: Lấy ví dụ phản chứng, giả sử x  {1, 2}, khi đó
xP(x)  xQ(x) = (P(1)  P(2))  (Q(1)  Q(2)) =
= (P(1)  Q(1))  (P(1)  Q(2))  (P(2)  Q(1))  (P(2)  Q(2))

(1)

x(P(x)  Q(x)) = (P(1)  Q(1))  (P(2)  Q(2)).

(2)

Hai mệnh đề trên rõ ràng là khác nhau, ví dụ nếu lấy P(1) = Q(2) = 1 và P(2) = Q(1) = 0 thì
(1) nhận giá trị 0 còn (2) nhận giá trị 1.
Ví dụ phản chứng trên gợi ý cho ta biểu thức: xP(x)  xQ(x)  x(P(x)  Q(x)) là
đồng nhất đúng. Độc giả tự chứng minh trường hợp này. 
20. Chứng minh rằng xP(x)  xQ(x) và x (P(x)  Q(x)) là không tương đương
Chứng minh:
23


Chương 3. Lôgic và suy luận toán học
Tương tự bài tập trên ta có :
xP(x)  xQ(x) = (P(1)  P(2))  (Q(1)  Q(2)) =
= (P(1)  Q(1))  (P(1)  Q(2))  (P(2)  Q(1))  (P(2)  Q(2))

(1)

x(P(x)  Q(x)) = (P(1)  Q(1))  (P(2)  Q(2)).


d. !x (x = x + 1)

Chứng minh:
a. 0

b. 0

c. 1



d. 0

24. Xác định chân trị của các mệnh đề sau :
a. !x P(x)  x P(x)

b. x P(x)  !x P(x)

c. !x P(x)  x P(x)

Chứng minh:
a. 1

b. 0

c. 1



25. *Biểu diễn lượng từ !x P(x) qua lượng từ phổ dụng (), lượng từ tồn tại () và các phép

độ ngoài trời nhỏ hơn 100 độ. Do đó ô nhiễm là nguy hại.
c. Linđa là vận động viên bơi tuyệt vời. Nếu Linđa là vận động viên bơi tuyệt vời, khi đó
cô ta có thể làm việc như một người cứu đắm ở bể bơi. Do đó Linđa có thể làm việc
như một người cứu đắm ở bể bơi.
d. Steve sẽ làm việc ở một công ty tin học vào mùa hè này. Do dó mùa hè này anh ta sẽ
làm việc ở một công ty tin học hoặc là một kẻ lang thang ngoài bãi biển.
e. Nếu tôi cả đêm làm bài tập này, thì tôi có thể trả lời được tất cả các bài tập. Nếu tôi trả
lời được tất cả các bài tập thì tôi sẽ hiểu được tài liệu này. Do đó nếu tôi cả đêm làm bài
tập này thì tôi sẽ hiểu được tài liệu này.
Chứng minh:
a. Qui tắc rút gọn
b. Qui tắc tam đoạn luận tuyển
c. Qui tắc kết luận
d. Qui tắc cộng
e. Qui tắc tam đoạn luận



28. Xác định xem mỗi suy luận sau là có căn cứ không. Nếu một suy luận là có căn cứ thì nó
dùng quy tắc suy luận nào. Nếu không hãy chỉ ra ngụy biện nào đã được sử dụng.
a. Nếu n là một số thực lớn hơn 1 khi đó n2 > 1. Giả sử n2 > 1. Khi đó n > 1.
b. log23 là vô tỷ nếu nó không là tỷ số của hai số nguyên. Do đó, vì log23 không thể viết
dưới dạng a/b với a và b là hai số nguyên, nên nó là vô tỷ.
c. Nếu n là một số thực và n > 3 khi đó n2 > 9. Giả sử n2  9. Khi đó n  3.
d. Một số nguyên dương hoặc là số chính phương hoặc có một số chẵn các ước nguyên
dương. Giả sử n là một số nguyên dương có một số lẻ các ước nguyên dương. Khi đó n
25