SÁCH Đ Ạ I HỌC s ư
N G Ô ì HỨC

PHẠM

LANH

Vả

HOC
TẬP

li

Đã được hội đòìtq thấm âịnh sủa Bộ giảo
giới thiệu làm sách dùng
chung
cho cấc trường đại học S!C
phạm)

NHÀ XUẤT BẢN GIÁO D i

dục


Biên soạn

: N G Ô THỨC L A N H

BU*

: NGUYỀN K I M THƯ

tập

huật : T R Ầ N T H U NGA
Trình

Mỹ

Sưa bản in

bid

í


CHƯƠNG

C ơ sở

LOGIC TOÁN

Mở đ ầ u lập ì gìto t r ì n h Đại số và số học, la d ã l à m
q u e n v ó i i r ộ t số khái niệm và kỉ h i ệ u c ỉ a logic toán
Ó u r o n g ì của tập l i này sẽ trình b à y m ộ t tảth có hệ
thống hon các khái n i ệ m co- Làn (ủa logic t o á n , bao gồm
đ ạ i số m ê n h đẽ và logic vi t ừ hep, hình t h à n h VÈO nửa
sau Cua t h ế kỷ X I X trong các công t r ì n h của Bun (G.Boo­
le 1805 — 1864), B c m o o c g ă n g (A. Eeroorgan l&'G — 1871)
Poretsky (n. c. riopeuKni 1846 - í%7) F r c g ơ (G. f r e g e

1849 - 1925), Peano (G.Pearo 1858 — 1932).
Cách t r ì n h bày ở đííy là sơ lượt: và phu cộp. K ỏ nhằm
giời t h i ệ u nhũng khái niệm cơ bốn của logic toán l à m
Ìíồa cho Sự suy luận và nhũng kí h i ệ u logic t h ô n g dờng
t f o n g n e giáo trình loến h é c hiện đ ạ i .

§ I . Đ Ạ I S Ổ MÌNH Đ Ì
1.1. Mệnh đi v à các p h é p t o á n

logic

ỉ 1.1. Mệnh đề : K h ả i n i ệ m nờnh đ ề là m ộ t khái n i ê m
B|uyén thủy. Ta có thề quan n i ệ m mệnh đi n h ư một l á u
trong lít ôn ngữ thông t h ư ờ n g biêu thị n ộ i ý t r ọ n vẹn
làà khi nói lên hoặc viẽt ra, ta co the k h ỉ n g định m ộ t
Jẻẫth khích quan là r ó rtđủng » hoặc (' tai » . > hí ng ỉ an câu


(•(Hai năm rổ mười).) là một m ệ n h đ ề
m ộ t số nguyên » là một mệnh đ ề sai.

đủng,

c â u (Kít l i

Không phải m ọ i câu trong ngón ngCr t h ò n g t h ư ơ n g ỉh\
l à một mệnh đ ề xét trong logic toán. Các c â u h ỏ i , câu
than, câu mệnli lệnh, các đ ị n h nghĩa trong t o á n học, và
nói chung các CUI k h ô n g n h ú n p h á n á n h tỉnh đ ú n g , sai
của thực te khách quan, đ ề Ì k h ô n g phải l à n h ữ n g mệnh


đ ề của

logic t o á n .

Trong logic loàn, k h i xét một mệnh đ ề , ta k h ô n g quan
t à m đến cấu t r ú c ngữ p h á p cũng n h ư ỳ nghĩa n ộ i dung
của nở, m à chỉ quan tà n đ ế n tính đ ú n g sai của nỏ mà
thói. Giá trị cc đúng;!) hay ( t s a i » của m ộ t mệnh đề gọi là
giá tri chăn li của t i T m h đ ề đ ó . Ta quy ưỏrc kí h i ệ u giá
trị chân lí (-(đúng).) bồng sá Ì, gin trị ((sai » bồng số 0.
| Ị ' M ộ t mệnh đ ì m à k h ô n g m } t bộ phận thực sự n à o của
n ỏ cũng là raện'i đề, gọi là một mệnh đề đơn giàn. Ta
sẽ k i h i ệ u các ra ánh đồ đ ơ n giản b ồ n g các c h ữ cái la
tinh nhỏ (có t h ề v ớ i các chỉ sổ) a, b, c,
p, q, r. ..
X, y, z
Hi, bi, CI, p i , q , r i , . Đày là các biến l ấ y g i ả
trị Ì hoặc 0 k h i ta thay c h ú n g bồng các m ệ n h đ ề cụ thề,
Vì vậy ta gọi c h ú n g là các biên mệnh
đầ.
t

T ừ các mệnh đ i đơn g i ả n , n h ờ cúc liên kết logic, cũng
gọi là cúc phép toán logic ta l ậ p đ ư yc những mênh 4ầ phức
tạp. Gác m i n h đề phức tạp cũng có một và chỉ m ộ t
trong hai giá t r ị «dúng»
hoặc « s a i » . Tính « đ ú n g » ,
« s a i » của các mệnh cfớ phức tạp p h ụ thuộc vào t i n h
ít đ ú n g », re sai » d ĩ a các m ệ n h đồ t h à n h p h ầ n cẩu t ạ o nên

c h ú n g . Một trong những n h i ệ m vụ cơ bản của
logic
mệnh đồ l à nghiên cứu sự phụ thu ọc đ ó .
í.1.2.

Các phép

a) Phép

phả định

kỉ h i ệ u là " l a
4

toán

logic.

í Cho m ê ọ li đ ề a. Phả

(hoặc ã ) v à đọc là

«không

định

của n ó ,

a»,


là

một


m ệ n h đề đ ú n g k h i a là mệnh đề gai và là m ộ i mệnh đê
sai khi a là mệnh đe đúng.
b) Phép hội: Cho bai n ệ n h cU- a và b. H ộ i cùa chúng
kí hiệu là a A b (Voặc a và b ) \ à đọc là « ã và b » là m ộ t
mệnh đi đ ú r g khi và chỉ khi a \ à b đêu đúng, -và là
một mệnh đề sai trong C Í X t r ư ờ n g ' l ọ p còn l ạ i .
5

tuỵhi : Cho hai mệnh đ ề a và b. Tuyền của
h i ệ u là a V b và đọc Jà «a hoặc b i ) , là một
sai k h i va chỉ k h i a và b đểu tai, v à la
đ ề đúng trong các t r u ờ n g họp còn ỉ ạ i .

c) Phép
c h ú n g , kỉ
mệnh đe
một mệnh

d) Phép kéo theo : Cho bai mệnh đì' a \ à b. a kẻo
theo b, k i h i ệ u là a =» b v à đọc J h ư thế, là m ộ t m ệ n h
đe sai c H trong t r ư ò r g họp a đ ú n g và ỉ) sai, và là n ọ t
m ệ n h đề đ ú n g ỉroĩìg các trường h ọ p còn l ạ i .
;

