Chương 3. Hệ toán tân từ


Trần Thọ Châu
Logic Toán. NXB Đại học quốc gia Hà Nội 2007.
Tr 70-125.


Từ khoá: Logic toán, Đại số mệnh đề, Lượng từ, Đồng nhất đúng, Định lý suy
diễn, Tính phi mâu thuẫn, Tính đầy đủ.


Tài liệu trong Thư viện điện tử ĐH Khoa học Tự nhiên có thể sử dụng cho mục
đích học tập và nghiên cứu cá nhân. Nghiêm cấm mọi hình thức sao chép, in ấn
phục vụ các mục đích khác nếu không được sự chấp thuận của nhà xuất bản và
tác giả.



Chu
.
o
.
ng 3
Hˆe
.
to´an tˆan t`u
.

3.1 C´ac lu
.
o
.
.
ng t`u
.
71
3.2 C´ac kh´ai niˆe
.
mv`adi
.
nhngh˜ıa 77
3.3 Minh hoa
.
,su
.
.
dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh . . . 81
3.3.1 Minh hoa
.
81
3.3.2 T´ınh thu
.
.
chiˆe

.
n du
.
o
.
.
c 83
3.3.3 Su
.
.
dˆo
`
ng nhˆa
´
t d´ung (h˘a
`
ng d´ung) 85
3.3.4 Mˆoh`ınh 85
3.3.5 Mˆo
.
tsˆo
´
hˆe
.
qua
’
86
3.3.6 Mˆo
.
tsˆo

´
di
.
nhngh˜ıakh´ac 89
3.3.7 C´ac cˆong th´u
.
c logic dˆo
`
ng nhˆa
´
t d´ung trong hˆe
.
to´an
tˆan t`u
.
92
3.3.8 Da
.
ng chuˆa
’
nt˘a
´
c trong logic tˆan t`u
.
93
3.4 L´y thuyˆe
´
t tˆan t`u
.
cˆa

´
p1K 100
3.4.1 Di
.
nhngh˜ıa 100
3.4.2 Mˆo
.
t v`ai th´ı du
.
vˆe
`
L´y thuyˆe
´
ttˆant`u
.
cˆa
´
p 1K . . . . 103
3.5 Di
.
nh l´y suy diˆe
˜
n trong logic tˆan t`u
.
104
3.1. C´ac lu
.
o
.
.

ng t`u
.
71
3.6 T´ınh phi mˆau thuˆa
˜
n v`a dˆa
`
y du
’
cu
’
a logic tˆan t`u
.
110
3.6.1 C´ac kh´ai niˆe
.
mv`adi
.
nhngh˜ıa 110
3.6.2 T´ınh phi mˆau thuˆa
˜
ncu
’
a l´y thuyˆe
´
t tˆan t`u
.
cˆa
´
p 1 PP111

3.6.3 Mˆo
.
tsˆo
´
di
.
nh l´y trong l´y thuyˆe
´
t tˆan t`u
.
cˆa
´
p1K . . 112
3.6.4 T´ınh dˆa
`
y du
’
cu
’
a l´y thuyˆe
´
t tˆan t`u
.
cˆa
´
p 1K . . . . . 120
3.7
´
Ap du
.

ng trong ch´u
.
ng minh di
.
nh l´y cu
’
a l´y thuyˆe
´
t
tˆan t`u
.
cˆa
´
p1 121
3.8 B`ai tˆa
.
p chu
.
o
.
ng3 123
Logic tˆan t`u
.
l`a mˆo
.
thˆe
.
thˆo
´
ng logic phˆo

’
biˆe
´
n nhˆa
´
t m`a ngˆon ng˜u
.
cu
’
an´o
gi´up ta h`ınh th`anh c´ac kh´ai niˆe
.
m, c´ac thuˆo
.
c t´ınh, c´ac quan hˆe
.
,v`at`u
.
d´o di
dˆe
´
n ph´an do´an, c˜ung nhu
.
c´ac co
.
chˆe
´
lˆa
.
p luˆa

.
nch˘a
.
t ch˜e, gi´up con ngu
.
`o
.
ihiˆe
’
u
r˜o v`a sˆau s˘a
´
cba
’
nchˆa
´
tcu
’
a c´ac
dˆo
´
itu
.
o
.
.
ng. Do
d´o c´o thˆe
’
n´oi logic tˆan t`u

.
l`a mˆo
.
t cˆong cu
.
nˆe
`
nta
’
ng cho su
.
.
ph´at triˆe
’
ncu
’
a nhiˆe
`
u l´y thuyˆe
´
t khoa ho
.
c,
d˘a
.
cbiˆe
.
t l`a To´an ho
.
c, ch˘a

’
ng ha
.
nnhu
.
b`ai to´an “Tˆo
`
nta
.
i ´ıt nhˆa
´
tmˆo
.
t nghiˆe
.
m
x
1
,x
2
, , x
n
”cu
’
a da th´u
.
c n biˆe
´
n f(x
1

,x
2
, , x
n
) du
.
o
.
.
cbiˆe
’
udiˆe
˜
n nh`o
.
logic
tˆan t`u
.
nhu
.
sau:
∃x
1
∃x
2
∃x
n
(f(x
1
,x

2
, , x
n
)=0).
3.1 C´ac lu
.
o
.
.
ng t`u
.
Logic tˆan t`u
.
l`a su
.
.
ph´at triˆe
’
nmo
.
’
rˆo
.
ng tu
.
.
nhiˆen cu
’
a logic mˆe
.

nh
dˆe
`
nh˘a
`
mthˆe
’
hiˆe
.
nmˆo
.
t c´ach
dˆa
`
y du
’
v`a ch˘a
.
tch˜enh˜u
.
ng kˆe
´
t luˆa
.
t thu
.
.
ctˆe
´
m`a logic mˆe

.
nh
dˆe
`
khˆong thˆe
’
n`ao diˆe
˜
nta
’
du
.
o
.
.
c, ch˘a
’
ng ha
.
n:
(1) Mˆo
˜
imˆo
.
t ngu
.
`o
.
iba
.

ncu
’
a Mai l`a ba
.
ncu
’
aYˆe
´
n. Ph´uc khˆong pha
’
i l`a ba
.
n
cu
’
aYˆe
´
n, nˆen Ph´uc khˆong pha
’
i l`a ba
.
ncu
’
a Mai.
(2) Mo
.
i ngu
.
`o
.

i
dˆe
`
ubˆa
´
ttu
.
’
. Socrates l`a ngu
.
`o
.
i, nˆen Socrates l`a bˆa
´
ttu
.
’
.
Dˆe
’
c´o thˆe
’
mˆo ta
’
b˘a
`
ng To´an ho
.
cnh˜u
.

ng mˆe
.
nh
dˆe
`
trˆen, ta du
.
a ra mˆo
.
tsˆo
´
k´yhiˆe
.
u
d˘a
.
cbiˆe
.
t:
72 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
–Nˆe
´
u P (x) c´o ngh˜ıa l`a “x c´o t´ınh chˆa

´
t P ” th`ı khi d´o ∀xP (x) c´o ngh˜ıa
l`a “Mˆo
˜
imˆo
.
tvˆa
.
t x c´o t´ınh chˆa
´
t P ”, hay n´oi c´ach kh´ac: “Mo
.
i x c´o t´ınh
chˆa
´
t P ”.
–Nˆe
´
utak´yhiˆe
.
u ∃xP (x) c´o ngh˜ıa l`a “Tˆo
`
nta
.
i ´ıt nhˆa
´
tmˆo
.
tvˆa
.

t x c´o t´ınh
chˆa
´
t P ”.
Khi
d´o trong c´ac biˆe
’
uth´u
.
c trˆen:
– ∀xP (x) th`ı phˆa
`
n ∀x
du
.
o
.
.
cgo
.
i l`a phˆa
`
nlu
.
o
.
.
ng t`u
.
, trong d´o k´y hiˆe

.
u ∀ -
du
.
o
.
.
cgo
.
il`alu
.
o
.
.
ng t`u
.
to`an thˆe
’
,v`ax du
.
o
.
.
cgo
.
il`abiˆe
´
nlu
.
o

.
.
ng t`u
.
.
– ∃xP (x) th`ı phˆa
`
n ∃x
du
.
o
.
.
cgo
.
i l`a phˆa
`
nlu
.
o
.
.
ng t`u
.
, trong
d´o k´y hiˆe
.
u ∃
du
.

o
.
.
cgo
.
il`alu
.
o
.
.
ng t`u
.
tˆo
`
nta
.
i, c`on x du
.
o
.
.
cgo
.
il`abiˆe
´
nlu
.
o
.
.

ng t`u
.
.
– Trong ca
’
2biˆe
’
uth´u
.
c th`ı phˆa
`
n P(x) du
.
o
.
.
cgo
.
il`amiˆe
`
n t´ac du
.
ng (scope)
cu
’
alu
.
o
.
.

ng t`u
.
.
Dˆo
´
iv´o
.
i c´ac th´ı du
.
d˜a cho, nˆe
´
utak´yhiˆe
.
u: m, y, p, s, F (x, y),M(x), I(x)
tu
.
o
.
ng ´u
.
ng l`a “Mai”, “Yˆe
´
n”, “Ph´uc”, “Socrates”, “x l`a ba
.
ncu
’
a y”, “x l`a
ngu
.
`o

.
i”, “x l`a bˆa
´
ttu
.
’
” th`ı khi
d´o c´ac kˆe
´
t luˆa
.
nt`u
.
(1) dˆe
´
n (2) du
.
o
.
.
cbiˆe
’
udiˆe
˜
n
nhu
.
sau:
(1


) ∀x( F (x, m) → F (x, y)) (a)
¬F (p, y)(b)
¬F (p, m)
(2

) ∀x(M(x) → I(x)) (c)
M(s)(d)
I(s)
Trong cˆong th ´u
.
c(1

), ta d˜a k´y hiˆe
.
u“F (y,z)” c´o ngh˜ıa l`a “y l`a ba
.
ncu
’
a
z” . Khi d´o dˆo
´
iv´o
.
imˆe
.
nh dˆe
`
(a) ta ´ap du
.
ng lu

.
o
.
.
ng t`u
.
∀x cho tru
.
`o
.
ng ho
.
.
p
riˆeng “x l`a p”, ta nhˆa
.
n du
.
o
.
.
cmˆe
.
nh dˆe
`
sau l`a mˆe
.
nh dˆe
`
d´ung:

F (p, m) → F (p, y) (e)
3.1. C´ac lu
.
o
.
.
ng t`u
.
73
Trong logic mˆe
.
nh dˆe
`
ta c´o cˆong th´u
.
c sau: (A → B) → (¬B →¬A)l`a
cˆong th´u
.
c dˆo
`
ng nhˆa
´
t d´ung. Do d´o ta thay A = F (p, m), v`a B = F (p, y), ta
nhˆa
.
nmˆe
.
nh
dˆe
`

sau dˆay l`a d´ung:
¬F (p, y) →¬F (p, m)(f)
nh`o
.
qui t˘a
´
c Modus Ponens.
´
Ap du
.
ng Modus Ponens mˆo
.
tlˆa
`
nn˜u
.
a
dˆo
´
iv´o
.
i
(b) v`a (f), ta nhˆa
.
n
du
.
o
.
.

ckˆe
´
t qua
’
:
¬F (p, m), ngh˜ıa l`a “Ph´uc khˆong pha
’
i l`a ba
.
ncu
’
a Mai” 
Trong cˆong th´u
.
c(2

) ta ´ap du
.
ng lu
.
o
.
.
ng t`u
.
to`an thˆe
’
∀x dˆo
´
iv´o

.
imˆe
.
nh dˆe
`
(c) b˘a
`
ng c´ach thay “x l`a s”, ta nhˆa
.
n
du
.
o
.
.
cmˆe
.
nh
dˆe
`
sau dˆay l`a d´ung:
M(s) → I(s)(g)
´
Ap du
.
ng qui t˘a
´
c Modus Ponens cho (d) v`a (g), ta nhˆa
.
n

du
.
o
.
.
ckˆe
´
t qua
’
l`a:
I(s), ngh˜ıa l`a “Socrates l`a bˆa
´
ttu
.
’
”. 
Mˆo
.
t
diˆe
`
uth´uvi
.
l`a ta c´o thˆe
’
kiˆe
’
m tra b˘a
`
ng chu

.
o
.
ng tr`ınh th´ı du
.
th ´u
.
2
v´o
.
ikˆe
´
t qua
’
“Socrates l`a bˆa
´
ttu
.
’
”b˘a
`
ng ngˆon ng˜u
.
lˆa
.
p tr`ınh PROLOG version
2.0 ([6]) d`ung trong Tr´ı tuˆe
.
nhˆan ta
.

o.
Khi ta v`ao mˆoi tru
.
`o
.
ng l`am viˆe
.
ccu
’
a TURBO PROLOG m`an h`ınh bao
gˆo
`
m4cu
.
’
asˆo
’
sau
dˆay:
H˜ay v`ao mu
.
c File/Load, cho
.
n tˆen chu
.
o
.
ng tr`ınh AI1.PRO v`a thˆem chı
’
thi

.
trace (vˆe
´
t) lˆen
dˆa
`
u chu
.
o
.
ng tr`ınh:
74 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
/*AI1.PRO*/
trace
domains
human, immortal=symb ol
predicates
is(symbol, symbol)
clauses
is(X, immortal): - is(X, human).
is(“So crates”, human).
goal
is(X, Y ),

write(X, “is”, Y ).
Ta cha
.
y chu
.
o
.
ng tr`ınh t`u
.
ng bu
.
´o
.
c (theo vˆe
´
t):
*Bˆa
´
m Alt-R
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chı

’
t`u
.
goal
–O
.
’
cu
.
’
asˆo
’
Trace ta thˆa
´
y
CALL: goal ()
* H˜ay bˆa
´
m F10 (lˆa
`
nth´u
.
nhˆa
´
t)
–O
.
’
cu
.

