Scan0014

22 Tautologie. Wynikanie logiczne. Systemy dowodzenia

2.2 Badanie tautologii

2.2.1    Metoda zero-jedynkowa

Metoda zero-jedynkowa polega na wyznaczeniu wszystkich 2ⁿ interpretacji, gdzie n oznacza liczbę atomów. Jeżeli w każdym przypadku otrzymamy 1, to formuła jest tautologią. Jeżeli w każdym prz}^padku otrzymamy 0, to formuła, jest kontrtautologią.

2.2.2    Skrócona metoda zero-jedynkowa

Metoda skrócona polega na poszukiwaniu interpretacji, dla której formuła ma wartość 0. W ten sposób wyklucza się możliwość, że jest ona tautologią. Kolejność postępowania:

1.    Założyć, że formuła ma wartość 0.

2.    Wyznaczyć wartościowania zgodnie z tym założeniem.

3.    Sprawdzić, czy nie ma sprzeczności:

•    jeżeli jest sprzeczność, to formuła jest tautologią.

•    jeżeli nie ma sprzeczności, to formuła nie jest tautologią.

Aby sprawdzić, czy formuła jest kontrtautologią postępujemy podobnie, przy czym zakładamy na początku, że formuła ma wartość 1.

Przykład 2.2 Czy formuła [(j)^g)V(r4~p)]=^[p^(ęV~ r)] jest tautologią?

w {[(P => O) V (r ~ p)\ => \p => (q V ~ r)]} = 0 w [(p => q) V (r => ~ p)\ = 1 w [p =$>■ (q V ~ r)] = 0

w (p) = 1 w (q V ~ r) = 0 w (q) = 0 w (~ r) = 0 w (r) = 1

[(1 =>• 0) V (1 =>■ 0)] = 1 0 V0 = 1

0 - 1

sprzeczność