e) phép

tương
đu ang. t h o Yâi ir.ệnh đ ề a và b. a
ítiơTK/
đương b, k í hiệu là a -H> 1), xà đọc tìlur the, là một
mệnh đi- đ ú n g k h i a và b cùng đ ú n g , hoặc cùng sai, và
là một mệnh đề sai trong các t r ư ờ n g hợp còn l ạ i .
Cốc phép toán logic đ ị n h nghĩa t r ê n đấy đ ư c c mô tả
m ộ t
c á c h đ ầ y
ó ủ Lằng Lảng S P U , g ọ i
l à b ả n g chân
lí của
c h ú n g .

a

b

I -

a A b

a V b

a

b

ỉ
1


1

Ị

0

1

1

1

1

1

0

;

0

0

1

0

0


0

1

1

Ọ

1

1

0

0

0

1

0

0

1

1

ã



1.2.

Công thức của dẹt

số mệnh đ ề

1.2.1. Nhờ các p-lép toán logic t r o ' t ó mệnh đề đ ơ m
g i ả n , ta có thì dựng dược
những m ; n ' i đồ m ớ i , ngà\y
càng phức tạp h ơ n , bằng cách tuực hiện trên các mộ ni-1
đề đ à cho một sổ hữu hạn tùy Ỷ n h t h i j p h ' p toán logiic
Các mệnh d ề dựng đirọc theo cách ợ y , k? cả cúc mệnh ố p .
x u ợ t phút, ịiọi là các; công thức của đại số mệnh
đĩ.
1.2.2. Bề đ!n'ì nghĩa một c'xch chính x-'tc khái niệ..n
n à y , ta .sẽ xu'it phát t ừ m ộ t l ậ o hợp kí hiệu cơ han fị(;.)i
hi bảng chữ cái
Bảng chừ cúi trong đ ạ i số mệnh đ'ĩ ba Ì gôm
( i ) 0 Ì lù kí hiệu của các mệnh đồ cỏ giá t r ị
t ư ơ n g ú n g tà .sai, hoặc đ ú n g . Ta gọi chúng là các

chím

lí

lìằiVỊ.

( i i ) Các chữ cái la t i n ' ! nhỏ a, b, c .. , p, q, r, ... X , V ,

7,,.. , ai. bị, C | , . . . . Pi, q i , T ị , ... là kí h i ệ u của cúc b i ể n
mệnh

đe.

( i i i ) ì, A, V, =>,
là kí hiệu của cúc pVỉp loàn
v à (,) là các dâu ngoặc.
1.2.3. M ỗ i dãy h ư u hạn tùy Ý những k í
g ọ i l à một từ t r ê n bảng chữ cúi đ ỏ . Ta
bằng các chữ cái la tỉnh l ò n A , H, c,..,
cả các t ừ , ta xét lỏrp t ừ gọi là công ì hức
nghĩa bằng quy nạp n h ư sau :

logic

hiện t r ê n đ i r ợ c
k i hiệu các t ù "
Trong l ớ p ttắlỉ.
và được địịnhi

