W rachunku zdań na szczególną uwagę zasługują zdania lub schematy zdań, utworzone ze zmiennych zdaniowych za pomocą funktorów zdaniotwórczych, których wartością jest zawsze prawda, tzn. te, które są spełnione przez wszystkie możliwe wartościowania zmiennych zdaniowych. Są to tautologie.

Matryca logiczna (inaczej, tablica wartości logicznych) zdania, które jest tautologią ma kolumnę wartości wypełnioną tylko jedynkami.

Matryca logiczna zdania sprzecznego ma kolumnę wartości wypełnioną tylko zerami. O zdaniach sprzecznych i sprzecznych zbiorach zdań będziemy jeszcze mówili w dalszej części tego wykładu (por. punkt 7.6).

Uwaga. Formuła α rachunku zdań jest tautologią wtedy i tylko wtedy, gdy ¬ α jest zdaniem sprzecznym.

Pytanie 7.3.1: Czy zdanie "Jeżeli Piotr jest najlepszym studentem PJWSTK, to jeśli Piotr nie jest studentem, to Piotr jest biologiem" jest zawsze prawdziwe, czy zawsze fałszywe?

Przykład 7.3.1

Następujące formuły są przykładami tautologii rachunku zdań.

(1) (a → a) prawo tożsamości dla implikacji,

(2) (a ∨ ¬ a) prawo wyłączonego środka - z dwóch zdań sprzecznych przynajmniej jedno jest prawdziwe,

(3) ¬ (a ∧ ¬ a) prawo wyłączonej sprzeczności - z dwóch zdań sprzecznych co najmniej jedno jest fałszywe,

(4) ¬ ( ¬ a) ↔ a prawo podwójnego przeczenia,

(5) ¬ a → (a → β ) prawo Dunsa Scotusa,

(6) ( ¬ a → a) → a prawo Claviusa.

Dla przykładu, obliczmy wartość logiczną trzeciego wyrażenia w przykładzie 7.3.1 tzn. ¬ (a ∧ ¬ a). Ponieważ α może być zdaniem albo prawdziwym albo fałszywym, rozważymy dwa przypadki:

1. w( α ) = 0. Wtedy

   w( ¬ ( α ∧ ¬ α)) = ¬ w ( α ∧ ¬ α) = ¬ (w( α) ∧ w( ¬ α)) = ¬ (0 ∧ ¬ w( α)) = ¬ (0 ∧ 1) = ¬ 0 = 1

2. w( α ) = 1. Wtedy

   w( ¬ ( α ∧ ¬ α)) = ¬ w( α ∧ ¬ α) = ¬ (w( α) ∧ w( ¬ α)) = ¬ (1 ∧ ¬ w( α)) = ¬ (1 ∧ 0 ) = ¬ 0 = 1

Na uwagę zasługuje też prawo Dunsa Scotusa (wymienione w przykładzie 7.3.1), które głosi, że jeśli ¬ α jest zdaniem prawdziwym, to α implikuje każde inne zdanie. Sprawdźmy: jeśli w( ¬ α ) = 0, to oczywiście w( ¬ α → (α → β )) = 1. Jeśli w( ¬ α )=1, tzn. w( α )= 0, to w(α → β ) = 1, ale wtedy w( ¬ α → (α → β)) = 1.

Rzeczywiście, wynik nie zależy od wartości logicznej zdania β.

Zaprezentowana tu metoda sprawdzania, czy formuła rachunku zdań jest tautologią, nosi nazwę metody zerojedynkowej. Polega ona na rozważeniu wszystkich możliwych wartości zdań składowych i obliczeniu, dla każdego przypadku osobno, wartości całej formuły. Jeśli formuła ma n zmiennych zdaniowych, a każda zmienna może przyjmować wartość 0 lub 1, to musimy sprawdzić aż 2ⁿ możliwych sytuacji. Dużo! Tym niemniej, metoda ta pozwala w skończonej liczbie kroków stwierdzić, czy dane wyrażenie rachunku zdań jest, czy nie jest tautologią.

Przykład 7.3.2

Sprawdźmy, czy formuła ¬ (α ∨ β) ↔ ( ¬ α ∧ ¬ β ) jest tautologią (prawo de Morgana) rachunku zdań. W tym celu utwórzmy matrycę logiczną tej formuły i jej podformuł (por. Rys.7.3.1). Ponieważ, niezależnie od wartości przyjętych dla zdań α, β, wartością naszej formuły jest 1, zatem ¬ (α ∨ β) ↔ ( ¬ α ∧ ¬ β ) jest tautologią rachunku zdań.

Rys. 7.3.1 Matryca logiczna prawa de Morgana ¬ (α ∨ β) ↔ ( ¬ α ∧ ¬ β ).

