Untitled Scanned 04

27

Zupełnie analogicznie rozumujemy w tych przypadkach, gdy A jest alternatywą, implikacją lub równoważnością dwóch innych formuł A_t i A₂. Różnica sprowadza się jedynie do zastąpienia znaku koniunkcji i funkcji Kn przez znak alternatywy i funkcję Al, albo przez znak implikacji i funkcję Im, albo wreszcie przez znak równoważności i funkcję Rw. Nie ma zatem potrzeby przytaczania tych rozumowań w ich pełnym brzmieniu. Można tym samym przyjąć, że dowód twierdzenia został zakończony.

§ 6. TAUTOLOGIK

DEFINICJA 6.1. Formula A jest tautologią rachunku zdań wtedy i tylko wtedy, gdy przy każdym wartościowaniu <vv_n> zachodzi równość:

V(A,<w_n» = 1.

Zhiór wszystkich tautologii rachunku zdań będziemy oznaczać symbolem Trz.

Mogłoby się wydawać, że definicja powyższa nie daje żadnego sposobu praktycznego sprawdzenia, czy dowolna dana formuła jest czy też nie jest tautologią: istnieje bowiem nieskończenie wiele różnych wartościowań, niepodobna zatem wziąć ich wszystkich pod uwagę. A jednak metoda taka istnieje. Daje ją definicja 6.1 w połączeniu z twierdzeniem 5.1. Przypuśćmy bowiem, że

/I jest dowolną formułą zawierającą zmienne zdaniowe p_it.....p_u i nie

zawierającą żadnych innych zmiennych. Podzielmy wszystkie wartościowania na dwie klasy w taki oto sposób: do pierwszej klasy zaliczmy te wszystkie wartościowania, które na miejscu i_{ mają element 1; do drugiej zaliczmy wszystkie pozostałe wartościowania, tzn. te, które na miejscu i, mają element 0. Każdą z tych dwóch klas znowu podzielmy na dwie klasy, zaliczając do nich wartościowania w zależności od tego, czy na miejscu i₂ mają 1 czy 0. Ogół wartościowań zostanie w ten sposób podzielony na cztery klasy. Każdą z tych klas podzielmy ponownie na dwie klasy w zależności od rodzaju elementu na miejscu i-,. W wyniku otrzymamy już 8 klas wartościowań. Podziały te

kontynuujemy dalej, aż zostaną uwzględnione wszystkie wskaźniki i_y, i₂.....i_k.

Po k-tym podziale wszystkie wartościowania zostaną rozbite na 2* rozłącznych klas. Dla sprawdzenia, czy A jest tautologią, wystarczy wybrać z każdej klasy po jednym wartościowaniu i przy każdym z tych wybranych wartościowań wyliczyć wartość formuły A. Jeżeli wartość ta będzie wynosiła 1 we wszystkich 2^X wypadkach, to zgodnie z twierdzeniem 5.1 będzie to znaczyło, że A jest tautologią. W przeciwnym razie A$Trz.

W praktyce przy sprawdzeniach tego rodzaju można się ograniczać do 2‘ wartościowań skończonych, k-wyrazowych (gdy formuła zawiera dokładnie k różnych zmiennych zdaniowych), tak jak to czyniliśmy wyżej w §2.