(i) Các hằng, các b i ế n mệnh đè l à nìiững công thán-'.,
( l i ) Nếu A là một ( ô n g thức t h i ( " I A ) là một công thávc.( i ỉ i ) Nếu A và B la những công thức thì ( A V B),>
(A A B) (A =»B) và (A «4 B ) là những công thức.
( i v ) Mọi l ừ khác, khàng được xác định theo các
tắc ( i ) , ( ị i ) và ( i ỉ i ) , t h ì không phải là công thức.

quw

Ta chú ý r ằ n g cúc dợu ngoặc trong đính nghĩa t r ộ m Ì

đ â y là cần thiết đ ề chỉ r ằ n g một công Ihửc đ ã cho đĩirọcc ĩ
t h i ế t l ậ p nên l ừ các công thức xiíẩt phút n h ư thế nĩâo),,
6


"Và đe đó ta cỏ thề khẳng định được một từ đ ã cho
phái là một công thức hay không.

cỏ

-

Chẳng hạn, xét từ ((X Ả y) => ((x V y) V X ) ) . Vì X, y, X
lù những cồng thức theo (i), (ỉi) và (x V y), (x A y ) ,
í((x V y) V x) là những công thức theo (iii), nên vẫn theo
l(iii) từ đ ã cho là một công thức. Trái lại, từ (x A v) =>
=>• ((x V y) không phải là một công thức vì nó dược thiết
ìlập không phải chỉ theo các quy tắc (ỉ) (ii) và (iii).
Có thề đua ra một sấ quy ước cho phép lu'Ọ"0 bỏ một
ỈSỐ dấu ngoặc, khi viết các công thức. Nhưng điều này không
tỉiật cằn thiết, nên ta sẽ không trình bày tỉ mĩ ử đây.
T a sẽ chỉ quy ước k'Ịỏng viết các dấu ngoặc ngoài cùng
phép phủ định các biến mệnh đề.
1 3 G i á t r ị của c ỏ n J t h ứ c - C ô n g t h ứ : h ã n g đ ú n g - C ô n g
nhức h ã n g s a i . T ư ơ n g đ t r v n g iogic- p h é p t h ế t r o n g m ộ t
vông thức

1.3.1. Giá trị của còng Ihức. Giả sử A lá một công tliửc
élâ cho. T a gọi là dãy giá trị chùn lí của các biến mệnh

đè trong còng thức A, một duy cỏ dạng e = (ej, ej, ... e„>
trong đ ó ei € ịo, lị ( í = Ì, ...,n) đưọ-c cho tương ứng
với cúc biển mọn li đề cỏ mặt 'vong còng thức A.
Giá trị cùa cỏny thức A trên dãy
ỉà Ale, được địnn nghĩa như sau;

giá (rị

e, kí

hiệu

— Nếu A là một biên mệnh đồ Pi thi A lo == ei
— Nếu A có dạng ì B, trong đó B là một cồng thức
m nếu B Ị e đ ã đ i r ọ c xác định Hù
A

— Nếu A có
(B =» C) và (B

16

( 0 nếu BỊe = Ì

ỉ Ì nếu

BỊe = 0

mội trong các dạng (B V C ) , (B AG),
C), trong đó B và c là những công

7


thức, và nếu giá t r ị của B và
t h ì giả t r ị của A trên e cũng
định giá trị của công thức
hợp v ớ i định nghĩa của các
nêu ở trẽn.

c t r ê n e đ ã được xác định
được xảo định và việc Xi'cli
 t r ê n dãy giá trị e phù
p h é p toán V, A, =*, <h> đi!

Thí dụ : Tí nh giá trị của cóng thức (a V b) =* ( ì A A (.)
trên các dãy giá trị e = <(), Ì, 0) và é' = ( Ì , Ì, 0> ứng
v ớ i cúc b i ế n mệnh đ ề a, b, c. Ta c ỏ
(a V b) => ( n a A c)

o i l

ơ

1000

111

0

0100

Vậy giá trị của cóng Ihủc đ ã cho, liên cúc dẩy gin L i
e và c' dì u bẵng í), (ó' đày ta đi! ghi đ u ô i cúc b i ế n mệnh
đ ề cúc gi;\ trị tương ứng của chúng, d ư ứ i cúc phôi' toán
logic Ci'.c gi;'', trị L i a c ô r g t h ú c l'iU'.g buộc hởi các p h é p
toán đ ố ) .
1.3.2.

Ceng

thức

hồng

dứng.

Công

thức

hằng

sai.

Một công t h ú c A gọi là hằng đúng nếu và chỉ nếu nơ
nhận giá trị Ì tiên m ọ i dãy giá t r ị của các biến m ệ n h
đ ề có mặt trong công thức A, tức là
A Ịe =
Thi

Ì trên m ọ i d ã y giá trị e.

dụ. Công thúc p => ( n
p

1
1
0
0

q V p) là h
n g đ ú n g

V p)
1 0
1 1 1
1 1 0
1 1
Ì ơ
Ì
0 0
1 1 0
11)
=* (~1

q

Nếu A là một công thức hẵng đ ú n g thì ta v i ế t 1= A .
Các công thức h
n g đ ú n g đống m ộ t vai t r ò r ấ t quan

trọng trong lôgic. Chúng là những hìậl logic.
8


C ă n cử v à o đ ị n h nghĩa g i ả t r ị c ủ a m ộ t c ô n g t h ứ c , t a
t h ấ y r ẳ n g n ế u m ộ t c ô n g thức A n h ậ n g i á t r i Ì t r ê n d ã y
g i á t r ị e t h ì ~~1 A n h í m g i á t r ị 0 c ũ n g t r ê n d ã y g i á t r ị đ ố .
Do đ ó n ế u A l à m ộ t c ô n g t h ú c h ằ n g đ ú n g t h i c ô n g t h ứ c
~~1 A n h ậ n g i á t r ị (} t r ê n m ọ i d ã y g i ũ t r ị c ủ a c á c b i ế n
mệnh đ ề .
M ộ t c ô n g t h ứ c chì n h ậ u g i á t r ị 0 t r ẽ n n c i d ã y g i á t r ị của
c á c b i ế n m ệ n h đ ề c ó m ặ t (rong c ô n g t h ứ c đ ó g ọ i l à m ộ t
công
thức hằng sai hay là mâu
Ihuẫn.
R ò r à n g L ế u n . ộ t c ô n g thức là hằ.i^ị sai ( h ì p h ủ
c ủ a no l à 1: ó t ( ô n g l l i ứ c h ằ n g đ ú n g v á n g ư ợ c l ạ i .
1.3.3.

Cônq

Ihửc

tươnq

đương

định.

logic

G i á sử A vù B là hai c ô n g t h ú c c h ú a c ù n g n h ồ n g b i ế n
m ệ n h de ìihxr n h a u . T a n ó i r ằ n g c h ú n g l à tương
áưonq
l o g i c n ế u v à t h í 1'ếu c h ú n g có c ù n g m ộ t gií\ t r ị t r ố n m ọ i
đ à y giá t r ị của c;':c b i ế n m ệ n h đ ề , l ứ c là A I e — B I e
t r ò n m ọ i d ã y g i á t r ị e. T a kí h i ệ u h a i công t h ứ c tivơng
đ ư r m ơ lôgic l á A == B .
Ta c h ú ý r a n g t r o n g đ ị n h n g h ĩ a t r ẽ n , đ u n k i ệ n A v à
B c h ứ a c ù n g n h u n g b i ế n m ệ n h đĩ nhir nhau k h ô n g p h ả i
l à c h ủ y ế u , v ì ta cỏ thê đ ị n h nghĩa m ộ t c á c h t ô n g q u á t
h ơ n sự lưcmg đ ư ơ n g logic g i ồ a các c ồ n g thực m à t ậ p h ợ p
cúc b i ồ n m ệ n h đ ề c ó m ặ t t r o n g các c ô n g t h ứ c đ ỏ , k h ô n g
h o à n t o à n t r ù n g nhau. C h ẳ n g h ạ n h a i t ô n g t h ứ c sau l à
l ư ơ n g đ ư ơ n g lỏgic : p => q và ( " I p V' q>-A ( x V ~1 x ) .
J.3A.

Phrp

thè

trong

mội

côriỊỊ

thức

— ( ì i ả s ử A là m ộ t c ô n g t h ứ c c ó chứa b i ế n m ệ n h đ è Pi

V,'; H là m ộ i c ô n g thức t ù v ý . T r o n g c ò n g t h ứ c k, m ỗ i k b i
x u ấ t h i ệ n b i ế n m ệ n h đ e Ị) ta thay p h ỏ i B . L à m n h ư
v ậ y , ta n h ũ n đ i r ọ c m ộ t c ô n g thức m ó i c . Ta n ó i r ằ n g
c là c ô n g t h ứ c n h ậ n đ ư ợ c t ừ A n h ò ' phép
thế h i ế n mỌnh
đ è p bời c ô n g t h ứ c B . K h i đ ó t a v i ế t G = S f A .
9


(

v

Thỉ dụ. Cho A là cô.ig thức p =*• (p V ỉ ) *à
là cố:g
thức) q A r) =» s. Công thức nhận được l ừ A nhờ
\)hfiỊ)
thế biêu mệnh đ ề p Lỏ i B là
s« A = ((q A r ) => s) => ((q A r) =* s)vq).
1.3.5.

Mộ!

số tinh

chái.

a) Nêu Ả và B lá hai còng thức lươn:/ đươnj
chữa
biến mệnh

đê Ị) V I c là một
CÒM) thức

sfr A =

lofjic cùn I
lùi] ý, thì

se B

Thụt vậy, già hử e la một dãy tùy ý những giá irị (.'lia
c X hií',1 mệnh đ ề cỏ mặt trong s i A. Khi dó giá trị V V.
se A iron e là giá trị củ i c trên e đ ê u (hv-/o xáo ui,;!!.
N ế u ta gựi e' là dãy giũ i n của các biến nv;nh ú ' Iropji
A đirự-c chựn tương ứng nlnr trong e, t r ừ gi;'), trị của bít',í
mệnh d ề Ị) được chựn bằng c ị e, thì biến nhiên A Ị é' =
— Sp A I e. ư ơ n g tự la có Bịe' = Sp i í / e . Tíieo giá i! ũ ế
A ị e = B ị é'. Vì vậy s£ A le = Sịr tì Ị e. V ớ i m ự i dãy g i ;
trị của cúc b i ế n mệnh d ề . Do đ ó Sp Ả = s i B.
Tương tự ta c'u'mg minh đưc/c tính c'ltit.
b) Giả sử A là một công
vá lì và c lá hai công thức