’
asˆo
’
Edit con tro
’
chı
’
tˆan t`u
.
is(X, Y )
–O
.
’
cu
.
’
asˆo
’
Trace ta thˆa
´
y
CALL: is(
, )
3.1. C´ac lu
.
o
.
.
ng t`u
.

75
*Bˆa
´
m F10 (lˆa
`
nth´u
.
2)
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chı
’
qui t˘a
´
c
is(X, immortal): - is(X, “human” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.

3)
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chı
’
is (X, human)
–O
.
’
cu
.
’
asˆo
’
Trace ta thˆa
´
y
CALL: is (
, “human” )
*Bˆa
´
m F10 (lˆa

`
nth´u
.
4)
O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chı
’
vi
.
tr´ı t`u
.
is (X, immortal)
*Bˆa
´
m F10 (lˆa
`
nth´u
.
5)
–O
.

’
cu
.
’
asˆo
’
Edit con tro
’
chı
’
su
.
.
kiˆe
.
n
is (“Socrates”, human)
–O
.
’
cu
.
’
asˆo
’
Trace ta thˆa
´
y
REDO: is(
, “human” )

*Bˆa
´
m F10 (lˆa
`
nth´u
.
6)
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
vˆa
˜
nchı
’
is (“Socrates”, human)
–O
.
’
cu
.
’
asˆo
’

Trace ta
du
.
o
.
.
c
RETURN: is (“Socrates”, “human” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.
7)
76 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
–O
.
’
cu
.
’
asˆo

’
Edit con tro
’
la
.
ichı
’
is (X, immortal)
–O
.
’
cu
.
’
asˆo
’
Trace ta c´o
RETURN: *is (“Socrates”, “immortal” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.
8)
–O
.
’
cu
.

’
asˆo
’
Edit con tro
’
chı
’
ch˜u
.
X trong
write (X, “is”, Y )
–O
.
’
cu
.
’
asˆo
’
Trace ta c´o
write(“Socrates” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.
9)
–O
.

’
cu
.
’
asˆo
’
Dialog xuˆa
´
thiˆe
.
nt`u
.
Socrates
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chuyˆe
’
nt`u
.
X sang chı
’
“is” trong

write(X, “is”, Y )
–O
.
’
cu
.
’
asˆo
’
Trace ta c´o
write(“is” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.
10)
–O
.
’
cu
.
’
asˆo
’
Dialog ta
du
.
o

.
.
cthˆemt`u
.
is, t´u
.
cl`aSocrates is
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chuyˆe
’
nt`u
.
“is” sang chı
’
sˆo
´
Y trong
write(X, “is”, Y )
–O
.
’

cu
.
’
asˆo
’
Trace ta c´o
write(“immortal” )
*Bˆa
´
m F10 (lˆa
`
nth´u
.
11)
–O
.
’
cu
.
’
asˆo
’
Dialog ta c´o thˆem t`u
.
immortal, t´u
.
c l`a Socrates is im-
mortal
3.2. C´ac kh´ai niˆe
.

mv`adi
.
nh ngh˜ıa 77
–O
.
’
cu
.
’
asˆo
’
Edit con tro
’
chı
’
t`u
.
goal
–O
.
’
cu
.
’
asˆo
’
Trace ta c´o
RETURN: goal()
*Bˆa
´

m F10 (lˆa
`
nth´u
.
12)
–O
.
’
cu
.
’
asˆo
’
Dialog thˆem cˆau nh˘a
´
c nho
.
’
Press the SPACE bar t´u
.
cl`a
bˆa
´
m thanh ngang
dˆe
’
tro
.
’
vˆe

`
mˆoi tru
.
`o
.
ng l`am viˆe
.
cc˜u.
Nhu
.
vˆa
.
y sau 12 bu
.
´o
.
c thu
.
.
chiˆe
.
nbˆa
´
m F10 ta d˜a thu du
.
o
.
.
cl`o
.

i gia
’
i d´ap:
Socrates is immortal hay l`a Socrates l`a bˆa
´
ttu
.
’
. 
Thu
.
.
cchˆa
´
ttad˜a su
.
’
du
.
ng c´ac da
.
ng cˆau lˆe
.
nh
dˆe
’
chı
’
cˆa
´

utr´uc logic cu
’
avˆa
´
n
dˆe
`
.Cˆa
´
utr´uc n`ay phu
.
thuˆo
.
c v`ao c´ac liˆen kˆe
´
tmˆe
.
nh dˆe
`
c˜ung nhu
.
da
.
ng suy
diˆe
˜
n c´o su
.
’
du

.
ng c´ac lu
.
o
.
.
ng t`u
.
,ch˘a
’
ng ha
.
nnhu
.
c´ac th´ı du
.
(1) v`a (2), ta d˜a c´o
thˆe
’
biˆe
’
udiˆe
˜
nch´ung mˆo
.
t c´ach tr`u
.
utu
.
o

.
.
ng qua (1

) v`a (2

).
Dˆe
’
da
.
t du
.
o
.
.
cmu
.
c d´ıch n`ay, ta cˆa
`
n pha
’
isu
.
’
du
.
ng c´ac k´yhiˆe
.
unhu

.
dˆa
´
u
phˆa
’
y, c´ac c˘a
.
pdˆa
´
u ngo˘a
.
c, dˆa
´
uphu
’
di
.
nh ¬,dˆa
´
uk´eo theo → cu
’
ahˆe
.
to´an
mˆe
.
nh dˆe
`
, c´ac biˆe

´
n c´a thˆe
’
x
1
,x
2
, , x
n
, ,; c´ac h˘a
`
ng c´a thˆe
’
a
1
,a
2
, , a
n
, ;
c´ac k´y hiˆe
.
u tˆan t`u
.
A
1
1
,A
2
1

, , A
j
k
, ,; v`a c´ac biˆe
´
n h`am f
1
1
,f
2
1
, , f
j
k
, , trong
d´o chı
’
sˆo
´
trˆen j l`a chı
’
sˆo
´
ngˆoi, chı
’
sˆo
´
du
.
´o

.
i k l`a chı
’
sˆo
´
th ´u
.
tu
.
.
.
Trong c´ac th´ı du
.
(1) v`a (2) ta su
.
’
du
.
ng c´ac k´y hiˆe
.
u m, y, p, s l`a c´ac h˘a
`
ng
c´a thˆe
’
, F l`a tˆan t`u
.
2 ngˆoi, c`on M v`a I l`a c´ac tˆan t`u
.
mˆo

.
t ngˆoi.
Tˆan t`u
.
n ngˆoi l`a mˆo
.
t h`am n ngˆoi nhˆa
.
n gi´a tri
.
True ho˘a
.
c False dˆo
´
iv´o
.
i
mˆo
.
t danh s´ach c´ac h˘a
`
ng, t´u
.
c l`a ´anh xa
.
cu
’
a D
n
v`ao {T, F }, trong d´o D l`a

miˆe
`
n x´ac di
.
nh cu
’
a tˆan t`u
.
.
Biˆe
´
n h`am n ngˆoi l`a mˆo
.
t to´an tu
.
’
t`u
.
tˆa
.
p D
n
v`ao D, trong d´o D l`a miˆe
`
n
x´ac di
.
nh.
3.2 C´ac kh´ai niˆe
.

mv`a di
.
nh ngh˜ıa
Di
.
nh ngh˜ıa 3.2.1 (term hay ha
.
ng tu
.
’
)
(a) Tˆa
´
tca
’
c´ac biˆe
´
n v`a h˘a
`
ng c´a thˆe
’
dˆe
`
u l`a term.
78 Chu
.
o
.
ng 3. Hˆe
.

to´an tˆan t`u
.
(b) Nˆe
´
u f
n
i
l`a mˆo
.
tbiˆe
´
n h`am v`a t
1
,t
2
, , t
n
l`a c´ac terms, th`ı f
n
i
(t
1
,t
2
, , t
n
)
l`a mˆo
.
t term.

(c) Mˆo
.
tbiˆe
’
uth´u
.
c l`a mˆo
.
t term, nˆe
´
un´odu
.
o
.
.
clˆa
.
pnˆent`u
.
co
.
so
.
’
(a) v`a (b).
Di
.
nh ngh˜ıa 3.2.2 (cˆong th ´u
.
cso

.
cˆa
´
p)
Nˆe
´
u A
n
i
l`a mˆo
.
tk´yhiˆe
.
u tˆan t`u
.
v`a t
1
,t
2
, , t
n
l`a c´ac term th`ı A
n
i
(t
1
,t
2
, , t
n

)
l`a mˆo
.
t cˆong th´u
.
cso
.
cˆa
´
p.
Di
.
nh ngh˜ıa 3.2.3 (cˆong th ´u
.
ctˆant`u
.
)
a) Mˆo
˜
imˆo
.
t cˆong th´u
.
cso
.
cˆa
´
p l`a mˆo
.
t cˆong th´u

.
c
b) Nˆe
´
u A v`a B l`a c´ac cˆong th´u
.
c, v`a y l`a mˆo
.
tbiˆe
´
nth`ı(¬A), (A→B),
(∀yA) l`a cˆong th´u
.
c.
c) Mˆo
.
tbiˆe
’
uth´u
.
c l`a mˆo
.
t cˆong th´u
.
c, nˆe
´
un´odu
.
o
.