Przykład 7.3.3

Dla dowolnych zdań p, q, r następujące formuły są zawsze prawdziwe, tzn. są tautologiami rachunku zdań :

Prawo transpozycji    (p → q) ↔ ( ¬ q → ¬ p )

Prawo zaprzeczenia implikacji     ¬ (p → q) ↔ (p ∧ ¬ q )

Prawo de Morgana     ¬ ( p ∧ q) ↔ ( ¬ p ∨ ¬ q)

Prawo sylogizmu warunkowego    (p → ( q → r)) → ((p → q) → (p → r))

Dla każdej z formuł przedstawionych w przykładzie 7.3.3 można utworzyć matrycę logiczną i sprawdzić, że niezależnie od przyjętych wartości zdań p, q, r, wartością każdej z wymienionych funkcji jest 1 (prawda). W pierwszych trzech przykładach występują tylko dwie zmienne p i q, zatem musimy rozważyć 4 układy wartości tych zmiennych. W ostatniej formule natomiast, występują aż trzy zmienne, co powoduje, że w metodzie zerojedynkowej musimy rozważyć aż 8 różnych układów wartości tych zmiennych. Czasami, a wszystko zależy od budowy rozważanej formuły, możemy sobie znacznie uprościć zadanie, wykorzystując właściwości spójników logicznych (w tym przypadku implikacji).

Rzeczywiście, jeśli wartością zmiennej r jest prawda, to (p → r) i ((p →q) → (p → r)) są zdaniami prawdziwymi i w konsekwencji w((p → ( q → r)) → ((p → q) → (p → r))) = 1 (korzystamy z tego, że jeśli następnik implikacji jest prawdziwy, to implikacja jest prawdziwa). W ten sposób przeanalizowaliśmy równocześnie aż 4 przypadki. Pozostały tylko te sytuacje, w których w(r)=0. W dalszej części wykładu przedstawimy jeszcze inną metodę, która pozwoli nieco uprościć proces sprawdzania tautologiczności formuł.

Następujący lemat daje metodę tworzenia nowych tautologii i uzasadnia dlaczego tautologie są wzorcami zdań prawdziwych.

Przykład 7.3.4

Wykazaliśmy powyżej (por. przykład 7.3.2), że formuła ¬ (α ∨ β) ↔ ( ¬ α ∧ ¬ β ) jest tautologią. Wstawmy teraz w miejsce α zdanie "x jest elementem A", a w miejsce β zdanie "x jest elementem B" . Otrzymamy zdanie prawdziwe postaci:

"nie jest prawdą, że x jest elementem A lub x jest elementem B wtedy i tylko wtedy, gdy x nie jest elementem A i x nie jest elementem B". Jeśli nieco uprościmy to sformułowanie, to z łatwością rozpoznamy znane nam prawo algebry zbiorów: jeśli x nie należy do sumy zbiorów A i B, to x nie należy ani do A ani do B.

Znajomość tautologii i właściwości semantycznych spójników logicznych jest również bardzo potrzebna programistom. Testy (tzw. wyrażenia Booleowskie) stosowane w instrukcjach warunkowych, czy pętlach, to nic innego jak formuły, często bardziej skomplikowane niż te z rachunku zdań. Wynik działania programu zależy od tego, czy i które testy są spełnione w danej chwili. Weźmy jako przykład instrukcję "while (p → (q → p)) do x := x+1 od". Jeśli ktoś nieuważny umieści taką instrukcję w swoim programie, to nie doczeka się wyniku, bo test w tej pętli jest tautologią. Zatem pętla jest wykonywana w nieskończoność (w praktyce zostanie zasygnalizowany błąd, ale dopiero po jakimś czasie).

Rozważmy jeszcze jeden przykład instrukcji "if p then I1 else if q then I2 else I3 fi fi". Załóżmy, że (q → p) jest prawdą ilekroć wykonujemy powyższą instrukcję warunkową. Czy instrukcja I2 będzie kiedykolwiek wykonana? Nie, bo jeśli p jest prawdziwe, to wcale nie dochodzimy do instrukcji "if q...", a gdy p nie jest prawdziwe, to na mocy założenia również q nie jest prawdziwe, a zatem wykona się I3. Wynika stąd, że nasza instrukcja warunkowa może przyjąć dużo prostszą (i równoważną) postać

"if p then I1 else I3 fi".

Pytanie 7.3.1: Przypuśćmy, że formuła (α → β) jest tautologią, to które z następujących zdań jest prawdziwe?

1. "Jeśli program while α do P od nie zapętla się, to program while β do P od nie zapętla się"
2. "Jeśli program while β do P od nie zapętla się, to program while α do P od nie zapętla się"