thức chứa biền mệnh
đề Ị)
tươnq
đương
lotjtc. Khi
đó

A = Sp A
c) Gia
và

B

là

sử

A

một

lờ

mội

công

vông
thức

thức
tùy

ỳ.

chứa

Liên

Khi

đó

mệnh
nếu

đ ề 1>

1= A

thì

|=S>A
Thật vậy, g i ả sử e là một dãy bíỈL k i những giá trị
của cốc biến mệnh l ề có mặt trong công thức
A. N ế u
ta chựn dãy e' các giả t r i của các b i ế n mệnh đ ề có m ặ t
trong A giống n h ư ta đ ã l à m trong p h é p cliứng m i n h
t i n h chát a) thì la có
A I e s= A I é* =

lí)

Ì


t ừ d ỏ suy ra rằng sị? À lấy giá trị Ì trên m ọ i dãy giá

trị của các biến mệnh ớ?, vì vậy 1= Sp A.
ả) Giã sử A ưa B là hai còng
nén và ch' nêu 1= (.1 ±= B).

thức.

Khi

đồ,

A =

B

(=*) Giả s ử A — B. Khi đu A Ị e = B I e v ớ i m ọ i dãy giá
trị e của các biến mệnh đ ề cỏ m ạ i trong A và B. Theo
định nghĩa của phép toán 4=>, ta có ( A
B) ị e == Ì trên
m ọ i dãy giá trị e. Vì v ậ y 1 = (A 4=> B ) .
{«=) Đảo lại.,, n í u
(A •*"•> B) thì ( \ ^ B|e =
lấiọi dãy giá trị e. Theo định ag'ũa (A 4= B ) Ị e =
vá c ! - f h i l l A | e — B ị * . T ừ đ ó suy ra A = lí. •
í.3.6.

Mót

sô cóm/

thức

hằng

đúng

đơn

Ì, v ò i
1 nếu

gián

Dựa vào cúc dị nil nghĩa và các t ú f i C i ĩ í l trên, ta có
Lhê đe dàng chửng m i n ' i m ộ t sợ công 1'ìửc hằng dứng
đ ư a giản sau đây :
X ^ X

Luật đỏng nhất

X A I « x

Luật lũy đấng của hội

X V X *Ạ X

Luật l ũ y dẳng của

(ĩ A y ) ^ ( j A x )
•
(X V y ) ^ ( y V x)

(X A (y A zj) ^ ( ( X A y) V z)
(x V (y V z)
( ( V y) V
X A (y V
( ( A y) V ( ^ ) )
x

z

x

x

x

(x V ( y A z)) ^ ( ( V y)

z

tuyên

L u ậ t giao Iioản của hội
Luật giao hoán của tuyên
L u ậ t kết họp của hội
L u ậ t kết hợp của tuyên
L u ậ t phân p h ợ i của hội
đ ợ i với tuyề n

V z)) Luật phàn phợi của ì uyển
đ ợ i v ớ i hội

l l x ^ x

L u ậ t phủ định

kép

( x ^ y ) ệ * (y ^» x)

L u ậ t giao ho Ún củía lưo-ng
đương

(x => y )

("Ì y => "Ì x)

ì (xAy)^(lxv

"ly)

L u ậ t phản đảo
L u ậ t phủ định h ộ i
l i


"Ì (x V y ) & í ~1 X Ả l y )

L u ậ t phủ định

tuyìn

( x A y ) < 4 H( "ì X V " l y ) ị

Công thức Đơir.oocgăng

íx v ỹ ) * * ~1( ~ l X À l y ) )
xAltìx
X
X

V Ì «^ Ì
0

Dựa vào cốc còng thúc hằng đ ú n g trên v à áp dụng t ỉ n h
chất (1.3.5. d), ta có thế suv ra những công thức t ư ơ n g
đ ư ơ n g lôgic v ớ i nhau.
1.4-

Hàm

Bun

1.4.1. Định n g h í a
Giả sử A là một công thức của đoi số
ri biến m i n h d ề khác ni au và e = (e
một dãy g i ả trị của các biến mạnh đê có
thức A . Ta định nghĩa một h à m ri biến
Xí.c định trôn lập hợp các dãy giá (rị e

ịt

f(ei,

Ẽ2,

mạnh đề chứa
e , ... , e „ ) là
mặt trong cônií
f(x],x ,
Xn)
bằng cách đ ạ t
2

2

. . , e ) = A I e vói m ọ i d ã y giá trị e.
n

Ta nói rằng h à m f định nghĩa như vậy là h à m
hợp
nhất vói công thức A . Còn công thức A thì gọi là c ò n g
thức thề hiện h à m f . Bằng cách định nghĩa như t r ê n ,
m ọ i công thức đ ề u có một h à m họp nhất vói nó.
Như vậy b á m f ( x i , X2, .... X a ) nhận giá trị Ì hoặc 0 k h i
các biến nhận các giá t r ị Ì hoặc 0. Nhũng hàm f như thế
gọi là hàm Bun hay hàm dụi số logic,
Đối với một h à m Bun n hiến, số róc dãy giá Irị của
các biến bằng 2 . \ ó ' i m ỗ i dày giá trị của các b i ế n , hàm f
nhấn giả t r ị 0 hoặc 1. Do đ ó số các hầm Bun khúc n^au
chứa lì biến bẵng 2

n

2 n

12


ÍÂ.2,

Vài hám

Bun

sơ

cấp

a) f t ( x ) =

0

h à m đòng nhai 0

},) f ( x ) =

Ì

h à m đòng nhất Ì

2

c) f , ( x )
d)

f4(x,

=7
y)

=

e) f (x> y ) =
5

Ỉ6

í)

( x

'

y)

=

h à m phủ định (ta
bởi
- )
XV

XV y
X e> y

thay đắn

ì

h à m tích logic (la'im h ộ i , đ ẩ u À
được thay b ở i . )
tuyền)