.
clˆa
.
pnˆent`u
.
co
.
so
.
’
(a) v`a
(b).
Trong biˆe
’
uth´u
.
c ∀yA th`ı “A” du
.
o
.
.
cgo
.
il`amiˆe
`
n t´ac du
.
ng cu
’
alu

.
o
.
.
ng t`u
.
∀y.
Ch´u ´y 1
(1) A khˆong nhˆa
´
t thiˆe
´
tch´u
.
abiˆe
´
n y. Trong tru
.
`o
.
ng ho
.
.
p n`ay, thˆong thu
.
`o
.
ng
ta hiˆe
’

u ∀yA v`a A l`a nhu
.
nhau.
(2) C´ac cˆong th´u
.
c A∧B, A∨B, A↔Bdu
.
o
.
.
c x´ac di
.
nh tu
.
o
.
ng tu
.
.
nhu
.
trong l´y thuyˆe
´
ttiˆen
dˆe
`
L cu
’
a chu
.

o
.
ng 2 t`u
.
D
1
− D
3
.
(3) K´yhiˆe
.
u ∃ du
.
o
.
.
cbiˆe
’
udiˆe
˜
n qua ∀ nh`o
.
cˆong th´u
.
ctu
.
o
.
ng du
.

o
.
ng sau dˆay:
∃xA≡¬(∀x¬A).
3.2. C´ac kh´ai niˆe
.
mv`adi
.
nh ngh˜ıa 79
(4) R´ut go
.
n c´ach viˆe
´
tdˆa
´
u ngo˘a
.
c trong logic tˆan t`u
.
:
Quy u
.
´o
.
ctu
.
o
.
ng tu
.

.
nhu
.
trong chu
.
o
.
ng 1, nhu
.
ng c`on thˆem 2 lu
.
o
.
.
ng t`u
.
∀ v`a ∃
du
.
o
.
.
cxˆe
´
p ch˘a
.
tch˜egi˜u
.
a hai nh´om ↔, → v`a ∨, ∧, ¬, ngh˜ıa l`a
mˆo

.
tth´u
.
tu
.
.
du
.
o
.
.
cxˆe
´
p nhu
.
sau:
↔, →, ∀, ∃, ∨, ∧, ¬
7654321
Th´ı du
.
3.2.1
(a) ∀x
1
A
1
1
(x
1
) → A
2

1
(x
1
,x
2
) pha
’
iviˆe
´
t ngo˘a
.
cl`a
((∀x
1
A
1
1
(x
1
)) → A
2
1
(x
1
,x
2
)).
(b) ∀x
1
A

1
1
(x
1
) ∨ A
2
1
(x
1
,x
2
) pha
’
iviˆe
´
t ngo˘a
.
cl`a
(∀x
1
(A
1
1
(x
1
)∨A
2
1
(x
1

,x
2
))), nhu
.
ng nˆe
´
u ta ho´an vi
.
hai sˆo
´
ha
.
ng cho nhau:
A
2
1
(x
1
,x
2
) ∨∀x
1
A
1
1
(x
1
)
th`ı ta pha
’

iviˆe
´
t ngo˘a
.
cl`a
(A
2
1
(x
1
,x
2
) ∨ (∀x
1
A
1
1
(x
1
))).
Ngo`ai ra tru
.
`o
.
ng ho
.
.
p cˆong th´u
.
cc´oda

.
ng QA th`ı ta du
.
avˆe
`
da
.
ng Q
1
(Q
2
A),
trong d´o A khˆong ch´u
.
alu
.
o
.
.
ng t`u
.
v`a Q, Q
1
, Q
2
l`a c´ac lu
.
o
.
.

ng tu
.
’
n`ao
d´o.
Th´ı du
.
3.2.2 ∀x
1
∃x
2
∀x
4
A
3
1
(x
1
,x
2
,x
4
) th`ı ta pha
’
iviˆe
´
t ngo˘a
.
cl`a
(∀x

1
(∃x
2
(∀x
4
A
3
1
(x
1
,x
2
,x
4
))))
Di
.
nh ngh˜ıa 3.2.4 (vi
.
tr´ıtu
.
.
do v`a r`ang buˆo
.
c)
Vi
.
tr´ı cu
’
abiˆe

´
n x trong mˆo
.
t cˆong th´u
.
c d˜a cho du
.
o
.
.
cgo
.
il`ar`ang buˆo
.
c,nˆe
´
u
x n˘a
`
m trong miˆe
`
n t´ac du
.
ng cu
’
alu
.
o
.
.

ng t`u
.
∀x c´o m˘a
.
t trong cˆong th´u
.
c d´o;
Tr´ai la
.
i, n´o du
.
o
.
.
cgo
.
il`atu
.
.
do.
Th´ı du
.
3.2.3
80 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u

.
(1) A
2
1
(x
1
,x
2
)
(2) A
2
1
(x
1
,x
2
) →∀x
1
A
1
1
(x
1
)
(3) ∀x
1
(A
2
1
(x

1
,x
2
) →∀x
1
A
1
1
(x
1
)).
– Trong cˆong th´u
.
c (1), vi
.
tr´ı th´u
.
nhˆa
´
tcu
’
abiˆe
´
n x
1
l`a tu
.
.
do.
– Trong cˆong th´u

