Bài giảng Toán rời rạc & Lý thuyết đồ thị - Chương 1: Cơ sở Logic

bằng 0 (sai) trong 
mọi trường hợp về chân trị của các biến mệnh đề trong biểu thức E. Nói một cách khác, 
E là một hằng sai khi ta có: E0. 
Như vậy, ta có thể kiểm tra xem một biểu thức logic có phải là hằng đúng (hằng sai) hay 
không bằng cách lập bảng chân trị của biểu thức logic đó 
Ví dụ: CMR biểu thức p p là hằng đúng 
p  p p p 
0 1 1 
1 0 1 
Ví dụ: CMR biểu thức p p là hằng sai 
p  p p p 
0 1 0 
1 0 0 
Lưu ý: 
 Giả sử E và F là 2 biểu thức logic. Khi đó, E tương đương logic với F (tức là ta có 
EF) khi và chỉ khi biểu thức logic EF là hằng đúng (tức là EF1). 
 Nếu EF và FG thì EG. 
4.CAC LUẬT LOGIC. 
 Các luật về phép phủ định 
   p p (luật phủ định của phủ định) 
  1  0 
  0  1 
Luật giao hoán 
 p  q  q  p 
 p  q  q  p 
Luật kết hợp 
 p  (q  r)  (p  q)  r 
 p  (q  r)  (p  q)  r 
Luật phân bố 
 p  (q  r)  (p  q)  (p  r) 
 p  (q  r)  (p  q)  (p  r) 
Luật De Morgan 
  (p  q)   p   q 
  (p  q)   p   q 
Luật về phần tử bù 
 p   p  1 
 p   p  0 
Luật kéo theo 
 p  q   p  q 
Luật tương đương 
 p  q  (p  q)  (q  p) 
Các luật đơn giản của phép tuyển 
 p  p  p (tính lũy đẳng của phép tuyển) 
 p  1  1 (luật này còn được gọi là luật thống trị) 
 p  0  p (luật này còn được gọi là luật trung hòa) 
 p  (p  q)  p (luật này còn được gọi là luật hấp thụ) 
Các luật đơn giản của phép hội 
 p  p  p (tính lũy đẳng của phép hội) 
 p  1  p (luật này còn được gọi là luật trung hòa) 
 p  0  0 (luật này còn được gọi là luật thống trị) 
 p  (p  q)  p (luật này còn được gọi là luật hấp thụ) 
Ví dụ 1: Chứng minh rằng (p  q)  ( q   p). 
Ta có 
(p  q) 
  p  q (luật kéo theo) 
 q   p (luật giao hoán) 
 q)   p (luật phủ định) 
  q   p (luật kéo theo) 
Ví dụ 2: Chứng minh rằng biểu thức 
 ((p  q)  p)  q 
là một hằng đúng. 
Ta có 
((p  q)  p)  q 
  ((p  q)  p)  q (luật kéo theo) 
 ( (p  q)   p)  q (luật De Morgan) 
  (p  q)  ( p  q) (luật kết hợp) 
  (p  q)  (p  q) (luật kéo theo) 
 1 (luật về phần tử bù) 
Vậy biểu thức ((p  q)  p)  q là hằng đúng. 
Ví dụ 3: Chứng minh rằng biểu thức 
p  q  p 
là một hằng đúng. 
Ta có 
p  q  p 
  ( p  q)  p (luật kéo theo) 
 ( p   q)  p (luật De Morgan) 
 ( q   p)  p (luật giao hoán) 
  q  ( p  p) (luật kết hợp) 
  q  1 (luật về phần tử bù) 
 1 (luật đơn giản) 
Vậy mệnh đề p  q  p là hằng đúng. 
Ví dụ 4: Chứng minh rằng biểu thức 
p  pq 
là một mệnh đề hằng đúng. 
Ta có 
p  pq 
  p  (p q) (luật kéo theo) 
 ( p  p)  q (luật kết hợp) 
 1  q (luật về phần tử bù) 
 1 (luật đơn giản) 
Vậy mệnh đề p  pq là hằng đúng. 
Luật logic cũng có nhiều áp dụng trong ngôn ngữ hàng ngày. Chẳng hạn xem một số áp 
dụng sau: 
 Áp dụng luật De morgan  (p  q)   p   q Để lấy phủ định của mệnh đề hội. 
Ví dụ: 
a= An học giỏi và Tuấn học giỏi. 
thì 
a= An không học giỏi hay Tuấn không học giỏi. 
 Áp dụng luật De morgan  (p  q)   p   q Để lấy phủ định của mệnh đề tuyển. 
Ví dụ: 
b= An học giỏi hay Tuấn học giỏi. 
thì 
b= An không học giỏi và Tuấn không học giỏi. 
Ta có công thức phủ định mệnh đề điều kiện như sau: 
p  q) 
  p  q) (Luật kéo theo) 
 p  q (Luật De Morgan) 
