JC WSEZ w A
odzi
Wykład 12
Treść wykładu
Klasyczny rachunek zdań
1) Wartościowanie klasyczne
2) Metoda matrycowa
1
JC WSEZ w A
odzi
Tautologie klasycznego rachunku zdań
Pod koniec Wykładu 11, podana została definicja tautologii
klasycznej. Przypomnijmy:
Formuły, które są schematami wyłącznie zdań
prawdziwych nazywane sÄ… tautologiami (klasycznego
rachunku zdań).
Zbiór tautologii klasycznego rachunku zdań jest zbiorem
tych wszystkich formuł, które przy dowolnym
wartościowaniu przyjmują wyróżnioną wartość 1.
Co to jest i na czym polega wartościowanie?
Aby odpowiedzieć na to pytanie, zacznijmy od przykładu.
Wez
my pod uwagÄ™ nazwÄ™ kwadrat. Nazwa ta oznacza
figurę płaską, która posiada pewne własności, np. ma
wszystkie kąty proste i wszystkie boki równej długości.
Nazwa kwadrat, jako wyrażenie językowe, oznacza więc
obiekt, który posiada wyżej wymienione cechy. Graficznie
relację nazwa - obiekt można by wyrazić w następujący
sposób.
2
JC WSEZ w A
odzi
kwadrat nazwa, wyrażenie językowe
oznacza
obiekt
Mamy tu do czynienia z pewnego rodzaju relacjÄ…
(oznaczania), zachodzącą pomiędzy wyrażeniem
językowym, a obiektem. W klasycznym rachunku zdań nie
operujemy nazwami (przynajmniej w takim sensie jak
ilustruje to diagram), rolę zaś  obiektów odniesienia
pełnią wartości logiczne. Rozważmy kolejny przykład.
Bolesław Chrobry był pierwszym królem Polski.
3
JC WSEZ w A
odzi
Powstaje pytanie, czy wyrażenie językowe: Bolesław
Chrobry był pierwszym królem Polski oznacza wyłącznie
obiekt (w tym przypadku będący następstwem wyobraz
ni
twórczej Jana Matejki)? Czy w podanym zdaniu mówi się
o czymś więcej?
Bolesław Chrobry był pierwszym królem Polski.
?
Możemy, co prawda, mówić o Bolesławie Chrobrym lub o
pierwszym królu Polski, lecz nie wskażemy, przez analogię
do kwadratu, takiego obiektu jak Bolesław Chrobry był
pierwszym królem Polski.
W podanym przykładzie rolę  obiektów pełnić będą
elementy ze zbioru wartości logicznych.
Bolesław Chrobry był pierwszym królem Polski.
{prawda, fałsz}
4
JC WSEZ w A
odzi
Oznaczmy zdanie Bolesław Chrobry był pierwszym królem
Polski przez p, prawdę jako 1, zaś fałsz przez 0.
p
{1, 0}
Zdaniu p przypiszemy dokładnie jedną wartość logiczną:
prawdÄ™, bÄ…dz
fałsz, co oznacza, że zdanie p jest albo
prawdziwe, albo fałszywe. W klasycznym rachunku zdań
każde zdanie podlega ocenie logicznej. Niebieska strzałka
wskazuje symbolicznie przypisanie dokładnie jednej z
dwóch wartości logicznych zdaniu p. Przypisanie wartości
logicznej zdaniu staje się możliwe dzięki definicji funkcji
wartościowania w klasycznym rachunku zdań.
Funkcja wartościowania w krz
Oznaczmy przez v funkcję wartościowania w klasycznym
rachunku zdań (w skrócie: krz), zaś przez For zbiór
wszystkich wyrażeń sensownych krz (tj. zbiór wszystkich
formuł krz).
5
JC WSEZ w A
odzi
FunkcjÄ™ v: For Ò! {0,1} nazywamy klasycznym
wartoÅ›ciowaniem, jeÅ›li dla dowolnych formuÅ‚ Ä…, ²
(należących do zbioru For) zachodzą następujące
równoważności:
v(<"Ä…) = 1 Ô! v(Ä…) = 0
v(Ä… '" ²) = 1 Ô! v(Ä…) = 1 i v(²) = 1
v(Ä… (" ²) = 1 Ô! v(Ä…) = 1 lub v(²) = 1
v(Ä… ²) = 1 Ô! v(Ä…) = 0 lub v(²) = 1
v(Ä… "! ²) = 1 Ô! v(Ä…) = v(²) = 1 lub v(Ä…) = v(²) = 0
Każde klasyczne wartościowanie jest jednoznacznie
wyznaczone przez przyporządkowanie wartości 1 oraz 0
zmiennym zdaniowym.
Warunki jakie musi speÅ‚nić funkcja v: For Ò! {0,1}, aby być
klasycznym wartościowaniem, często przedstawiane są w
postaci tzw. tabelek prawdziwościowych (zob. Wykład 2).
Przypomnijmy w tym miejscu raz jeszcze:
Zdanie Ä… nazywamy tautologiÄ… klasycznego rachunku
zdań, o ile zdanie ą jest zawsze prawdziwe, tj. przy
dowolnym wartościowaniu zawsze przyjmuje wartość 1.
6
JC WSEZ w A
odzi
Metoda matrycowa
Sprawdzając, czy dane wyrażenie klasycznego rachunku
zdań (tzw. formuła) jest tautologią klasyczną, możemy
wykorzystać metodę matrycową. Rozważmy przykładową
formułę o postaci (p q) (" ~ q, zadając jednocześnie
pytanie, czy (p q) (" ~ q jest tautologiÄ… klasycznego
rachunku zdań?
Aby odpowiedzieć na to pytanie, zbudujmy matrycę dla
badanej formuły.
Krok 1. Wypisujemy w kolejnych rzędach wszystkie
zmienne zdaniowe, które pojawiły się w badanej formule.
p q
W badanej formule pojawiajÄ… siÄ™ tylko dwie zmienne
zdaniowe: p oraz (dwukrotnie) q.
W następnym kroku wypiszemy zmienne (o ile takie
istniejÄ…) wraz z negacjami.
7
JC WSEZ w A
odzi
Krok 2. Wpisujemy w kolejnej kolumnie negacjÄ™ zmiennej
q (bo tylko q występuje z negacją w badanej formule).
p q
<"q
Krok 3. W następnych kolumnach wypisujemy tzw.
podformuły, w których występują spójniki
dwuargumentowe. W ostatniej kolumnie powinna
figurować cała badana formuła.
p q
<"q pq (p q) (" ~ q
Krok 4. Określamy wartości logiczne wyrażeń atomowych
(tj. zmiennych zdaniowych).
8
JC WSEZ w A
odzi
p q
<"q pq (p q) (" ~ q
1 1
1 0
0 1
0 0
Zauważmy, że istnieją tylko cztery takie kombinacje:
1) obydwa zadnia: p oraz q są jednocześnie prawdziwe (w
drugim wierszu zarówno pod zmienną p jaki i zmienną q
figuruje cyfra1, czyli prawda)
2) zdanie p jest prawdziwe, zaś zdanie q  fałszywe (w
trzecim wierszu pod zmiennÄ… p widnieje 1, zaÅ› pod
zmienną q pojawiało się 0)
3) zdanie p jest fałszywe, zaś zdanie q  prawdziwe (w
czwartym wierszu pod zmiennÄ… p widnieje 0, zaÅ› pod
zmiennÄ… q pojawia siÄ™ 1)
4) obydwa zadnia: p oraz q są jednocześnie fałszywe (w
piątym wierszu zarówno pod zmienną p jaki i zmienną q
figuruje cyfra 0, oznaczająca fałsz).
9
JC WSEZ w A
odzi
Krok 5. Określamy wartość logiczną dla negacji zdania q
(zgodnie z tabelkÄ… negacji).
p q
<"q pq (p q) (" ~ q
1 1 0
1 0 1
0 1 0
0 0 1
Krok 6. Określamy wartość logiczną implikacji pq
(zgodnie z tabelkÄ… implikacji).
p q
<"q pq (p q) (" ~ q
1 1 0 1
1 0 1 0
0 1 0 1
0 0 1 1
Krok 7. Określamy wartość logiczną alternatywy  ("  w
formule (p q) (" ~ q (zgodnie z tabelkÄ… alternatywy).
10
JC WSEZ w A
odzi
p q
<"q pq (p q) (" ~ q
1 1 0 1 1
1 0 1 0 1
0 1 0 1 1
0 0 1 1 1
Uwaga! W ostatniej kolumnie pojawiły się same jedynki.
Oznacza to, że badana formuła jest prawdziwa (przyjmuje
wartość 1) przy dowolnym wartościowaniu klasycznym.
Formuła (p q) (" ~ q jest zatem tautologią krz.
Czy formuła <" (p (" q) "! (<" (p '" q) <"q) jest tautologią
klasycznego rachunku zdań?
Nim udzielimy odpowiedzi na podane pytanie, zbudujmy
matrycę dla badanej formuły.
p q <"q p(" q <" (p(" q) p'" q <" (p '" q) <" (p'"q) <"q <" (p("q) "! (<" (p'"q) <"q)
1 1 0 1 0 1 0 1 0
1 0 1 1 0 0 1 1 0
0 1 0 1 0 0 1 0 1
0 0 1 0 1 0 1 1 1
11
JC WSEZ w A
odzi
W ostatniej kolumnie pojawiło się 0 (dwukrotnie). Istnieje
zatem wartościowanie, przy którym badana formuła
przyjmuje wartość 0. Badana formuła nie jest więc
tautologiÄ….
Ograniczenia metody matrycowej
Im więcej zmiennych zdaniowych występuje w danej
formule, tym więcej możliwych kombinacji wartości
logicznych (więcej wierszy w matrycy).
Zbudujmy matrycę dla formuły (p (" q) "! r.
p q r
p (" q p (" q "! r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
12
JC WSEZ w A
odzi
Ilość wierszy w matrycy w porównaniu z poprzednim
przykładem zwiększyła się dwukrotnie (8 możliwych
kombinacji, nie licząc wiersza z wypisanymi formułami).
Stopień komplikacji zwiększy się wraz z analizą kolejnego
przykładu. Zbudujmy matrycę dla (p (" q) "! (r '" s).
p q r s
p (" q r '" s (p (" q) "! (r '" s)
1 1 1 1
1 1 1 0
1 1 0 1
1 1 0 0
1 0 1 1
1 0 1 0
1 0 0 1
1 0 0 0
0 1 1 1
0 1 1 0
0 1 0 1
0 1 0 0
0 0 1 1
0 0 1 0
0 0 0 1
0 0 0 0
13
JC WSEZ w A
odzi
W formule (p (" q) "! (r '" s) występują cztery zmienne
zdaniowe: p, q, r oraz s. Możliwych kombinacji jest więc
16 (nie wliczamy wiersza z formułami, zaznaczonego
kolorem niebieskim).
Liczbę wierszy w matrycy, w których występują wartości
logiczne, można określić posługując się wzorem: L = 2n,
gdzie L  to liczba wierszy w matrycy (z wartościami
logicznymi), n  ilość zmiennych zdaniowych
występujących w formule, dla której budujemy matrycę.
Dla przykładu w formule p (" <" p występuje tylko jedna
zmienna zdaniowa p. Możliwe są więc dwie opcje: albo
zmienna zdaniowa p jest prawdziwa (przypisujemy jej
wówczas wartość 1), albo fałszywa (przypisujemy wartość
0). A zatem L = 21, czyli L = 2.
Z kolei w formule (p q) (" ~ q występują dwie zmienne
zdaniowe: p oraz q. Oznacza to, że L = 22, czyli L = 4.
W formule (p (" q) "! r zmienne sÄ… trzy: p, q oraz r. Tak
więc, L = 23, czyli L = 8. W formule (p (" q) "! (r '" s)
zmienne sÄ… cztery, zatem L = 24, czyli L = 16.
ZaletÄ… metody matrycowej jest jej prostota, niemniej w
niektórych przypadkach okazuje się metodą żmudną.
DobrÄ… alternatywÄ™ dla metody matrycowej stanowi tzw.
metoda skrócona.
14