.
c (2), vi
.
tr´ı th´u
.
nhˆa
´
tcu
’
abiˆe
´
n x
1
l`a tu
.
.
do, c`on c´ac vi
.
tr´ı
th ´u
.
2, th´u
.
3cu
’
abiˆe
´
n x
1
l`a r`ang buˆo

.
c.
–Tˆa
´
tca
’
c´ac vi
.
tr´ı cu
’
abiˆe
´
n x
1
trong cˆong th´u
.
c (3) dˆe
`
u l`a r`ang buˆo
.
c.
–Mˆo
˜
imˆo
.
tvi
.
tr´ı cu
’
abiˆe

´
n x
2
trong ca
’
3 cˆong th´u
.
c dˆe
`
ul`atu
.
.
do.
Ch´u ´y 2 C`ung mˆo
.
tbiˆe
´
nvi
.
tr´ıcu
’
an´oc´othˆe
’
v`u
.
a l`a tu
.
.
do, v`u
.

a l`a r`ang buˆo
.
c
trong c `ung mˆo
.
t cˆong th´u
.
c, ch˘a
’
ng ha
.
n nhu
.
(2).
Di
.
nh ngh˜ıa 3.2.5 (biˆe
´
ntu
.
.
do v`a biˆe
´
n r`ang buˆo
.
c)
Mˆo
.
tbiˆe
´

n du
.
o
.
.
cgo
.
il`abiˆe
´
ntu
.
.
do (biˆe
´
n r`ang buˆo
.
c) trong mˆo
.
t cˆong th´u
.
c,
nˆe
´
utˆo
`
nta
.
i c´ac vi
.
tr´ı tu

.
.
do (r`ang buˆo
.
c)cu
’
a n´o trong cˆong th´u
.
c d´o.
Ch´u ´y 3 Mˆo
.
tbiˆe
´
n c´o thˆe
’
v`u
.
al`abiˆe
´
ntu
.
.
do, v`u
.
abiˆe
´
n r`ang buˆo
.
c trong c`ung
mˆo

.
t cˆong th´u
.
c, ch˘a
’
ng ha
.
n nhu
.
(2).
Di
.
nh ngh˜ıa 3.2.6 (term tu
.
.
do dˆo
´
iv´o
.
imˆo
.
tbiˆe
´
n)
Mˆo
.
t term t du
.
o
.

.
cgo
.
il`atu
.
.
do dˆo
´
iv´o
.
ibiˆe
´
n x
i
trong cˆong th´u
.
c A,nˆe
´
u
khˆong c´o mˆo
.
tvi
.
tr´ı tu
.
.
do n`ao cu
’
a x
i

n˘a
`
m trong miˆe
`
n t´ac du
.
ng cu
’
alu
.
o
.
.
ng
t`u
.
∀x
j
, trong d´o x
j
l`a biˆe
´
nc´om˘a
.
t trong term t.
3.3. Minh hoa
.
,su
.
.

dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 81
Th´ı du
.
3.2.4
(1) Term t = x
j
l`a tu
.
.
do dˆo
´
iv´o
.
ibiˆe
´
n x
i
trong cˆong th´u
.
c A = A
1
1
(x
i
), nhu
.

ng
khˆong tu
.
.
do dˆo
´
iv´o
.
ibiˆe
´
n x
i
trong cˆong th´u
.
c:
B = ∀x
j
A
2
1
(x
i
,x
j
).
(2) Term t = f
2
1
(x
1

,x
3
) l`a tu
.
.
do dˆo
´
iv´o
.
ibiˆe
´
n x
1
trong cˆong th´u
.
c A =
∀x
2
A
2
1
(x
1
,x
2
) → A
1
1
(x
1

), nhu
.
ng khˆong tu
.
.
do dˆo
´
iv´o
.
ibiˆe
´
n x
1
trong
cˆong th´u
.
c
B = ∃x
3
A
2
1
(x
1
,x
3
) → A
1
1
(x

1
).
Di
.
nh ngh˜ıa 3.2.7 (cˆong th´u
.
c d´ong)
Mˆo
.
t cˆong th´u
.
c A du
.
o
.
.
cgo
.
il`acˆong th´u
.
c d´ong,nˆe
´
u A khˆong ch´u
.
a c´ac biˆe
´
n
tu
.
.

do.
3.3 Minh hoa
.
,su
.
.
dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh
Mˆo
.
t cˆong th´u
.
cchı
’
c´o ngh˜ıa khi mˆo
.
t minh hoa
.
du
.
o
.
.
cchı
’
ra cho c´ac k´yhiˆe
.

u
cu
’
a n´o.
3.3.1 Minh hoa
.
Di
.
nh ngh˜ıa 3.3.1
Mˆo
.
t minh ho
.
a (Interpretation) bao gˆo
`
mmˆo
.
ttˆa
.
pho
.
.
p D kh´ac rˆo
˜
ng du
.
o
.
.
c

go
.
il`atru
.
`o
.
ng minh hoa
.
(hay miˆe
`
n x´ac di
.
nh) v`a mˆo
.
tsˆo
´
tu
.
o
.
ng quan n`ao d´o
sao cho:
-Mˆo
˜
imˆo
.
t tˆan t`u
.
A
n

j
l`a mˆo
.
t quan hˆe
.
n ngˆoi trong D,t´u
.
c l`a ´anh xa
.
t`u
.
tˆa
.
p D
n
v`ao {T, F }.
-Mˆo
˜
imˆo
.
tbiˆe
´
n h`am f
n
j
l`a mˆo
.
t to´an tu
.
’

n ngˆoi trong D,t´u
.
c l`a ´anh xa
.
t`u
.
D
n
v`ao D.
-Mˆo
˜
imˆo
.
th˘a
`
ng tu
.
’
a
i
l`a mˆo
.
t phˆa
`
ntu
.
’
cu
’
a D.

Ch´u ´y 1
82 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
(1) Khi d˜a cho mˆo
.
t minh hoa
.
n`ao d´o th`ı c´ac biˆe
´
n du
.
o
.
.
c x´ac di
.
nh trˆen tru
.
`o
.
ng
minh hoa
.
D, c`on c´ac ph´ep to´an v`a c´ac lu

.
o
.
.
ng t`u
.
vˆa
˜
nhiˆe
’
u theo ngh˜ıa
thˆong thu
.
`o
.
ng, v`a cho ph´ep ta hiˆe
’
umˆo
.
t quan hˆe
.
n ngˆoi trong D l`a mˆo
.
t
tˆa
.
p con cu
’
atˆa
.

p D
n
.
(2)
Dˆo
´
iv´o
.
imˆo
.
t minh hoa
.
d˜a cho th`ı mˆo
.
t cˆong th´u
.
c khˆong ch´u
.
abiˆe
´
ntu
.
.
do (hay l`a cˆong th´u
.
c d´ong) thˆe
’
hiˆe
.
nmˆo

.
tmˆe
.
nh dˆe
`
ho˘a
.
cl`ad´ung, ho˘a
.
c
l`a sai, c`on
dˆo
´
iv´o
.
imˆo
˜
imˆo
.
t cˆong th´u
.
c c´o ch´u
.
abiˆe
´
ntu
.
.
do thˆe
’

hiˆe
.
n
mˆo
.
t quan hˆe
.
n`ao d´o trˆen tru
.
`o
.
ng minh hoa
.
. Quan hˆe
.
n`ay c´o thˆe
’
thu
.
.
c
hiˆe
.
n du
.
o
.
.
c(d´ung) dˆo
´

iv´o
.
imˆo
.
tsˆo
´
gi´a tri
.
n`ao dˆa
´
ycu
’
abiˆe
´
n trong tru
.
`o
.
ng
minh hoa
.
, v`a c˜ung c´o thˆe
’
khˆong thu
.
.
chiˆe
.
n du
.

o
.
.
c (sai) dˆo
´
iv´o
.
imˆo
.
tsˆo
´
gi´a tri
.
kh´ac cu
’
abiˆe
´
n trong tru
.
`o
.
ng minh hoa
.
.
Th´ı du
.
3.3.1 (a) A
2
1
(x

1
,x
2
)
(b) ∀x
2
A
2
1
(x
1
,x
2
)
(c) ∃x
2
∀x
1
A
2
1
(x
2
,x
1
)
Nˆe
´
u ta cho
.

n tru
.
`o
.
ng minh hoa
.
l`a tˆa
.
pho
.
.
p c´ac sˆo
´
nguyˆen du
.
o
.
ng D =
N
+
= {1, 2, 3, , ∞}, v`a tˆan t`u
.
2 ngˆoi:
A
2
1
(y,z)=
def
“y ≤ z”
th`ı khi

