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
Tài liệu đang bị lỗi
File tài liệu này hiện đang bị hỏng, chúng tôi đang cố gắng khắc phục.
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