Giáo trình Logic Toán

Gv: Trịnh Huy Hoàng Trang 1

MỤC LỤC
BÀI 1: KHÁI QUÁT VỀ LOGÍC 3

1. Giới thiệu: 3

2. Định nghĩa logic học: 3

3. Sự hình thành và phát triển của logic học: 3

4. Ứng dụng của logic học: 4

5. Đôi nét về logic mờ 5

BÀI 2: LOGÍC MỆNH ĐỀ 9

1. Định nghĩa : 10

2. Phân tích : 10

3. Các phép toán logic cơ bản : 11

Bảng chân trị 12

4. Công thức trong đại số logic : 12

4.1/ Công thức : 12


4. Thuật toán biểu diễn một công thức logic dưới dạng hội chun: 30

Bài 4: CÀI T MIN H HA 33

1. Thuật toán tính số logic của một công thức: 33

2. Chương trình minh họa việc kiểm tra 2 công thức tương đương: 39

BÀI 5: SUY DIN LOGIC VÀ VN T 42

1. Giới thiệu: 42

2. Định nghĩa qui tắc suy diễn: 42

3. Kiểm tra một qui tắc suy diễn: 44

4. Các qui tắc suy diễn cơ bản: 45

5. Các ví dụ áp dụng trong suy luận và chứng minh 48

6. Định nghĩa vị từ và ví dụ 50

6.1/ Ðnh nghĩa: 50

6.2/ Các phép toán trên các v t 50 Giáo trình Logic Toán



1. Một số khái niệm 81

1.1/ Tp m (Fuzzy Sets) 81

1.2/ S m (Fuzzy N umbers) 85

1.3/ S logic dng hình khi 86

1.4/ S logic dng tam giác 87

1.5/ S logic dng hình thang 89

2. Áp dụng của logic mờ trong dự đoán 90

2.1/ Giá tr trung bình trong thng kê 90

2.2/ Các phép toán vi s tam giác vá s hình thang 91

2.3/ Trung bình trong logic m 93

2.4/ D oán bng phương pháp Delphi kt hp logic m 95

2.5/ Phương pháp Fuzzy Delphi có trng s: 99

2.6/ ng dng Fuzzy Pert trong vic qun lý các  án 100

 TÀI CN G IM CUI KỲ 110

TÀI LIU THAM KHO 111

 thi c i, logic hc ca Aristote ưc các hc trò ca ông tip tc phát trin sau
khi ông mt nhưng hc ch nêu ra mt s qui tc suy lun vI tin  là phán oán iu kin
và phán oán la chn nghiêm ngt mà thôi. Các nhà trit hc thuc trưng phái Megat và
trưng phái khc k i xa hơn: h nghiên cu các quan h suy din.  nghiên cu vn 
này, h ưa ra quan h
bao hàm (implication) và h cũng ưa ra hình thc u tiên ca nh
lý din dch - nh lý làm cơ s cho các phép chng minh trong các h thng hình thc hóa:
mt suy lun ưc gi là hp logic khi và ch khi công thc biu th nó là mt công thc hng
úng.
Các thành tu quan trng nht  thi La mã c i là: h thng các thut ng logic
ưc s dng n ngày nay: hình vuông logic (sau này ưc Boethius hoàn thin); lý thuyt
v tam on lun phc hp và tam on lun vi tin  là phán oán quan h.
Vào thi phc hưng, logic hc truyn thng b ch trích mnh m. Mt s nhà tư tưng
tin b ca thi kỳ này buc ti logic là ch da cho tư tưng kinh vin. N hà trit hc ngưi

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 4
Anh F. Bacon (1561-1626) cho rng tam on lun ca Aristote hoàn toàn vô ích vì nó không
cho phép tìm ra các thông tin mi t các tin  ã có. Vy nên khoa hc s dng nó không
th phát hin các qui lut mi thông qua vic nghiên cu các s kin thc nghim ã bit.
Ông xây dng nên logic qui np mà v sau ưc mt nhà trit hc và logic hc Anh khác là
S.Mill (1806 – 1873) phát trin.
V phn logic din dch thì mãi n th k XVII mi ưc nhà toán hc và trit hc
ngưi Pháp R.Descates (1596 – 1650) thanh minh và bo v. Ông mun xây dng nó thành
phương pháp nhn thc tng hp. Công lao rt ln trong vic phát trin logic din dch vn
thuc v nhà toán hc và logic hc ngưi c Leibniz (1646 – 1716). Ông ưc coi là ngưi
u tiên t nn tng cho logic kí hiu. Ông ưa ra tư tưng s dng các kí hiu và phương
pháp toán hc vào logic. Ông ch ra rng khi s dng các kí hiu thay cho li nói, không
nhng chúng ta làm cho tư tưng ưc tr nên rõ ràng hơn, chính xác hơn mà còn làm cho tư

