- Trang chủ >>
- Đại cương >>
- Toán rời rạc
TOÁN RỜI RẠC 1
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.41 MB, 99 trang )
LOGO
TOÁN R I R C
Ph m Th B o
email:
www.math.hcmus.edu.vn/~ptbao/TRR/
N i dung
N i dung: g m 5 ph n
- C s logic
- Phép đ m
- Quan h
- Hàm Bool
-
th
2
Tài li u tham kh o
Tài li u tham kh o
1. ThS. Nguy n Duy Nh t, ThS. Nguy n
V n Phong, PGS.TS inh Ng c Thanh,
Toán r i r c.
2. TS. Tr n Ng c H i, Toán r i r c.
3. GS.TS Nguy n H u Anh, Toán r i r c,
Nhà xu t b n giáo d c.
4. Rosen, Discrete Mathematics and Its
Applications, 6th edition, 2007.
3
Ki m tra
Ki m tra
Ki m tra gi a k :
Ki m tra cu i k :
i m th ng:
30%
70%
5-10%
4
C s Logic
Ch
ng I: C
s
logic
- M nh đ
- D ng m nh đ
- Qui t c suy di n
- V t ,l
ng t
- T ph p
- Ánh x
- Qui n p toán h c
5
C s Logic
I. M nh đ
1.
nh ngh a: M nh đ là m t kh ng đ nh có giá tr chân lý
xác đ nh, đúng ho c sai.
Câu h i, câu c m thán, m nh l nh… không là m nh đ .
Ví d :
- m t tr i quay quanh trái đ t
- 1+1 =2
- Hôm nay tr i đ p quá ! (ko là m nh đ )
- H c bài đi ! (ko là m nh đ )
- 3 là s ch n ph i không? (ko là m nh đ )
6
C s Logic
I. M nh đ
Ký hi u: ng
i ta dùng các ký hi u P, Q, R… đ ch m nh đ .
Chân tr c a m nh đ :
M t m nh đ ch có th đúng ho c sai, không th
đ ng th i v a đúng v a sai. Khi m nh đ P đúng ta
nói P có chân tr đúng, ng c l i ta nói P có chân tr
sai.
Chân tr đúng và chân tr sai s đ c ký hi u l n
l t là 1 (hay ,T) và 0 (hay S,F)
7
C s Logic
I. M nh đ
Ki m tra các kh ng đ nh sau có ph i là m nh đ không?
- Paris là thành ph c a M .
- n là s t nhiên.
- con nhà ai mà xinh th !
- 3 là s nguyên t .
- Toán r i r c là môn b t bu c c a ngành Tin h c.
- B n có kh e không?
- x2 +1 luôn d
ng.
8
C s Logic
I. M nh đ
2. Phân lo i: g m 2 lo i
a. M nh đ ph c h p: là m nh đ đ c xây d ng t các
m nh đ khác nh liên k t b ng các liên t (và, hay, khi
và ch khi,…) ho c tr ng t “không”.
b. M nh đ s c p (nguyên th y): Là m nh đ không th
xây d ng t các m nh đ khác thông qua liên t ho c
tr ng t “không”.
Ví d :
- 2 không là s nguyên t
- 2 là s nguyên t (s c p)
- N u 3>4 thì tr i m a
- An đang xem phim hay An đang h c bài
- Hôm nay tr i đ p và 1 +1 =3
9
C s Logic
I. M nh đ
3. Các phép toán: có 5 phép toán
a. Phép ph đ nh: ph đ nh c a m nh đ P đ c ký
hi u là ¬P hay (đ c là “không” P hay “ph đ nh
c a” P).
B ng chân tr :
Ví d :
- 2 là s nguyên t
Ph đ nh: 2 không là s nguyên t
- 1 >2
Ph đ nh : 1≤ 2
10
C s Logic
I. M nh đ
b. Phép n i li n (h i): c a hai m nh đ P, Q đ c kí hi u
b i P ∧ Q (đ c là “P và Q”), là m nh đ đ c đ nh b i :
P ∧ Q đúng khi và ch khi P và Q đ ng th i đúng.
B ng chân tr
Ví d :
- 3>4 và Tr n H ng
o là v t ng
- 2 là s nguyên t và là s ch n
- An đang hát và u ng n c
11
C s Logic
I. M nh đ
c. Phép n i r i (tuy n): c a hai m nh đ P, Q đ c kí
hi u b i P ∨ Q (đ c là “P hay Q”), là m nh đ đ c đ nh
b i : P ∨ Q sai khi và ch khi P và Q đ ng th i sai.
B ng chân tr
Ví d :
- π >4 hay π >5
- 2 là s nguyên t hay là s ch n
12
C s Logic
I. M nh đ
Ví d
- “Hôm nay, An giúp m lau nhà và r a chén”
- “Hôm nay, cô y đ p và thông minh ”
- “Ba đang đ c báo hay xem phim”
13
C s Logic
I. M nh đ
d. Phép kéo theo: M nh đ P kéo theo Q c a hai m nh đ
P và Q, kí hi u b i P → Q (đ c là “P kéo theo Q” hay
“N u P thì Q” hay “P là đi u ki n đ c a Q” hay “Q là
đi u ki n c n c a P”) là m nh đ đ c đ nh b i:
P → Q sai khi và ch khi P đúng mà Q sai.
B ng chân tr
14
C s Logic
I. M nh đ
Ví d :
- N u 1 = 2 thì Lenin là ng
i Vi t Nam
- N u trái đ t quay quanh m t tr i thì 1 +3 =5
- π >4 kéo theo 5>6
- π < 4 thì tr i m a
- N u 2+1=0 thì tôi là ch t ch n
15
c
C s Logic
I. M nh đ
e. Phép kéo theo hai chi u: M nh đ P kéo theo Q và
ng c l i c a hai m nh đ P và Q, ký hi u b i P ↔ Q
(đ c là “P n u và ch n u Q” hay “P khi và ch khi Q” hay
“P là đi u ki n c n và đ c a Q”), là m nh đ xác đ nh
b i:
P ↔ Q đúng khi và ch khi P và Q có cùng chân tr
B ng chân tr
16
C s Logic
I. M nh đ
Ví d :
- 2=4 khi và ch khi 2+1=0
- 6 chia h t cho 3 khi và chi khi 6 chia h t cho 2
- London là thành ph n
c Anh n u và ch n u thành ph
HCM là th đô c a VN
- π >4 là đi u ki n c n và đ c a 5 >6
17
C s Logic
II. D ng m nh đ
1. nh ngh a: là m t bi u th c đ c c u t o t :
- Các m nh đ (các h ng m nh đ )
- Các bi n m nh đ p, q, r, …, t c là các bi n l y giá tr là
các m nh đ nào đó
- Các phép toán ¬, ∧, ∨, →, ↔ và d u đóng m ngo c ().
Ví d :
E(p,q) = ¬(¬p ∧q)
F(p,q,r) = (p → q) ∧ ¬(q ∧r)
18
C s Logic
II. D ng m nh đ
B ng chân tr c a d ng m nh đ E(p,q,r): là b ng ghi t t c
các tr
ng h p chân tr có th x y ra đ i v i d ng m nh đ
E theo chân tr c a các bi n m nh đ p, q, r.
N u có n bi n, b ng này s có 2n dòng, ch a k dòng
tiêu đ .
Ví d :
E(p,q,r) =(p ∨q) →r . Ta có b ng chân tr sau
19
C s Logic
II. D ng m nh đ
M nh đ E(p,q,r) =(p ∨q) →r theo 3 bi n p,q,r có b ng chân
tr sau
p
q
r
p∨q
(p ∨q) →r
0
0
0
0
1
0
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
20
C s Logic
II. D ng m nh đ
21
C s Logic
II. D ng m nh đ
Bài t p: L p b ng chân tr c a nh ng d ng m nh đ sau
E(p,q) = ¬(p ∧q) ∧p
F(p,q,r) = p ∧(q ∨r) ↔ ¬q
22
C s Logic
II. D ng m nh đ
2. T ng đ ng logic: Hai d ng m nh đ E và F đ c g i là
t ng đ ng logic n u chúng có cùng b ng chân tr (hay
m nh đ A↔B là h ng đúng).
Ký hi u E ⇔ F (hay E
Ví d
F).
• ¬(p ∧ q) ⇔ ¬p ∨ ¬ q
nh lý: Hai d ng m nh đ E và F t
và ch khi E↔F là h ng đúng.
23
ng đ
ng v i nhau khi
C s Logic
II. D ng m nh đ
H qu logic: F đ c g i là h qu logic c a E n u E→F là
h ng đúng.
Ký hi u E ⇒ F
Ví d : ¬(p ∨ q) ⇒ ¬ p
Trong phép tính m nh đ ng i ta không phân bi t nh ng
m nh đ t ng đ ng logic v i nhau. Do đó đ i v i nh ng
d ng m nh đ có công th c ph c t p, ta th ng bi n đ i đ
nó t ng đ ng v i nh ng m nh đ đ n gi n h n.
th c hi n các phép bi n đ i ta s d ng qui t c thay th
và quy lu t logic.
24
C s Logic
II. D ng m nh đ
Qui t c thay th : Trong d ng m nh đ E, n u ta thay th bi u
th c con F b i m t d ng m nh đ t ng đ ng logic thì d ng
m nh đ thu đ c v n còn t ng đ ng logic v i E.
Ví d . ¬(p ∧ q) ∨ r⇔ (¬p ∨ ¬ q) ∨ r
25