Như vậy phủ định của câu điều kiện không phải một câu điều kiện, mà là câu hội với giả 
thiết đã xẩy ra và kết luận không xẩy ra 
Ví dụ: 
c= Nếu An chăm học thì An thi đậu. 
thì 
c= An chăm học và An thi không đậu. 
Cũng có thể dùng các từ đồng nghĩa với từ “và” như “mà”, “nhưng”, để câu phủ định 
hay hơn 
c= An chăm học mà An thi không đậu. 
c= An chăm học nhưng An thi không đậu. 
II. LOGIC VỊ TỪ VÀ LƯỢNG TỪ. 
1. VỊ TỪ. 
Ðịnh nghĩa: 
Một vị từ là một phát biểu p(x, y, ) phụ thuộc theo các biến x, y,  lấy giá trị trên các miền 
xác định X, Y,  nào đó. Bản thân vị từ chưa có chân trị đúng hoặc sai. Tuy nhiên khi thay 
thế các biến trong vị từ bởi các giá trị cụ thể, thuộc các miền xác định của nó, thì nó có chân 
trị đúng hoặc sai, tức là nó trở thành một mệnh đề. 
Số biến có trong vị từ gọi là bậc của vị từ. (mệnh đề không chứa biến nên có thể xem là vị từ 
bậc 0) 
Ví dụ: Vị từ bậc 1 
p(n)  "n là một số nguyên tố", với n là biến số tự nhiên. (chưa biết đúng hay sai) 
Nó có thể tạo ra các mệnh đề như: 
 p(1) = "1 là một số nguyên tố" (0). 
 p(2) = "2 là một số nguyên tố" (1). 
 p(12) = "12 là một số nguyên tố" (0). 
 p(17) = "17 là một số nguyên tố" (1). 
Ví dụ: Vị từ bậc 2 
p(m,n)  "m là một ước số của n", với m và n là các biến số tự nhiên. (chưa biết đúng hay 
sai) 
Nó có thể tạo ra các mệnh đề như: 
 p(2,4) = "2 là một ước số của 4" (1) 
 p(3,4) = "3 là một ước số của 4" (0) 
2. CÁC LƯỢNG TỪ VÀ CÁC MỆNH ĐỀ CÓ LƯỢNG TỪ. 
Ngoài việc thay thế giá trị cụ thể cho các biến trong vị từ để được một mệnh đề ta còn có một 
cách quan trọng khác để chuyển từ vị từ sang mệnh đề. Ðó là cách sử dụng các lượng từ "với 
mọi" và "tồn tại" (hay "có ít nhất một"). Lượng từ được sử dụng để nói lên rằng vị từ đúng đối 
với mọi giá trị thuộc miền xác định hay chỉ đúng với một phần các giá trị thuộc miền xác định. 
Giả sử P(x) là một vị từ theo biến x (biến x lấy giá trị thuộc một miền xác định đã biết nào đó 
và miền xác định nầy có thể được hiểu ngầm, không cần ghi rõ ra). Các phát biểu sau đây: 
 x : P(x) (1) 
 x : P(x) (2) 
Có chân trị hoàn toàn xác định. Nói cách khác chúng là những mệnh đề. Chân trị của các mệnh 
đề nầy được xác định một cách tự nhiên theo ngữ nghĩa thông thường của các lượng từ. Mệnh 
đề (1) là đúng khi và chỉ khi ứng với mỗi giá trị tùy ý x thuộc miền xác định ta đều có mệnh đề 
P(x) có chân trị đúng. Mệnh đề (2) là đúng khi và chỉ khi có một giá trị x nào đó thuộc miền 
xác định, ta có P(x) có chân trị đúng. 
Ghi chú: 
Phát biểu " x : P(x)" và phát biểu " x : P(x)" không phải là vị từ theo biến x nữa mà là các 
mệnh đề có chân trị xác định là đúng hoặc sai. Trong các phát biểu trên biến x đã được lượng từ 
hóa và chân trị của phát biểu không phụ thuộc theo biến x nữa. Ta cũng nói rằng biến x bị buộc 
bởi lượng từ. 
Ðối với một vị từ theo nhiều biến thì ta có thể lượng từ hóa một số biến nào đó trong vị từ để 
có một vị từ mới theo các biến còn lại. Chẳng hạn, nếu p(x, y, ) là một vị từ theo các biến x, 
y,  thì ta có biểu thức 
 q(y, )   x : p(x, y, ) 
sẽ là một vị từ theo các biến y,  . 
Nếu tất cả các biến của vị từ đều được lượng từ hóa thì ta sẽ có một mệnh đề.Chẳng hạn, nếu 
p(x, y) làmột vị từ theo 2 biến x, y thì biểu thức 
 x,  y : p(x, y) 