d´o:
- Cˆong th´u
.
c (a) thˆe
’
hiˆe
.
n quan hˆe
.
x
1
≤ x
2
l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c dˆo
´
iv´o
.
imo
.
i

c˘a
.
ps˘a
´
pth´u
.
tu
.
.
(a, b) nguyˆen du
.
o
.
ng sao cho a ≤ b.
- Cˆong th´u
.
c (b) thˆe
’
hiˆe
.
n t´ınh chˆa
´
t“Dˆo
´
iv´o
.
imˆo
˜
imˆo
.

tsˆo
´
nguyˆen du
.
o
.
ng
x
2
: x
2
≥ x
1
” l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c dˆo
´
iv´o
.
isˆo
´
1.

- Cˆong th´u
.
c (c) thˆe
’
hiˆe
.
nmˆo
.
tmˆe
.
nh dˆe
`
d´ung: “Tˆo
`
nta
.
imˆo
.
tsˆo
´
nguyˆen
du
.
o
.
ng nho
’
nhˆa
´
t”.

M˘a
.
t kh´ac, nˆe
´
uc˜ung dˆo
´
iv´o
.
i tˆan t`u
.
trˆen v`a tru
.
`o
.
ng minh hoa
.
bˆay gi`o
.
ta cho
.
nl`atˆa
.
pho
.
.
p c´ac sˆo
´
nguyˆen Z = {−∞, , −1, 0, 1, , +∞} th`ı khi d´o
cˆong th´u
.

c (c) nhˆa
.
n gi´a tri
.
sai, v`ır˘a
`
ng
∃x
2
∀x
1
(x
2
≤ x
1
) ≡∀x
2
∃x
1
(x
2
>x
1
) = True
3.3. Minh hoa
.
,su
.
.
dˆo

`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 83
3.3.2 T´ınh thu
.
.
chiˆe
.
n
du
.
o
.
.
c
C´ac kh´ai niˆe
.
mvˆe
`
su
.
.
thu
.
.
chiˆe
.
n du
.

o
.
.
cv`asu
.
.
dˆo
`
ng nhˆa
´
t d´ung theo tru
.
.
c quan
l`a rˆa
´
t r˜o r`ang, nhu
.
ng dˆe
’
hiˆe
’
u sˆau s˘a
´
cho
.
nba
’
nchˆa
´

tcu
’
aviˆe
.
c t´ınh gi´a tri
.
cu
’
a
mˆo
.
t cˆong th´u
.
c logic tˆan t`u
.
, ta cˆa
`
n thu
.
.
chiˆe
.
n n´o mˆo
.
t c´ach ch´ınh x´ac theo
t`u
.
ng bu
.
´o

.
c t´ınh to´an.
Gia
’
su
.
’
cho mˆo
.
t minh hoa
.
n`ao
d´o v`a D l`a tru
.
`o
.
ng minh hoa
.
.

l`a tˆa
.
ptˆa
´
t
ca
’
c´ac d˜ay dˆe
´
m du

.
o
.
.
c trˆen D. Gia
’
su
.
’
s =(b
1
,b
2
, ) ∈

. Khi d´o ta di
.
nh
ngh˜ıa h`am mˆo
.
t ngˆoi s
∗
l`a ´anh xa
.
t`u
.
tˆa
.
pho
.

.
p c´ac terms (ha
.
ng tu
.
’
) v`ao D nhu
.
sau:
(1) Nˆe
´
u term t l`a biˆe
´
n x
i
th`ı s
∗
(t)=b
i
.
(2) Nˆe
´
u term t l`a mˆo
.
th˘a
`
ng c´a thˆe
’
th`ı s
∗

(t)b˘a
`
ng h˘a
`
ng d´o.
(3) Nˆe
´
u f
n
j
l`a biˆe
´
n h`am du
.
o
.
.
c minh hoa
.
bo
.
’
i to´an tu
.
’
g trong D,v`at
1
,t
2
, , t

n
l`a c´ac terms th`ı s
∗
(f
n
j
(t
1
,t
2
, , t
n
)) = g( s
∗
(t
1
), s
∗
(t
2
), , s
∗
(t
n
)).
Nhu
.
vˆa
.
y s

∗
l`a mˆo
.
t h`am x´ac di
.
nh trˆen tˆa
.
pho
.
.
ptˆa
´
tca
’
c´ac terms v`a nhˆa
.
n
gi´a tri
.
trong D nh`o
.
c´o d˜ay s =(b
1
,b
2
, ).
N´oi mˆo
.
t c´ach kh´ac, v´o
.

ibˆa
´
tk`ymˆo
.
t d˜ay s =(b
1
,b
2
, , ) ∈

v`a bˆa
´
tk`y
term t th`ı s
∗
(t) l`a mˆo
.
t phˆa
`
ntu
.
’
cu
’
atˆa
.
p D. Phˆa
`
ntu
.

’
n`ay (s
∗
(t)) nhˆa
.
n du
.
o
.
.
c
b˘a
`
ng c´ach thˆe
´
dˆo
´
iv´o
.
imˆo
˜
i i phˆa
`
ntu
.
’
b
i
v`ao tˆa
´

tca
’
c´ac vi
.
tr´ı cu
’
abiˆe
´
n x
i
trong
term t, v`a sau d´o thu
.
.
chiˆe
.
n to´an tu
.
’
tu
.
o
.
ng ´u
.
ng cu
’
abiˆe
´
n h`am dˆo

´
iv´o
.
i term t.
Th´ı du
.
3.3.2 Cho term t = f
2
1
(x
3
,f
2
2
(x
1
,a
1
)) v`a D = Z, trong d´o f
2
1
v`a f
2
2
tu
.
o
.
ng ´u
.

ng l`a ph´ep nhˆan v`a ph´ep cˆo
.
ng, c`on a
1
=2.
Khi d´o v´o
.
ibˆa
´
tk`y d˜ay s =(b
1
,b
2
, ) ∈

ta c´o:
s
∗
(t)=b
3
∗ (b
1
+2).
Di
.
nh ngh˜ıa 3.3.2 (T´ınh thu
.
.
chiˆe
.

n du
.
o
.
.
c)
(1) Nˆe
´
u A l`a mˆo
.
t cˆong th´u
.
cso
.
cˆa
´
p A
n
j
(t
1
,t
2
, , t
n
)v`aB
n
j
l`a quan hˆe
.

tu
.
o
.
ng
´u
.
ng cu
’
a n´o trong minh hoa
.
th`ı cˆong th´u
.
c A du
.
o
.
.
cgo
.
il`athu
.
.
chiˆe
.
n du
.
o
.
.

c
84 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
trˆen d˜ay s =(b
1
,b
2
, ) ∈

khi v`a chı
’
khi B
n
j
(s
∗
(t
1
),s
∗
(t
2
), , s
∗

(t
n
)),
t´u
.
c l`a bˆo
.
n phˆa
`
ntu
.
’
(s
∗
(t
1
),s
∗
(t
2
), , s
∗
(t
n
)) n˘a
`
m trong quan hˆe
.
B
n

j
.
Th´ı du
.
3.3.3
(a) Cho tru
.
`o
.
ng minh hoa
.
D = R (sˆo
´
thu
.
.
c); tˆan t`u
.
A
2
1
l`a quan hˆe
.
“ ≤ ” v`a biˆe
´
n h`am f
1
1
(x)=e
x

. Khi d´o cˆong th´u
.
cso
.
cˆa
´
p A =
A
2
1
(f
1
1
(x
1
),x
5
) l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s =(b
1
,b

2
, ), khi v`a
chı
’
khi
e
b
1
≤ b
5
.
(b) Cho tru
.
`o
.
ng minh hoa
.
D = Z, tˆan t`u
.
A
4
1
(x, y, u, v) l`a quan hˆe
.
xv =
uy,v`aa
1
= 2. Khi d´o cˆong th´u
.
cso

.
cˆa
´
p A = A
4
1
(x
3
,a
1
,x
1
,x
3
)l`a
thu
.
.
chiˆe
.
n
du
.
o
.
.
c trˆen d˜ay s =(b
1
,b
2

, ), khi v`a chı
’
khi
b
2
3
=2∗ b
1
.
(2) Cˆong th´u
.
c ¬A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s =(b
1
,b
2
, ) ∈

, khi v`a
chı
’

khi A khˆong thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s.
(3) Cˆong th´u
.
c A→Bl`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s =(b
1
,b
2
, ) ∈

, khi v`a

chı
’
khi A khˆong thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s ho˘a
.
c B thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s.
(4) Cˆong th´u
.
c ∀x
i
A l`a thu

.
.
chiˆe
.
n trˆen d˜ay s =(b
1
,b
2
, , b
i
, ) ∈

, khi v`a
chı
’
khi A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen mˆo
˜
i d˜ay bˆa
´
tk`y s


∈

kh´ac s khˆong
qu´a th`anh phˆa
`
nth´u
.
i.
N´oi mˆo
.
t c´ach kh´ac, cˆong th´u
.
c A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s =
(b
1
,b
2
, ) ∈


, khi v`a chı
’
khi ph´ep thˆe
´
dˆo
´
iv´o
.
imˆo
˜
i i,k´yhiˆe
.
u b
i
ta
.
imo
.
i
vi
.
tr´ı tu
.
.
do cu
’
a x
i
trong A th`ı ta du
.

