manhmanh_08
New Member
Download miễn phí Giáo trình Toán ứng dụng trong tin học
Giảsửcó một đàn chim bồcâu bay vào chuồng. Nếu sốchim nhiều hơn sốngăn
chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩnhiên là có
thểáp dụng cho các đối tượng không phải là chim bồcâu và chuồng chim.
Mệnh đề(Nguyên lý
: Nếu có k+1 (hay nhiều hơn) đồvật được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồvật.
Chứng minh:Giảsửkhông có hộp nào trong k hộp chứa nhiều hơn một đồvật. Khi đó tổng
sốvật được chứa trong các hộp nhiều nhất là bằng k. điều này trái giảthiết là có ít nhất k + 1
vật.
Nguyên lý này thường được gọi là nguyên lý Dirichlet, mang tên nhà toán học người
đức ởthếkỷ19. Ông thường xuyên sửdụng nguyên lý này trong công việc của mình.
Ví dụ1:
a) Trong bất kỳmột nhóm 367 người thếnào cũng có ít nhất hai người có ngày sinh nhật
giống nhau bởi vì chỉcó tất cả366 ngày sinh nhật khác nhau.
b) Trong kỳthi học sinh giỏi, điểm bài thi được đánh giá bởi một sốnguyên trong khoảng từ
0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dựthi đểcho chắc chắn tìm được hai học
sinh có kết quảthi nhưnhau?
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
cho 4.c) Hình töù giaùc naøy khoâng phaûi laø hình chöõ nhaät maø cuõng khoâng phaûi laø hình thoi.
d) Neáu An khoâng ñi laøm ngaøy mai thì seõ bò ñuoåi vieäc.
e) Moïi tam giaùc ñeàu coù caùc goùc baèng 60o.
1.5- Cho bieát chaân trò cuûa caùc m eänh ñeà sau:
a) pi = 2 vaø toång caùc goùc cuûa moät tam giaùc baèng 180o.
b) pi = 3,1416 keùo theo toång caùc goùc cuûa moät tam giaùc baèng 170o.
c) pi = 3 keùo theo toång caùc goùc cuûa moät tam giaùc baèng 170o.
d) Neáu 2 > 3 thì nöôùc soâi ôû 100oC.
e) Neáu 3 < 4 thì 4 < 3.
f) Neáu 4 < 3 thì 3 < 4.
1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc
Bieân soaïn: Tröôøng Sôn 11
1.6- Giaû söû P vaø Q laø hai meänh ñeà nguyeân thu ûy sao cho P → Q sai. Haõy xaùc ñònh
chaân trò cuûa caùc meänh ñeà sau: (Kí hieäu ¬P laø phuû ñònh cuûa P)
a) P ∧ Q b) ¬ P ∨ Q c) Q → P.
1.7- Goïi P, Q, R laø caùc meänh ñeà sau:
P: ABC laø moät tam giaùc caân. Q: ABC laø moät tam giaùc ñeàu.
R: Tam giaùc ABC coù 3 goùc baèng nhau.
Haõy vieát laïi caùc meänh ñeà sau theo ngoân ngöõ thoâng thöôøng:
a) Q → P b) ¬ P → Q
c) P ∧ ¬ Q d) R → P
1.8- Coù bao nhieâu caùch ñaët daáu "( )" khaùc nhau vaøo daïng meänh ñeà ¬ p ∨ q ∨ r. Laäp
baûng chaân trò cho töøng tröôøng hôïp.
1.9- Laäp baûng chaân trò cho caùc daïng meänh ñeà sau vaø chæ ra caùc haèng ñuùng:
a) ¬ p → (p ∨ q) b) ¬ p → (¬ q ∨ r)
c) (p ∧ q) → ¬ p d) (p ∨ r) → (r ∨ ¬ p)
e) (p → q) ∨ (q → p) f) (p ∨ ¬ q) ∧ (¬ p ∨ q)
g) (p → ¬ q) ∨ (q → ¬ p) h) ¬ (¬ p ∧ ¬ q)
1.10- Ch o bieát q u y lu aä t lo g ic n aø o ñ aõ ñ ö ôï c aù p d uï n g tr o n g moã i b ö ôù c t ö ô n g ñ ö ô n g s a u :
Bieåu thöùc Quy luaät logic
a) [(p ∨ q) ∧ (p ∨ ¬ q)] ∨ q Luaät phaân phoái
≡ [p ∨ (q ∧ ¬ q)] ∨ q Luaät baøi trung (luaät pt buø)
≡ (p ∨ 0) ∨ q Luaät trung hoøa
≡ p ∨ q
b) ¬ (p ∨ q) ∨ [(¬ p ∧ q) ∨ ¬ q] . . . . . . . . . . . . . . . . . . . . . (1)
≡ ¬ (p ∨ q) ∨ [¬ q ∨ (¬ p ∧ q)] . . . . . . . . . . . . . . . . . . . . . (2)
≡ ¬ (p ∨ q) ∨ [(¬ q ∨ ¬ p) ∧ (¬ q∨ q)] . . . . . . . . . . . . . . . . . . . . . (3)
≡ ¬ (p ∨ q) ∨ [(¬ q ∨ ¬ p) ∧ 1] . . . . . . . . . . . . . . . . . . . . . (4)
≡ ¬ (p ∨ q) ∨ (¬ q ∨ ¬ p) . . . . . . . . . . . . . . . . . . . . . (5)
≡ ¬ (p ∨ q) ∨ ¬ (q ∧ p) . . . . . . . . . . . . . . . . . . . . . (6)
≡ ¬ [(p ∨ q) ∧ (q ∧p)] . . . . . . . . . . . . . . . . . . . . . (7)
≡ ¬ [(q ∧p) ∧(p ∨ q)] . . . . . . . . . . . . . . . . . . . . . (8)
≡ ¬ [q ∧[p ∧(p ∨ q)]] . . . . . . . . . . . . . . . . . . . . . (9)
≡ ¬ (q ∧ p)
c*) C/minh: p→ (q → r) ≡ p ∧ q→ r ; (p→ q) ∧ [¬q ∧ (r ∨ ¬q)] ≡ ¬ (q ∨ p)
1.12- Haõy ñieàn meänh ñeà thích hôïp vaøo choã troáng ñeå cho caùc suy luaän sau ñaây theo
phöông phaùp khaúng ñònh vaø phuû ñònh laø ñuùng:
a) Neáu xe cuûa Minh khoâng khôûi ñoäng ñöôïc thì anh phaûi kieåm tra bugi.
Maø xe cuûa Minh khoâng khôûi ñoäng ñöôïc
Suy ra ..............................................
b) Neáu Haø laøm baøi ñuùng thì Haø ñöôïc ñieåm cao.
Maø Haø khoâng ñöôïc ñieåm cao
Suy ra ..............................................
c) Neáu chieàu nay Minh ñaù boùng thì Minh khoâng ñöôïc xem Tivi.
Maø ...................................................
Vaäy Minh khoâng ñaù boùng chieàu nay.
1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc
Bieân soaïn: Tröôøng Sôn 12
1.13- Cho bieát suy luaän naøo trong caùc suy luaän sau laø ñuùng vaø qui taéc suy luaän naøo ñaõ ñöôïc söû duïng?
a) Ñieàu kieän ñuû ñeå Caûng SG thaéng traän laø ñoái thuû ñöøng gôõ laïi vaøo phuùt cuoái
Maø Caûng SG ñaõ thaéng traän
Vaäy ñoái thuû cuûa Caûng SG khoâng gôõ laïi vaøo phuùt cuoái
b) Neáu Minh giaûi ñöôïc baøi toaùn thöù tö thì em ñaõ noäp baøi tröôùc giôø quy ñònh
Maø Minh ñaõ khoâng noäp baøi tröôùc giôø quy ñònh
Vaäy Minh khoâng giaûi ñöôïc baøi toaùn thöù tö.
c) Neáu laõi suaát giaûm thì soá ngöôøi göûi tieát kieäm seõ giaûm
Maø laõi suaát ñaõ khoâng giaûm
Vaäy soá ngöôøi göûi tieát kieäm khoâng giaûm
d) Neáu ñöôïc thöôûng cuoái naêm Haø seõ ñi Ñaø Laït
Neáu ñi Ñaø Laït Haø seõ thaêm Suoái vaøng
Do ñoù neáu ñöôïc thöôûng cuoái naêm Haø seõ thaêm Suoái Vaøng.
1.14- Xeùt suy dieãn:
[p ∧ (p → q) ∧ (s ∨ r) ∧ (r → ¬ q)] → s
Cho bieát caùc böôùc suy luaän sau ñaõ söû duïng caùc quy taéc, qui luaät naøo?
Böôùc Quy taéc suy luaän
p giaû thieát
p → q giaû thieát
∴q tam ñoaïn luaän (Kí hieäu ∴laø keát luaän)
hay ¬¬ q . . . . . . . . . . (1)
maø r → ¬ q . . . . . . . . . . (2)
∴¬ r . . . . . . . . . . (3)
maø s ∨ r . . . . . . . . . . (4)
hay ¬ r → s . . . . . . . . . . (5)
∴s . . . . . . . . . . (6)
1.15- Xeùt suy luaän sau:
(¬ p ∨ q) → r
r → (s ∨ t)
¬ s ∧ ¬ u
¬ u → ¬ t
∴ p
Cho bieát caùc quy taéc, quy luaät naøo ñaõ söû duïng caùc böôùc sau:
Böôùc Quy taéc suy luaän
¬ s ∧ ¬ u . . . . . . . . . . . . . (1)
∴¬ u . . . . . . . . . . . . . (2)
maø ¬ u → ¬ t . . . . . . . . . . . . . (3)
∴¬ t . . . . . . . . . . . . . (4)
maø ¬ s . . . . . . . . . . . . . (5)
neân ¬ s ∧ ¬ t . . . . . . . . . . . . . (6)
hay ¬ (s ∨ t) . . . . . . . . . . . . . (7)
maø r → s ∨ t . . . . . . . . . . . . . (8)
∴¬ r . . . . . . . . . . . . . (9)
maø (¬ p ∨ q) → r . . . . . . . . . . . . . (10)
∴¬ (¬ p ∨ q) . . . . . . . . . . . . . (11)
hay p ∧ ¬ q . . . . . . . . . . . . . (12)
∴p . . . . . . . . . . . . . (13)
1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc
Bieân soaïn: Tröôøng Sôn 13
1.16- Haõy kieåm tra caùc suy luaän sau, suy luaän naøo laø ñuùng / sai ? (∴kyù hieäu keát luaän)
a) p → q b) p → q c) p → (q → r)
¬ q r → ¬ q ¬ q → ¬ p
¬ r r p
∴¬ (p ∨ r) ∴¬ p ∴¬ r
d) p ∧ q e ) p → (q → r) f) p ∨ q
p → (r ∧ q) p ∨ s ¬ p ∨ r
r → (s ∨ t) t → q ¬ r
¬ s ¬ s
∴q
∴t ∴¬ r → ¬ t
1.17- Xeùt caùc vò töø:
p(x): "x ≤ 5"
q(x): "x+3 chaün"
Trong ñoù x laø moät bieán nguyeân. Tìm chaân trò cuûa caùc meänh ñeà sau:
a) p(1) b) q(1) c) ¬ p(2)
d) q(3) e) p(6) ∨ q(6) f) ¬ (p(-1) ∨ q(-1))
1.18- Xeùt vò töø p(x): "x2 - 3x + 2 = 0". Cho bieát chaân trò cuûa caùc meänh ñeà sau:
a) p(0) b) p(1) c) p(2)
d) ∃x, p(x) e) ∀x, p(x)
1.19- Xeùt vò töø theo hai bieán nguyeân lôùn hôn 0:
p(x, y): "x laø öôùc cuûa y"
Haõy xaùc ñònh chaân trò cuûa caùc meänh ñeà sau:
a) p(2, 3) b) p(2, 6) c) ∀y, p(1, y)
d) ∀x, p(x, x) e) ∀y, ∃x, p(x, y) f) ∃y∀x, p(x, y)
g) ∀x∀y, (p(x, y) ∧ p(y, x)) → (x = y)
h) ∀x∀y∀z, (p(x, y) ∧ p(y, z)) → p(x, z)
1.20- Haõy chöùng minh caùc coâng thöùc sau:
a) 02 + 11 + … + n2 =
6
)1n2)(1n(n ++ , ∀n∈ N
b) 03 + 13 + … + n3 =
4
)1n(n 22 + , ∀n∈ N
c) 1.2.3 + 2.3.4 + … + n(n + 1)(n + 2) = ( )
4
3n)2n)(1n(n +++ , ∀n∈ N
d) ( )( )
( )
( )( )2n1n4
3nn
2n1nn
1
4.3.2
1
3.2.1
1
++
+
=
++
+++ ⋯ , ∀n∈ N
e) 1.1! + 2.2! + … + n.n! = (n + 1)! - 1 , ∀n∈ N
f) ( ) ( )!1n
11
!1n
n
!3
2
!2
1
+
−=
+
+++ ⋯ , ∀n∈ N
g) (1 + a)n ≥ 1 + na, ∀n∈ N, a> -1.
h) 2n > n ; ∀n∈ N.
i) 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1.
1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc
Bieân soaïn: Tröôøng Sôn 14
HÖÔÙNG DAÃN VAØ ÑAÙP SOÁ
1.1 Caâu a, c, f : laø meänh ñeà; Caâu b, d, e : khoâng phaûi laø meänh ñeà.
1.2 a/ P ∧ Q b/ ¬ P ∧ Q c/ P ∨ (¬ Q ∧ ¬ P)
d/ P ⇒ ¬ Q e/ (P ∧ ¬ Q) ∨ (¬ P ∧ ¬ Q)
1.3 a/ P ∧ R ∧¬ Q b/ P ∧ Q ∧¬ (Q ∧ R) c/ ¬ (R ∧ ¬ P) ≡ ¬ R ∨ P
d/ ¬ ((R∨ Q) ∧¬ P) e/ ¬ Q ∧ ¬ R ∧ P
1.4 a/ Khoâng ñuùng laø ngaøy mai neáu trôøi möa hay trôøi laïnh thì toâi seõ khoâng ra ngoaøi.
hay : ngaøy mai duø trôøi möa hay trô...