h à m tỏng logic ( h à m
hàm

tồng

môđun 2

Bảng giá t r ị của các h à m trôn được cho n h ư

sau

f4

h

u

1

0

0

0

1

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

X

y

0

0

0

1

0

1

0

1

0

1

1

f

2

f

3

í.4.3. Sự xác định còng thức the hiện một hàm
Bun
cho
trước
Trôn kia ta đ ã thấy rằng m ỗ i còng thức của đ ạ i số
mệnh đ ề đ ề u c
một hàm Bun hợp nhất v
i nỏ. Sau đ à y
ta sẽ chứng m i n h rang m ỏ i h à m . B a n cho trir
c đồu có
một công thức của đ ạ i số mệnh trô the h i ệ n n ó .
M ệ n h d è . Giả sử f(xi, %2>
Xa) là một hàm Ban n
biín, và e= Cei, e>,
e > vời e, 6 ịo, lị ((

=t,2,...,n)
a

13


và

le < tì. -Khi

dưới

đó

f(Xi,

có

the

bưu

V
ei,

X i

1

x f

e ,

[

2

1

k

x£ -f(ei,...

=
ek,

X

k

1,

+

x

mọi

là

u ột lích

bộ qiá trị

sơ cáp

(ei,

và

V /ó long

minh : T r ư ớ c hết ta chứng minh rằng lích NO"
nhận giá trị Ì khi và chỉ khi các b i i ế n

2

X® ...

dãy

( d , e

t

'íbạt

, C k

2

e

Ci = 0 thì X j ' =

t r o n g

c h ỉ

khi

t r ư ờ n g

Ck t r o m ị *

2

) .

vậy, tích sơ cấp x j '

chỉ lỉhi, vói n . ọ i ĩ =

khi và

hngic

Ểk).

Xk nhận Ci'.c g i ả trị t u ô n g ứng c . e . .

e =

)

/ , .... Ả-, a - ị x i r.ểu ei = 0
(Xi
nếu e i = Ì

XI, x .
2

n

e i

/71(Ỉ /• =

ccị gọi

Chứng
t ấ p a-j .

. . .

k

X ị . xị ...

theo

2

X 2 , X n )

ek

2

/ n n ợ đ ó , với

=

duĩn

dọng
f(xi,

lấy

.to)

S j

Ì, 2,

2

. . .

Xfc

k, x

nhận

k

e i

g i á

(rị

Ì

=

h ọ p

ei. Nếu ei =

0 =
n à y

X j '

=

Ì

khi

v à

nhận giá trị 1. N^ếư

X i . V ậ y trong t r ư ờ n g hợp này x
Xi

k h i

Ì thì

v à

ei. V ậ y trong cả hai t r ư ờ n g h ọ p ,

c h ỉ
x ei
t

e i

=- Ì
wậy

Xi,
k h i

Xi =

Ì

=

nhận £>iầ trí? Ì

k h i và chi khi X i nhận giá t r ị bằng ei. T ừ đó suy ra rẳ»ng
2

k

lích sơ cấp X j ' , x f . . . xị
Xi, x

a

, X í t

nhận giả t r ị

Ì k h i và chỉ kklii

nhận các giá. t r ị l ư ơ n g ứng ei

ti

eiu;

Đề chối g m i n h đẳng t h ú c (1), ta sẽ chống tỏ r £ m g
v ớ i m ọ i d ã y giả t r i của cốc M ế n X i , X2, . . . X k , hai v ế
đ ề u bằng nhau.
14


' T h ậ t vậy, giả sử < e , e ,
ek > là m ộ t dãy bất k ì
n h i ting giũ t r ị của các b i ế n X I , X 2 ,
Xk. Dĩiy này trùng
v ố n m ộ t duy số mũ trong các tích so- cấp ở vế phải của
(1)). Khi thay dãy giá t r ị này vào các biến
x ,
Xít
troong đ*ng thúc (1), thí c h ỉ một tích sơ cấp nhận íịià
trịt Ì, còn c;'\c tích so- cấp khúc nhận giá trị 0, cho nên ta cỏ
ĩ(eữị,
ek, X k + 1 , ••• » ) =
• f(ei,
ek, Xk+1,
x ) ==
t

2

2

x

=

f(e

1

ek,

1 }

Xk+1,..., X n )

^Vì ( e i
de) là mót d ã y b ấ t k ì , nê;i đẳng thức (1) đ ã
đin-ọc chứng minh. Q]
ĩHệ q u à 1. Đổi với mỗi hàm Bun khàng dòng nhốt ớ.
rỏm tại một còng thức chỉ chứa cái- ph<''p toán logic A
V,, ~| thè hiện nổ.
' T h ậ t vậy theo đỉnh lí trên, ta cỏ
f(sci, x ,
2

Xi) =

1

V
(ci,

xỉ .

t2ĩ

.••)

*2

2

x

•••

n

n -

f

e i

'

e

2

e

'

°)

Én)

'Trong đẳng thức n à y . nếu f ( e j , C2,
1

(

2

e) =

Ì t h i ta

n

cồn nếu f ( e i , ea,

e

g i i ỷ l ạ i tích sư cấp X j . x ^ . . . x " ,

e ) = 0 t h ì ta b ỏ tích SO' cấp đ ố đ i . Cuối cùng í a đ ư ọ c
n)

f ( x i , Xa, .... x » ) =

V

(ei, £ ,
2

1

X? • xf^... x*

n

e)
B

f(ei. e ,.... e ) = l
2

n

'Vế phải của đẳng thức (2) chinh là công thức chỉ chứa
'Me p h é p toàn A, V , "Ì thề hiện hàm Bun f ( x X 2 . . . , X n ) . Q
Tà chú ỷ rằng trong v ể phải của đẳng thức ( 2 ) , m ỗ i
í c ì h s ơ c ấ p c h ứ a đ u n g n b i ê n va m ỗ i b i ế n c h ỉ x u ấ t h i ệ n
l t

mệột l ầ n t r o n g m ỗ i

lích s ơ c ấ p .

Lác

tích sơ cấp

íihiau, v i chúng c ó d ã y số m ũ khỉiC nhau.

dì u

khác


Vè' phải của đẳng thức (2) gọi là dạng clìiiằn
hoàn loàn của hàm Bun /"(.ti, x , .... X n ) .

lắc

tuyên

2

Thí dụ: T i m dạng chuẵn tác tuyên h o à i l o à n của
hun f ( x i , x , x ) cho bời bảng sau
2

'âm

3

X!

f(x ,

x ,

*2

X3

0

1
1
0
0
l
1

0

1)

1
0
1
0
1
0
1

1
1

0

0

0

0

1
1
1
1
1)

t

x )

2

3

1
0
0

1
0

Theo t r ê n , ta có
•f(Xị, X2, x )

3

=

Xi . x

2

. x

3

V XI . x

2

. x

3

V XI . X2 . x

3

V

Xl.X2.X3,

Ta chú ý r ằ n g một h à m Bun đòng nhất b ằ n g 0 thì
k h ô n g thề biếu diễn đir.ro d ư ớ i dạng chuầu tấc t u y ê n