o
.
.
cmˆo
.
tmˆe
.
nh dˆe
`
d´ung trong minh hoa
.
d˜a cho.
3.3. Minh hoa
.
,su
.
.
dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 85
3.3.3 Su
.
.
dˆo
`
ng nhˆa
´
t

d´ung (h˘a
`
ng
d´ung)
Di
.
nh ngh˜ıa 3.3.3 Mˆo
.
t cˆong th´u
.
c A du
.
o
.
.
cgo
.
il`adˆo
`
ng nhˆa
´
t d´ung trong minh
hoa
.
d˜a cho, khi v`a chı
’
khi A l`a thu
.
.
chiˆe

.
n du
.
o
.
.
c trˆen mˆo
˜
i d˜ay bˆa
´
tk`y s =
(b
1
,b
2
, ) ∈

.
Di
.
nh ngh˜ıa 3.3.4 Mˆo
.
t cˆong th´u
.
c A du
.
o
.
.
cgo

.
il`adˆo
`
ng nhˆa
´
t sai trong minh
hoa
.
d˜a cho, khi v`a chı
’
khi A khˆong thu
.
.
chiˆe
.
n du
.
o
.
.
c dˆo
´
iv´o
.
ibˆa
´
t k`y d˜ay
s =(b
1
,b

2
, ) ∈

.
Th´ı du
.
3.3.4 X´et mˆo
.
t minh hoa
.
bao gˆo
`
m:
-Tru
.
`o
.
ng minh hoa
.
D = N
+
= {1, 2, }
-Tˆant`u
.
mˆo
.
t ngˆoi A
1
1
: A

1
1
(x)=
def
“x l`a ch˘a
˜
n”.
Khi d´o cˆong th´u
.
c A = ∀x
1
(A
1
1
(x
1
) → A
1
1
(x
1
)) l`a dˆo
`
ng nhˆa
´
t d´ung.
Thˆa
.
tvˆa
.

y ta h˜ay x´et mˆo
.
t d˜ay s =(b
1
,b
2
, ) ∈

.
• Tru
.
`o
.
ng ho
.
.
p1:
Nˆe
´
u b
1
l`a mˆo
.
tsˆo
´
ch˘a
˜
n th`ı khi
d´o ta c´o
A

1
1
(b
1
) → A
1
1
(b
1
)=True
• Tru
.
`o
.
ng ho
.
.
p2:
Nˆe
´
u b
1
l`a mˆo
.
tsˆo
´
le
’
th`ı A
1

1
(b
1
)=False, do d´o ta c˜ung c´o: A
1
1
(b
1
) →
A
1
1
(b
1
)=True. Kˆe
´
tho
.
.
p hai tru
.
`o
.
ng ho
.
.
p ta thˆa
´
y cˆong th´u
.

c A =
∀x
1
(A
1
1
(x
1
) → A
1
1
(x
1
)) l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s =(b
1
,b
2
, ) ∈

.

V`ı s
du
.
o
.
.
ccho
.
n tu`y ´y, do d´o cˆong th´u
.
c A = ∀x
1
(A
1
1
(x
1
) → A
1
1
(x
1
)) l`a
dˆo
`
ng nhˆa
´
t d´ung trong minh hoa
.
d˜a cho. 

3.3.4 Mˆo h`ınh
Di
.
nh ngh˜ıa 3.3.5 Mˆo
.
t minh hoa
.
du
.
o
.
.
cgo
.
il`amˆo h`ınh (model) dˆo
´
iv´o
.
imˆo
.
t
tˆa
.
pho
.
.
p Γ c´ac cˆong th´u
.
c, nˆe
´

umˆo
˜
imˆo
.
t cˆong th´u
.
ccu
’
aΓl`adˆo
`
ng nhˆa
´
t d´ung
trong minh hoa
.
d˜a cho.
86 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
3.3.5 Mˆo
.
tsˆo
´
hˆe
.

qua
’
1) Cˆong th´u
.
c A l`a
dˆo
`
ng nhˆa
´
t sai trong minh hoa
.
d˜a cho, khi v`a chı
’
khi ¬A
l`a dˆo
`
ng nhˆa
´
t d´ung trong c `ung minh hoa
.
d´o.
2) Khˆong c´o mˆo
.
t cˆong th´u
.
c n`ao v`u
.
a dˆo
`
ng nhˆa

´
t d´ung, v`u
.
a dˆo
`
ng nhˆa
´
t sai
trong c`ung mˆo
.
t minh hoa
.
.
3) Nˆe
´
u A v`a A→Bl`a
dˆo
`
ng nhˆa
´
t d´ung trong minh hoa
.
d˜a cho th`ı B c˜ung
dˆo
`
ng nhˆa
´
t d´ung trong minh hoa
.
d´o.

4) A→Bl`a
dˆo
`
ng nhˆa
´
t sai trong minh hoa
.
d˜a cho, khi v`a chı
’
khi A l`a dˆo
`
ng
nhˆa
´
t d´ung v`a B l`a dˆo
`
ng nhˆa
´
t sai trong c`ung minh hoa
.
.
5) (i) −A∧B l`a thu
.
.
chiˆe
.
n du
.
o
.

.
c trˆen d˜ay s ∈

, khi v`a chı
’
khi A v`a B
c`ung thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s.
- A∨Bl`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s ∈

, khi v`a chı

’
khi A thu
.
.
chiˆe
.
n
du
.
o
.
.
c trˆen s, ho˘a
.
c B thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s.
- A↔Bl`a thu
.
.
chiˆe
.

n du
.
o
.
.
c trˆen d˜ay s ∈

khi v`a chı
’
khi A v`a B ho˘a
.
c
c`ung thu
.
.
chiˆe
.
n trˆen s ho˘a
.
c khˆong c`ung thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen s.

Ch´u ´y 2
O
.
’
dˆay ta su
.
’
du
.
ng c´ac cˆong th´u
.
ctu
.
o
.
ng du
.
o
.
ng sau:
* A∧B tu
.
o
.
ng du
.
o
.
ng v´o
.

i ¬(A→¬B)
* A∨B tu
.
o
.
ng du
.
o
.
ng v´o
.
i (¬A → B)
* A↔Btu
.
o
.
ng du
.
o
.
ng v´o
.
i (A→B) ∧ (B→A)
* ∃x
i
A tu
.
o
.
ng du

.
o
.
ng v´o
.
i ¬( ∀x
i
¬A)
(ii) Cˆong th´u
.
c ∃x
i
A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s ∈

, khi v`a chı
’
khi A
l`a thu
.
.

chiˆe
.
n du
.
o
.
.
c dˆo
´
iv´o
.
i ´ıt nhˆa
´
tmˆo
.
t d˜ay s

∈

kh´ac s khˆong qu´a th`anh
phˆa
`
nth´u
.
i.
3.3. Minh hoa
.
,su
.
.

dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 87
Th´ı du
.
3.3.5 Gia
’
su
.
’
cho mˆo
.
t minh hoa
.
bao gˆo
`
m:
-Tru
.
`o
.
ng minh hoa
.
D = N
+
= {1, 2, 3, }
- Tˆan t`u
.

A
2
1
l`a “=”
-Biˆe
´
n h`am f
2
1
l`a ph´ep nhˆan
-H˘a
`
ng c´a thˆe
’
a
1
=1.
Khi
d´o quan hˆe
.
mˆo
.
t ngˆoi trong D tu
.
o
.
ng ´u
.
ng v´o
.

i cˆong th´u
.
c:
A =¬A
2
1
(x
1
,a
1
) ∧∀x
2
(∃x
3
A
2
1
(x
1
,f
2
1
(x
2
,x
3
))
→ A
2
1

(x
2
,x
1
) ∨ A
2
1
(x
2
,a
1
))
l`a tˆa
.
pho
.
.
p c´ac sˆo
´
nguyˆen tˆo
´
:
M = {b ∈ N
+
|b l`a sˆo
´
nguyˆen tˆo
´
}
Vˆa

.
y cˆong th´u
.
c A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen mˆo
˜
i d˜ay bˆa
´
tk`y
s = {b
1
,b
2
, }∈

, trong d´o b
1
l`a mˆo
.
tsˆo
´

nguyˆen tˆo
´
.
Ta thu
.
’
kiˆe
’
mch´u
.
ng kh˘a
’
ng di
.
nh trˆen:
Gia
’
su
.
’
ta x´et mˆo
.
t d˜ay s = {b
1
,b
2
, }∈

.
• Tru

.
`o
.
ng ho
.
.
p1: b
1
l`a sˆo
´
nguyˆen tˆo
´
,ch˘a
’
ng ha
.
n b
1
= 7. Trong cˆong th´u
.
c
d˜a cho, ta thˆa
´
y x
1
l`a biˆe
´
ntu
.
.

do v`a d´ong vai tr`o l`a sˆo
´
nguyˆen tˆo
´
, c`on
x
2
v`a x
3
dˆe
`
ul`abiˆe
´
n r`ang buˆo
.
c.
Khi d´o
x
1
=7= 1
↑
x
2
.7= 7
↑
x
2
.1
- ¬A
2

1
(x
1
,a
1
) =True
- x
2
=1
x
1
= x
2
.x
3
= True → x
2
=
F
x
1
∨ x
2
=
T
 T 
1} True
88 Chu
.
o

.
ng 3. Hˆe
.
to´an tˆan t`u
.
- x
2
=7:
x
1
= x
2
.x
3
= True → x
2
=
T
x
1
∨ x
2
=
F
 T 
