KIF83

rozważań jch w rachunku zdań, o dowolnym schemacie m«. ieray rozstrzygnąć, czy jest on tautologią, w skończonej liczbie kroków. W tym celu podstawiamy w badanym schemacie na miejsce .zmiennych zdaniowych — symbole prawdy i fałszu we wszystkich możliwych kombinacjach (jest ich zawsze 2*. gdzie »jest liczbą występujących w schemacie róźnoksztah-nycb~zm5eilhyćli). Jeśli wynik każdego z tych podstawień redukuje aę, w oparciu o matryce logiczne, do symbolu prawdy, badany schemat jest tautologią. Na przykład, ustalenie, czy jest tautologią schemat:

wymaga zbadanii, czy podsta wicriftr 'każdej z czterech nasię-pojących kombi nagi zer i jedynek:

(1) P/l. dl i (2) Pil f/0; (3) Pio, q! 1; (4) p/0, g/0 redukuje się na gruncie matryc logicznych do jedynki. Spraw-dzenie przebiega następująco: ^

(1)    -!)=-!-«>—(?)— 1-*1 —1

(3)    !)= 1 -ł -0)= I -0-0

Podstawienie (3) prowadzi do wniosku, żc badany schemat nie jest tautologią (podstawienie (4) jest więc już zbędne).

(A)    Wskaż tautologie wśród schematów podanych w zada-mach 7 i 8.

(B)    Zbadaj, które z podanych niżej schematów są tautologiami.

(*)

(g) ((/-«) A q\-*p © (/ a q)s(q a p) (0 (P v f)s(ł v p)

(g)    ~(P a ę)=(~p A -q)

(h)    ~(P a q) = (~p v ~ę)

(O ~0 v <7)s(-p v -9)

O) ~(P ^v 9)=(~p a ~ę)

24. Przedstawioną w zadaniu 23 procedurę sprawdzania tautologiczności schematów rachunku zdań (zwaną metodą zerojedynkową lub matry cową) można skrócić, nic wykonując tych podstawień, o których w drodze prostego rozumowania ustalamy, że schemat redukuje się przy nich do symbolu prawdy. Na przykład, sprawdzając schemat:

możemy pominąć obydwa podstawienia, w których na miejscu p występuje 0. bowiem na miejscu ~~p wystąpiłoby wówczas 1. zaś implikacja mająca następnik o wartości I sama ma również — niezależnie od budowy swego poprzednika — wartość 1. Podobnie, sprawdzając schemat:

v r)]-»[/>-*(~₉ v ~r)]

wykonamy tylko podstawienie:p/l, qj 1, rj 1,przeprowadziwszy następujące rozumowanie: badany schemat jest implikacją, a zatem może przyjąć wartość 0 tylko wtedy, gdy jego następnik przyjmie wartość 0; następnik ten jest również implikacją, będzie więc miał wartość 0 wtedy, gdy jego poprzednik (czyli p) przyjmie wartość 1, następnik zaś (czyli alternatywa ~q v ~r) wartość 0; hędzic tak tylko wówczas, gdy qlI i r/1.

(A)    Zbadaj skróconą metodą z.cro-jedynkową, które ze schematów (a) — (h) z zadania 23(B) są tautologiami.

(B)    Podane niżej schematy nic są tautologiami; zbadaj skróconą metodą zero-jedynkową, który z nich jest kontrtautologlą, tj. schematem wyłącznie fałszywych zdań.

(a)    ~(p-*q)-*(p->q)

(b)    ~(/>-*?)=(p-*q)

21