1. Podaj określenie wartościowania w KRZ i jego rozszerzenia na dowolne formuły. Podaj przykład wartościowania formuły w KRZ.
1. Wartości logiczne: 1 (prawda), 0 (fałsz).
2. Wartościowaniem nazywamy funkcję: w : V→{0,1}.
3. Funkcją logiczną nazywamy funkcję f : {0,1}n→{0,1}.
Określamy funkcje:
i
następująco:
x
y
0
1
4. Każde wartościowanie w : V→{0,1} rozszerzamy do funkcji : FOR→{0,1}, ( - wartość logiczna formuły A przy wartościowaniu w) następująco:
ŵ(p) = w(p) dla pÎV
ŵ (ØA) = f_(ŵ(A))
ŵ(AÙB) = fÙ(ŵ(A), ŵ(B))
ŵ(AÚB) = fÚ(ŵ(A),ŵ(B))
ŵ(A_B) = f_(ŵ(A),ŵ(B))
ŵ(A«B) = f«(ŵ(A),ŵ(B))
Przykład wartościowania:
A:
w: w(p) = 1, w(q) = 0, w(r) = 1,
2. Podaj określenia następujących pojęć w KRZ: spełnialność formuły i zbioru formuł przez wartościowanie, formuła spełniana, zbiór spełnialny.
Spełnialność formuły i zbioru formuł przez wartościowanie:
1. Wartościowanie w spełnia formułę A (oznaczenie: w |= A), jeżeli (A) = 1.
2. Wartościowanie w spełnia zbiór (oznaczenie w |= Γ) jeżeli (A) = 1 dla każdej formuły
Formułę A nazywamy spełnialną, jeżeli istnieje wartościowanie takie, że w |= A.
Zbiór formuł nazywamy spełnialnym, jeśli istnieje wartościowanie takie, że w |= Γ.
3. Omów wynikanie logiczne w KRZ. Podaj określenie logicznej reguły wnioskowania w KRZ i reguły rezolucji zdaniowej. Wykaż, że reguła rezolucji zdaniowej jest logiczną regułą wnioskowania.
Wynikanie logiczne:
Formuła A wynika ze zbioru formuł Γ w KRZ, jeżeli dla każdego wartościowania w zachodzi warunek:
Jeżeli w |= Γ, to w |= A.
Logiczna reguła wnioskowania:
Jeżeli ze zbioru formuł {A1,…,An} które będziemy nazywać przesłankami, wynika formuła A, którą będziemy nazywać wnioskiem, to schemat:
nazywamy logiczną regułą wnioskowania.
Literałem pozytywnym nazywamy dowolną zmienną zdaniową , a literałem negatywnym negację zmiennej zdaniowej . Literały oznaczamy L1,L2,…
Wtedy reguła rezolucji zdaniowej ma postać:
dla
Dowód, że reguł rezolucji zdaniowej jest logiczną regułą wnioskowania:
Założenie, że istnieje wartościowanie w spełniające obie przesłanki: w |= , w |= . Rozważmy dwa przypadki:
1. w(p)=1, wtedy , tzn. , stąd w(Li’)=1 dla pewnego . Zatem w spełnia wniosek w |= .
2. w(p)=0, wtedy istnieje takie, że w(Lj)=1. Zatem w spełnia wniosek w |= .
4. Podaj określenie derywacji klauzuli ze zbioru klauzul oraz refutacji zbioru klauzul w KRZ. Podaj przykład derywacji i refutacji.
Derywacją klauzuli A ze zbioru klauzul Σ nazywamy drzewo etykietowane (X, E, f) takie, że:
1. E jest zbiorem klauzul Σ.
2. dla każdego liścia x drzewa X, .
3. f(Λ) = A.
4. dla każdego wierzchołka x drzewa nie będącego liściem f(x) jest rezolwentą etykiet bezpośrednich potomków wierzchołka x.
Refutacja zbioru klauzul:
Derywację klauzuli pustej □ ze zbioru klauzul Σ nazywamy refutacją zbioru Σ.
Przykłady:
Derywacja:
, Σ ├RZ {q}
\ /
{q}
Refutacja:
\ / \ /
□
5. Uzasadnij algorytm sprawdzania tautologiczności formuł KRZ za pomocą rezolucji zdaniowej.
Algorytm:
Wejście: formuła A
Wyjście: odpowiedź tak, jeżeli formuła A jest tautologią KRZ, nie, w przeciwnym wypadku.
(1) bierzemy formułę B identyczną z ,
(2) sprowadzamy formułę B do koniunkcyjnej postaci normalnej
(3) KPN(B) przedstawiamy w postaci klauzulowej Σ(KPN(B)).
(4) Szukamy derywacji klauzuli pustej □ ze zbioru Σ(KPN(B)).
(5) Jeżeli klauzula pusta została otrzymana, to odpowiedź - TAK.
(6) Jeżeli algorytm zatrzymał się ze względu na brak możliwości stosowania reguły rezolucji, mamy odpowiedź - NIE.
Uzasadnienie:
Formuła A jest tautologią KRZ.
Fakt: równoważność: formuła A jest tautologią KRZ; formuła nie jest spełnialna,
Formuła nie jest spełnialna.
Fakt: równoważność warunków: w |= A; w |= KPN(A); w |= Σ(KPN(A)).
Formuła KPN() nie jest spełnialna.
Zbiór Σ(KPN()) nie jest spełnialny.
Tw.: równoważność warunków: Zbiór Σ nie jest spełnialny; Σ ├RZ □
Σ(KPN()) ├RZ □
Jeżeli zbiór Σ jest skończony, to istnieje algorytm sprawdzania, czy Σ ├RZ □.
6. Podaj określenie języka pierwszego rzędu oraz termów, formuł atomowych, formuł, zdań, termu bazowego i atomu bazowego.
Język pierwszego rzędu:
Symbole:
a) logiczne
...
Wujek_Misiek