1} True
Vˆa
.
yta
d˜a kiˆe

’
mch´u
.
ng du
.
o
.
.
cr˘a
`
ng v´o
.
i b
1
= 7 l`a mˆo
.
tsˆo
´
nguyˆen tˆo
´
th`ı
cˆong th´u
.
c A l`a thu
.
.
chiˆe
.
n
du

.
o
.
.
c trˆen d˜ay s =(b
1
,b
2
, ).
• Tru
.
`o
.
ng ho
.
.
p2: b
1
khˆong pha
’
i l`a sˆo
´
nguyˆen tˆo
´
,ch˘a
’
ng ha
.
n b
1

= 12.
Khi d´o ta c´o:
x
1
=1
↑
x
2
.12 = 2
↑
x
2
.6= 6
↑
x
2
.2= 3
↑
x
2
.4= 4
↑
x
2
.3= 12
↑
x
2
.1
- ¬A

2
1
(x
1
,a
1
)=True
- x
2
=1
x
1
= x
2
.x
3
= True → x
2
=
F
x
1
∨ x
2
=
T
 T 
1} True
- x
2

=2
x
1
= x
2
.x
3
= True → x
2
=
F
x
1
∨ x
2
=
F
 F 
1} False
- x
2
=6, 3, 4 t´ınh to´an tu
.
o
.
ng tu
.
.
nhu
.

x
2
=2v`akˆe
´
t qua
’
l`a False.
- x
2
=12
x
1
= x
2
.x
3
= True → x
2
=
T
x
1
∨ x
2
=
F
 T 
1} True
Ta
d˜a kiˆe

’
m tra du
.
o
.
.
cr˘a
`
ng nˆe
´
u b
1
= 12 - khˆong pha
’
i l`a mˆo
.
tsˆo
´
nguyˆen
tˆo
´
th`ı kˆe
´
t qua
’
t´ınh to´an l`a
¬A
2
1
(x

1
,a
1
) ∧∀x
2
(∃x
3
A
2
1
(x
1
,f
2
1
(x
2
,x
3
)) → A
2
1
(x
2
,x
1
) ∨ A
2
1
(x

2
,a
1
))
= True ∧ False = False.
Vˆa
.
ych´u
.
ng to
’
r˘a
`
ng cˆong th´u
.
c A l`a khˆong thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen d˜ay s =
(b
1
,b
2

, ) trong d´o b
1
khˆong pha
’
i l`a sˆo
´
nguyˆen tˆo
´
. 
3.3. Minh hoa
.
,su
.
.
dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 89
3.3.6 Mˆo
.
tsˆo
´
di
.
nh ngh˜ıa kh´ac
Di
.
nh ngh˜ıa 3.3.6 Mˆo
.

t cˆong th´u
.
c A
du
.
o
.
.
cgo
.
il`alogic
dˆo
`
ng nhˆa
´
t d´ung trong
hˆe
.
to´an tˆan t`u
.
, khi v`a chı
’
khi A l`a d´ung dˆo
´
iv´o
.
imo
.
i minh hoa
.

bˆa
´
tk`y.
Di
.
nh ngh˜ıa 3.3.7 Mˆo
.
t cˆong th´u
.
c A du
.
o
.
.
cgo
.
il`athu
.
.
chiˆe
.
n du
.
o
.
.
c trong hˆe
.
to´an tˆan t`u
.

, khi v`a chı
’
khi nˆe
´
utˆo
`
nta
.
imˆo
.
t minh hoa
.
,m`adˆo
´
iv´o
.
i minh hoa
.
d´o A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen ´ıt nhˆa
´

tmˆo
.
t d˜ay s ∈

.
Ch´u ´y 3
(1) A l`a logic
dˆo
`
ng nhˆa
´
t d´ung khi v`a chı
’
khi ¬A l`a khˆong thu
.
.
chiˆe
.
n du
.
o
.
.
c,
v`a A l`a thu
.
.
chiˆe
.
n du

.
o
.
.
c, khi v`a chı
’
khi ¬A l`a khˆong logic dˆo
`
ng nhˆa
´
t
d´ung.
(2) Nˆe
´
u A l`a mˆo
.
t cˆong th´u
.
c d´ong th`ı A l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c, khi v`a chı
’

khi
A l`a
d´ung dˆo
´
iv´o
.
imˆo
.
t minh hoa
.
n`ao d´o.
Di
.
nh ngh˜ıa 3.3.8 Mˆo
.
t cˆong th´u
.
c A du
.
o
.
.
cgo
.
il`amˆau thuˆa
˜
n (contradictory)
trong hˆe
.
to´an tˆan t`u

.
, khi v`a chı
’
khi ¬A l`a logic dˆo
`
ng nhˆa
´
t d´ung, hay l`a khi
v`a chı
’
khi A l`a sai dˆo
´
iv´o
.
imo
.
i minh hoa
.
bˆa
´
tk`y.
Di
.
nh ngh˜ıa 3.3.9 Cˆong th´u
.
c A du
.
o
.
.

cgo
.
il`alogic k´eo theo B trong hˆe
.
to´an
tˆan t`u
.
, khi v`a chı
’
khi dˆo
´
iv´o
.
ibˆa
´
tk`y minh hoa
.
, B l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen mˆo
˜
i

d˜ay m`a ta
.
i d´o A thu
.
.
chiˆe
.
n
du
.
o
.
.
c.
Mˆo
.
t c´ach tˆo
’
ng qu´at ho
.
n, B l`a logic k´eo theo t`u
.
tˆa
.
pho
.
.
p Γ c´ac cˆong th´u
.
c,

khi v`a chı
’
khi, dˆo
´
iv´o
.
i minh hoa
.
, B l`a thu
.
.
chiˆe
.
n du
.
o
.
.
c trˆen mˆo
˜
i d˜ay, m`a ta
.
i
d´o mˆo
˜
i cˆong th´u
.
ccu
’
a Γ l`a thu

.
.
chiˆe
.
n du
.
o
.
.
c.
Di
.
nh ngh˜ıa 3.3.10 Hai cˆong th´u
.
c A v`a B du
.
o
.
.
cgo
.
il`alogic tu
.
o
.
ng du
.
o
.
ng

trong hˆe
.
to´an tˆan t`u
.
, khi v`a chı
’
khi A logic k´eo theo B v`a B logic k´eo theo
A.
Hˆe
.
qua
’
3.3.1
90 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
a) A logic k´eo theo B khi v`a chı
’
khi cˆong th´u
.
c (A→B) l`a logic dˆo
`
ng nhˆa
´
t

d´ung.
b) A v`a B l`a logic tu
.
o
.
ng du
.
o
.
ng, khi v`a chı
’
khi cˆong th´u
.
c (A↔B) l`a logic
dˆo
`
ng nhˆa
´
t d´ung.
c) Nˆe
´
u A l`a logic k´eo theo B,v`aA
d´ung trong mˆo
.
t minh hoa
.
d˜a cho th`ı B
c˜ung d´ung trong minh hoa
.
d´o.

d) Nˆe
´
u B l`a logic k´eo theo t`u
.
tˆa
.
pho
.
.
p Γ c´ac cˆong th´u
.
cv`amo
.
i cˆong th´u
.
c
cu
’
a Γ d´ung trong minh hoa
.
d˜a cho th`ı B c˜ung d´ung trong minh hoa
.
.
Di
.
nh ngh˜ıa 3.3.11 Gia
’
su
.
’

S = {A
1
, A
2
,.,A
n
} l`a mˆo
.
ttˆa
.
pho
.
.
p c´ac cˆong
th ´u
.
c tˆan t`u
.
. Khi d´o, S du
.
o
.
.
cgo
.
i phi mˆau thuˆa
˜
n (hay thoa
’
du

.
o
.
.
c), nˆe
´
utˆo
`
n
ta
.
imˆo
.
t minh hoa
.
cu
’
a S sao cho mo
.
i cˆong th´u
.
c A
1
, A
2
,.,A
n
dˆe
`
u d´ung trong

minh hoa
.
d´o.
- S du
.
o
.
.
cgo
.
il`amˆau thuˆa
˜
n (khˆong thoa
’
m˜an du
.
o
.
.
c), nˆe
´
u khˆong tˆo
`
nta
.
i
mˆo
.
t minh hoa
.

n`ao nhu
.
vˆa
.
y.
- Cˆong th´u
.
c A
du
.
o
.
.
cgo
.
il`alogic k´eo theo t`u
.
S,k´yhiˆe
.
u S |= A,nˆe
´
u trong
mo
.
i minh hoa
.
m`a ta
.
i d´o mo
.

i cˆong th´u
.
ccu
’
a S dˆe
`
u d´ung th`ı A c˜ung d´ung.
D˘a
.
cbiˆe
.
t, nˆe
´
u S = ∅ th`ı |= A c´o ngh˜ıa A l`a cˆong th´u
.
ch˘a
`
ng d´ung.
Ch´u ´y 4
Di
.
nh l´y 2.2.1 (nguyˆen l´y suy diˆe
˜
n) trong chu
.
o
.
ng2c˜ung d´ung cho tru
.
`o

