Metoda tablic analitycznych
1
Tablice analityczne: pojęcie drzewa
Drzewa są specjalnym rodzajem grafów. W uproszczeniu, graf to zbiór wierzchołków
połączonych krawędziami. Na gruncie teorii mnogości graf opisujemy jako parę postaci
G = 〈 W, E〉,
w której
• W jest niepustym zbiorem, zaś
• E jest dwuczłonową relacją zachodzącą między elementami zbioru W.
Elementy zbioru W nazywamy wierzchołkami lub węzłami, zaś elementy zbioru E nazywamy krawędziami.
2
Tablice analityczne: pojęcie drzewa
PRZYKŁAD. Drzewem jest w szczególności następujący graf (struktura):
(G1)
Poziom 1.
A
Poziom 2.
B
C
Poziom 3.
D
E F G
Poziom 4.
H I J
3
Tablice analityczne: pojęcie drzewa
(G2)
Poziom 1.
1
Poziom 2.
2
Poziom 3.
3
Poziom 4.
4 9
Poziom 5.
5 10 12
Poziom 6.
6 11 13 14
Poziom 7.
7 8
■
4
Tablice analityczne: pojęcie drzewa
Krawędzie w drzewie symbolizują następstwo kolejnych węzłów w strukturze drzewa.
Wszystkie węzły połączone z danym węzłem, leżące na jakimkolwiek niższym poziomie,
nazywamy potomkami (następnikami) tego węzła, przy czym węzły leżące na następnym
poziomie nazywamy dziećmi tego węzła; np. potomkami węzła A są wszystkie pozostałe węzły,
jego dziećmi są tylko B i C, dziećmi węzła C są F i G.
Węzeł, który nie ma dzieci nazywamy liściem; liśćmi są D, E, H, I, J.
Węzeł, który posiada dwoje dzieci nazywamy rozgałęzionym; węzłami rozgałęzionymi są A, B,
C, G.
Węzeł jest rodzicem dla każdego swego dziecka (liście nie są więc rodzicami). Każdy węzeł ma
dokładnie jednego rodzica. Wyjątkiem jest korzeń drzewa, który nie ma rodzica; jest nim węzeł
A występujący na poziomie 1.
5
Tablice analityczne: pojęcie drzewa
Przez ścieżkę w drzewie rozumie się ciąg węzłów spełniający warunek: każdy węzeł poprzedni
jest rodzicem węzła następnego. W drzewie istnieje dokładnie jedna ścieżka pomiędzy węzłem a
korzeniem. Najdłuższą ścieżkę, od korzenia do liścia, nazywa się gałęzią. Gałęzią w drzewie
(G1) jest np. ścieżka wyznaczona przez węzły: A, C, F, H.
Liczba krawędzi w ścieżce to jej długość. Liczba o 1 większa określa poziom węzła. Poziomy
drzewa definiuje się przez indukcję:
• poziom pierwszy to zbiór jednoelementowy, złożony z korzenia drzewa;
• poziom ( k + 1) to zbiór wszystkich dzieci węzłów poziomu k.
Część wspólną wszystkich gałęzi danego drzewa nazywamy pniem tego drzewa; w przypadku
grafu (G1) jego pień złożony jest tylko z korzenia, zaś w przypadku grafu (G2) jego pień
stanowią węzły 1, 2 i 3.
6
Tablice analityczne: pojęcie drzewa
Drzewo nazywamy binarnym (dwójkowym), jeśli każdy węzeł ma co najwyżej dwoje dzieci (tj.
ma dokładnie dwoje dzieci bądź ma jedno dziecko, bądź nie ma dzieci); podane tu przykłady
drzew to właśnie drzewa binarne. Ściślejsza definicja drzewa binarnego ma następującą postać:
Drzewem binarnym nazywamy dowolny układ T = 〈 W, E, f 〉, gdzie
• 〈 W, E〉 jest grafem,
• f jest funkcją przyporządkowującą każdemu węzłowi w ∈ W liczbę całkowitą dodatnią, zwaną
poziomem węzła w,
który spełnia następujące cztery warunki:
• istnieje dokładnie jeden węzeł poziomu 1, tzw. korzeń drzewa;
• każdy węzeł nie będący korzeniem ma dokładnie jednego rodzica;
• każdy węzeł ma co najwyżej dwoje dzieci;
• dla dowolnych w, v ∈ W, jeżeli v jest dzieckiem w, to f( v) = f( w) + 1.
7
Tablice analityczne: pojęcie drzewa
Rozważać będziemy tzw. drzewa znakowane. Przez drzewo znakowane (elementami ze zbioru
L) rozumiemy parę 〈 D, g〉, gdzie D jest drzewem, a g jest funkcją przyporządkowującą węzłom drzewa D elementy zbioru L. Zwykle L będzie pewnym zbiorem formuł. Znakowanie drzew formułami pozwala w precyzyjny sposób mówić o wystąpieniach danej formuły w drzewie.
8
Metoda tablic analitycznych jest motywowaną semantycznie metodą dowodową (a więc jest ona
metodą syntaktyczną). Proponowane są pewne syntaktyczne reguły przekształcania wyrażeń –
eliminacji poszczególnych spójników. Przekształcenie „zakończone i udane” uważa się za
dowód formuły. Z uwagi na twierdzenie o pełności KRZ, dowody posiadają wyłącznie
tautologie KRZ. Dowody mają postać drzew.
Trzy najważniejsze cechy metody tablic analitycznych to:
• apagogiczność;
• analityczność;
• algorytmiczność (w przypadku KRZ, a w przypadku KRP – półalgorytmiczność).
9
Apagogiczność polega na tym, że omawiana metoda jest metodą nie wprost: sprowadza się do
wykluczania zajścia pewnych sytuacji – wykluczenia, że badana formuła ma wartość 0 przy
jakimkolwiek wartościowaniu zmiennych zdaniowych.
Analityczność metody polega na tym, że przy ustalaniu własności semantycznych formuł (np.
wykluczaniu, że maja wartość 0) odwołujemy się jedynie do własności semantycznych
podformuł (oraz negacji podformuł) badanej formuły.
Tablica analityczna jest to skończone drzewo dwójkowe, którego węzłami są formuły języka
KRZ. Prócz tego każda formuła A będąca węzłem tego drzewa ma uzasadnienie dla swej
obecności na drzewie i może być
• przodkiem
• potomkiem pewnej formuły B, uzyskanym w wyniku zastosowania do B jednej z reguł
eliminacji poszczególnych spójników.
10
Mamy dwa rodzaje reguł:
• reguły listowe (ang. listing rules), które rozkładając daną formułę każą jej składniki umieścić
na jednej gałęzi jeden pod drugim;
• reguły rozgałęziające (ang. branching rules), które rozkładając daną formułę każą jej
składniki umieścić na oddzielnych gałęziach drzewa (rozgałęziają drzewo).
Dygresja. Metoda tablic analitycznych jest też znana pod następującymi nazwami: metoda drzew
semantycznych, metoda tabel analitycznych, metoda tablic semantycznych, metoda tablic
Smullyana. ■
11
Tablice analityczne: reguły tworzenia drzew semantycznych
(~~) ~~ A (∧) A ∧ B
(∨) A ∨ B
(→) A → B (≡) A ≡ B
A A
A B
~ A B A ~ A
B B ~ B
(~∧) ~( A ∧ B) (~∨) ~( A ∨ B) (~→) ~( A → B) (~≡) ~( A ≡ B)
~ A ~ B ~ A A
A ~ A
~ B ~ B ~ B B
12
Tablice analityczne: reguły tworzenia drzew semantycznych
Przykład tworzenia drzewa:
p ∨ ( q ∧ r) → ( p ∨ q) ∧ ( p ∨ r) 1; →
(1 l) ~( p ∨ ( q ∧ r)) 2; ~∨
(1 p) ( p ∨ q) ∧ ( p ∨ r) 4; ∧
(2 g) ~ p
(4 g) p ∨ q 5; ∨
(2 d) ~( q ∧ r) 3; ~∧
(4 d) p ∨ r 6; ∨
(3 l) ~ q
(3 p) ~ r
(5 l) p (5 p) q
(6 l) p (6 p) r (6 l) p (6 p) r
13
Tablice analityczne: reguły tworzenia drzew semantycznych
Zasady numeracji:
• z prawej strony formuły zapisujemy numer wykonywanego kroku i oznaczenie reguły, z
której korzystamy;
• z lewej strony formuły (w nawiasie) zapisujemy numer kroku, w którym ona powstała; jeśli
w danym kroku powstaje więcej niż jedna formuła, to do numerów dodajemy litery
oznaczające ich położenie w drzewie, np. (1 l) oznacza formułę powstałą w pierwszym kroku
znajdującą się po lewej stronie gałęzi, a (2 g) oznacza formułę powstałą w drugim kroku
znajdującą się u góry;
• gdy tę samą formułę rozkładamy na różnych gałęziach drzewa, to powstające formuły
otrzymują te same numery (o ile nie prowadzi to do niejednoznaczności).
14
Tablice analityczne: tautologie
Przypomnijmy:
Formuła A jest tautologią KRZ wtw jest ona prawdziwa przy dowolnym wartościowaniu
występujących w niej zmiennych zdaniowych.
Aby stwierdzić, że formuła A jest tautologią należy wykluczyć możliwość, że ma ona wartość 0
przy jakimś wartościowaniu zmiennych.
Innymi słowy:
Aby stwierdzić, że formuła A jest tautologią należy wykluczyć możliwość, że (~ A) ma wartość 1
przy jakimś wartościowaniu zmiennych.
15
Tablice analityczne: tautologie
Gałąź drzewa nazywamy
• zamkniętą, jeśli zawiera co najmniej jedną formułę zarówno ze znakiem negacji jak i bez;
gałęzie zamknięte oznaczamy przez ×;
• otwartą, w przeciwnym przypadku (tj. gdy gałąź nie zawiera żadnej zmiennej zarówno ze
znakiem negacji jak i bez); gałęzie otwarte oznaczamy przez ○.
Drzewo, którego wszystkie gałęzie są zamknięte nazywamy drzewem zamkniętym.
Dana formuła jest tautologią KRZ wtw wszystkie gałęzie drzewa rozpoczynającego się jej zaprzeczeniem są zamknięte (innymi słowy: wtw drzewo mające w korzeniu zaprzeczenie
tej formuły jest drzewem zamkniętym). W przeciwnym przypadku nie jest tautologią.
Dygresja: Dowolne drzewo mające w korzeniu zaprzeczenie formuły A i zamknięte możemy
nazwać dowodem formuły A. ■
16
Tablice analityczne: tautologie
Budując drzewo stosujemy następujące zasady:
(Z1) Sprawdzaj po każdym kroku, czy możesz zamknąć którąś z gałęzi. Jeśli tak, to oznacz ją ×
i nie przedłużaj.
(Z2) Najpierw stosuj reguły nie powodujące rozgałęzienia drzewa, a dopiero potem reguły
powodujące rozgałęzienie.
Przykłady:
1.
( p → q) ∧ (~ p → q) → q
2.
( p → q) → ( p ∨ r → q ∧ r)
17
Tablice analityczne: tautologie
~[( p → q) ∧ (~ p → q) → q] 1; ~→
(1 g) ( p → q) ∧ (~ p → q) 2; ∧
(1 d) ~ q
(2 g) p → q 3; →
(2 d) ~ p → q 4; →
(3 l) ~ p
(3 p) q
(4 l) ~~ p 5; ~~ (4 p) q
×
(5) p
×
×
Badana formuła jest tautologią (wszystkie gałęzie drzewa zostały zamknięte).
18
~[( p → q) → ( p ∨ r → q ∧ r)] 1; ~→
(1 g) p → q 3; →
(1 d) ~( p ∨ r → q ∧ r) 2; ~→
(2 g) p ∨ r 4; ∨
(2 d) ~( q ∧ r) 5; ~∧
(3 l) ~ p (3 p) q
(4 l) p (4 p) r (4 l) p (4 p) r
× (5 l) ~ q (5 p) ~ r (5 l) ~ q (5 p) ~ r (5 l) ~ q (5 p) ~ r
○ × × ○ × ×
19
Tablice analityczne: tautologie
A zatem, badana formuła nie jest tautologią. Gałęzie otwarte (oznaczone przez ○) zawierają
następujące ciągi zmiennych bądź zanegowanych zmiennych:
~ p, ~ q, r
p, q, ~ r.
Oznacza to, że dla następujących wartościowań zmiennych formuła przyjmuje wartość 0:
p q r
0 0 1
1 1 0
20
Tablice analityczne: wynikanie logiczne
Metodę tablic analitycznych możemy wykorzystać do sprawdzenia, czy dana formuła A wynika
logicznie ze zbioru formuł X. Przypomnijmy:
Formuła A wynika logicznie ze zbioru formuł X wtw A jest prawdziwa przy każdym
wartościowaniu, przy którym prawdziwe są wszystkie formuły tworzące zbiór X.
Aby sprawdzić, czy dana formuła A wynika ze zbioru formuł X postępujemy następująco:
•
zakładamy, że wszystkie formuły ze zbioru X są prawdziwe;
•
zakładamy, że formuła A jest fałszywa (czyli ~ A jest prawdziwa);
•
budujemy drzewo o pniu zawierającym wszystkie formuły ze zbioru X oraz formułę ~ A.
Gałęzie otwarte w otrzymanym drzewie odpowiadają wartościowaniom, przy których wszystkie
formuły ze zbioru X są prawdziwe, a formuła A jest fałszywa. A zatem:
•
jeśli drzewo ma choć jedna gałąź otwartą, to formuła A nie wynika ze zbioru formuł X;
•
jeśli drzewo ma wszystkie gałęzie zamknięte, to formuła A wynika ze zbioru formuł X.
21
Tablice analityczne: wynikanie logiczne
Przykład: Czy { p → q, r → s, p ∨ r}╞═ ~ q → s ?
p → q 2; →
r → s 3; →
p ∨ r 4; ∨
~(~ q → s) 1; ~→
(1 g) ~ q
(1 d) ~ s
(2 l) ~ p
(2 p) q
(3 l) ~ r (3 p) s
×
(4 l) p (4 p) r ×
× ×
Ponieważ wszystkie gałęzie drzewa są zamknięte, wynikanie zachodzi. ■
22
Tablice analityczne: wynikanie logiczne
Czy { p → q, ~ p}╞═ ~ q ?
p → q 2; →
~ p
~~ q 1; ~~
(1) q
(2 l) ~ p
(2 p) q
○ ○
Ponieważ nie wszystkie gałęzie drzewa są zamknięte, wynikanie nie zachodzi. ■
23