Ch ng 4ươ
BI U DI N BÀI TOÁN B NG LOGIC VÀ CÁC PH NGỂ Ễ Ằ ƯƠ
PHÁP CH NG MINHỨ
Nh ta đã bi t, không th có ph ng pháp gi i quy t v n đ t ng quát choư ế ể ươ ả ế ấ ề ổ
m i bài toán. Có th ph ng pháp này phù h p cho bài toán này, nh ng l iọ ể ươ ợ ư ạ
không phù h p cho l p bài toán khác. ợ ớ Đi u này có nghĩa là khi nói t i m t bàiề ớ ộ
toán, ta ph i chú ý đ n ả ế ph ng pháp bi u di n nóươ ể ễ cùng v i các ớph ngươ
pháp tìm ki m trong không gian bài toán nh n đ cế ậ ượ .
1. Bi u di n bài toán nh không gian tr ng thái (có các chi n l c tìmể ễ ờ ạ ế ượ
ki m trên đ th bi u di n v n đ )ế ồ ị ể ễ ấ ề
2. Quy v các bài toán conề
3. Bi u di n v n đ nh logic hình th c (có các ph ng pháp suy di nể ễ ấ ề ờ ứ ươ ễ
logic)
....
và trong ph n này s trình bày ph ng pháp bi u di n v n đ nh logic hìnhầ ẽ ươ ể ễ ấ ề ờ
th c và các ph ng pháp gi i quy t v n đ trên cách bi u di n này. ứ ươ ả ế ấ ề ể ễ
Logic hình th c th ng dùng đ thu g n quá trình tìm ki m l i gi i.ứ ườ ể ọ ế ờ ả
Tr cướ khi gi i quy t v n đ , nh phân tích logic, có th ch ng t r ng m tả ế ấ ề ờ ể ứ ỏ ằ ộ
bài toán nào đó có th gi i đ c hay không?.ể ả ượ
Ngoài ra, các k t lu n logic r t c n ngay c trong cách ti p c n d aế ậ ấ ầ ả ế ậ ự
trên không gian tr ng thái và quy bài toán v bài toán con. Ch ng h n, trongạ ề ẳ ạ
các ph ng pháp d a trên không gian tr ng thái, các k t lu n logic dùng đươ ự ạ ế ậ ể
ki m tra m t tr ng thái nào đó có ph i là tr ng thái đích hay không?,....ể ộ ạ ả ạ
Ngoài ra, logic hình th c có th đ c s d ng đ gi i quy t nh ng bàiứ ể ượ ử ụ ể ả ế ữ
toán ch ng minh logic, ch ng h n nh ch ng minh m t kh ng đ nh nào đó làứ ẳ ạ ư ứ ộ ẳ ị
107
đúng khi bi t nh ng ti n đ ban đ u và các lu t suy di n. ế ữ ề ề ầ ậ ễ Đây là m t d ngộ ạ
quen thu c nh t và đ c các chuyên gia TTNT quan tâm ngay t đ u. ộ ấ ượ ừ ầ
Ví dụ
Ta có th dùng các bi u th c logic đ mô t m i quan h c a các thành ph nể ể ứ ể ả ố ệ ủ ầ
trong 1 tam giác nh sau:ư
1) a ∧ b ∧ c ⇒ p
2) b ∧ p ∧ c ⇒ a
3) a ∧ p ∧ c ⇒ b
4) a ∧ b ∧ p ⇒ c
5) S ∧ c ⇒ hc
6) a ∧ b ∧ C ⇒ c
7) a ∧ b ∧ C ⇒ S
8) a ∧ b ∧ c ∧ p ⇒ S
9) S ∧ hc ⇒ c
(Trong đó: a, b, c là ký hi u các c nh, A, B, C là ký hi u các góc t ng ng, pệ ạ ệ ươ ứ
là ký hi u n a chu vi, và hc là đ ng cao xu t phát t đ nh C c a tam giácệ ữ ườ ấ ừ ỉ ủ )
Gi s ta bi t các c nh a, b và m t góc C. ả ử ế ạ ộ Ta có th có k t lu n v đ ngể ế ậ ề ườ
cao hc không?
1. BI U DI N V N Đ NH LOGIC HÌNH TH CỂ Ễ Ấ Ề Ờ Ứ
1.1. Logic m nh đệ ề
Đây là ki u bi u di n tri th c đ n gi n nh t và g n gũi nh t đ i v i chúngể ể ễ ứ ơ ả ấ ầ ấ ố ớ
ta.
a) M nh đệ ề là m t kh ng đ nh, m t phát bi u mà giá tr c a nó ch có thộ ẳ ị ộ ể ị ủ ỉ ể
ho c là đúng ho c là sai.ặ ặ
Ví dụ
phát bi u "1+1=2" (có giá tr đúng)ể ị
phát bi u "Tr i m a" ể ờ ư
108
(Giá tr c a m nh đ không ch ph thu c vào b n thân m nh đ đó. Cóị ủ ệ ề ỉ ụ ộ ả ệ ề
nh ng m nh đ mà giá tr c a nó luôn đúng ho c sai b t ch p th i gianữ ệ ề ị ủ ặ ấ ấ ờ
nh ng cũng có nh ng m nh đ mà giá tr c a nó l i ph thu c vào th i gian,ư ữ ệ ề ị ủ ạ ụ ộ ờ
không gian và nhi u y u t khác quan khác. Ch ng h n nh m nh đ : "Conề ế ố ẳ ạ ư ệ ề
ng i không th nh y cao h n 5m v i chân tr n" là đúng khi trái đ t , còn ườ ể ả ơ ớ ầ ở ấ ở
nh ng hành tinh có l c h p d n y u thì có th sai.)ữ ự ấ ẫ ế ể
b) Bi u th c logicể ứ
- Ta ký hi u m nh đ b ng nh ng ch cái la tinh nh ệ ệ ề ằ ữ ữ ư a, b, c, ... và các ký hi uệ
này đ c ượ g i là bi n m nh đọ ế ệ ề
- Bi u th c logicể ứ đ c đ nh nghĩa đ quy nh sau:ượ ị ệ ư
•Các h ng logic (True, False) và các bi n m nh đ là các bi u th c logicằ ế ệ ề ể ứ
•Các bi u th c logic k t h p v i các toán t logic (phép tuy n (ể ứ ế ợ ớ ử ể ∨), phép
h i (ộ∧ ), ph đ nh (ủ ị ¬ , ~, ), phép kéo theo (⇒, →), phép t ng đ ngươ ươ
(⇔, ≡)) là các bi u th c logic.ể ứ
T c là n u E và F là các bi u th c logic thì E ứ ế ể ứ ∧ F, E ∨ F, E → F, E ≡ F cũng
là các bi u th c logicể ứ
Th t u tiên c a các phép toán logic:ứ ự ư ủ ¬, ∧, ∨, →, ≡
Ví d ụ M t s bi u th c logic:ộ ố ể ứ
1) True
2) ¬ p
3) p ∧ (p ∨ r)
.....
- Bi u th c logic d ng chu n: ể ứ ạ ẩ là bi u th c đ c xây d ng t các bi n m nhể ứ ượ ự ừ ế ệ
đ và các phép toán ề¬, ∧, ∨.
109
Ví dụp ∧ (¬ p ∨ r)
(Chúng ta đã t ng s d ng logic m nh đ trong ch ng trình r t nhi u l nừ ử ụ ệ ề ươ ấ ề ầ
(nh trong c u trúc l nh IF ... THEN ... ELSE) đ bi u di n các tri th cư ấ ệ ể ể ễ ứ
"c ng" trong máy tính ! )ứ
c) B ng chân tr (b ng chân lý) ả ị ả Dùng đ dánh giá giá tr c a bi u th cể ị ủ ể ứ
logic.
p q ¬p p ∨ q p ∧ q ¬p ∨ q p → q p ≡ q
T T F T T T T T
T F F T F F F F
F T T T F T T F
F F T F F T T T
Nh n xétậ
- M i bi u th c logic đ u có th chuy n v các bi u th c logic d ngọ ể ứ ề ể ể ề ể ứ ạ
chu n nh vào:ẩ ờ
p → q ≡ ¬p ∨ q
- N u có n bi n m nh đ trong bi u th c logic thì b ng chân tr s có 2ế ế ệ ề ể ứ ả ị ẽ n
tr ng h p khác nhau đ i v i các bi n m nh đ . ườ ợ ố ớ ế ệ ề
d) Đ ng nh t đúngồ ấ
M t đ ng nh t đúng là m t bi u th c logic luôn luôn có giá tr ộ ồ ấ ộ ể ứ ị True v i b tớ ấ
kỳ giá tr nào c a các bi n m nh đ trong bi u th c logic đó.ị ủ ế ệ ề ể ứ
Ví d ụ(Có th ki m tra b ng cách dùng b ng chân tr )ể ể ằ ả ị
1) p ∨ ¬ p
2) 0 → p
3) (p ∨ q) ∧ (¬p ∨ r) → q ∨ r
110
Ta th y r ng bi u th c có d ng VTấ ằ ể ứ ạ →VP luôn có giá tr True (T) v i m iị ớ ọ
giá tr c a a, b; ch có m t tr ng h p đ a ị ủ ỉ ộ ườ ợ ể →b có giá tr False (F) là a: True vàị
b: False. Nh v y, đ ch ng minh bi u th c 3) là m t đ ng nh t đúng, ta chư ậ ể ứ ể ứ ộ ồ ấ ỉ
c n ch ng minh n u b: F thì a: F, không có tr ng h p a: T và b: F. ầ ứ ế ườ ợ
Th t v y, gi s VP: F nghĩa là q: F và r: F. Xét 2 tr ng h p c a p:ậ ậ ả ử ườ ợ ủ
- N u p: T thì VT: Fế
- N u p: F thì VT: Fế
Do đó bi u th c 3) là m t đ ng nh t đúngể ứ ộ ồ ấ
Bài t pậ. Bi u th c nào trong s các bi u th c sau đây là đ ng nh t đúng?ể ứ ố ể ứ ồ ấ
1) p ∧ q ∧ r → p ∨ q
2) (p → q) → p
3) (( p → q ∧ (q → r)) → (p → r)
1.2. M t s lu t đ i s ộ ố ậ ạ ố
Sau đây là m t s đ ng nh t đúng th ng g pộ ố ồ ấ ườ ặ
a) Lu t ph n x (cho phép t ng đ ng):ậ ả ạ ươ ươ p ≡ p
b) Lu t giao hoánậ
-phép t ng đ ng: p ươ ươ ≡ p
-phép h i:ộp ∧ q ≡ q ∧ p
-phép tuy n: ểp ∨ q ≡ q ∨ p
c) Lu t b c c u:ậ ắ ầ
-phép kéo theo: (p → q) ∧ (q → r) → (p → r)
-phép t ng đ ng:ươ ươ (p ≡ q) ∧ (q ≡ r) → (p ≡ r)
d) Lu t k t h p:ậ ế ợ
-phép h i: ộp ∧ (q ∧ r) ≡ (p ∧ q) ∧ r
-phép tuy n:ểp ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
e) Lu t phân ph i:ậ ố
-phép ∧ trên phép ∨: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
111
