1. Podaj określenie wartościowania w KRZ i jego rozszerzenia na dowolne formuły. Podaj przykład wartościowania formuły w KRZ.
Def. Wartościowanie.
1. Wartości logiczne : 1 (prawda), 0 (fałsz)
2. Wartościowaniem nazywamy funkcję w: V->{0, 1};
gdzie V = {p, q, r,...,p1,...,p’,...} - nieskończony, ale przeliczalny zbiór zmiennych zdaniowych
3. Funkcją logiczną nazywamy funkcję f: {0, 1}^n -> {0, 1}.
Określamy funkcje: f⌐:{0,1}->{0,1} i fᴧ, fv , f->, f<-> :{0,1}^2->{0,1} następująco:
x, y ,f⌐(x), fᴧ(x, y) ,fv(x, y) ,f->(x, y) f<->(x, y)
1,1,0,0
1,0,1,0
0,0,1,1
1,0,0,0
1,1,1,0
1,0,1,1
1,0,0,1
4. Każde wartościowanie w: V -> {0,1} rozszerzamy do funkcji ŵ FOR -> {0,1}, (ŵ(A) – 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))
ŵ(AvB) = fv(ŵ(A),ŵ(B))
ŵ(A->B) = f->(ŵ(A),ŵ(B))
ŵ(A<->B) = f<->(ŵ(A),ŵ(B))
Przykład 1.2. Wartościowanie formuł.
Formuła A: p -> q v r. Wartościowanie: w(p)=1, w(q)=0, w(r)=1.
ŵ(A) = ŵ(p-> q v r ) = f-> (ŵ(p), ŵ(q v r )) = f->(ŵ(p), f v (ŵ (q), ŵ (r))) = f->(w(p),f v (w(q), w(r))) = f->(1, f v (0,1)) = f-> (1,1) = 1
2. Podaj określenia następujących pojęć w KRZ: spełnialność formuły i zbioru formuł przez wartościowanie, formuła spełnialna, zbiór spełnialny. Wykaż, że następujące warunki są równoważne:
a) formuła A jest tautologią KRZ
b) formuła ( Ø A ) nie jest
spełnialna.
Def. Spełnianie 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 formuł G Ì FOR (ozn. w |= G ), jeżeli ŵ (A) = 1 dla każdej formuły A Î G.
Def. Spełnialność formuły i zbioru formuł.
1. Formułę A nazywamy spełnialną, jeżeli istnieje wartościowanie w takie, że w |= A.
2. Zbiór formuł G Ì FOR nazywamy spełnialnym, jeżeli istnieje wartościowanie w takie, że w |= G.
Def. Tautologia KRZ
Tautologią rachunku zdań nazywamy formułę A taką, że ŵ (A) = 1 dla każdego wartościowania w.
Fakt 1.1
Następujące warunki są równoważne:
b) formuła (ØA) nie jest spełnialna
Dowód faktu 1.1
a) należy udowodnić za pomocą tabeli wartościowania, że kadże wartościowanie daje prawdę
b) należy wskazać, że żadne wartościowanie nie spełnia ØA, zatem ØA nie jest spełnialna czyli A jest tautologią KRZ
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.
Def. Wynikanie logiczne.
Formuła A wynika ze zbioru formuł G w KRZ, jeżeli dla każdego wartościowania w zachodzi warunek: jeżeli w |= G, to w |= A.
Fakt 1.2.
a) formuła A wynika ze zbioru formuł G w KRZ
b) zbiór Gv (⌐A ) nie jest spełnialny.
Fakt 1.3.
a) formuła A wynika ze zbioru formuł {A1 , ..., An}
b) formuła A1 ᴧ ... ᴧ An -> A jest tautologią KRZ
Def. 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
A1
.
An
__
A
nazywamy logiczną regułą wnioskowania.
Def. Literały.
Literałem pozytywnym nazywamy dowolną zmienną zdaniową p Î V , a literałem negatywnym negację zmiennej zdaniowej ⌐p, pÎ V.
Literały oznaczamy: L1, L2, ....
Reguła rezolucji zdaniowej
{L1, L2, ..., Lm, p}
{L1’, L2’,…,Ln’,⌐ p}
__________________
{L1, L2, ..., Lm,L1’,L2’, ..., Ln’} n,m >= 0
Fakt 1.6.
Reguła rezolucji zdaniowej jest logiczną regułą wnioskowania, tzn. wniosek reguły rezolucji zdaniowej wynika ze zbioru przesłanek
tej reguły.
Dowód
Zał., że istnieje wartościowanie w spełniające obie przesłanki: w |= {L1, L2,..., Lm, p} w |= {L1’, L2’,..., Ln’, ⌐p}
Rozważmy dwa przypadki:
1. w(p)=1, wtedy w(⌐p)=0, tzn w| nie=(⌐p), stąd w(L’i)=1 dla pewnego 1=< i =<n. Zatem w spełnia wniosek w |= {L1’, L2’,..., Ln’ }
2. w(p)=0, wtedy istnieje 1=< j =<m takie, że w(Lj )=1. Zatem w spełnia wniosek w |= {L1, L2,..., Lm }
4. Podaj określenie derywacji klauzuli ze zbioru klauzul oraz refutacji zbioru klauzul w KRZ. Podaj przykład derywacji i refutacji.
...
Wujek_Misiek