.
ng
ho
.
.
p c´ac cˆong th´u
.
c A, B, H
1
, H
2
,,H
n
l`a cˆong th´u
.
c logic tˆan t`u
.
.
Th´ı du
.
3.3.6 Cho mˆo h`ınh suy diˆe
˜
n trong logic tˆan t`u
.
∀x
1
(P (x
1
) → Q(x
1

)) (H
1
)
∃x
1
P (x
1
)(H
2
)
∀x
1
(Q(x
1
) → R(x
1
)) (H
3
)
∀x
1
(S(x
1
) → R(x
1
)) (H
4
)
∴ ∃x
1

S(x
1
)(A)
3.3. Minh hoa
.
,su
.
.
dˆo
`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 91
trong d´o P (x
1
),Q(x
1
),R(x
1
),S(x
1
) l`a c´ac tˆan t`u
.
mˆo
.
t ngˆoi x´ac di
.
nh trˆen
mˆo
.

t tru
.
`o
.
ng minh hoa
.
D n`ao d´o.
Mˆo h`ınh suy diˆe
˜
n trˆen c´o
dˆo
`
ng nhˆa
´
t d´ung hay khˆong trˆen tru
.
`o
.
ng minh
hoa
.
v`a xˆay du
.
.
ng c´ac bu
.
´o
.
c suy diˆe
˜

ncu
’
a mˆo h`ınh trˆen?
Gia
’
i: Tas˜ech´u
.
ng minh r˘a
`
ng cˆong th´u
.
c B =(H
1
∧ H
2
∧ H
3
∧ H
4
→A)l`a
dˆo
`
ng nhˆa
´
t d´ung trˆen tru
.
`o
.
ng minh hoa
.

D theo nguyˆen l´y suy diˆe
˜
ncu
’
a di
.
nh
l´y 2.2.1 v`a phu
.
o
.
ng ph´ap gia
’
icu
’
a Robinson trong chu
.
o
.
ng 2.
Thˆa
.
tvˆa
.
y, x´et mˆo
.
t d˜ay s =(b
1
,b
2

, ) ∈

.T`u
.
H
1
,H
2
,H
3
,H
4
v`a A,
ta c´o hˆe
.
suy diˆe
˜
n sau nh`o
.
thay k´y hiˆe
.
uh˘a
`
ng c´a thˆe
’
b
1
v`ao c´ac vi
.
tr´ı cu

’
a x
1
trong hˆe
.
cˆong th´u
.
c d˜a cho:
P (b
1
) → Q(b
1
)
P (b
1
)
Q(b
1
) → R(b
1
)
S(b
1
) → R(b
1
)
∴ S(b
1
)
⇔

P (b
1
) ∨ Q(b
1
)
P (b
1
)
Q(b
1
) ∨ R(b
1
)
S(b
1
) ∨ R(b
1
)
∴ S(b
1
)
v`a chı
’
cˆa
`
nch´u
.
ng minh tˆa
.
p c´ac cˆong th´u

.
c
S = {P (b
1
) ∨ Q(b
1
), P (b
1
), Q(b
1
) ∨ R(b
1
), S(b
1
) ∨ R(b
1
), S(b
1
)}
l`a mˆau thuˆa
˜
n (theo nguyˆen l´y suy diˆe
˜
ncu
’
a di
.
nh l´y 2.4.1 (3) v`a phu
.
o

.
ng ph´ap
gia
’
icu
’
a Robinson (chu
.
o
.
ng 2)).
Tac´ohˆe
.
suy diˆe
˜
nnhu
.
sau:
92 Chu
.
o
.
ng 3. Hˆe
.
to´an tˆan t`u
.
1.P(b
1
) ∨ Q(b
1

)
2.
P (b
1
)
3. Q(b
1
) ∨ R(b
1
)
4. S(b
1
) ∨ R(b
1
)
5.S(b
1
)
















(S)
6.Q(b
1
)(1, 2, gia
’
ith´u
.
c)
7.R(b
1
)(3, 6, gia
’
ith´u
.
c)
8. S(b
1
)(4, 7, gia
’
ith´u
.
c)
9.  (5, 8, gia
’
ith´u
.
c)

Theo nguyˆen l´y suy diˆe
˜
n: S l`a mˆau thuˆa
˜
n (hay
dˆo
`
ng nhˆa
´
t sai) ⇔ S dˆa
˜
n
vˆe
`
suy diˆe
˜
n  (rˆo
˜
ng) theo phu
.
o
.
ng ph´ap gia
’
icu
’
a Robinson (chu
.
o
.

ng 2).
V`ı s du
.
o
.
.
ccho
.
n tu`y ´y, nˆen mˆo h`ınh suy diˆe
˜
n d˜a cho l`a dˆo
`
ng nhˆa
´
t d´ung.

3.3.7 C´ac cˆong th´u
.
c logic
dˆo
`
ng nhˆa
´
t
d´ung trong hˆe
.
to´an tˆan t`u
.
1) ¬∀xA≡∃x¬A
2) ¬∃xA≡∀x¬A

3) (∀xA∧∀xB) ≡∀x(A∧B)
4) (∃xA∨∃xB) ≡∃x(A∨B)
5) (∀xA∧G) ≡∀x(A∧G)
6) (∀xA∨G) ≡∀x(A∨G)
7) (∃xA∧G) ≡∃x(A∧G)
8) (∃xA∨G) ≡∃x(A∨G)
trong
d´o v´o
.
i 4 cˆong th ´u
.
c cuˆo
´
ic`ung x khˆong pha
’
i l`a biˆe
´
ntu
.
.
do trong cˆong
th ´u
.
c G.
3.3. Minh hoa
.
,su
.
.
dˆo

`
ng nhˆa
´
t d´ung v`a mˆo h`ınh 93
3.3.8 Da
.
ng chuˆa
’
nt˘a
´
c trong logic tˆan t`u
.
3.3.8.1 Da
.
ng chuˆa
’
nt˘a
´
ctiˆe
`
ntˆo
´
Di
.
nh ngh˜ıa 3.3.12 Mˆo
.
t cˆong th´u
.
ctˆant`u
.

A du
.
o
.
.
cgo
.
il`achuˆa
’
nt˘a
´
ctiˆe
`
ntˆo
´
,
nˆe
´
u A khˆong ch´u
.
a c´ac lu
.
o
.
.
ng t`u
.
ho˘a
.
cc´oda

.
ng Q
1
x
1
Q
2
x
2
Q
n
x
n
M, trong
d´o Q
i
(i =1 n) ho˘a
.
cl`a∀ ho˘a
.
cl`a∃,v`aM l`a cˆong th´u
.
c khˆong ch´u
.
alu
.
o
.
.
ng

t`u
.
.
Da
.
ilu
.
o
.
.
ng Q
1
x
1
Q
2
x
2
Q
n
x
n
du
.
o
.
.
cgo
.
il`atiˆe

`
ntˆo
´
, c`on M du
.
o
.
.
cgo
.
il`ama
trˆa
.
n cu
’
a cˆong th´u
.
c A.
Th´ı du
.
3.3.7 ∃x∀y(x ≤ y).
Di
.
nh l´y 3.3.1 Mo
.
i cˆong th´u
.
c tˆan t`u
.
A dˆe

`
utˆo
`
nta
.
imˆo
.
t cˆong th´u
.
c chuˆa
’
n
t˘a
´
ctiˆe
`
ntˆo
´
tu
.
o
.
ng du
.
o
.
ng v´o
.
i n´o.
Ch´u

.
ng minh
Ta c´o thˆe
’
vˆa
.
ndu
.
ng c´ac cˆong th´u
.
ch˘a
`
ng d´ung (c´ac cˆong th´u
.
ctu
.
o
.
ng
du
.
o
.
ng) trong mu
.
c 3.3.7 v`a thˆem c´ac cˆong th´u
.
ch˘a
`
ng d´ung sau dˆe

’
du
.
a A vˆe
`
da
.
ng chuˆa
’
nt˘a
´
ctiˆe
`
ntˆo
´
(phu
.
o
.
ng ph´ap dˆo
’
itˆenbiˆe
´
n):
1) ∀xA(x) ∨∀xB(x) ≡∀x∀y(A(x) ∨B(y ))
2) ∃xA(x) ∧∀xB(x) ≡∃x∀y(A(x) ∨B(y ))
3) ∀xA(x) ∧∃xB(x) ≡∀x∃y(A(x) ∧B(y ))
4) ∃xA(x) ∨∀xB(x) ≡∃x∀y(A(x) ∨B(y ))
5) ∀xA(x) ∨∃xB(x) ≡∀x∃y(A(x) ∨B(y )).
Dˆo

`
ng th`o
.
i ta thu
.
.
chiˆe
.
n c´ac bu
.
´o
.
cbiˆe
´
n dˆo
’
i liˆen tiˆe
´
p sau dˆay:
• Tru
.
´o
.
chˆe
´
t loa
.
ibo
’
ph´ep k´eo theo → nh`o

.
cˆong th´u
.
c: A → B tu
.
o
.
ng
du
.
o
.
ng v´o
.
i A ∨ B, v`a ph´ep ↔ nh`o
.
cˆong th´u
.
c: A ↔ B tu
.
o
.
ng du
.
o
.
ng
v´o
.
i(A → B) ∧ (B → A).