sẽ là một mệnh đề, tức là có chân trị xác định và không phụ thuộc vào các biến x, y nữa. 
Trong nhiều phát biểu người ta cò dùng cụm từ "tồn tại duy nhất", ký hiệu bởi  !, như là một 
sự lượng từ hóa đặc biệt. 
Ví dụ: 
1. Mệnh đề "Với mọi số nguyên n ta có 2n-1 là một số lẻ" có thể được viết dưới dạng ký hiệu 
như sau: 
  n Z : 2n-1 lẻ. Mệnh đề nầy có chân trị là 1 (đúng). 
2. Mệnh đề "Ta có x2 > 0, với mọi số thực x khác 0" có thể được viết là 
 x R -  0 : x2 > 0. Mệnh đề nầy có chân trị là 1 (đúng). 
3.QUI TẮC PHỦ ĐỊNH MỆNH ĐỀ CÓ LƯỢNG TỪ. 
Dựa vào cách xác định chân trị của các mệnh đề có lượng từ theo ngữ nghĩa tự nhiên của các 
phát biểu, ta có các qui tắc phủ định mệnh đề có lượng từ sau đây: 
 ( x : P(x))   x :  P(x) (1) 
 ( x : P(x))   x :  P(x) (2) 
Ví dụ: Tìm phủ định của các mệnh đề sau 
a=Tồn tại một số thực x, thỏa x2 < 0. 
b=Mọi sinh viên đều chăm học. 
c=Có sinh viên chăm học. 
Giải 
a=Với mọi số thực x, thỏa x2  0. 
 b=Có sinh viên không chăm học.
 c=Mọi sinh viên không chăm học. 
Ghi chú: 
Từ các qui tắc trên ta có thể nói chung về qui tắc phủ định mệnh đề có lượng từ như sau: Nếu 
trong một mệnh đề có lượng từ ta thay thế lượng từ  bởi lượng từ  , lượng từ  bởi lượng từ 
 , và biểu thức vị từ được thay thế bởi phủ định của nó thì ta sẽ được mệnh đề phủ định của 
mệnh đề có lượng từ ban đầu. Qui tắc nầy cũng áp dụng được cho các mệnh đề với nhiều lượng 
từ. 
Ví dụ: 
p=  x,  y: x = y 
Thì 
p= x,  y: x # y 
BÀI TẬP 
Bài 1. Chứng minh các biểu thức logic sau đây là hằng đúng, bằng hai cách: bảng chân trị 
và dùng luật. 
 a/ (p  q)  ( p  q)  q 
 b/ (p  q)  (p  q) 
 c/ (p q  r)  ((p q)  (p r)) 
 d/  (p  q)  p   q 
 e/ ((p  q) p)  (p  q) 
Bài 2. Hãy cho biết chân trị của mỗi mệnh đề dưới đây và viết mệnh đề phủ định của 
mệnh đề đó. 
a/  x : x+3 = 5 
b/  x : x+3 = 5 
c/  x,  y : x+y = 3 
d/  x,  y : x+y = 3 
e/  x,  y : x+y = 3 
f/  x,  y : x+y = 3 
Trong các mệnh đề trên các biến x và y là các biến số thực. 
Bài 3. Hãy sử dụng các ký hiệu toán học và logic để viết lại mệnh đề sau đây: 
Với mọi số thực dương x, có một số tự nhiên n sao cho x bằng 2n hoặc x nằm giữa 2n và 
2n+1. 
Viết ra mệnh đề phủ định của nó. 
Bài 4. Trong bài tập nầy ký hiệu n chỉ một biến nguyên. Cho các vị từ : 
P(n)  "0 < n2  4" 
R(n)  "0 < n3  8" 
S(n)  "0 < n  2" 
a/ Ứng với mỗi vị từ trên hãy cho biết tập hợp các giá trị n làm cho vị từ có chân trị đúng. 
b/ Trong các vị từ trên, những vị từ nào tương đương với nhau. 
c/ Mệnh đề " n : R(n)  P(n)" là đúng hay sai? 
Bài 5. Viết mệnh đề phủ định của các mệnh đề sau: 
a/ Nếu mọi sinh viên trong lớp chăm học thì cả lớp thi đậu. 
b/ Kết quả tốt đẹp khi có sư cố gắng. 
c/ Nếu có sinh viên nói chuyện trong lớp thì mọi người khó tập trung. 
d/ Nếu được tăng lương thí An sẽ mua xe và máy tính. 
e/ Mọi người đều mệt mỏi và buồn ngủ. 
f/ Có người vui hay có người buồn. 
Bài 6. Cho vị từ P(x,y) = “x yêu y”, với x,y thuộc tập nhân lọai: NHANLOAI. Hãy dùng 
các lượng từ diễn đạt các câu nói sau: 
a/ Mọi người đều yêu An. 
b/ Mọi người đều yêu một ai đó. 
c/ Có một người mà tất cả mọi người đều yêu. 
d/ Có một người mà An không yêu. 
e/ Có một người mà không ai yêu. 
f/ Mọi người đều yêu chính mình.