Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Giáo trình cơ sở toán học
Nội dung xem thử
Mô tả chi tiết
Bé gi¸o dôc vµ ®µo t¹o
®¹i häc huÕ
tr−êng ®¹i häc khoa häc
nguyÔn gia ®Þnh
gi¸o tr×nh
C¥ Së TO¸N HäC
{a}
{a,b,c}
{a,b}
∅
{b} {c}
{a,c} {b,c}
huÕ − 2005
LO`.
I NOI D ´ - `
AˆU
Nh˜u.
ng ngu.
`o.
i m´o.
i b˘a´t d¯ˆa`u nghiˆen c´u.
u to´an ho.c thu.
`o.
ng ca’m thˆa´y kh´o xˆay
du.
. ng th´oi quen ph´at biˆe’u mˆo.t c´ach ch˘a.t ch˜e nh˜u.
ng ´y kiˆe´n muˆo´n tr`ınh b`ay, kh´o
ho.c tˆa.p c´ac phu.
o
.
ng ph´ap lˆa.p luˆa.n d¯´ung d¯˘a´n v`a kh´o n˘a´m d¯u.
o
.
. c c´ac kh´ai niˆe.m co.
ba’n cu’a to´an ho.c. Nh˜u.
ng kh´o kh˘an n`ay du.
`o.
ng nhu. b˘a´t nguˆo`n t`u. chˆo˜: mˆo.t l`a
khˆong d¯u.
o.
. c luyˆe.n tˆa.p vˆe` lˆogic to´an, mˆo.t chu’ d¯ˆe` nghiˆen c´u.
u c´ach lˆa.p luˆa.n suy
diˆe˜n ´ap du. ng v`ao viˆe.c ch´u.
ng minh c´ac d¯i.nh l´y to´an ho.c; hai l`a do thiˆe´u c´ac kh´ai
niˆe.m co. ba’n v`a c´ac phu.
o
.
ng ph´ap d`ung trong l´y thuyˆe´t tˆa.p ho.
. p m`a ng`ay nay
thu.
`o.
ng d¯u.
o.
. c ´ap du. ng trong mo.i ng`anh to´an ho.c v`a d`ung l`am co. so.
’ d¯ˆe’ khai ph´a
v`a gia’i th´ıch c´ac kh´ai niˆe.m co. ba’n cu’a to´an ho.c (nhu. ´anh xa., quan hˆe., ...); ba
l`a do khˆong n˘a´m d¯u.
o.
. c nh˜u.
ng kh´ai niˆe.m co. ba’n cu’a d¯a.i sˆo´ tr`u.
u tu.
o.
. ng, mˆo.t chu’
d¯ˆe` d¯ang ph´at triˆe’n ma.nh m˜e v`a c´o a’nh hu.
o
.
’ ng d¯ˆe´n mo.i ng`anh to´an ho.c kh´ac, cu.
thˆe’ qua c´ac cˆa´u tr´uc d¯a.i sˆo´ cu’a c´ac tˆa.p ho.
. p sˆo´ quen thuˆo.c (nhu. tˆa.p c´ac sˆo´ tu.
. nhiˆen, tˆa.p c´ac sˆo´ nguyˆen, tˆa.p c´ac sˆo´ h˜u.
u tı’, tˆa.p c´ac sˆo´ thu.
. c v`a tˆa.p c´ac sˆo´ ph´u.
c).
D- u.
o
.
. c su.
. d¯ˆo.ng viˆen ma.nh m˜e cu’a c´ac d¯ˆo`ng nghiˆe.p trong c´ac Khoa To´anCo.
-Tin ho.c, Cˆong nghˆe. Thˆong tin v`a Vˆa.t l´y (Tru.
`o
.
ng D- a.i ho.c Khoa ho.c-D- a.i ho.c
Huˆe´), c´ac Khoa To´an v`a Tin ho.c (Tru.
`o.
ng D- a.i ho.c Su. pha.m-D- a.i ho.c Huˆe´) v`a
d¯˘a.c biˆe.t do nhu cˆa`u ho.c tˆa.p cu’a c´ac sinh viˆen trong D- a.i ho.c Huˆe´ o.
’ c´ac Khoa
n´oi trˆen, ch´ung tˆoi ma.nh da.n viˆe´t gi´ao tr`ınh Co. so.
’ To´an ho.c, trong khi trˆen thi.
tru.
`o
.
ng s´ach c´o kh´a nhiˆe`u t`ai liˆe.u liˆen quan d¯ˆe´n ho.c phˆa`n n`ay (nhu.
ng d¯u.
o
.
. c tr`ınh
b`ay ta’n ma.n v`a r`o.
i ra.c). D- iˆe`u m`a ch´ung tˆoi mong muˆo´n l`a c´ac kiˆe´n th´u.
c cu’a
ho.c phˆa`n n`ay pha’i d¯u.
o.
. c d¯u.
a v`ao d¯ˆa`y d¯u’, cˆo d¯o.ng, ch´ınh x´ac, cˆa.p nhˆa.t v`a b´am
s´at theo yˆeu cˆa`u d¯`ao ta.o sinh viˆen c´ac ng`anh To´an, Vˆa.t l´y, Cˆong nghˆe. Thˆong tin
v`a mˆo.t sˆo´ ng`anh k˜y thuˆa.t kh´ac cu’a c´ac tru.
`o
.
ng d¯a.i ho.c v`a cao d¯˘a’ ng. V´o.
i su.
. nˆo’
lu.
. c hˆe´t m`ınh cu’a ba’n thˆan, ch´ung tˆoi thiˆe´t ngh˜ı d¯ˆay c`on l`a t`ai liˆe.u tham kha’o
tˆo´t cho c´ac gi´ao viˆen gia’ng da.y ho.c phˆa`n Nhˆa.p mˆon D- a.i sˆo´ hay Co. so.
’ To´an ho.c
Nˆo.i dung cu’a t`ai liˆe.u n`ay d¯u.
o
.
. c bˆo´ tr´ı trong 6 chu.
o
.
ng. Trong c´ac phˆa`n cu’a
mˆo˜i chu.
o.
ng c´o nhiˆe`u th´ı du. cu. thˆe’ minh hoa. cho nh˜u.
ng kh´ai niˆe.m c˜ung nhu.
nh˜u.
ng kˆe´t qua’ cu’a ch´ung. Cuˆo´i cu’a mˆo˜i chu.
o.
ng l`a nh˜u.
ng b`ai tˆa.p d¯u.
o.
. c cho.n lo.c
t`u. dˆe˜ d¯ˆe´n kh´o b´am theo nˆo.i dung cu’a chu.
o.
ng d¯´o v`a liˆe`n sau d¯´o l`a c´ac l`o.
i gia’i
cu’a ch´ung. D- ´o l`a c´ac chu.
o.
ng vˆe` Lˆogic to´an v`a tˆa.p ho.
. p, Anh xa ´ ., Quan hˆe., Sˆo´ tu.
.
nhiˆen v`a sˆo´ nguyˆen, Sˆo´ h˜u.
u tı’, sˆo´ thu.
. c v`a sˆo´ ph´u.
c, D- a th´u.
c.
Ch´ung tˆoi xin chˆan th`anh c´am o.
n c´ac d¯ˆo`ng nghiˆe.p d¯˜a d¯ˆo.ng viˆen v`a g´op ´y
cho cˆong viˆe.c viˆe´t gi´ao tr`ınh Co. so.
’ To´an ho.c n`ay v`a l`o.
i c´am o.
n d¯˘a.c biˆe.t xin
d`anh cho Khoa To´an-Co.
-Tin ho.c (Tru.
`o
.
ng D- a.i ho.c Khoa ho.c-D- a.i ho.c Huˆe´) vˆe` su.
. gi´up d¯˜o. qu´y b´au v`a ta.o d¯iˆe`u kiˆe.n thuˆa.n lo.
. i cho viˆe.c xuˆa´t ba’n gi´ao tr`ınh n`ay.
Typeset by AMS-TEX
T´ac gia’ mong nhˆa.n d¯u.
o.
. c su.
. chı’ gi´ao cu’a c´ac d¯ˆo`ng nghiˆe.p v`a d¯ˆo.c gia’ vˆe`
nh˜u.
ng thiˆe´u s´ot kh´o tr´anh kho’i cu’a cuˆo´n s´ach.
Cˆo´ D- ˆo Huˆe´, Aˆ´t Dˆa.u Tro.ng D- ˆong (2005)
Nguyˆe˜n Gia D- i
.nh
2
CHU.
O.
NG I:
LOGIC TO ˆ AN V ´ A T ` Aˆ
. P HO.
. P
1.1. LOGIC TO ˆ AN. ´
1.1.1. Mˆe.nh d¯ˆe` v`a c´ac ph´ep to´an lˆogic:
1.1.1.1. Mˆe.nh d¯ˆe` : Mˆe.nh d¯ˆe` l`a mˆo.t cˆau pha’n ´anh mˆo.t d¯iˆe`u d¯´ung ho˘a.c sai, ch´u.
khˆong pha’i v`u.
a d¯´ung v`u.
a sai.
Th´ı du. :
1) Sˆo´ 35 chia hˆe´t cho 5: mˆe.nh d¯ˆe` d¯´ung.
2) M˘a.t tr`o.
i quay quanh tr´ai d¯ˆa´t: mˆe.nh d¯ˆe` sai.
3) Tam gi´ac ABC c´o 3 g´oc vuˆong: mˆe.nh d¯ˆe` sai.
4) 2 < 5: mˆe.nh d¯ˆe` d¯´ung.
C´ac cˆau ho’i, cˆau ca’m th´an, cˆau mˆe.nh lˆe.nh, ... v`a n´oi chung c´ac cˆau khˆong
nh˘a`m pha’n ´anh t´ınh d¯´ung sai cu’a thu.
. c tˆe´ kh´ach quan d¯ˆe`u khˆong d¯u.
o
.
. c coi l`a
mˆe.nh d¯ˆe` .
Trong lˆogic mˆe.nh d¯ˆe` , ta khˆong quan tˆam d¯ˆe´n cˆa´u tr´uc ng˜u. ph´ap c˜ung nhu.
y ngh˜ıa nˆo ´ .i dung cu’a mˆe.nh d¯ˆe` m`a chı’ quan tˆam d¯ˆe´n t´ınh d¯´ung sai cu’a mˆo˜i mˆe.nh
d¯ˆe` .
D- ˆe’ chı’ c´ac mˆe.nh d¯ˆe` chu.
a x´ac d¯i.nh, ta d`ung c´ac ch˜u. c´ai: p, q, r, ... v`a go.i
ch´ung l`a c´ac biˆe´n mˆe.nh d¯ˆe` . Ta quy u.
´o.
c viˆe´t p = 1 khi p l`a mˆe.nh d¯ˆe` d¯´ung v`a
p = 0 khi p l`a mˆe.nh d¯ˆe` sai. C´ac gi´a tri. 0 v`a 1 go.i l`a c´ac gi´a tri. chˆan l´y cu’a c´ac
mˆe.nh d¯ˆe` .
George Boole d¯˜a nghiˆen c´u.
u phu.
o.
ng ph´ap ta.o ra c´ac mˆe.nh d¯ˆe` m´o.
i b˘a`ng
c´ach tˆo’ ho.
. p t`u. mˆo.t ho˘a.c nhiˆe`u mˆe.nh d¯ˆe` d¯˜a c´o. C´ac mˆe.nh d¯ˆe` m´o.
i d¯u.
o.
. c go.i l`a
c´ac mˆe.nh d¯ˆe` ph´u.
c ho.
. p, ch´ung d¯u.
o.
. c ta.o ra t`u. c´ac mˆe.nh d¯ˆe` hiˆe.n c´o b˘a`ng c´ach
d`ung c´ac ph´ep to´an lˆogic.
1.1.1.2. Ph´ep phu’ d¯i.nh: Phu’ d¯i.nh cu’a mˆe.nh d¯ˆe` p , k´y hiˆe.u l`a p, d¯o.c l`a “khˆong
p”, l`a mˆe.nh d¯ˆe` sai khi p d¯´ung v`a d¯´ung khi p sai.
Ph´ep phu’ d¯i.nh trong lˆogic mˆe.nh d¯ˆe` ph`u ho.
. p v´o.
i ph´ep phu’ d¯i.nh trong ngˆon
ng˜u. thˆong thu.
`o.
ng, ngh˜ıa l`a ph`u ho.
. p v´o.
i ´y ngh˜ıa cu’a t`u. “khˆong” (“khˆong pha’i”).
Th´ı du. : 1) p: “9 l`a mˆo.t sˆo´ le’” (D- ), p: “9 khˆong l`a mˆo.t sˆo´ le’” (S).
2) p: “v´o.
i mo.i sˆo´ thu.
. c x, y, (x + y)2 < 0” (S), p: “tˆo`n ta.i sˆo´ thu.
. c
x, y, (x + y)2 ≥ 0” (D- ).
1.1.1.3. Ph´ep hˆo.i: Hˆo.i cu’a hai mˆe.nh d¯ˆe` p, q, k´y hiˆe.u l`a p ∧ q, d¯o.c l`a “p v`a q”,
l`a mˆo.t mˆe.nh d¯ˆe` d¯´ung khi ca’ p lˆa˜n q c`ung d¯´ung v`a sai trong c´ac tru.
`o.
ng ho.
. p c`on
la.i.
Ph´ep hˆo.i ph`u ho.
. p v´o.
i ´y ngh˜ıa cu’a liˆen t`u. “v`a” cu’a ngˆon ng˜u. thˆong thu.
`o
.
ng.
Th´ı du. : 1) p: “2 l`a sˆo´ nguyˆen tˆo´” (D- ) v`a q: “2 l`a sˆo´ ch˜an” (D- ) th`ı p ∧ q: “2 l`a
sˆo´ nguyˆen tˆo´ v`a l`a ch˘a˜n” (D- ).
3
2) Mˆe.nh d¯ˆe` “Sˆo´ π l´o.
n 3 v`a l`a mˆo.t sˆo´ h˜u.
u tı’” (S) l`a hˆo.i cu’a hai mˆe.nh d¯ˆe`
“Sˆo´ π l´o.
n ho.
n 3” (D- ) v`a “Sˆo´ π l`a mˆo.t sˆo´ h˜u.
u tı’” (S).
1.1.1.4. Ph´ep tuyˆe
’
n: Tuyˆe’n cu’a hai mˆe.nh d¯ˆe` p, q, k´y hiˆe.u p ∨ q, d¯o.c l`a “p
ho˘a.c q”, l`a mˆo.t mˆe.nh d¯ˆe` sai khi ca’ p lˆa˜n q d¯ˆe`u sai v`a d¯´ung trong mo.i tru.
`o
.
ng
ho.
. p c`on la.i.
Ph´ep tuyˆe’n ´u.
ng v´o.
i liˆen t`u. “ho˘a.c” trong ngˆon ng˜u. thˆong thu.
`o.
ng theo ngh˜ıa
khˆong loa.i tr`u.
, c´o ngh˜ıa l`a mˆe.nh d¯ˆe` “p ho˘a.c q” d¯´ung khi v`a chı’ khi ´ıt nhˆa´t mˆo.t
trong hai mˆe.nh d¯ˆe` p v`a q d¯´ung.
Th´ı du. : 1) p: “3 nho’ ho.
n 5” (D- ) v`a q: “3 b˘a`ng 5” (S) th`ı p ∨ q: “3 nho’ ho.
n
ho˘a.c b˘a`ng 5” (D- ).
2) p: “Paris l`a thu’ d¯ˆo nu.
´o.
c Anh” (S) v`a q: “6 l´o.
n ho.
n 8” (S) th`ı p ∨ q:
“Paris l`a thu’ d¯ˆo nu.
´o
.
c Anh ho˘a.c 6 l´o.
n ho.
n 8” (S).
1.1.1.5. Ph´ep tuyˆe
’n loa.i: Tuyˆe’n loa.i cu’a hai mˆe.nh d¯ˆe` p, q, k´y hiˆe.u p ⊕ q, d¯o.c
l`a “p ho˘a.c q (nhu.
ng khˆong ca’ hai)”, l`a mˆo.t mˆe.nh d¯ˆe` d¯´ung khi chı’ c´o mˆo.t trong
hai mˆe.nh d¯ˆe` p v`a q l`a d¯´ung v`a sai trong mo.i tru.
`o.
ng ho.
. p c`on la.i.
Ph´ep tuyˆe’n loa.i ´u.
ng v´o.
i liˆen t`u. “ho˘a.c” trong ngˆon ng˜u. thˆong thu.
`o.
ng theo
ngh˜ıa loa.i tr`u.
.
Th´ı du. : p: “√
2 l`a mˆo.t sˆo´ h˜u.
u tı’” (S) v`a q: “√
2 l`a mˆo.t sˆo´ vˆo tı’” (D- ) th`ı p ⊕ q:
“
√2 l`a mˆo.t sˆo´ h˜u.
u tı’ ho˘a.c l`a mˆo.t sˆo´ vˆo tı’” (D- ).
1.1.1.6. Ph´ep k´eo theo: Mˆe.nh d¯ˆe` k´eo theo p ⇒ q, d¯o.c l`a “p k´eo theo q” hay
”nˆe´u p th`ı q”, l`a mˆo.t mˆe.nh d¯ˆe` sai khi p d¯´ung v`a q sai v`a d¯´ung trong c´ac tru.
`o.
ng
ho.
. p c`on la.i.
Trong ph´ep k´eo theo n´oi trˆen, p d¯u.
o.
. c go.i l`a gia’ thiˆe´t, c`on q d¯u.
o.
. c go.i l`a kˆe´t
luˆa.n.
V`ı ph´ep k´eo theo xuˆa´t hiˆe.n o.
’ nhiˆe`u no.
i trong c´ac suy luˆa.n to´an ho.c, nˆen c´o
nhiˆe`u thuˆa.t ng˜u. d¯u.
o.
. c d`ung d¯ˆe’ diˆe˜n d¯a.t mˆe.nh d¯ˆe` p ⇒ q. Du.
´o.
i d¯ˆay l`a mˆo.t sˆo´ th´ı
du. thu.
`o.
ng g˘a.p nhˆa´t.
– “Nˆe´u p th`ı q”,
– “p k´eo theo q”,
– “T`u. p suy ra q”,
– “p l`a d¯iˆe`u kiˆe.n d¯u’ d¯ˆe’ c´o q”,
– “q l`a d¯iˆe`u kiˆe.n cˆa`n d¯ˆe’ c´o p”.
Th´ı du. : 1) “Nˆe´u hˆom nay tr`o.
i n˘a´ng, ch´ung tˆoi s˜e d¯i ra b˜ai biˆe’n” l`a mˆo.t mˆe.nh
d¯ˆe` k´eo theo v`a d¯u.
o.
. c xem l`a d¯´ung tr`u. phi hˆom nay tr`o.
i thu.
. c su.
. n˘a´ng, nhu.
ng
ch´ung tˆoi khˆong d¯i ra b˜ai biˆe’n.
2) “Nˆe´u hˆom nay l`a th´u. hai th`ı 3 + 5 = 7” l`a mˆo.t mˆe.nh d¯ˆe` k´eo theo v`a l`a
d¯´ung v´o.
i mo.i ng`ay tr`u. th´u. hai.
Trong suy luˆa.n to´an ho.c, ch´ung ta x´et c´ac ph´ep k´eo theo thuˆo.c loa.i tˆo’ng
qu´at ho.
n trong ngˆon ng˜u. thˆong thu.
`o.
ng. Kh´ai niˆe.m to´an ho.c vˆe` ph´ep k´eo theo
d¯ˆo.c lˆa.p v´o.
i mˆo´i quan hˆe. nhˆan - qua’ gi˜u.
a gia’ thiˆe´t v`a kˆe´t luˆa.n.
4
Khˆong may, cˆa´u tr´uc nˆe´u - th`ı d¯u.
o.
. c d`ung trong nhiˆe`u ngˆon ng˜u. lˆa.p tr`ınh
la.i kh´ac v´o.
i cˆa´u tr´uc d¯u.
o
.
. c d`ung trong lˆogic to´an. D- a sˆo´ c´ac ngˆon ng˜u. lˆa.p tr`ınh
ch´u.
a nh˜u.
ng cˆau lˆe.nh nhu. nˆe´u p th`ı S (if p then S), trong d¯´o p l`a mˆo.t mˆe.nh d¯ˆe`
c`on S l`a mˆo.t d¯oa.n chu.
o.
ng tr`ınh (gˆo`m mˆo.t ho˘a.c nhiˆe`u lˆe.nh cˆa`n pha’i thu.
. c hiˆe.n).
Khi thu.
. c hiˆe.n mˆo.t chu.
o.
ng tr`ınh g˘a.p nh˜u.
ng cˆa´u tr´uc nhu. vˆa.y, S s˜e d¯u.
o.
. c thu.
. c
hiˆe.n nˆe´u p l`a d¯´ung, trong khi d¯´o S s˜e khˆong d¯u.
o
.
. c thu.
. c hiˆe.n nˆe´u p l`a sai.
1.1.1.7. Ph´ep tu.
o.
ng d¯u.
o.
ng: Mˆe.nh d¯ˆe` “p tu.
o.
ng d¯u.
o.
ng q”, k´y hiˆe.u l`a p ⇔ q,
l`a mˆo.t mˆe.nh d¯ˆe` d¯´ung khi p v`a q c´o c`ung gi´a tri. chˆan l´y v`a sai trong c´ac tru.
`o
.
ng
ho.
. p c`on la.i.
D- i
.nh ngh˜ıa cu’a ph´ep tu.
o.
ng d¯u.
o.
ng ph`u ho.
. p v´o.
i ´y ngh˜ıa cu’a cu. m t`u. “khi
v`a chı’ khi” hay “nˆe´u v`a chı’ nˆe´u” cu’a ngˆon ng˜u. thˆong thu.
`o.
ng. Trong to´an ho.c,
mˆe.nh d¯ˆe` “p tu.
o
.
ng d¯u.
o
.
ng q” c´o thˆe’ diˆe˜n d¯a.t du.
´o
.
i da.ng: “d¯iˆe`u kiˆe.n cˆa`n v`a d¯u’
d¯ˆe’ c´o p l`a c´o q”.
Th´ı du.: 1) D- iˆe`u kiˆe.n cˆa`n v`a d¯u’ d¯ˆe’ 4ABC cˆan l`a hai g´oc o.
’ d¯´ay cu’a n´o b˘a`ng
nhau.
2) Dˆa´u b˘a`ng xa’y ra trong bˆa´t d¯˘a’ ng th´u.
c Cauchy
√
n a1a2 ...an ≤
a1 + a2 + ··· + an
n
khi v`a chı’ khi a1 = a2 = ··· = an.
Sau d¯ˆay l`a ba’ng chˆan tri. cu’a c´ac ph´ep to´an lˆogic n´oi trˆen.
p q p p ∧ q p ∨ q p ⊕ q p ⇒ q p ⇔ q
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
1 1 0 1 1 0 1 1
1.1.1.8. C´ac ph´ep to´an lˆogic v`a c´ac ph´ep to´an bit: C´ac m´ay t´ınh d`ung
c´ac bit d¯ˆe’ biˆe’u diˆe˜n thˆong tin. Mˆo.t bit c´o hai gi´a tri. l`a 0 v`a 1. Y ngh˜ıa cu ´ ’a t`u.
n`ay b˘a´t nguˆo`n t`u. binary digit (sˆo´ nhi. phˆan). Thuˆa.t ng˜u. n`ay do nh`a Thˆo´ng kˆe
ho.c nˆo’i tiˆe´ng John Turkey d¯u.
a ra v`ao n˘am 1946. Bit c˜ung c´o thˆe’ d¯u.
o.
. c d`ung d¯ˆe’
biˆe’u diˆe˜n gi´a tri. chˆan l´y. Ta s˜e d`ung bit 1 d¯ˆe’ biˆe’u diˆe˜n gi´a tri. d¯´ung v`a bit 0 d¯ˆe’
biˆe’u diˆe˜n gi´a tri. sai.
Ta s˜e d`ung c´ac k´y hiˆe.u NOT, AND, OR, XOR thay cho c´ac ph´ep to´an
−,∧,∨, ⊕ nhu. thu.
`o.
ng d¯u.
o.
. c l`am trong c´ac ngˆon ng˜u. lˆa.p tr`ınh kh´ac nhau.
Thˆong tin thu.
`o
.
ng d¯u.
o
.
. c biˆe’u diˆe˜n b˘a`ng c´ach d`ung c´ac xˆau bit, d¯´o l`a d˜ay
c´ac sˆo´ 0 v`a 1. Khi d¯˜a l`am nhu. thˆe´, c´ac ph´ep to´an trˆen c´ac xˆau bit c˜ung c´o thˆe’
d¯u.
o.
. c d`ung d¯ˆe’ thao t´ac c´ac thˆong tin d¯´o. Ta c´o thˆe’ mo.
’ rˆo.ng c´ac ph´ep to´an bit
t´o.
i c´ac xˆau bit. Ta d¯i.nh ngh˜ıa c´ac OR bit, AND bit v`a XOR bit d¯ˆo´i v´o.
i hai xˆau
5
bit c´o c`ung chiˆe`u d`ai l`a c´ac xˆau c´o c´ac bit cu’a ch´ung l`a c´ac OR, AND v`a XOR
cu’a c´ac bit tu.
o
.
ng ´u.
ng trong hai xˆau tu.
o
.
ng ´u.
ng.
Th´ı du. :
xˆau 1 0 1 1 0 1 1 0 1 1 0
xˆau 2 1 1 0 0 0 1 1 1 0 1
OR bit 1 1 1 0 1 1 1 1 1 1
AND bit 0 1 0 0 0 1 0 1 0 0
XOR bit 1 0 1 0 1 0 1 0 1 1
1.1.2. Su.
. tu.
o.
ng d¯u.
o.
ng lˆogic cu’a c´ac cˆong th´u.
c:
Trong lˆogic mˆe.nh d¯ˆe` , ngu.
`o.
i ta d¯u.
a ra kh´ai niˆe.m cˆong th´u.
c, tu.
o.
ng tu.
. nhu.
kh´ai niˆe.m biˆe’u th´u.
c trong to´an ho.c.
1.1.2.1. D- i
.nh ngh˜ıa:
1) C´ac biˆe´n mˆe.nh d¯ˆe` p, q, r, ... l`a c´ac cˆong th´u.
c,
2) Nˆe´u P, Q l`a c´ac cˆong th´u.
c th`ı P,P ∧ Q, P ∨ Q, P ⊕ Q, P ⇒ Q, P ⇔ Q l`a
c´ac cˆong th´u.
c,
3) Chı’ chˆa´p nhˆa.n c´ac cˆong th´u.
c d¯u.
o
.
. c th`anh lˆa.p b˘a`ng viˆe.c ´ap du. ng mˆo.t sˆo´
h˜u.
u ha.n c´ac quy t˘a´c 1)-2).
1.1.2.2. D- i
.nh ngh˜ıa: Cˆong th´u.
c A go.i l`a h˘a`ng d¯´ung nˆe´u A nhˆa.n gi´a tri. 1 v´o.
i
mo.i hˆe. gi´a tri. chˆan l´y c´o thˆe’ c´o cu’a c´ac biˆe´n mˆe.nh d¯ˆe` c´o m˘a.t trong A.
Cˆong th´u.
c A go.i l`a h˘a`ng sai nˆe´u A nhˆa.n gi´a tri. 0 v´o.
i mo.i hˆe. gi´a tri. chˆan l´y
c´o thˆe’ c´o cu’a c´ac biˆe´n mˆe.nh d¯ˆe` c´o m˘a.t trong A. Khi d¯´o ta go.i A l`a mˆo.t mˆau
thuˆa’n.
Mˆo.t cˆong th´u.
c khˆong pha’i l`a h˘a`ng d¯´ung, c˜ung khˆong pha’i l`a mˆau thuˆa’n
d¯u.
o
.
. c go.i l`a tiˆe´p liˆen.
1.1.2.3. D- i
.nh ngh˜ıa: Hai cˆong th´u.
c A v`a B d¯u.
o.
. c go.i l`a tu.
o.
ng d¯u.
o.
ng lˆogic,
k´y hiˆe.u A ≡ B, nˆe´u A ⇔ B l`a mˆo.t h˘a`ng d¯´ung. Hˆe. th´u.
c A ≡ B c`on d¯u.
o
.
. c go.i l`a
mˆo.t d¯˘a’ ng th´u.
c.
1.1.2.4. C´ac tu.
o.
ng d¯u.
o.
ng lˆogic co. ba’n:
1) Luˆa.t d¯ˆo`ng nhˆa´t:
p ∧ 1 ≡ p, p ∨ 0 ≡ p.
2) Luˆa.t nuˆo´t:
p ∧ 0 ≡ 0, p ∨ 1 ≡ 1.
3) Luˆa.t l˜uy d¯˘a’ ng:
p ∧ p ≡ p, p ∨ p ≡ p.
6
4) Luˆa.t phu’ d¯i.nh k´ep:
p ≡ p.
5) Luˆa.t giao ho´an:
p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p.
6) Luˆa.t kˆe´t ho.
. p:
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r), (p ∨ q) ∨ r ≡ p ∨ (q ∨ r).
7) Luˆa.t phˆan phˆo´i:
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).
8) Luˆa.t De Morgan:
p ∧ q ≡ p ∨ q, p ∨ q ≡ p ∧ q.
9) Mˆo.t sˆo´ tu.
o.
ng d¯u.
o.
ng tiˆe.n ´ıch:
p ∧ p ≡ 0, p ∨ p ≡ 1,
p ⇔ q ≡ q ⇔ p, p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p), p ⇔ q ≡ p ⇔ q,
(p ⇒ q) ≡ (p ∨ q),
(p ⇒ q) ≡ (q ⇒ p).
1.1.3. Suy luˆa.n to´an ho. c:
1.1.3.1. Suy luˆa.n diˆ˜en di.ch: Suy luˆa.n l`a r´ut ra mˆo.t mˆe.nh d¯ˆe` m´o.
i t`u. mˆo.t hay
nhiˆe`u mˆe.nh d¯ˆe` d¯˜a c´o.
Phˆan t´ıch c´ac suy luˆa.n trong ch´u.
ng minh to´an ho.c, ngu.
`o.
i ta thˆa´y mˆo˜i ch´u.
ng
minh bao gˆo`m mˆo.t sˆo´ h˜u.
u ha.n bu.
´o.
c suy luˆa.n d¯o.
n gia’n. Trong mˆo˜i bu.
´o.
c suy
luˆa.n d¯o.
n gia’n d¯´o, ta d¯˜a “ngˆa`m” vˆa.n du. ng mˆo.t quy t˘a´c suy luˆa.n tˆo’ng qu´at d¯ˆe’
t`u. c´ac mˆe.nh d¯ˆe` d¯˜a d¯u.
o
.
. c th`u.
a nhˆa.n l`a d¯´ung (tiˆen d¯ˆe` , d¯i.nh l´y, d¯i.nh ngh˜ıa, gia’
thiˆe´t) c´o thˆe’ r´ut ra mˆo.t mˆe.nh d¯ˆe` m´o.
i. Ngu.
`o.
i ta go.i c´ac mˆe.nh d¯ˆe` xuˆa´t ph´at d¯˜a
d¯u.
o.
. c th`u.
a nhˆa.n l`a d¯´ung l`a c´ac tiˆe`n d¯ˆe` , c`on mˆe.nh d¯ˆe` m´o.
i d¯u.
o.
. c r´ut ra (nh`o. vˆa.n
du. ng c´ac quy t˘a´c suy luˆa.n tˆo’ng qu´at) go.i l`a hˆe. qua’ lˆogic cu’a c´ac tiˆe`n d¯ˆe` . Ph´ep
suy luˆa.n nhu. thˆe´ go.i l`a suy luˆa.n diˆe˜n di.ch hay go.i t˘a´t l`a suy diˆe˜n.
1.1.3.2. D- i
.nh ngh˜ıa: Gia’ su.
’ A1, A2,... ,An, B l`a nh˜u.
ng cˆong th´u.
c. Nˆe´u tˆa´t
ca’ c´ac hˆe. gi´a tri. chˆan l´y cu’a c´ac biˆe´n mˆe.nh d¯ˆe` c´o m˘a.t trong c´ac cˆong th´u.
c d¯´o
l`am cho A1, A2,... ,An nhˆa.n gi´a tri. 1 c˜ung d¯ˆo`ng th`o.
i l`am cho B nhˆa.n gi´a tri. 1,
t´u.
c l`a A1 ∧ A2 ∧ ... ∧ An ⇒ B l`a mˆo.t cˆong th´u.
c h˘a`ng d¯´ung, th`ı ta go.i B l`a hˆe. qua’ lˆogic cu’a A1, A2,... ,An. Khi d¯´o ta c˜ung n´oi r˘a`ng c´o mˆo.t quy t˘a´c suy luˆa.n
t`u. c´ac tiˆe`n d¯ˆe` A1, A2,... ,An t´o.
i hˆe. qua’ lˆogic B cu’a ch´ung.
7
Quy t˘a´c suy luˆa.n d¯´o d¯u.
o.
. c k´y hiˆe.u l`a:
A1, A1,... ,An
B .
1.1.3.3. Mˆo. t sˆo´ quy t˘a´c suy luˆa.n thu.
`o.
ng d`ung:
1) p
p ∨ q (Quy t˘a´c cˆo.ng).
2) p ∧ q
p (Quy t˘a´c r´ut go.n).
3) p, p ⇒ q
q (Quy t˘a´c kˆe´t luˆa.n - Modus ponens).
4) p ⇒ q, q
p (Quy t˘a´c kˆe´t luˆa.n ngu.
o.
. c - Modus tollens).
5) p ⇒ q, q ⇒ r
p ⇒ r
(Quy t˘a´c tam d¯oa.n luˆa.n).
6) p ⇒ q, q ⇒ p
p ⇔ q (Quy t˘a´c d¯u.
a tu.
o.
ng d¯u.
o.
ng v`ao).
7) p ∨ q, p
q (Quy t˘a´c t´ach tuyˆe’n).
8) p ⇒ r, q ⇒ r
p ∨ q ⇒ r (Quy t˘a´c t´ach tuyˆe’n gia’ thiˆe´t).
9) p ⇒ q, p ⇒ r
p ⇒ q ∧ r (Quy t˘a´c hˆo.i kˆe´t luˆa.n).
10) q ⇒ p
p ⇒ q (Quy t˘a´c pha’n d¯a’o).
11) p ⇒ q, p ⇒ q
p (Quy t˘a´c pha’n ch´u.
ng).
Th´ı du. :
1) Cho: Nˆe´u tr`o.
i mu.
a (p) th`ı sˆan u.
´o.
t (q) (d¯´ung)
Tr`o.
i d¯ang mu.
a (d¯´ung)
Kˆe´t luˆa.n: Sˆan u.
´o
.
t (d¯´ung).
2) Cho: Nˆe´u hai g´oc d¯ˆo´i d¯ı’nh (p) th`ı b˘a`ng nhau (q) (d¯´ung)
Ab v`a Bb khˆong b˘a`ng nhau (d¯´ung)
Kˆe´t luˆa.n: Ab v`a Bb khˆong d¯ˆo´i d¯ı’nh (d¯´ung).
3) Cho: Mo.i h`ınh vuˆong d¯ˆe`u l`a h`ınh thoi (p ⇒ q) (d¯´ung)
Mo.i h`ınh thoi c´o c´ac d¯u.
`o.
ng ch´eo vuˆong g´oc (q ⇒ r) (d¯´ung)
Kˆe´t luˆa.n: Mo.i h`ınh vuˆong d¯ˆe`u c´o c´ac d¯u.
`o
.
ng ch´eo vuˆong g´oc (p ⇒ r) (d¯´ung).
8
1.1.3.4. Suy luˆa.n nghe c´o l´y: Suy luˆa.n nghe c´o l´y l`a suy luˆa.n khˆong theo mˆo.t
quy t˘a´c suy luˆa.n tˆo’ng qu´at n`ao d¯ˆe’ t`u. nh˜u.
ng tiˆe`n d¯ˆe` d¯˜a c´o, r´ut ra d¯u.
o.
. c mˆo.t kˆe´t
luˆa.n x´ac d¯i.nh. Nˆe´u c´ac tiˆe`n d¯ˆe` d¯ˆe`u d¯´ung th`ı kˆe´t luˆa.n r´ut ra khˆong ch˘a´c ch˘a´n
d¯´ung, m`a chı’ c´o t´ınh chˆa´t du.
. d¯o´an, gia’ thuyˆe´t.
Trong to´an ho.c c´o hai kiˆe’u suy luˆa.n nghe c´o l´y thu.
`o
.
ng d`ung, d¯´o l`a
– Ph´ep quy na.p khˆong ho`an to`an,
– Ph´ep tu.
o.
ng tu.
. .
Th´ı du. : 1) T`u. d¯i.nh l´y trong h`ınh ho.c ph˘a’ ng: “Hai d¯u.
`o.
ng th˘a’ ng c`ung vuˆong
g´oc v´o.
i mˆo.t d¯u.
`o
.
ng th˘a’ ng th´u. ba th`ı song song v´o.
i nhau”, ch´ung ta nˆeu ra mˆo.t
“du.
. d¯o´an”: “Hai m˘a.t ph˘a’ ng c`ung vuˆong g´oc v´o.
i mˆo.t m˘a.t ph˘a’ ng th´u. ba th`ı song
song v´o.
i nhau”.
D- ˆay l`a mˆo.t th´ı du. vˆe` ph´ep suy luˆa.n b˘a`ng tu.
o.
ng tu.
. .
2) C´ac sˆo´ 220
+ 1, 221
+ 1, 222
+ 1, 223
+ 1, 224
+ 1 l`a nh˜u.
ng sˆo´ nguyˆen tˆo´.
Kˆe´t luˆa.n: v´o.
i mo.i sˆo´ tu.
. nhiˆen n, sˆo´ 22n
+ 1 l`a sˆo´ nguyˆen tˆo´.
D- ˆay l`a lˆo´i suy luˆa.n quy na.p khˆong ho`an to`an d¯˜a nˆeu lˆen bo.
’ i Fermat (1601-
1665) sau khi d¯˜a kiˆe’m nghiˆe.m v´o.
i c´ac sˆo´ n = 0, 1, 2, 3, 4. Nhu.
ng sau d¯´o Euler d¯˜a
chı’ ra r˘a`ng v´o.
i n = 5, kh˘a’ ng d¯i.nh n`ay khˆong d¯´ung, ngh˜ıa l`a 225
+ 1 khˆong l`a sˆo´
nguyˆen tˆo´.
3) 6= 3+3, 8= 3+5, 10 = 5 + 5, 12 = 5 + 7,... . Kˆe´t luˆa.n: mo.i sˆo´
nguyˆen du.
o.
ng ch˘a˜n l´o.
n ho.
n 4 l`a tˆo’ng cu’a hai sˆo´ nguyˆen tˆo´.
Mˆe.nh d¯ˆe` n`ay mang tˆen l`a b`ai to´an Goldbach. D- ˆay l`a mˆo.t trong nhiˆe`u kh˘a’ ng
d¯i.nh trong to´an ho.c chu.
a d¯u.
o
.
. c ch´u.
ng minh.
4) Phu.
o.
ng tr`ınh x3 + y3 = z3 khˆong c´o nghiˆe.m nguyˆen, phu.
o.
ng tr`ınh
x4 + y4 = z4 khˆong c´o nghiˆe.m nguyˆen. Kˆe´t luˆa.n: phu.
o.
ng tr`ınh xn + yn = zn
khˆong c´o nghiˆe.m nguyˆen v´o.
i mo.i sˆo´ nguyˆen n > 2.
Mˆe.nh d¯ˆe` n`ay d¯u.
o
.
. c nˆeu ra bo.
’ i Fermat n˘am 1637, go.i l`a “d¯i.nh l´y cuˆo´i c`ung
cu’a Fermat”. M˜ai d¯ˆe´n th´ang 5 n˘am 1995, mˆe.nh d¯ˆe` n`ay m´o.
i d¯u.
o.
. c ho`an to`an
ch´u.
ng minh xong bo.
’ i nh`a to´an ho.c ngu.
`o.
i Anh tˆen l`a Wiles.
To´an ho.c l`a khoa ho.c cu’a suy luˆa.n diˆe˜n di.ch. Tˆa´t ca’ c´ac vˆa´n d¯ˆe` trong to´an
ho.c chı’ d¯u.
o
.
. c tr`ınh b`ay b˘a`ng c´ac suy luˆa.n diˆe˜n di.ch. Tuy nhiˆen, trong qu´a tr`ınh
ph´at minh, s´ang ta.o to´an ho.c, l´y luˆa.n diˆe˜n di.ch g˘a´n ch˘a.t v´o.
i c´ac suy luˆa.n nghe
c´o l´y. Ta d`ung quy na.p khˆong ho`an to`an hay tu.
o.
ng tu.
. d¯ˆe’ nˆeu ra c´ac gia’ thuyˆe´t.
Sau d¯´o m´o.
i ch´u.
ng minh c´ac gia’ thuyˆe´t n`ay b˘a`ng diˆe˜n di.ch.
1.1.4. C´ac phu.
o.
ng ph´ap ch´u.
ng minh:
1.1.4.1. Ch´u.
ng minh l`a g`ı? Trong suy luˆa.n diˆe˜n di.ch, nˆe´u t`u. c´ac tiˆe`n d¯ˆe`
A1, A2,... ,An, ta r´ut ra kˆe´t luˆa.n B b˘a`ng c´ach vˆa.n du. ng nh˜u.
ng quy t˘a´c suy
luˆa.n tˆo’ng qu´at th`ı ta n´oi B l`a kˆe´t luˆa.n lˆogic cu’a c´ac tiˆe`n d¯ˆe` A1, A2,... ,An v`a
suy luˆa.n d¯´o l`a ho.
. p lˆogic. Nˆe´u tˆa´t ca’ c´ac tiˆe`n d¯ˆe` A1, A2,... ,An d¯ˆe`u d¯´ung th`ı
ta go.i kˆe´t luˆa.n lˆogic B l`a mˆo.t kˆe´t luˆa.n ch´u.
ng minh v`a go.i suy luˆa.n d¯´o l`a mˆo.t
ch´u.
ng minh.
9
Phˆan t´ıch c´ac ch´u.
ng minh to´an ho.c ta thˆa´y mˆo˜i ch´u.
ng minh gˆo`m mˆo.t sˆo´
h˜u.
u ha.n bu.
´o
.
c, mˆo˜i bu.
´o
.
c l`a mˆo.t suy luˆa.n diˆe˜n di.ch trong d¯´o ta vˆa.n du. ng mˆo.t
quy t˘a´c suy luˆa.n tˆo’ng qu´at. Nhu. vˆa.y, mˆo.t ch´u.
ng minh to´an ho.c gˆo`m ba bˆo. phˆa.n
cˆa´u th`anh:
1) Luˆa.n d¯ˆe` , t´u.
c l`a mˆe.nh d¯ˆe` cˆa`n ch´u.
ng minh.
2) Luˆa.n c´u.
, t´u.
c l`a nh˜u.
ng mˆe.nh d¯ˆe` d¯u.
o
.
. c th`u.
a nhˆa.n (d¯i.nh ngh˜ıa, tiˆe`n d¯ˆe` ,
d¯i.nh l´y, gia’ thiˆe´t) d¯u.
o
.
. c lˆa´y l`am tiˆe`n d¯ˆe` trong mˆo˜i suy luˆa.n.
3) Luˆa.n ch´u.
ng, t´u.
c l`a nh˜u.
ng quy t˘a´c suy luˆa.n tˆo’ng qu´at d¯u.
o.
. c vˆa.n du. ng
trong mˆo˜i bu.
´o.
c suy luˆa.n cu’a ch´u.
ng minh.
1.1.4.2. Phu.
o.
ng ph´ap ch´u.
ng minh tru.
. c tiˆe
´p: Khi ta ch´u.
ng minh mˆe.nh d¯ˆe`
B b˘a`ng c´ach va. ch r˜o B l`a kˆe´t luˆa.n lˆogic cu’a nh˜u.
ng tiˆe`n d¯ˆe` d¯´ung A1, A2,... ,An,
ngh˜ıa l`a B l`a mˆo.t kˆe´t luˆa.n ch´u.
ng minh th`ı ta n´oi l`a d¯˜a ch´u.
ng minh tru.
. c tiˆe´p
mˆe.nh d¯ˆe` B.
Th´ı du. : H˜ay ch´u.
ng minh tru.
. c tiˆe´p mˆe.nh d¯ˆe` : “Nˆe´u n l`a mˆo.t sˆo´ le’ th`ı n2 c˜ung
l`a mˆo.t sˆo´ le’”.
Gia’ su.
’ r˘a`ng gia’ thiˆe´t cu’a mˆe.nh d¯ˆe` k´eo theo n`ay l`a d¯´ung, t´u.
c l`a n l`a mˆo.t sˆo´
le’. Khi d¯´o n = 2k + 1, v´o.
i k l`a mˆo.t sˆo´ nguyˆen. T`u. d¯´o suy ra n2 = 4k2 + 4k +1=
2(2k2 + 2k) + 1. Do d¯´o n2 l`a mˆo.t sˆo´ le’.
1.1.4.3. Phu.
o.
ng ph´ap ch´u.
ng minh t`ım pha’n th´ı du.: Gia’ su.
’ ta cˆa`n ch´u.
ng
minh mˆe.nh d¯ˆe` p sai. Nˆe´u ta t`ım d¯u.
o.
. c mˆe.nh d¯ˆe` q, tru.
`o.
ng ho.
. p d¯˘a.c biˆe.t cu’a p l`a
sai. Khi d¯´o q d¯´ung v`a p ⇒ q l`a d¯´ung. Do d¯´o theo quy t˘a´c kˆe´t luˆa.n ngu.
o.
. c th`ı p
l`a d¯´ung. T`u. d¯´o p l`a sai.
Th´ı du. : Cho m v`a n l`a nh˜u.
ng sˆo´ kh´ac khˆong bˆa´t k`y. Ch´u.
ng minh r˘a`ng n+m <
nm l`a khˆong d¯´ung. Chı’ cˆa`n lˆa´y n = m = 1 th`ı 1 + 1 = 2 > 1.1.
1.1.4.4. Phu.
o.
ng ph´ap ch´u.
ng minh pha’n d¯a’o: Gia’ su.
’ ta cˆa`n ch´u.
ng minh
p ⇒ q. Nˆe´u ta ch´u.
ng minh d¯u.
o.
. c q ⇒ p th`ı theo quy t˘a´c pha’n d¯a’o, ta c´o p ⇒ q
d¯´ung. Nhu. vˆa.y, d¯ˆe’ ch´u.
ng minh p ⇒ q, ta c´o thˆe’ chuyˆe’n sang ch´u.
ng minh q ⇒ p
l`a d¯u’.
Th´ı du. : Cho a l`a mˆo.t sˆo´ h˜u.
u tı’ kh´ac 0. Ch´u.
ng minh r˘a`ng nˆe´u b l`a mˆo.t sˆo´ vˆo
tı’ th`ı ab c˜ung l`a mˆo.t sˆo´ vˆo tı’.
Ta viˆe´t a = m
n
, v´o.
i m, n l`a hai sˆo´ nguyˆen kh´ac 0. Nˆe´u ab l`a sˆo´ h˜u.
u tı’ th`ı ta
c´o thˆe’ viˆe´t ab = k
l v´o.
i k,l l`a hai sˆo´ nguyˆen v`a l 6= 0. Khi d¯´o b = ab
a = k/l
m/n = kn
lm
v`a suy ra b l`a mˆo.t sˆo´ h˜u.
u tı’.
1.1.4.5. Phu.
o.
ng ph´ap ch´u.
ng minh pha’n ch´u.
ng: Co. so.
’ lˆogic cu’a phu.
o.
ng
ph´ap ch´u.
ng minh pha’n ch´u.
ng l`a nhu. sau: muˆo´n ch´u.
ng minh mˆe.nh d¯ˆe` p l`a d¯´ung,
ta gia’ thiˆe´t p l`a sai, t´u.
c l`a p l`a d¯´ung. Sau d¯´o ta ch´u.
ng minh r˘a`ng p ⇒ q l`a d¯´ung
v`a q l`a d¯´ung. Do d¯´o theo quy t˘a´c pha’n ch´u.
ng th`ı p l`a d¯´ung. D- iˆe`u n`ay dˆa˜n d¯ˆe´n
mˆau thuˆa’n (luˆa.t b`ai trung).
10
Th´ı du. : Ch´u.
ng minh r˘a`ng u.
´o.
c sˆo´ tu.
. nhiˆen nho’ nhˆa´t kh´ac 1 cu’a mˆo.t sˆo´ tu.
. nhiˆen
l´o.
n ho.
n 1 l`a mˆo.t sˆo´ nguyˆen tˆo´.
Gia’ su.
’ k l`a u.
´o
.
c tu.
. nhiˆen nho’ nhˆa´t kh´ac 1 cu’a sˆo´ tu.
. nhiˆen n (n > 1) v`a k
khˆong l`a sˆo´ nguyˆen tˆo´. Do d¯´o tˆo`n ta.i u.
´o.
c sˆo´ m cu’a k sao cho 1 <m<k. Nhu.
ng
khi d¯´o m c˜ung l`a mˆo.t u.
´o.
c sˆo´ cu’a n. D- iˆe`u n`ay mˆau thuˆa’n v´o.
i k l`a u.
´o.
c tu.
. nhiˆen
nho’ nhˆa´t kh´ac 1 cu’a n.
1.1.4.6. Phu.
o.
ng ph´ap ch´u.
ng minh x´et tˆa´t ca’ c´ac tru.
`o.
ng ho.
. p: Trong
to´an ho.c, d¯ˆe’ ch´u.
ng minh mˆe.nh d¯ˆe` n`ao d¯´o l`a d¯´ung, ta c´o thˆe’ x´et n´o trong tˆa´t ca’
c´ac tru.
`o.
ng ho.
. p c´o thˆe’ c´o.
Th´ı du. : Ch´u.
ng minh r˘a`ng t´ıch cu’a 3 sˆo´ nguyˆen liˆen tiˆe´p chia hˆe´t cho 3.
V´o.
i n l`a mˆo.t sˆo´ nguyˆen, ta viˆe´t n = 3q + r v´o.
i q l`a mˆo.t sˆo´ nguyˆen v`a
r = 0, 1, 2.
a) r =0: n = 3q hay n chia hˆe´t cho 3, khi d¯´o n(n + 1)(n + 2) chia hˆe´t cho
3.
b) r =1: n = 3q + 1 hay n + 2 = 3(q + 1) hay n + 2 chia hˆe´t cho 3, khi d¯´o
n(n + 1)(n + 2) chia hˆe´t cho 3.
c) r =2: n = 3q + 2 hay n + 1 = 3(q + 1) hay n + 1 chia hˆe´t cho 3,
n(n + 1)(n + 2) chia hˆe´t cho 3.
1.1.4.6. Phu.
o.
ng ph´ap ch´u.
ng minh quy na.p: Phu.
o.
ng ph´ap n`ay s˜e d¯u.
o.
. c
tr`ınh b`ay trong Chu.
o
.
ng IV vˆe` “Sˆo´ nguyˆen v`a sˆo´ tu.
. nhiˆen”.
1.2. TAˆ
. P HO.
. P.
1.2.1. Tˆa.p ho.
. p v`a c´ach x´ac d¯i.nh mˆo. t tˆa.p ho.
. p:
1.2.1.1. Kh´ai niˆe.m tˆa.p ho.
. p: Nh˜u.
ng d¯ˆo´i tu.
o.
. ng d¯u.
o.
. c tu. tˆa.p do mˆo.t t´ınh chˆa´t
chung n`ao d¯´o th`anh lˆa.p mˆo.t tˆa.p ho.
. p. D- ˆay khˆong pha’i l`a mˆo.t d¯i.nh ngh˜ıa m`a chı’
l`a mˆo.t su.
. mˆo ta’ cho ta mˆo.t h`ınh a’nh tru.
. c quan cu’a kh´ai niˆe.m d¯´o.
Su.
. mˆo ta’ mˆo.t tˆa.p ho.
. p c´ac d¯ˆo´i tu.
o.
. ng du.
. a trˆen mˆo.t kh´ai niˆe.m tru.
. c quan vˆe`
mˆo.t d¯ˆo´i tu.
o.
. ng n`ao d¯´o d¯˜a d¯u.
o.
. c nh`a to´an ho.c ngu.
`o.
i D- u´.
c Georg Cantor d¯u.
a ra
lˆa`n d¯ˆa`u tiˆen v`ao n˘am 1895. L´y thuyˆe´t h`ınh th`anh t`u. kh´ai niˆe.m tru.
. c quan d¯´o
cu’a tˆa.p ho.
. p d¯˜a dˆa˜n d¯ˆe´n nh˜u.
ng nghi.ch l´y ho˘a.c c´ac mˆau thuˆa’n lˆogic nhu. nh`a triˆe´t
ho.c ngu.
`o.
i Anh Bertrand Russell d¯˜a chı’ ra n˘am 1902. Nh˜u.
ng mˆau thuˆa’n lˆogic
d¯´o c´o thˆe’ tr´anh d¯u.
o.
. c b˘a`ng c´ach xˆay du.
. ng mˆo.t l´y thuyˆe´t tˆa.p ho.
. p xuˆa´t ph´at t`u.
nh˜u.
ng gia’ thiˆe´t co. ba’n, go.i l`a c´ac tiˆen d¯ˆe` . Tuy nhiˆen, ch´ung ta s˜e d`ung phiˆen
ba’n ban d¯ˆa`u cu’a Cantor, d¯u.
o
.
. c go.i l`a l´y thuyˆe´t tˆa.p ho.
. p ngˆay tho.
, ch´u. khˆong
ph´at triˆe’n phiˆen ba’n tiˆen d¯ˆe` cu’a l´y thuyˆe´t n`ay, bo.
’ i v`ı tˆa´t ca’ c´ac tˆa.p ho.
. p d¯u.
o.
. c
xem x´et trong t`ai liˆe.u n`ay c´o thˆe’ xu.
’ l´y phi mˆau thuˆa’n b˘a`ng c´ach d`ung l´y thuyˆe´t
ban d¯ˆa`u cu’a Cantor.
C´ac vˆa.t hay d¯ˆo´i tu.
o
.
. ng th`anh lˆa.p mˆo.t tˆa.p ho.
. p go.i l`a c´ac phˆa`n tu.
’ cu’a tˆa.p
ho.
. p d¯´o.
11
Trong ngˆon ng˜u. thˆong thu.
`o.
ng, ngu.
`o.
i ta d`ung nh˜u.
ng t`u. nhu.
: nh´om, to`an
thˆe’, tˆa.p thˆe’, ch`um, bˆa`y, d¯`an, ... d¯ˆe’ n´oi vˆe` mˆo.t tˆa.p ho.
. p n`ao d¯´o.
Mˆo.t tˆa.p ho.
. p thu.
`o
.
ng d¯u.
o
.
. c k´y hiˆe.u bo.
’ i c´ac ch˜u. c´ai in hoa: A, B, C, D,
E, X, Y , Z, ... Phˆa`n tu.
’ cu’a tˆa.p ho.
. p thu.
`o.
ng d¯u.
o.
. c k´y hiˆe.u bo.
’ i c´ac ch˜u. c´ai in
thu.
`o.
ng: a, b, c, d, x, y, z, ...
Th´ı du. :
1) Tˆa.p ho.
. p c´ac sˆo´ tu.
. nhiˆen, k´y hiˆe.u N.
2) Tˆa.p ho.
. p c´ac sˆo´ nguyˆen, k´y hiˆe.u Z.
3) Tˆa.p ho.
. p c´ac sˆo´ h˜u.
u tı’, k´y hiˆe.u Q.
4) Tˆa.p ho.
. p c´ac sˆo´ thu.
. c, k´y hiˆe.u R.
5) Tˆa.p ho.
. p c´ac sˆo´ ph´u.
c, k´y hiˆe.u C.
6) Tˆa.p ho.
. p c´ac d¯iˆe’m trˆen m˘a.t ph˘a’ ng.
7) Tˆa.p ho.
. p c´ac nghiˆe.m thu.
. c cu’a phu.
o.
ng tr`ınh sin 3x − sin x + sin 2x = 0.
8) Tˆa.p ho.
. p c´ac sinh viˆen n˘am th´u. nhˆa´t ng`anh tin ho.c cu’a tru.
`o.
ng D- a.i ho.c
Khoa ho.c.
K´y hiˆe.u:
– D- ˆe’ chı’ a l`a mˆo.t phˆa`n tu.
’ cu’a tˆa.p ho.
. p A, ta viˆe´t a ∈ A v`a d¯o.c l`a “a thuˆo.c
A” hay “a l`a phˆa`n tu.
’ cu’a tˆa.p ho.
. p A”.
– D- ˆe’ chı’ b khˆong pha’i l`a mˆo.t phˆa`n tu.
’ cu’a tˆa.p ho.
. p A, ta viˆe´t b /∈ A ho˘a.c
b∈A v`a d¯o. c l`a “b khˆong thuˆo.c A” ho˘a.c “b khˆong pha’i l`a mˆo.t phˆa`n tu.
’ cu’a tˆa.p
ho.
. p A”.
1.2.1.2. Tˆa.p ho.
. p rˆo˜ng: Tˆa.p ho.
. p khˆong ch´u.
a phˆa`n tu.
’ n`ao go.i l`a tˆa.p rˆo˜ng, k´y
hiˆe.u ∅.
Th´ı du. : Tˆa.p ho.
. p c´ac nghiˆe.m thu.
. c cu’a phu.
o.
ng tr`ınh x2 + 1 = 0 l`a tˆa.p ho.
. p rˆo˜ng.
1.2.1.3. C´ach x´ac d¯i.nh mˆo. t tˆa.p ho.
. p
1. Liˆe.t kˆe tˆa´t ca’ c´ac phˆa`n tu.
’ cu’a tˆa.p ho.
. p: Theo c´ach n`ay, d¯ˆe’ x´ac
d¯i.nh mˆo.t tˆa.p ho.
. p n`ao d¯´o ta liˆe.t kˆe d¯ˆa`y d¯u’ tˆa´t ca’ c´ac phˆa`n tu.
’ cu’a n´o.
Th´ı du. : 1) Tˆa.p ho.
. p 4 sˆo´ nguyˆen du.
o.
ng d¯ˆa`u tiˆen d¯u.
o.
. c viˆe´t l`a:
{1, 2, 3, 4}.
2) Tˆa.p ho.
. p c´ac ch˜u. c´ai trong ba’ng ch˜u. c´ai tiˆe´ng Anh d¯u.
o.
. c viˆe´t l`a:
{a, b, c, . . . , z}.
3) Tˆa.p ho.
. p c´ac sˆo´ tu.
. nhiˆen ch˘a˜n d¯u.
o.
. c viˆe´t l`a:
{0, 2, 4, 6,... , 2n, . . . }.
Ch´u ´y r˘a`ng khi liˆe.t kˆe c´ac phˆa`n tu.
’ cu’a mˆo.t tˆa.p ho.
. p ta khˆong quan tˆam d¯ˆe´n
th´u. tu.
. cu’a ch´ung.
2. Chı’ r˜o thuˆo. c t´ınh d¯˘a. c tru.
ng cu’a c´ac phˆa`n tu.
’ cu’a tˆa.p ho.
. p. Ta
c´o thˆe’ x´ac d¯i.nh mˆo.t tˆa.p ho.
. p b˘a`ng c´ach chı’ r˜o c´ac t´ınh chˆa´t chung cu’a c´ac phˆa`n
tu.
’ cu’a tˆa.p ho.
. p d¯´o d¯ˆe’ sau d¯´o du.
. a v`ao c´ac t´ınh chˆa´t n`ay ta c´o thˆe’ kh˘a’ ng d¯i.nh
mˆo.t d¯ˆo´i tu.
o.
. ng n`ao d¯´o c´o l`a mˆo.t phˆa`n tu.
’ cu’a tˆa.p ho.
. p d¯´o hay khˆong. C´ac t´ınh
chˆa´t nhu. vˆa.y go.i l`a thuˆo.c t´ınh d¯˘a.c tru.
ng cu’a c´ac phˆa`n tu.
’ cu’a tˆa.p ho.
. p.
Th´ı du. : Tˆa.p ho.
. p c´ac u.
´o
.
c sˆo´ nguyˆen du.
o
.
ng cu’a 24 l`a:
12
A = {1, 2, 3, 4, 6, 8, 12, 24}
v`a d¯u.
o
.
. c viˆe´t la.i l`a:
A = {n ∈ N : n|24}.
Trong tru.
`o.
ng ho.
. p tˆo’ng qu´at, nˆe´u tˆa.p ho.
. p X l`a tˆa.p ho.
. p tˆa´t ca’ c´ac phˆa`n tu.
’
x, sao cho x c´o t´ınh chˆa´t T th`ı ta viˆe´t:
X = {x | x c´o t´ınh chˆa´t T} ho˘a.c X = {x : x c´o t´ınh chˆa´t T}.
1.2.1.4. Gia’n d¯ˆo` Venn: C´ac tˆa.p ho.
. p c˜ung c´o thˆe’ d¯u.
o.
. c minh hoa. b˘a`ng h`ınh
v˜e nh`o. d`ung gia’n d¯ˆo` Venn, do nh`a to´an ho.c ngu.
`o
.
i Anh John Venn lˆa`n d¯ˆa`u tiˆen
d¯u.
a ra v`ao n˘am 1881. Trong c´ac gia’n d¯ˆo` Venn, tˆa.p ho.
. p v˜u tru. U - tˆa.p ho.
. p ch´u.
a
tˆa´t ca’ c´ac d¯ˆo´i tu.
o.
. ng d¯ang x´et - d¯u.
o.
. c biˆe’u diˆe˜n b˘a`ng mˆo.t h`ınh ch˜u. nhˆa.t. Bˆen
trong h`ınh ch˜u. nhˆa.t n`ay, nh˜u.
ng miˆe`n ph˘a’ ng gi´o.
i ha.n bo.
’ i c´ac d¯u.
`o.
ng cong kh´ep
k´ın khˆong tu.
. c˘a´t d¯u.
o
.
. c d`ung d¯ˆe’ biˆe’u diˆe˜n c´ac tˆa.p ho.
. p. D- ˆoi khi c´ac d¯iˆe’m d¯u.
o.
. c
d`ung d¯ˆe’ biˆe’u diˆe˜n c´ac phˆa`n tu.
’ cu’a tˆa.p ho.
. p. C´ac gia’n d¯ˆo` Venn thu.
`o.
ng d¯u.
o.
. c
d`ung d¯ˆe’ chı’ ra mˆo´i quan hˆe. gi˜u.
a c´ac tˆa.p ho.
. p.
1.2.1.5. D- i
.nh ngh˜ıa: Cho A l`a mˆo.t tˆa.p ho.
. p. Nˆe´u c´o ch´ınh x´ac n phˆa`n tu.
’ phˆan
biˆe.t trong A, v´o.
i n l`a mˆo.t sˆo´ nguyˆen khˆong ˆam, th`ı ta n´oi r˘a`ng A l`a mˆo.t tˆa.p
h˜u.
u ha.n v`a n l`a ba’n sˆo´ cu’a A. Ba’n sˆo´ cu’a A d¯u.
o.
. c k´y hiˆe.u l`a |A|. Mˆo.t tˆa.p ho.
. p
d¯u.
o
.
. c go.i l`a vˆo ha.n nˆe´u n´o khˆong pha’i l`a h˜u.
u ha.n.
Th´ı du. : 1) Cho A l`a tˆa.p ho.
. p c´ac ch˜u. c´ai trong ba’ng ch˜u. c´ai tiˆe´ng Anh. Khi
d¯´o |A| = 26.
2) Tˆa.p ho.
. p c´ac sˆo´ nguyˆen tˆo´ l`a mˆo.t tˆa.p ho.
. p vˆo ha.n.
1.2.2. Tˆa.p ho.
. p con v`a quan hˆe. bao h`am:
1.2.2.1. D- i
.nh ngh˜ıa: Tˆa.p ho.
. p A d¯u.
o.
. c go.i l`a mˆo.t tˆa.p ho.
. p con (hay tˆa.p con)
cu’a B, k´y hiˆe.u A ⊂ B, nˆe´u mˆo˜i phˆa`n tu.
’ cu’a A l`a mˆo.t phˆa`n tu.
’ cu’a B. Nhu. vˆa.y,
A ⊂ B khi v`a chı’ khi v´o.
i mo.i x ∈ A k´eo theo x ∈ B.
Khi c´o A ⊂ B, ta c`on n´oi “A l`a mˆo.t bˆo. phˆa.n cu’a B” hay “A bao h`am trong
B”. Khi d¯´o ta c`on viˆe´t B ⊃ A v`a d¯o. c l`a “B bao h`am A” hay “B ch´u.
a A”.
Quan hˆe. “⊂” d¯u.
o
.
. c go.i l`a quan hˆe. bao h`am. C´ac hˆe. th´u.
c A ⊂ B, B ⊃ A
d¯u.
o
.
. c go.i l`a c´ac bao h`am th´u.
c.
Nˆe´u A ⊂ B v`a c´o ´ıt nhˆa´t mˆo.t phˆa`n tu.
’ thuˆo.c B nhu.
ng khˆong thuˆo.c A th`ı ta
n´oi A l`a mˆo.t tˆa.p con thu.
. c su.
. cu’a B hay bˆo. phˆa.n thu.
. c su.
. cu’a B.
Th´ı du. : 1) Tˆa.p ho.
. p N c´ac sˆo´ tu.
. nhiˆen l`a tˆa.p con thu.
. c su.
. cu’a tˆa.p ho.
. p Z c´ac
sˆo´ nguyˆen.
2) Tˆa.p ho.
. p c´ac h`ınh vuˆong l`a tˆa.p con cu’a tˆa.p ho.
. p c´ac h`ınh ch˜u. nhˆa.t, c˜ung
nhu. l`a tˆa.p con cu’a tˆa.p c´ac h`ınh thoi.
1.2.2.2. T´ınh chˆa´t: V´o.
i A, B, C l`a 3 tˆa.p ho.
. p bˆa´t k`y, ta luˆon c´o:
1) ∅ ⊂ A,
2) A ⊂ A,
3) nˆe´u A ⊂ B v`a B ⊂ C th`ı A ⊂ C.
13
Thˆa.t vˆa.y, 1) d¯u.
o.
. c suy ra t`u. mˆe.nh d¯ˆe` “x ∈∅⇒ x ∈ A” l`a luˆon luˆon d¯´ung
(do “x ∈ ∅” l`a sai). 2) d¯u.
o
.
. c suy ra t`u. mˆe.nh d¯ˆe` “x ∈ A ⇒ x ∈ A” l`a luˆon luˆon
d¯´ung. Cuˆo´i c`ung 3) d¯u.
o
.
. c suy ra t`u. t´ınh d¯´ung cu’a mˆe.nh d¯ˆe` “(x ∈ A ⇒ x ∈
B ∧ x ∈ B ⇒ x ∈ C) ⇒ (x ∈ A ⇒ x ∈ C)”
1.2.2.3. Tˆa.p ho.
. p l˜uy th`u.
a: Cho X l`a mˆo.t tˆa.p ho.
. p. Tˆa.p l˜uy th`u.
a cu’a X, k´y
hiˆe.u P(X) hay 2X , l`a tˆa.p ho.
. p gˆo`m tˆa´t ca’ c´ac tˆa.p con cu’a X, t´u.
c l`a
P(X) = {A | A ⊂ X}.
Th´ı du. : 1) V´o.
i X = {a, b, c} th`ı ta c´o
P(X) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, X}.
2) P(∅) = {∅}, P({∅}) = {∅, {∅}}.
1.2.2.4. D- i
.nh ngh˜ıa: Hai tˆa.p A v`a B d¯u.
o.
. c go.i l`a b˘a`ng nhau, k´y hiˆe.u A = B,
nˆe´u A ⊂ B v`a B ⊂ A.
Th´ı du. : V´o.
i A = {1, 2, 3, 5, 6, 10, 15, 30} v`a B = {n ∈ N : n|30} th`ı ta c´o A = B.
1.2.3. C´ac ph´ep to´an tˆa.p ho.
. p:
1.2.3.1. D- i
.nh ngh˜ıa: Ho.
. p cu’a hai tˆa.p ho.
. p A v`a B, k´y hiˆe.u l`a A ∪ B (d¯o.c l`a
“A ho.
. p B”), l`a tˆa.p ho.
. p gˆo`m c´ac phˆa`n tu.
’ thuˆo.c ´ıt nhˆa´t mˆo.t trong hai tˆa.p ho.
. p
A, B, t´u.
c l`a
A ∪ B = {x | x ∈ A ∨ x ∈ B}.
Th´ı du. : 1) V´o.
i A = {a, b, c, d} v`a B = {c, d, e, f}, ta c´o A∪B = {a, b, c, d, e, f}.
2) V´o.
i A = {x ∈ N | x chia hˆe´t cho 2} v`a B = {x ∈ N | x chia hˆe´t cho 3},
ta c´o A ∪ B = {x ∈ N | x chia hˆe´t cho 2 ho˘a.c 3}.
1.2.3.2. D- i
.nh ngh˜ıa: Giao cu’a hai tˆa.p ho.
. p A v`a B, k´y hiˆe.u l`a A ∩ B (d¯o.c l`a
“A giao B”), l`a tˆa.p ho.
. p gˆo`m c´ac phˆa`n tu.
’ v`u.
a thuˆo.c A v`u.
a thuˆo.c B, t´u.
c l`a
A ∩ B = {x | x ∈ A ∧ x ∈ B}.
Hai tˆa.p ho.
. p d¯u.
o
.
. c go.i l`a r`o.
i nhau nˆe´u giao cu’a ch´ung l`a tˆa.p ho.
. p rˆo˜ng.
Th´ı du. : 1) V´o.
i A = {a, b, c, d} v`a B = {c, d, e, f}, ta c´o A ∩ B = {c, d}.
2) V´o.
i A = {x ∈ N | x chia hˆe´t cho 2} v`a B = {x ∈ N | x chia hˆe´t cho 3},
ta c´o A ∩ B = {x ∈ N | x chia hˆe´t cho 6}.
3) Tˆa.p ho.
. p c´ac sˆo´ h˜u.
u tı’ v`a tˆa.p ho.
. p c´ac sˆo´ vˆo tı’ l`a hai tˆa.p con r`o.
i nhau
cu’a tˆa.p ho.
. p R c´ac sˆo´ thu.
. c.
1.2.3.3. D- i
.nh ngh˜ıa: Hiˆe.u cu’a hai tˆa.p ho.
. p A v`a B, k´y hiˆe.u l`a A\B hay A−B,
l`a tˆa.p ho.
. p gˆo`m c´ac phˆa`n tu.
’ thuˆo.c A nhu.
ng khˆong thuˆo.c B, t´u.
c l`a
A \ B = {x | x ∈ A ∧ x /∈ B}.
14