h o à n toàn. Còn m ộ i h à m Bun n biến đ ò n g nhất b ằ n g Ì
t h i hiền diễn được d ư ớ i dạng clmần tảe tuyên h o à n toàn
chứa đ ú n g 2 tích sơ cấp.
n

Bày g i ờ g i ả sử f ( x i , X2,
X n ) là một h à m Bun n b i ế n
không đỏng n h ấ t bằng 1. Khi đó h à m f ( x i , X 2 ,
x )
không đòng nhất bằng 0. V ậ y theo đ ị n h lí t r ê n , ta cỏ
n

f(xi,

í?6

X2...M

!*)=

V

l

x® .x*2...

D

X* T

(ei,

e i , ....

e«)


p h é p phủ định hai vế của đ ẳ n g thức n à y ,

Thực hiện
ta đ ư ợ c

F(xi, x ,..., x ) =
2

V

n

(si,
=

A

(x^i V e2
x

ti,

e

ei. e 2 . . .
x

...,

e J
fl

e

( e i >

_

2t

f

C n )

e)
n

. , V e„)

v

x

x

(ei, eỉ,

., e >

=

(x[ vx^v...vx ;)v

V T"(

eiỉ

e

2)

# > 1 Í

e)
n

n

A

1

e

f(ei,ei, ...Ì

c )

<ei, e , ... e >
2

l ừ đ ó suy

n

ra

f( ,X2,...,x„) =

e

A

X l

x /v

x

e|

V -

..

v

x

e

(3)

n )

en)
f(ei, e2, .... e ) = 0
n

V ế phải của đ ẳ n g thức (3) g ọ i là dạitCỊ chuàn lắc
hoàn toàn cùa hàm Bun f(xi,
x,
Xa).
N h ư vậy ta đ ã chửng m i n h đ ư ợ c

hội

2

H ệ quả 2. Đỗi với mọi hàm Ban khónq
đòng
bằng í , lỏn lụi một cống thức dụng chuồn tắc hội

toàn thì hiện nỏ [ j

nhát
hoàn

Thỉ dụ. Công thức dạng chuẫn tác h ộ i hoàn loàn thế
h i ệ n h à m Boole
x , x ) đ ã cho trong thí dụ irên l à :
2

3

f(n, x , Xj)=:
2

=

( x i v x v x ) A (XIVX2VX3) A (Xivx7vx ) A ( X i V X 2 V X ) 2

3

3

Ta c h ú Ỷ r
n g m ộ i h à m Bun đòng nhất b
n g Ì
biêu d i ê n i t i r / Y f . rlii-.Tri rlnnrr f i l l !
2-129

3

khỏn^
f


m ộ i h à m n b i ế n đòng n h ấ t bằng 0 t h ì b i h i diễn được
dirỏi dạng chuầri tắc h ộ i h o à n toàn chửa đúng 2
tông sơ cấp.
R

Tử
công
họp
biêu
(hội)

định nghĩa của h à m Bun v à định nghĩa của cúc
thức t ư ơ n g đ ư ơ n g logic, suy ra rằng hai h à m Bun
nhất v ớ i hai công thức t ư ơ n g đưirng : logic đ ư ọ c
d i ễ n hỏi cung m ộ t công thức dạng chuần tắc t u y ề n
hoàn loàn.

1.5. Hệ quả logic
1.5.1. a) Định nghía. Già sử A và B là hai
Ta nói công thức B là hệ quả logic của công
hiệu là A ỗ = B, nếu và chỉ nếu v ớ i m ọ i d ã y
các biến mệnh đ ề có mặt trong A và B, m ỗ i
của À bằng Ì thì giả {rị của B cũng b ằ n g 1.

công Ihức.

thức A , k í
giả t r ị của
k h i giá t r ị

T ừ đ ị n h nghĩa suy ra ngay rằng nếu B là hệ quả logic
của A thì l ậ p h ọ p các dãy giá trị của các biển m ệ n h
đ ề l à m cho giá trị của A bằng Ì b ị chửa trong tập hợp
các giá trị của các biến mệnh đ ề làm cho giá t r ị của B
bằng 1.
Thí dụ : p =• q là hệ quả logic của
bằng Ì thì ỗ) => q cũng bằng 1.

q, vì m ỗ i k h i q

G i ả sử A = ( A i , A 2 , A m ) là một d ã y h ữ u h ạ n
những công thức. Ta nói r ằ n g cócg thức B i a hệ quả
logic cùa dãy A, k i h i ệ u là A 1 = B, n ế u v à chỉ nếu B l à
h ệ quả logic của công (hức A i A A2 A .. A Am.
1.5.2. Các tỉnh chất.
à) Giả sử A và B là hai công
lâu và chì nếu 1 = (A 1 = B).

thức.

Khi đồ A 1 =

B

(=»•) G i ả sử A ] = B . Theo định nghĩa, v ớ i m ọ i d ã y
g i ả l r j e của cấc biến mệnh đ ề , m ỗ i k h i A j e = Ì t h i

38


BỊe a= 1 . N h ư vậy, M o theo A =* B nhận gù', trị Ì trên m ọ i
d ã y giá t r ị e. Do đ ó 1 = (A =» B ) .
(«=•> Đảo l ạ i . giả sử 1 = ( A =* B). Nếu B không phải là
hè quả logic của A thì tồn tại ít nhất một dãy giá trị e
của các b i ế n mệnh đ ề chửa trong A v à B sao
cho
AỊe 3= Ì và B | e = 0.
Khi đ ỏ theo đỉnh nghĩa của giá Irị của m ộ i công thức,
ta có ( A =» B ) | e — 0. Do đ ó A =* B không ị hải là một
công thức hằng đ ú n g .
•
b) Mọi công thức đêa
thức hằng sai.
— Mọi công thức
một công thức bát

là hệ quả logic

hăng
kì.

cùa

một

đúng đều lồ hệ quả logic

công
của

Ta k i h i ệ u m ộ t công Ihức hằng sai là s và một công
thức hằng đ ú n g là Đ. Ta phải chửng minh rằng nếu Alà
một công thức bất kì thì s 1 = A và A Ị = Đ.
T h ậ t vậy vì 1 = (S =» A ) và 1 = ( A ri. Đ) theo đỉnh nghĩa
của p h é p =», nén theo tính chất a, ỉa có S | = A
và
A 1= Đ. •
c) Giả sử A — ( A Á ,...,
A)
lá một dãy hữu
hợn
những
công thức. Khi đỏ, mọi cồng Ihức trong Á đều
là hệ quá logic của A .
u

2

m

Theo tinh chai a), ta sẽ chửng minh rằng

1=

Ai

A Ả2 A ... A A

m

=* A i

( i = Ì, 2 , . ., m )

