1105140228

9

ROZDZIALI. RACHUNEK ZDAŃ

Obliczenia te można zapisać trochę mniej formalnie, ale za to bardziej czytelnie 7r(<£>) = (1 V 0) A (-.1) = 1 A 0 = 0 .

Definicja 1.4 Zdanie <p nazywamy tautologią, co zapisujemy jako \= <p, jeśli n(<p) = 1 dla dowolnej waluacji ir.

Najprostszą tautologią jest oczywiście zdanie T. Inny prosty przykład to zdanie po V -'Po. Zauważmy, że do zbadania, czy dane zdanie jest waluacją wystarczy tylko ten fragment waluacji, który odpowiada zmiennym wchodzącym w skład analizowanego zdania. Ułatwia to znacznie badanie tego, czy dane zdanie jest waluacją i sprowadza to zagadnienie do znanej ze szkoły średniej metody zero-jedynkowej.

Przykład 1.3 Pokażemy, że zdanie ((poVpi)Vp₂) ^ (poV (piVp₂)) jest tautologią. Niech (p = ((p₀Vpi)Vp₂) oraz f = (po V (Pi Vp₂)). Rozważmy następującą tabelkę:

Po	Pi	P2	PoVpi	Pl Vp2	<P	i’	(p+yip
1	t	1	1	1	t	i	1
1	1	©	11	11	1	i	t
1	©	1	1	1	1	i	t
1	©	©	1	0	1	i	t
©	t	1	11	1	11	i	t
©	t	©	11	11	11	i	1
©	©	1	©	1	1	i	1
©	©	©	©	C	C	©	1

W tabelce tej mamy 8 wierszy, gdyż istnieje 8 = 2³ równych kombinacji wartości logicznych po, Pi i p₂. W kolejnych kolumnach ustalonego wiersza prowadzone są wszystkie pomocnicze obliczenia, których celem jest wyznaczenie wartości leżącej w ostatniej kolumnie. Rozważane zdanie jest tautologią, gdyż w ostatniej kolumnie występują tylko wartości t.

Zwróćmy uwagę na to, że metoda tabelek zero - jedynkowych określa automatyczną metodę badania tego, czy dane zdanie jest tautologią. Zagadnienia tego typu nazywamy rozstrzygalnymi. Jednak metoda ta dla zdań zbudowanych ze 100 zmiennych zdaniowych wymagałaby rozpatrzenia 2¹⁰⁰ « 1.2 • 10³⁰ przypadków, co jest zadaniem znacznie przekraczającym moce obliczeniowe współczesnych komputerów. Nie wiadomo, czy istnieje istotnie szybszy algorytm rozstrzygający o danym zdaniu, czy jest ono tautologią.

Definicja 1.5 Zdanie <p nazywamy sprzecznym, jeśli tt(<p) = 0 dla dowolnej waluacji 7r.

Zdania sprzeczne nazywane są czasem anty-tautologiami. Zauważmy, że zdanie •0 jest sprzeczne wtedy i tylko wtedy, gdy zdanie —>-0 jest tautologią. Podobnie, zdanie 7r jest tautologią wtedy i tylko wtedy, gdy zdanie jest sprzeczne. Najprostszym przykładem zdania sprzecznego jest zdanie _L. Innym prostym przykładem zdania sprzecznego jest po A ->po.

Definicja 1.6 Zdanie <p nazywamy spełnialnym, jeśli istnieje waluacja ir taka, że 7r(<p) = 1.