Kỹ thuật lập trình nâng cao - 96 -
PHU LỤC
MỘT SỐ KIẾN THỨC VỀ LOGIC

I. LOGIC TOÁN.

Trong đời sống hàng ngày, người ta cần có những lý luận để từ các điều kiện được
biết hay được giả đònh (các tiền đề - premises) có thể suy ra các kết luận (conclusion)
đúng. Hãy xét 2 lý luận sau :
Lý luận (1) : - Các tiền đề :
+ Nếu hôm nay trời đẹp thì tôi đi chơi.
+ Nếu tôi đi chơi thì hôm nay về trễ .
- Gỉa thiết : Hôm nay trời đẹp .
- kết luận : Hôm nay tôi sẽ về trễ .
Lý luận (2) : - Các tiên đề :
+ Nếu hôm nay rạp hát không đóng cửa thi tôi sẽ xem phim.
+ Nếu tôi xem phim thì tôi sẽ không soạn kòp bài .
- Gỉa thiết : Hôm nay rạp hát không đóng cửa .
- kết luận : Hôm nay tôi sẽ không soạn kòp bài.
Hai lý luận trên là đúng và có cùng dạng lý luận. Chúng đúng vì có dạng lý luận
đúng, bất kể ý nghóa mà chúng đề cập đến.
Còn lý luận sau :
Lý luận (3) : - Các tiền đề :
+ Nếu trời đẹp thì tôi đi chơi.
+ Nếu tôi đi chơi thì tôi sẽ về trễ.
- Giả thiết : Hôm nay tôi về trễ.
- kết luận : Hôm nay trời đẹp .
là lý luận sai và mọi lý luận dạng như vậy đều sai .
Logic toán học quan tâm đến việc phân tích các câu (sentences), các mệnh đề
(propositions) và chứng minh với sự chú ý đến dạng (form) lược bỏ đi sự việc cụ thể.

or hay
not không
==> nếu...thì...
<==> ...nếu và chỉ nếu... Với các ký hiệu này, (4) có thể được viết như sau:
[ ( A ==> B ) and ( B ==> C ) and A ] ====> C
Nếu A thì B và nếu B thì C và A Thì suy ra C
Tức là mệnh đề phức hợp [(A ==> B) and (B ==> C) and A] ==> C .
Nói chung một lý luận sẽ được chuyển thành một mệnh đề phức với dạng :
[ (tiên đề 1) and (tiên đề 2 ) and ... ] ====> kết luận .

3. Ýnghóa của các liên từ Logic. Bảng chân trò.
Các liên từ nối kết các mệnh đề thành phần tạo nên mệnh đề mới, mà tính đúng
sai của nó được xác đònh từ tính đúng sai của các mệnh đề thành phần theo qui luật
được khái quát trong các bảng giá trò đúng sai sau đây :

Trần Hoàng Thọ Khoa Toán - Tin

Kỹ thuật lập trình nâng cao - 98 -

P not P
------------
T F
------------
F T
p q p and q p or q p ==> q p <==> q

F F F F T T

Đặt : A : hôm nay trời đẹp
B : Tôi đi chơi
C : Tôi về trễ
Dạng lý luận (3) là : [(A ==> B) and (B ==> C) and C ] ==> A
là sai vì với A, B False , C true thì mệnh đề :
[(A ==> B) and (B ==> C) and C ] ==> A nhận gía trò False

Trần Hoàng Thọ Khoa Toán - Tin

Kỹ thuật lập trình nâng cao - 99 -

A B C [(A ==> B) and (B ==> C) and C ] ==> A

F F T [ T and T and T ] ==> F 5. Tương đương (Equivalence).
a) Đònh nghóa:
Hai mệnh đề P và Q được gọi là tương đương nhau (ký hiệu P
≡
Q), nếu mệnh đề
P <==> Q luôn nhận giá trò đúng (True) với mọi khả năng đúng sai của các mệnh đề
thành phần .
Ta có thể chứng minh một sự tương đương bằng cách lập bảng chân trò .
Ví dụ: chứng minh : p and q
≡
not( not p or not q ).

Bảng chân trò :
p q p and q not ( not p or not q )

not p
Luật loại trừ trung gian : p or not p
≡
true
Luật về mâu thuẫn : p and not p
≡
false
Luật phủ đònh : not not p
≡
p
Luật Kết hợp : p or (q or r)
≡
(p or q) or r
p and (q and r)
≡
(p and q) and r
p <==> (q <==> r)
≡
(p <==> q) <==> r
Luật giao hoán : p and q
≡
q and p
p or q
≡
q or p

Trần Hoàng Thọ Khoa Toán - Tin

Kỹ thuật lập trình nâng cao - 100 -
p <==> q

≡
( (p ==> q) and (q ==> p) )

p <==> q
≡
((p ==> q) and (not p ==> not q))
p <==> q
≡
((p and q) or (not p and not q))

6. Tính thay thế, tính truyền và tính đối xứng.
Khi 2 mệnh đề P và Q là tương đương thì ta có thể thay thế cái này bởi cái kia
trong một mệnh đề bất kỳ mà không làm sai trò của nó.
Ta có thể chứng minh tính chất của một mệnh đề bằng cách biến đổi nó thành các
mệnh đề tương đương.
Ví dụ: ta chứng minh rằng (p and (p ==> q)) ==> q là một lý luận hợp logic bằng
cách biến đổi tương đương.
(p and (p ==> q)) ==> q
(p and (not p or q)) ==> q (hàm ý)
≡

((p and not p) or (p and q)) ==> q (phân phối)
≡

(false or (p and q)) ==> q (mâu thuẫn)
≡

(p and q) ==> q (hằng)
≡
not (p and q) or q (hàm ý)

Xét bài toán : Trên hòn đảo có hai loại người sinh sống : quân tử và tiểu nhân.

Trần Hoàng Thọ Khoa Toán - Tin