i
i
“694-Hafner-naslov” — 2009/6/19 — 14:26 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 12 (1984/1985)
Številka 1
Strani 29–31
Izidor Hafner:
METODA SEMANTIČNIH TABEL ZA REŠEVANJE
LOGIČNIH NALOG
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/12/694-Hafner.pdf
c© 1984 Društvo matematikov, fizikov in astronomov Slovenije
c© 2009 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
METODA SEMANTIČNIHTABEL
ZA REŠEVANJE LOGIČNIHNALOG
V tem sestavku se bomo seznanili s preprosto metodo reševanja log i čn ih
na log, kakršna je na primer naslednja uganka :
Andrej, Boris in Cene vsak dan kosijo v restavraciji , naročijo pa pečenko
ali šunko.
1. Če je Andrej šunko, potem je Boris pečenko.
2. Šunko naroči Andrej ali Cene, vendar pa ne oba.
3 . Oba, Boris in Cene , ne jesta hkrati pečenke.
Kdo je lahko včeraj jedel šunko, danes pa pečenko?
Preden se lotimo te uqanke -Ibralec jo lahko za vajo reši sam), bomo uved -
li osnovne izjavne povezave. Definirali jih bomo tako , da bomo povedal i, kako
je resničnost sestavljene izjave odvisna od resničnosti njenih delov:
ime povezave simbolični zapis resnica neresnica
negacija ""'A če jeA če jeA
neresnična res n i č na
konjunkcija A A8 če sta A in če je vsaj ena
8 resnični izmed izjav A in
8 neresnična
disjunkcija AV8 če je vsaj ena če sta obe
izmed izjav A izjaviA in
in 8 resnična 8 neresnični
implikacija A =>8 čejeA če je A
neresnična resnična in 8
ali pa 8 neresnična
resnična
ekvivalenca A~8 če staA in 8 če je Aresnična
obe resnični in 8 neresnična
ali obe ne- ali:
resnični če je Aneresnična
in 8 resnična
Prvi de l reševanja naloge je sestavljen iz prevajanja v logično simboliko, to
je iz logične stavčne analize.
Označimo posamezne enostavne izjave takole:
43
z "A" izjavo"Andrej je (danes) šunke."
z "8" izjavo "Boris je (danes) šunke. "
s "C" izjavo "Cene je (danes) šunke."
Potem lahko izjavo
"Andrej je (danes) pečenko ." zaznamujemo" ~A", ker je Andrej šunko
ali pečenko, vendar ne obojega isti dan. Podobno velja tudi za Borisa in Cene-
ta. Lahko bi seveda uvedli tri dodatne črke za izjave "oo. je pečenko.", vendar
se bomo držali naslednjega napotka : Uporabljaj čim manj črk.
Pogoj 1 prevedemo z
(a) A ~ -'8
Ta pogoj namreč izključuje možnost, da bi And rej jedel šunko (da je izja-
va A resnična) in da bi hkrati tudi Boris jedel šunko (in da je hkrati izjava 8
resnična) .
Pogoj 2 pravi , da je Andrej šunko natanko tedaj. kadar je Cene ne naroči,
torej
Pogoj 3 pravi , da ni res, da oba (Cene in Boris) hkrati jesta pečenko. To
pomeni, da je v danem dnevu vsaj eden ne naroči, torej je vsaj eden šunko :
(1') 8 V C
Seveda bi pogoj 3 lahko prevedli tudi kot
(1") .....( -. 8 1\ .....C)
vendar bi s tem kršili naslednji napotek:
Prevodi naj bodo čim bolj enostavni.
Mimogrede opazimo, da velja De Morganov zakon
8 V C ~ ..., ( ..... 8 1\ -, C)
Sedaj smo pred naslednjo nalogo:
pri kakšnih vrednostih enostavnih izjav A , 8 in C so izpolnjeni (resnični)
pogoji (al. (~) in (1')?
Da bi bil izpolnjen pogoj (1'), mora biti resnična vsaj ena izmed izjav 8
oziroma C. Da bi bil izpolnjen pogoj (~l. imamo dve možnosti : (1) da sta A
in ..., C obe resnični ali (2) da sta A in -, Cobe neresnični in zato izjavi
..., A in C resn ični. Da bi bil pogoj (o) izpolnjen, sta dve možnosti: da A
44
ni resnična (da je -.A resnična) ali da je --'8 resnična.
Zapišimo vse kombinacije resničnih izjav :
pogoj (1)
pogoj (2)
pogoj (3)
dani pogoji
(12) -'A }
(13) C
(18) '""\AI (19)-'8
}
(1) A => -'8
(2)A~'""\C
(3) 8VC
(4) 8 J (5) C
(6) A (8) --A (10) A
m--c (9)C (l1)--'C
(14) --Al (15) --8 (16) --Al (17) -. X
X X X
Veja (1), (2), (3), (5), (10), (11) vsebuje protislovje, namreč zahtevo po
resničnosti obeh izjav C in -. C, zato smo jo označili z X (mrtva veja) in je
nismo nadaljevali.
Ko smo upoštevali še tretji pogoj, smo dobili še nadaljnje mrtve veje. Pre-
ostale pa vsebujejo naslednje možnosti :
8, -'A, G
G, -'A
G, """"'lA, -'8
veja (1), (2), (3), (4), (8), (9), (16)
veja (1), (2), (3), (5), (12), (13), (18)
veja (1), (2), (3), (5), (12), (13), (19)
Vse pa vključujejo zahtevo po resničnosti izjav
Torej:
Gin -'A Ceneje (vedno) šunko.
Andrej je (vedno) pečenko.
medtem ko sta za 8 obe možnosti odprti. Boris j~ lahko eno ali drugo.
Analiza pogojev, kot smo jo naredili, se imenuje semantična tabela. Iz nje
lahko razberemo vse možnosti, ki izpolnjujejo dane pogoje. Namesto "seman-
tična tabela" bi lahko rekli tudi "semantičnodrevo. H
Drugačen vrstni red upoštevanja pogojev nam bo dal drugačno semantično
tabelo:
(1)A=> 8
(2)A~ C
(3) 8 V C
(4)A
(5) ..... C
(6) --. A
mc } pogoj (2)
(8) --A
)(.
(9) -'8
(12) 8 I (13) C
)( X
(10)""A I(11)-'8
(14) 81 (15) C (16) 81 (17) C
X
pogoj (1)
pogoj (3)
45
Neprotislovne veje vselej vsebujejo -'A in C.
Algoritem semantičnih tabel ima za vhod neko množico izjav (za katere
želimo, da so resnične), A 1,A 2 , ••• ,An .
Te izjave zapišemo eno za drugo v tabelo. Nato tabelo razširimo tako, da
naredimo naslednje:
A
(a) Označimo za mrtve tiste veje, ki vsebujejo protislovne zahteve, to je,
v njih sepojavlja neka izjava in njena negacija.
(b) Odkljukamo tiste točke, v katerih nastopajo le enostavne izjave ali
njihove negacije.
(c) Končamo, če so vse veje mrtve.
B
(a) Poiščemo vejo, ki ni označena za mrtvo in vsebuje neodkljukano
točko.
(b) Izberemo izjavo v neodkljukani točki.
(c) Razširimo vse žive veje, ki vsebujejo to točko in to točko odkljukamo.
(d) Končamo, če ni nobene žive veje z neodkljukano točko.
(e) Vrnemo se na točko A.
To, da smo določeno točko odkljukali, pomeni, da smo upoštevali pogoj.
ki je zapisan v tej točki; razen seveda, ko pridemo do enostavnih izjav oziroma
njihovih negacij. ki jih ne moremo naprej analizirati. Takšen pogoj pa moramo
upoštevati na vseh živih vejah, ki to točko vsebujejo. Ko smo upoštevali vse
pogoje, se lahko zgodi , da:
- končamo v A (cl, to je tako , da so vse veje označene za mrtve. Tedaj
je začetna množica pogojev protislovna .
- končamo v B (d). Veje, ki niso označene za mrtve, vsebujejo seznam
enostavnih izjav ali njihovih negacij. Če so te izjave resnične, so resnične tudi
dane izjave Al, ... , An.
Vsaka takšna veja nam da kakšno tako možnost.
Sedaj želimo pokazato, da iz množice izjav
{ A ~ B, B ~ (C V D). ...,C, A }
sledi izjava D. To pomen i, da je nemogoče, da so vse izjave iz te množice res-
nične, da pa je hkrati D neresnična, to je, -.... Dresnična . Semantična tabela
za množico
{ A ~ B, B ~ (C V D). ...., C, A, ...,D }
se mora zaključiti s samimi mrtvimi vejami:
46
(1) A = 8
(2) 8 = (C v Dl
(3) ...c
(4) A
(5) -'0
(6) --A (7)8
(9) C vox (8) -'8
x (10) C
X
I(11) :
Bve
1
1
1
O
1
1
1
O
1 1 1 O O
1 1 O O 1
1 O 1 1 O
1 O O 1 1
10 1 1 I 1 1
O 1 O 1 O
10 O 1\ 1 1
O O O 1 O
Druga metoda, s katero bi rešili problem, je metoda resničnih tabel. Za
prvo nalogo imamo osem kombinacij za logične vrednosti enostavnih izjav.
Nato izračunamo logične vrednosti pogojev
ABe A =-'B
Obkrožimo t iste nabore, za katere so vsi trije pogoji resn ič ni (imajo vred-
nost 1). A je neresni č n a, C pa re sn i čna izjava.
Tretja možnost je sklepanje :
Rec imo, da je Andrej šunko . Potem je Bori s pečenko. Zahteva 3 prav i, da
je Cene šunko . Skratka - Andrej in Cene oba jesta šunke, to pa je v prot islovju
s pogojem 2.
Torej je Andrej pečenko. Iz dr ugega pogoja sledi , da Cene je šunke. Tretji
pogoj je avtomatično izpolnjen .
Razlike med temi tremi metodam i so nasled nje : metodi semant ičnih in
resn ičnostnih tabel bosta vedno dali rezultat; sta torej mehanični metod i, ki
ju lahko sprogramiramo na ra čuna lniku. Metoda resn i č nostn i h tabe l kratko-
ma lo i zčrpa vse možnost i za vrednosti enostavnih izjav.
Pri metodi semantičnih tabel lahko z dobrim vrstnim redom upoštevanja
pogojev (ta izbir a je kreativni del metode) nekatere veje hitro zaključimo in s
tem izločimo marsikateri nabor logičnih vrednosti enostavnih izjav.
Metodi st a si inve rzni. Pri resničnostnih tabelah izhajamo iz vrednosti
enostavn ih izjav in izračunavamo vrednosti danih pogojev. Pri semantičn ih ta -
belah Izhajamo iz resničnost i pogojev in iščemo vrednosti enostavnih izjav.
Pri sklepanju pa je večk rat po t rebna kakš na "i deja".
47
NALOG E: 
1. ZapiSi 9e druge semantiEne tabele za na3o IogiCno nalogo in poiECi ta- 
belo, k i  vsebuje nairnanj izjavl 
2. PokaZi, da so nasldnje izjave resniEne za vse vrednosti osnovnih izjav 
(semantiena tabela za negacije takjnih izjav vsebuje le rnrtve veje) : 
(a)  A =+ (15 * A )  
(b) (A'B)  =+ ( (A=$(B=cl )"  (A'CII 
(c) A* (3 * C4 AB1) 
(d) (A *C) *(I6 * C )  3 ( ( A  v B )  *C)) 
3. Janez, Peter in Tomai  so osurnljeni prestopka. Na sodigEu so dali na- 
slednje izjave: 
Janet: Peter je kriv, Tomat ni kriv. 
Peter: c e  je Janez kriv, potem je kriv tudi Tomaf. 
Tomai:  Jaz nisem kriv, toda vsaj eden od drugih dveh je kriv. 
(a) A l i  so vse tri izjave lahko hkrati  resnitne? 
(b) Izjava enega sledi iz  izjave drugega. 0 katerih govorimo? 
(c) Ce so vsi tri je nedolrni, kdo je I qa l?  
(d) Ce so vse izjave resniEne, kdo je kriv, kdo ne? 
(e) Kdo je kriv, Ce krivi lasejo, nedolini pa govore resnico? 
4. Upoaevaj naslednje IogiCne zakone: 
(a) Ce velja A * D ,  potern lahko povsod A nadomestirno z D. 
{b) A * 3 * 7 ?  * -A 
( c ) A = * B w q A  y 3 
lz pogojev n a b  zaCetne naloge odpravi A in nato rei i  natogo na razliCne 
nadine. 
bidor Hafner