Gỉả sử e là m ộ t dãy b ấ t kì nhờng giả trị của tóc biển
mệnh đ ề có m ã i trong các cóng thức của d â y A. Theo
đ ị n h nghĩa (ủa p h é p kéo theo ta chỉ cần XAi|e = 0. N ế u Ai'e = 0 t h i hiền nhiên ( A i A A ỉ A ...Ai ...
A ) | e = 0, v ì vậy giá trị của cong thức ( A i , A Â 2 A ...
A Am) ==* A i trên dãy e bằng 1. Do đ ó công thức ( A i A
A A ... A A ) =» A i là hằng đúng.
•
m

2

m

19


d) Nến A I = . 4 thi với mọi cõng thức B, ta có A | =
(B => A), tức là nhi A là hệ quả lo'jic của A / A i B =* .1
là hệ quả logic cũn A, vời mọi cônq thức
B.
Ta gọi l ậ p hợp
dãy giũ trị e của các biến mệnh (tồ

có mặt trong một công thức làm cho công thức đ ó nhím
giũ trị Ì là miền đúng của còng thức đ ó .
Theo g i ả thiết A 1 = A , vạy miền đúng của còng thức A b ị
chửa trong micii đúng của công thức A.. N h ư n g v ử i m ỗ i
d ẫ y giá trị e, nếu A''e = Ì t h ì (B => A)|e = 1 , tức là m i ề n
đ ú n g của công thức A bị chứa trong m i ề n đ ú n g của công
thức B => A. Do đ ó m i ề n đủng của còng thức A bị c h ú a
trong m i ề n đúng của còng thức B => A. Vì v ậ y A Ị =
(B=> A ) . •

Ả

Các tựnh chất e), f ) , g) dirời đây được chứng m i n h
l ư ơ n g t ự n h ư các tính chất trôn.
e) Nếu A \=A
ihì A, B \— Ả, tức là nhi A là hệ quả
logic của A thì Ả cũng là hệ quả logic của mọi tập
hợp
công thức chứa A.
f ) Xỉu
y)

A | = .4 và

N ế u ủ , .4

1=

A

1=

1=
A1=

li thì A

h) Nếu A, A\=B
T h ậ t vậy. do g)
A|=B.
•
í) Nếu

A|== (.4

thì A\ =

B.

(A => B).

và
.4 thì A 1 = li.
ta có A 1 = (A => l ĩ ) , t ừ

(A =» fì) thì

A, A\=

đo

do

f)

B.

T h ậ t vậy v i A | = ( A => B) nên theo e) ta có A, A Ị =
( A => B ) . Theo c) ta cỏ A, A 1 = A . V i A, A. 1 = A . và A , A
1 = 3 (A 4 B) nên theo f ) la có A, A 1 = B .
k ) Nếu .4i, A2,.... Ầm \=A
thì cônj thức Ai ^(Ầ2 =>
(...
(.4 _! => (A =* ^1)) ...)) là hằng
đúng.
Đế chứng m i n h , ta á p dạng nhiều l ầ n tựnh chắt g ) .
m

ẳQ

m

-í

„


/ ) Nếu công thức hằng sai s là hệ quả logic cùa các
công thức Ai, A ,
An, ~1 B thì cổng ihửc B là hệ

quả logic cùa các công thức Ai, A ,
...,Ả .
2

2

D

T h ậ t vậy, theo giả t h i ế t ta có Ai, A , . . . An, ì B 1 = s,
do đ ó theo tính chất g) : A i , A , A n 1 = ( H B =» S ) . Già
sử e là một d ã y giũ trị của các biến mệnh đ ề chứa trong
các công thức trên sao cho ( A i A A2 A ... Ả An)Ị = 1.
K h i đ ó vì A i , A
An 1 = ( - | ú =>S) nen (1B=>S)|e = 1.
T ừ đ ỏ suy ra ~1 H|e = í), do đ ó B|e = 1. Nhu- vậy miÊn
đúng của A i A A ỉ \ .... A An bị chứa trong m u n đ ú n g
của công thức B . Do đ ó theo định nghĩa, ta có A i ,
2

2

2

A ,..
2

1=

An

B.

•

1.6- L ư ơ e đồ chứng

minh

1.(5.1. Xét một dãy h ữ u hạn cổng thức, m ỗ i cóng
hoặc l à hằng đúng, hoặc đước suy ra từ các công
đ ú n g t r ư ó c nhờ n h ù n g quy tác nhất đ ị n h . Ta n ó i
công thức đ ó là íược đỏ chứncỊ minh của cồnP thức
cùng trong dãy đ ã cho.

thức
thúc
dãy
cuối

1.6.2. D ư ớ i đây là một số quy tắc thường d ù n g . Thay
cho Ci.ch viế t A 1 = lì. ta ghi l i ề n đe A trên dấu gạch
ngang và k ế t luận B đ u ô i d ấ u đ ỏ d ư ó i dạng
a)

A =» B, A

^

k£t

^

n

— .

grá 1^

môđun

B

ponenơ
b)

c)

(đọc là : liế n cò A =» B và có A t h ì có B).
, ỳ" ^ — quy tắc đ ư a h ỏ i vào
(A A B )
'
H

Ạ AB

Ạ ẠB

A ~ '

li

B

A

ủ)

AýB

quỵ t.'.c tách h ộ i

'

quy tắc đ ư a tuy?!! v à o

AyB
21


e) — L _ _ ^
A.

quy tắc tách tuyên

À

-

f)

quy lắc đưa phủ đinh vào

T I A
n ì A.
g) ——-— quy tác bỏ phủ đỉnh
A
. . A^B,B=»A
.
li)
•
quy tác đưa tương đương vào
A 44 B
A =>• B
, í
»o
i) —--—•
quy lac phan đao
- | B => n A
,
~~! A => B, 1A=> I B
_
,ị
. ,
k)
—•
quy tác phan chứng
A
ì)
quy tác bác câu
A. =>• Cí
• V

1 9

s

—

m

)

À => V.B

'
.
.
'
V

p)

ì)

t

£

c

(ẢAB)=»C

A => (B => l i )
B =>• (A => C)
(A A B) => L
A=»(B=*C)
A => c, B => c

,

I ẻ

6

t

kig

18
Ịkiế*

v
!

^

c

t

k

t

H

B

Ikiết
8

. 1

.

*

.9

. V . V .

quy tác tuyên gia thiết

A V tí =» c
Mỗi quy tắc trên ứng với một kéo theo hằng đúng
của đại số mệnh đề.
1.6.3. Sau đây là vài thí dụ về phép chủng minh các
công thức hằng đúng. Đề xét xem một công thức là hằng
đúng hay khùng, ta có thề lờp bảng giá trị chân lí của
của nó. Tuy nhiên cách làm này không phải bao giờ cũng
dễ dàng, nhất là khi số biến mệnh đề là khá lớn.
22

