Bài giảng Toán rời rạc - Chương I: Cơ sở logic
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Nguyeãn Anh Thi
Phöông phaùp quy naïp
toaùn hoïc
2017
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Chöông 1
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Cô sôû logic
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Noäi dung
Nguyeãn Anh
Thi
Noäi dung
1 Chöông 1: Cô sôû logic
Meänh ñeà
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Pheùp tính meänh ñeà
Daïng meänh ñeà
Phöông phaùp quy naïp
toaùn hoïc
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Meänh ñeà
Nguyeãn Anh
Thi
Ñònh nghóa
Meänh ñeà toaùn hoïc (goïi taét laø meänh ñeà) laø moät khaúng ñònh coù
giaù trò chaân lyù xaùc ñònh (ñuùng hoaëc sai, nhöng khoâng theå vöøa
ñuùng vöøa sai).
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Ví duï
Phöông phaùp quy naïp
toaùn hoïc
•
•
•
"Soá 25 chia heát cho 5" laø moät meänh ñeà ñuùng.
"Maët trôøi xoay quanh traùi ñaát" laø moät meänh ñeà sai.
"Baïn bao nhieâu tuoåi?" khoâng phaûi laø moät meänh ñeà toaùn
hoïc vì noù laø moät caâu hoûi khoâng coù giaù trò chaân lyù xaùc ñònh
(ñuùng hay sai).
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Ta thöôøng kyù hieäu caùc meänh ñeà baèng caùc chöõ caùi: P, Q, R . . .
Chöông 1: Cô
sôû logic
Ñònh nghóa
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Meänh ñeà phöùc hôïp laø meänh ñeà ñöôïc xaây döïng töø caùc meänh ñeà
khaùc nhôø lieân keát chuùng laïi baèng caùc lieân töø (vaø, hay,
neáu...thì...) hoaëc traïng töø khoâng.
Phöông phaùp quy naïp
toaùn hoïc
Ví duï
Neáu toâi raûnh roãi, thì toâi seõ ñi chôi.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Chaân trò cuûa meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Moät meänh ñeà chæ coù theå ñuùng hoaëc sai, khoâng theå vöøa ñuùng
vöøa sai. Khi meänh ñeà P ñuùng, ta noùi P coù chaân trò ñuùng, ngöôïc
laïi ta noùi P coù chaân trò sai. Chaân trò ñuùng vaø chaân trò sai seõ
ñöôïc kyù hieäu laàn löôït laø 1, hay Ñ, hay T (True), vaø 0, hay S, hay
F (False).
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Muïc ñích cuûa pheùp tính meänh ñeà laø nghieân cöùu chaân trò cuûa
moät meänh ñeà phöùc hôïp töø chaân trò cuûa caùc meänh ñeà ñôn giaûn
hôn vaø caùc pheùp noái nhöõng meänh ñeà naøy theå hieän qua lieân töø
hoaëc traïng töø "khoâng".
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Caùc pheùp noái
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
Pheùp phuû ñònh: phuû ñònh cuûa meänh ñeà P ñöôïc kyù hieäu
bôûi ¬P (ñoïc laø khoâng P). Chaân trò cuûa ¬P laø 0 neáu chaân trò
cuûa P laø 1 vaø ngöôïc laïi. Ta coù baûng sau, goïi laø baûng chaân
trò cuûa pheùp phuû ñònh.
Phöông phaùp quy naïp
toaùn hoïc
P
0
1
¬P
1
0
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Ví duï
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
10 laø soá chaün.
Phuû ñònh: 10 khoâng laø soá chaün.
Phöông phaùp quy naïp
toaùn hoïc
•
4 > 10
Phuû ñònh: 4 ≤ 10
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
•
Pheùp noái lieàn: meänh ñeà noái lieàn cuûa hai meänh ñeà P, Q
ñöôïc kyù hieäu bôûi P ∧ Q (ñoïc laø P vaø Q). Chaân trò cuûa P ∧ Q
laø 1 neáu caû P laãn Q ñeàu coù chaân trò 1. Trong caùc tröôøng
hôïp khaùc P ∧ Qcoù chaân trò 0. Noùi caùch khaùc pheùp noái lieàn
ñöôïc xaùc ñònh bôûi baûng chaân trò sau:
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp
toaùn hoïc
P
0
0
1
1
Q
0
1
0
1
P ∧ Q
0
0
0
1
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Ví duï
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
•
Hoâm nay trôøi ñeïp vaø traän boùng ñaù seõ haáp daãn.
15 chia heát cho 3 vaø 14 chia heát cho 5.
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
•
Pheùp noái rôøi: meänh ñeà noái rôøi cuûa hai meänh ñeà P, Q laø
meänh ñeà kyù hieäu bôûi P ∨ Q (ñoïc laø P hay Q). Chaân trò cuûa
P ∨ Q laø 0 neáu caû hai P, Q cuøng chaân trò 0. Trong caùc
tröôøng hôïp khaùc, P ∨ Q coù chaân trò 1. Noùi caùch khaùc pheùp
noái rôøi ñöôïc xaùc ñònh bôûi baûng chaân trò sau
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp
toaùn hoïc
P
0
0
1
1
Q
0
1
0
1
P ∨ Q
0
1
1
1
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Ví duï
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
•
Ba ñang ñoïc baùo hay meï ñang xem tivi.
2 laø soá nguyeân toá hay laø soá chaün.
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
•
Pheùp loaïi tröø: meänh ñeà loaïi tröø cuûa hai meänh ñeà P, Q laø
meänh ñeà kyù hieäu bôûi P Y Q (ñoïc laø P hoaëc Q). Chaân trò cuûa
P Y Q laø 0 neáu caû hai P, Q coù cuøng chaân trò 0 hay 1. Ta coù
baûng chaân trò,
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
P
0
0
1
1
Q
0
1
0
1
P Y Q
Phöông phaùp quy naïp
toaùn hoïc
0
1
1
0
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Ví duï
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
•
15 laø soá chaün hoaëc laø soá leû.
7 laø soá nguyeân toá hoaëc khoâng phaûi laø soá nguyeân toá.
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
•
Pheùp keùo theo: meänh ñeà neáu P thì Q ñöôïc kyù hieäu laø
P → Q (cuõng ñoïc laø P keùo theo Q, hay P laø ñieàu kieän ñuû
cuûa Q, hay Q laø ñieàu kieän caàn cuûa P. Ta coù baûng chaân trò
cuûa pheùp keùo theo:
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
P
0
0
1
1
Q
0
1
0
1
P → Q
Phöông phaùp quy naïp
toaùn hoïc
1
1
0
1
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Ví duï
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
•
•
Neáu trôøi möa thì toâi seõ ôû nhaø xem tivi.
Neáu 2 > 3 thì 3 > 4.
Neáu 2 < 3 thì 3 > 4.
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
•
Pheùp keùo theo hai chieàu: meänh ñeà neáu P thì Q vaø ngöôïc
laïi ñöôïc kyù hieäu bôûi P ↔ Q (cuõng ñoïc laø P khi vaø chæ khi
Q, P neáu vaø chæ neáu Q, P laø ñieàu kieän caàn vaø ñuû ñeå coù Q).
Ta coù baûng chaân trò cuûa pheùp keùo theo hai chieàu:
Noäi dung
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
P
0
0
1
1
Q
0
1
0
1
P ↔ Q
Phöông phaùp quy naïp
toaùn hoïc
1
0
0
1
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Pheùp tính meänh ñeà
Nguyeãn Anh
Thi
Noäi dung
Chöông 1: Cô
sôû logic
Ví duï
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
•
•
•
2 = 4 khi vaø chæ khi 2 + 1 = 0.
6 chia heát cho 3 khi vaø chæ khi 5 laø soá nguyeân toá.
Paris laø thuû ñoâ cuûa nöôùc Phaùp khi vaø chæ khi Quy Nhôn laø
thuû ñoâ cuûa Vieät Nam.
Phöông phaùp quy naïp
toaùn hoïc
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Daïng meänh ñeà
Nguyeãn Anh
Thi
Ñònh nghóa
Noäi dung
Daïng meänh ñeà laø moät bieåu thöùc ñöôïc xaây döïng töø:
Chöông 1: Cô
sôû logic
•
•
Caùc meänh ñeà (caùc haèng meänh ñeà).
Caùc bieán meänh ñeà p, q, . . . töùc laø caùc bieán laáy giaù trò laø
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
caùc meänh ñeà naøo ñoù.
Phöông phaùp quy naïp
toaùn hoïc
•
Caùc pheùp toaùn ¬, ∧, ∨, Y, →, ↔ vaø daáu ñoùng môû ngoaëc
"()".
Ví duï
E(p, q, r) = (p ∧ q) ∨ ((¬r → P)) laø moät daïng meänh ñeà trong
ñoù p, q, r laø caùc bieán meänh ñeà coøn P laø moät haèng meänh ñeà.
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp toaùn hoïc
Noäi dung
Chöông 1: Cô sôû logic
Baøi giaûng moân
hoïc Toaùn Rôøi
Raïc
Daïng meänh ñeà
Nguyeãn Anh
Thi
Ñònh nghóa
Noäi dung
Baûng chaân trò cuûa daïng meänh ñeà E(p, q, r) laø baûng ghi taát caû
caùc tröôøng hôïp chaân trò coù theå xaûy ra ñoái vôùi daïng meänh ñeà E
theo chaân trò cuûa caùc bieán meänh ñeà p, q, r. Neáu coù n bieán,
baûng naøy seõ coù 2n doøng, chöa keå doøng tieâu ñeà.
Chöông 1: Cô
sôû logic
Meänh ñeà
Pheùp tính meänh ñeà
Daïng meänh ñeà
Vò töø vaø löôïng töø
Quy taéc suy dieãn
Phöông phaùp quy naïp
toaùn hoïc
Ví duï
Laäp baûng chaân trò cuûa nhöõng daïng meänh ñeà sau:
E(p, q) = ¬(p ∧ q) ∧ p
E(p, q, r) = (p ∨ q) ∧ r
Nguyeãn Anh Thi
Baøi giaûng moân hoïc Toaùn Rôøi Raïc
Tải về để xem bản đầy đủ
64 trang
15/01/2024
6760
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương I: Cơ sở logic", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_i_co_so_logic.pdf