s vt, tri t; mi s vt hin tưng u có hai mt âm và dương i lp nhau, cùng tn ti,
mt này thnh thì mt kia suy (phn âm to ra thì phn dương nh i và ngưc li); du trng
trong phn en và du en trong phn trng th hin trong âm có dương, trong dương có âm;
du en trong u to ca phn trng th hin khi dương cc thnh thì chính là lúc trong lòng
nó xut hin âm (và ngưc li).
Sau c Pht 200 năm, nhà bác hc Hy-lp là Aristote phát trin logic nh phân. Trái
ngưc vi trit lý nhà Pht, Aristote cho rng th gii to bi các i nghch, thí d nam-n,
nóng-lnh, khô-ưt. Mi th hoc là A hoc là không-A, không th c hai. Logic nh phân ca
Aristote tr thành nn tng cho khoa hc, nu mt th ưc chng minh v mt logic (nh
phân) thì nó ưc và vn s ưc khoa hc công nhn. Cho ti cui th k 19, khi mt nhà
văn-nhà toán hc ngưi Anh, Russel, phát hin ra mt nghch lý ca logic nh phân . . .
Russel (1872-1970), người khai sinh logic mờ
Bá tưc Bertrand Arthur William Russel sinh ra trong mt gia ình quý tc Anh năm
1872. Ông có mt cuc i dài và y bin ng. Thi tr tui, ông nghiên cu toán hc và
sau ó, cùng vi mt nhà toán hc khác, vit mt cun sách v nhng cơ s ca toán hc.
Trong sách, h dành c mt trang ch  chng minh 1 + 1 = 2. Trong quá trình nghiên cu,
ông ã phát hin ra mt nghch lý mà ngày nay gi là nghch lý tp ca Russell :
Trưc ht chúng ta phân bit hai loi tp: tp cha chính nó và tp không cha chính
nó.

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 6
Xét thí d: mt qu lê thuc tp các qu lê, nhưng tp các qu lê không thuc v tp
các qu lê do bn thân nó không phi là mt qu lê! N ghĩa là tp các qu lê không phi là mt
thành viên ca chính nó.
Bây gi ta xét mt tp khác, tp mi th không phi qu lê, gm sách, chut cng, hay
c tng thng Bush na! Do trong tp này bn tìm thy mi th không phi qu lê, nên bn
cũng có th tìm thy trong ó tp các qu lê và tp mi th không phi qu lê ! N ghĩa là tp
mi th không phi qu lê là thành viên ca chính nó.

nhanh chóng áp dng logic m vào ngành khoa hc ca mình.
N ăm 1987, N ht Bn ã xây dng h thng tàu in ngm u tiên làm vic vi h
thng iu khin hot ng tàu t ng da trên logic m. ây là mt thành công ln và dn
ti s phát trin bùng n ca logic m. Các trưng i hc và các hãng công nghip ua nhau
phát trin nhng ý tưng mi. u tiên là  N ht Bn, do tôn giáo  N ht tha nhn rng mi
th có th cha phn i lp ca chính nó, ch không coi là mt th "kinh khng" như hu ht
nhng nơi khác trên th gii. Và logic m cũng ha hn em li nhiu tin bc cho các hãng
công nghip, tt nhiên là iu này ưc ón chào.
Logic m ưc công b ln u tiên ti M vào năm 1965 do giáo sư Lotfi Zadeh. K
t ó, logic m ã có nhiu phát trin qua các chng ưng sau : phát minh  M, áp dng 
Châu Âu và ưa vào các sn phNm thương mi  N ht.
ng dng u tiên ca logic m vào công nghip ưc thc hin  Châu âu, khong
sau năm 1970. Ti trưng Queen Mary  Luân ôn – Anh, Ebrahim Mamdani dùng logic m
 iu khin mt máy hơi nưc mà trưc ây ông y không th iu khin ưc bng các k