Đe chứng m i n h một còng thức là hằng đúng ta cũng cỗ
thề dựa vào định nghĩa và các tinh chất của k h ả i n i ệ m
hệ quả logic. Ta hãy xét mấy thí d ụ sau :
Thỉ dụ í : Chứng minh răng công {hức p => (q => Ị)) là
hằng
đúng.
Ta sẽ chửng minh rằng p j = (q =* p ) . Thật vậy, la có
p 1= p (theo tính chất c). Do đỏ p 1= (q =» p) (theo tính
chất (ỉ). Vậy (theo tính chất a) 1= (p => (q =» p)).
•
Thí du 2. Chứng minh \=(p =* (q =• r ) ) =* ({p =» q) =>
(p => /•)). Đặt A = ( p =» (q => r ) , p =»• q, p ) . Nếu ta chứng
minh đưực A ể— r, thì á p dụng tính chất g ĩìhiĩu làn ta
sẽ suy ra đ i ề u phải chúng minh.
Ta
theo
chất
À 1=

có A I — p và A 1= (p => q) (theo tính chất c). T ừ đ o ,
tính chất f, A 1= q. Vì A 1= (p =* (q => r ) ) theo tính
c, và A 1 = p, nén theo t ỉ n h chất f, A [ = (q => r ) . Vì
q và A 1= (q => r ) nên l ạ i theo tính chất f, à 1 = r.£2

Thí dự 3. Tìm lược đồ chứng
ị=(A-*A).

minh của luật đồng

nhất

Ta vừa chứng minh
1= p - (q - p) ( t h i dụ 1)

(1)

l=(p=>(q-r))=*((p=>q)-(p

=* r))

( t h i dụ 2)

(2\

Theo tinh chất c của p h í p t h ể , khi ta thay trong (1) va
(2) p b ả i A, q h ỏ i B => A và r bởi A, thì ta được

I—

A =• ((B =* A) =* A )

(3)

1= (A => ((B => A ) => A ) ) =* ( ( A => ( B => A ) ) =>
- ( A - A))

(4)

Á p dụng quy tắc két luận cho (3) và (4), ta được
|=(A=KB=>A))=»(A=>A)

(5)
23


Thay trong (1) p b ờ i A và q b ở i B, ta đ ư ọ c
|=A"»(B=*A)
Á p dụng quy

tắc k ế t luận cho (5) và ( 6 ) , ta đ ư ọ c
/ = A => A .

1.7. Áp
t o á n học1.7.1.
chứng).

,6)

dụng các l u ậ t logic

Phương

pháp

chứng

•

vào

minh

p h é p chứng

gián

ỉiếp

(bẵng

minh
phản

G i ả sử p h ả i chứng minh một mệnh đ ề
p nào đó là
đ ủ n g . Ta g i ả t h i ế t n g ư ẹ r l ạ i rằng -|p ià đúng. Sau đo t a
chứng m i n h rằng tòn l ạ i một mệnh đ ề q vừa đ ú n g vừa
sai, tức là ta chứng minh đ ư ọ c rằng các mệnh đ ề Hp
q
và Hp => ~~iq đ ì u đúng. K h i đó ta k ế t luận đ ư ọ c rằng p
là đ ú n g .
Cơ sở của

lập

luận này

là công thức hằng đ ú n g sau: ị

1= ( Hp => q) A ( Hp => n q) => p

J

Trong t r ư ờ n g họp tông quát, g i ả sử phải chúng m i n h
r ằ n g B là hệ quả logic của các tiên đ ề A i , A , . . . , Am. Ta
g i ả t h i ế t H B là đímg và chứng n i i r h rằng tữn t ạ i m ộ t
công thức c sao cho c A n e (công thúc hằng sai) là h ệ
q u ả logic của cúc công thức A i , A2,
A , ~1B. Dựa vào
t í n h c l ' ấ t k) của h ệ quả logic, ta k ế t luận rằng B là hệ
q u ả logic của các cóng thức A i , A2,
Am.
2

m

1.7.2.
trường

Phương
hợp.

pháp

chứng

minh

tuyền

bâng

các

Giả. sử p h ả i chứng m i n h một mệnh đ ề p nào đó là đ ú n g .
Ta t ì m hai mệnh đề (Ji và q2 (thông thường là qi và
Iq-í),
và chứng m i n h rằng qi =* p, q => p, q i V q
là những
m ệ n h đữ đ ú n g . Khi đ ó ta kết luận được rằng mệnh đữ p
lạ đúng.
2

24

2


Cơ sở của

lập luận này là công thức hằng đ ú n g sau5

1= ( q i

=>

p) A (q2 => p) => ( ( q i V q«) =» p)

í.7.3. Phương pháp chứng minh bằng một chuỗi phép
kéo theo.
Giả sử p h ả i chửng m i n h mệnh đề p =• q là đ ú n g . Ta
dựng k mệnh đ e m ó i (k > 1) : p i , p ,
Pk gọi là Ci'c
mệnh đe trung gian, v à chúng minh rằng ir.ỗi mệnh đề
p =*• pi> pi =* P2'
Pk => q lá đúng. Khi đ ỏ t a k ế t luận được
rằng m ê n h đề p =>q là đ ú n g .
2

Cơ sở của lập luận này là luật bắc cầu
1= (p =* q) A (q =*. r) => (p => r )
Ngoài các p h ư ơ n g p h á p chửng minh t r ê n , còn nhiều
p h ư ơ n g p h á p chứng minh khác. Song v i c h ú n g ít thòng
dụng hon, nên ta không đ ề rập đạn.

§2.

LOGIC

VỊ

Từ

B ạ i sạ mệnh đè lá bộ phận cư bản v à sơ cấp nhất
của logic toán. Các phượng tiên của nỏ là ríu cần t h i ế t
n h ư n g chưa đ ủ dề phân tích nhiêu suy luận loàn học.
Chẳng hạn, chỉ trong khuôn k h ạ của d ạ i sạ mệnh đ ề thì
không thế thiết l ậ p được tính đúng đản của suy luận sau:

M ọ i sạ h ữ u tỉ đ ề u là sạ thực, 3/5 là một sạ h ữ u tỉ, v ậ y
3/5 là một hạ thực.
Nguyên nhân của tình hình này là các mệnh de đ ơ n
giản đưọ c xem là không pliíin tích được, vá chúng không
cỏ lính chất nào khúc lính chát « đ ú n g i ) hoặc « s a i » .
-

V i v ậ y cần thiííl phải xây dựng một hệ thạng logic sao
cho bằng các p h ư ơ n g tiện của no, có thê n g h i ê n cứu được
cấu t r ú c của các mệnh đờ. H ệ thạng logic này g ọ i là logic
vị từ.

25