thut c in. Và ti c, Hans Zimmermann dùng logic m cho các h ra quyt nh. Liên
tip sau ó, logic m ưc áp dng vào các lĩnh vc khác như iu khin lò xi măng, …
nhưng vn không ưc chp nhn rng rãi trong công nghip.
K t năm 1980, logic m t ưc nhiu thành công trong các ng dng ra quyt nh
và phân tích d liu  Châu âu. N hiu k thut logic m cao cp ưc nghiên cu và phát
trin trong lĩnh vc này.
Cm hng t nhng ng dng ca Châu Âu, các công ty ca N ht bt u dùng logic
m vào k thut iu khin t năm 1980. N hưng do các phn cng chuNn tính toán theo gii
thut logic m rt kém nên hu ht các ng dng u dùng các phn cng chuyên v logic
m. Mt trong nhng ng dng dùng logic m u tiên ti ây là nhà máy x lý nưc ca Fuji
Electric vào năm 1983, h thng xe in ngm ca Hitachi vào năm 1987.

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 8
N hng thành công u tiên ã to ra nhiu quan tâm  N ht. Có nhiu lý do  gii

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 9
BÀI 2: LOGÍC MỆH ĐỀ

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 .
Gi 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 .
Gi 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 


ây cũng là dng lý lun ca (2) .  Thưng mt phát biu s gm nhiu phát biu nh ni kt vi nhau bng các liên
 t "và" , "hay" , "vì vy " ,"kt qu là"
 Mt mnh  ơn (simple proposition) là mnh  không cha mnh  khác.
N u A thì B (4)
N u B thì C
Có A kt lun ưc : C

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 11
 Mt mnh  phc (compound proposition) là mnh  ưc to thành t hai hay
nhiu mnh  ơn .Vic ni kt này ưc thc hin bi các liên t logic.
Ví dụ : Xét các mnh  sau ây.
p = "15 chia ht cho 3".
q = "2 là mt s nguyên t và là mt s l".
Ta có p là mt mnh  sơ cp. N hưng q là mt mnh  phc hp, vì mnh  q ưc
to thành t hai mnh  "2 là mt s nguyên t" và "2 là mt s l" nh vào liên kt logic
"và".
3. Các phép toán logic cơ bản :
Các phép toán logic ưc nh nghĩa bng bảng chân trị (truth table). Bng chân tr
ch ra rõ ràng chân tr ca mnh  phc hp theo tng trưng hp ca các chân tr ca các
mnh  sơ cp to thành mnh  phc hp. Bng chân tr ca các phép toán logic tt nhiên
là phn ánh ng nghĩa t nhiên ca các t liên kt tương ng. V mt t nhiên ca ngôn ng,
trong nhiu trưng hp cùng mt t nhưng có th có nghĩa khác nhau trong nhng ng cnh
khác nhau. Do ó, bng chân tr không th din t mi nghĩa có th có ca t tương ng vi
ký hiu phép toán. Ðiu ny cho thy rng i s logic là rõ ràng hoàn chnh theo nghĩa là nó


Gv: Trnh Huy Hoàng Trang 12
¬ p∨ q ∧ r là không rõ ràng cn phi dùng các du ngoc  ch rõ nghĩa.
Xét hai mnh  x và y, khi ó ta có:
Bng chân tr ca các phép toán mnh 

Mnh  p Ph nh p Mnh  p Phép tuyn Phép hi Kéo theo Tương ương
x
¬x
y
x ∨ y x ∧ y x → y x ↔ y
1 0 1 1 1 1 1
1 0 0 1 0 0 0
0 1 1 1 0 1 0
0 1 0 0 0 1 1

N goài ra ta còn có thêm mt phép toán logic khác là “phép tuyn chn” ng vi 2
mnh  sơ cp p và q khác vi phép tuyn ã cho  trên ưc vit là p + q, hay p ⊕ q hay có
th biu din như sau:
Bng chân tr
x y x v y
1
1
0
0
1
0
1
0
0

 Lut kt hp  Lut phân b

 Lut De Morgan

 Lut v phn t bù

 Lut kéo theo
 Lut tương ương

 Các lut ơn gin ca phép tuyn ¬

¬
p
⇔
p (lut ph nh ca ph nh)
¬ 1 ⇔ 0 ¬
0
⇔
1

p

∧
r)
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)

¬
(p
∧
q)
⇔

¬
p
∨

¬
q
¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q
p
∨

¬
p
⇔
1
p ∧ ¬ p ⇔ 0
p
→
q
⇔



Mt s lut trong các lut trình bày  trên có th ưc suy ra t các lut khác. Các công
thc tương ương logic khác:

4.3/ Các qui tắc thay thế:
Dưi ây là các qui tc  cho ta có th suy ra nhng biu thc logic mi hay tìm ra
các biu thc logic tương ương vi mt biu thc logic cho trưc.
Qui tắc 1:
x
⊕
y = (
¬
x
∧
y)
∨
( x
∧¬
y)
x ⊕ y = y ⊕ x
(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
x( y ⊕ z) = xy ⊕ xz
¬
x ⊕ 1 = x

Ví dụ :

Cho biu thc logic E = q ∨¬ p. Thay th q trong biu thc E bi biu thc ¬ ¬ q
(tương ương vi q) ta ưc mt biu thc mi E' = ¬ ¬ q ∨¬ p. Theo qui tc thay th 1 ta
có:
q ∨ ¬ p ⇔ ¬ ¬ q ∨ ¬ p
Qui tắc 2:

Gi s biu thc logic E là mt hng úng. N u ta thay th mt bin mnh  p bi
mt biu thc logic tuỳ ý thì ta s ưc mt biu thc logic mi E' cũng là mt hng úng.
Ví dụ : Ta có biu thc E(p,q) = (p → q)
⇔
( ¬ p ∨ q) là mt hng úng. Thay th bin q
trong biu thc E bi biu thc q ∧ r ta ưc biu thc logic mi:
E'(p,q,r) = (p → (q ∧ r))
⇔
( ¬ p ∨ (q ∧ r))
Theo qui tc thay th 2 ta có biu thc E'(p,q,r) cũng là mt hng úng.
Ví dụ áp dụng:
 Ví dụ 1: Chng minh rng
(p → q) ⇔ (¬ q → ¬ p).
Chng minh :

(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 sau là mt hng úng.

((p → q) ∧ p) → q

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ù)

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 17
⇔ 1 (lut ơn gin)
Vy mnh  p → p ∨ q là hng úng.
hận xét: Các ví d trên cho ta thy mt quan h khác gia các mnh  phc hp hay các
mnh  : quan h "suy ra". Khi mnh  p → q là hng úng, ta nói rng p suy ra q (v mt
logic). Chúng ta s dùng ký hiu ⇒  ch quan h "suy ra". Quan h suy ra ny có tính truyn
(hay bc cu), nhưng không có tính cht i xng.
5. Hệ quả logic và tương đương logic:
N u công thc x → y =1 thì mnh  y ưc gi là h qu logic ca x.
N u x là h qu logic ca y và y và h qu logic ca x thì x và y là tương ương logic.
Ví d: N u
1
( ) ( )
F x y y z
= → ∧ →1
( )
G x z
= →2

= ∨ ∧
thì
*
1 2 3
( )
F x x x
= ∧ ∨

7. Tính đầy đủ của một hệ các phép toán
Mt h thng
∑
bao gm các phép toán logic ưc gi là mt h y  nu mi công
thc logic u có th biu din ch gm các bin mnh  vi ch các phép toán logic trong
h.
Các h sau là th hin tính y  ca các phép toán:

0
{ , , }
= ∧ ∨ ¬
∑
,
1
{ , }
= ∧ ¬
∑
,
2
{ , }
= ∨ ¬
∑

x y z
x y z
xyz
x y
z
y
x
xyz x y z
+
F xyz x y z x y z
= + +
F
F = xyzt ’+ x’zt’ + x’yz’t + xz’ Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 19
x
y
z
t
⊕


z‘
t‘
F
xy’z’ yz’t’
⊕
xt y’z
⊕

BÀI TẬP
1.

Cho bit nhng khng nh nào dưi ây là mnh :
a.

2 là mt s nguyên dương.
b.

2k – 1 là mt chn.
c.

Tri lnh quá!

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 21
d.

N u bit trưc là khó khăn sao anh còn c gng?
2.


b.

2
2 1 0 1
x x x
− + ≤ → =

c.

2
2 1 0 0
x x x
− + ≤ ↔ =

d.

2
4 3 0 2
x x x
− + ≤ → =

4.

Lp bng chân tr và ch ra các mnh  luôn úng:
a.

( )
m n p
→ →


m n n p n
→ ∧ ∧ ∨

c.

( ) ( )
m n p m n p
∧ ∨ ∧ ∨ ∨

d.

[[( ) ] [( ) ]]
m n p m p p n
∧ ∧ ∨ ∧ ∧ ∨

6.

Hãy
F
, F
*
,
F*
,
( , , , )
F*
m n p q
ca các công thc sau:
a.



= ∨ ∧ ∨ ∨
( ( ))
G n m m n p

b.

= ⊕ ∨
( )
F n m p

c.

= ↔ ⊕
( )
G m n p

d.

= ⊕ ↔ ∨
( ) ( )
G n m m p

8.

Mt x th bn cung vào mt mc tiêu, kt qu ưc th hin theo các mnh 
sau: P
k
= { Phát th k trúng ích} k = 1, 2, 3
Hãy gii thích các mnh  phc hp sau:

nào nu:
-

N gưi th 1 d oán: B hng nhì, C hng ba.
-

N gưi th 2 d oán: A hng nhì, C hng tư.
-

N gưi th 3 d oán: B hng nht, D hng nhì.
-

ưc bit là mi ngưi có phn úng phn sai.
10.

Trong mt chatroom, có tng công 5 ngưi An, Bình, Chinh, Dung, Yn ang
tho lun v  tài logic toán vi nhau trên mng.
Bit rng:
-

Hoc An, hoc Bình hoc là c 2 ang tho lun.
-

Hoc Chinh, hoc Dung, nhưng không phi c 2 cùng tho lun.

Giáo trình Logic Toán

Gv: Trnh Huy Hoàng Trang 23
-


úng/sai trên máy tính, anh ta không bit tr li chính xác cho bt kỳ câu hi nào
nhưng bit rng:
-

Câu 1 và câu 5 cùng òi hi tr li trái ngưc nhau.
-

Câu 2 và câu 4 cn tr li như nhau.
-

Ít nht 1 trong 2 câu hi u cn tr li là khng nh.
-

N u câu 4 tr li là “úng” thì câu 5 phi tr li là “sai”.
-

Kinh nghim cho sinh viên này thy rng máy t câu hi cn tr li “úng”
nhiu hơn “sai”.
Hãy xác nh các áp án cn chn la.
13.

Sau khi thu gn, hãy tìm các b nghim (x, y, z, t )  các công thc hàm sau t
giá là 0:
a.

[( ) ( )] [ ( )]
F yt xz xt y z x yt y z xt
= ∨ → → → → ∨

b.

p
1
, p
2
, … , p
n
ưc gi là mt biu thc hi cơ bn nu nó có dng sau: 
Ví dụ:
Biu thc x
∧

¬
y
∧
z là mt biu thc hi cơ bn theo 3 bin mnh  x, y, z.
Biu thc logic E(p
1
, p
2
, … , p
n
) theo các bin mnh  p
1
, p
2
, … , p
n

(x
∧
y
∧
z)
F(p
1
,p
2
,p
3
,p
4
) = (p
1

∧
p
2

∧
p
3

∧
p
4
)
∨
(p

1
, E
2
, … , E
m}
sao cho
biu thc E(p
1
, p
2
, … , p
n
) tương ương logic vi biu thc ( E
1

∨
E
2

∨
…
∨
E
m
.)
1.2/ Dạng hội chuẩn:
Gi s p
1
, p
2

vi q
j
= p
j
hoc q
j
=
¬
p
j
(j = 1, … , n).
E = E
1

∨
E
2

∨
…
∨
E
m

F = q
1

∨
q
2

Biu thc logic E(p
1
, p
2
, … , p
n
) theo các bin mnh  p
1
, p
2
, … , p
n
ưc nói là có
dng hi chuNn khi E có dng: Trong ó mi biu thc con E
i
u có dng tuyn chuNn theo các bin p
1
, p
2
, … , p
n
.

Ví dụ: Các biu thc sau ây có dng hi chuNn:
E(x,y,z) = (x
∨ ¬
y


∨
p
3

∨
p
4
)
∧
(p
1

∨ ¬
p
2

∨
p
3

∨ ¬
p
4
)
Ðịnh lý :
Mi biu thc logic E(p
1
, p
2


E
m
.)
2. Số logic :
2.1/ Định nghĩa :
♦
S logic ca mt bin nguyên thy A , kí hiu #A là chân tr ca bin ó xét trong
không gian logic N chiu mà A tham gia biu din.
♦
Ví d:
Xét trong không gian mt bin thì #A =(1,0)
Trong không gian 2 bin: AB.
1 1
1 0
0 1
0 0
A B
 
 
 
 
 
 
 
 

Xét trong không gian 3 chiu: ABC
E = E
1