Język logiki zdaniowej

Zaczniemy od definicji języka logiki zdaniowej. Składa się on z formuł zdefiniowanych następująco:
Definicja 2.1 [Formuła logiki zdaniowej]

zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. \( p,q,r \)),
jeśli \( {\phi} \) oraz \( {\psi} \) są formułami to \( (\phi \Rightarrow \psi) \) jest formułą (spójnik \( \Rightarrow \) nazywamy implikacją),
jeśli \( {\phi} \) jest formułą to \( \neg \phi \) jest formułą (spójnik \( \neg \) nazywamy negacją),
nic innego nie jest formułą.

Powyższa definicja mówi, że formułami nazywamy te napisy, które dają się skonstruować ze zmiennych zdaniowych przy pomocy spójników \( \Rightarrow \) oraz \( \neg \).
Uwaga 2.2.

Zgodnie z powyższą definicją nie jest formułą napis \( p\Rightarrow q \), gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać \( (p\Rightarrow q) \) możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić. Często przyjmuje się również prawostronne nawiasowanie dla implikacji, czyli formuła \( p \Rightarrow q \Rightarrow r \) jest domyślnie nawiasowana w następujący sposób \( (p \Rightarrow (q \Rightarrow r)) \).

Przykład 2.3 Poniższe napisy nie są formułami

\( p \Rightarrow \Rightarrow q \),

\( \neg \neg \neg \),

ten napis na pewno nie jest formułą,

\( (p \Rightarrow \neg q)) \).

Poniższe napisy są formułami

\( (p \Rightarrow (r \Rightarrow q)) \),

\( \neg \neg \neg q \),

\( (p \Rightarrow \neg q) \).

Ćwiczenie 2.1

Rozmiarem formuły nazwiemy ilość występujących w niej spójników. Na przykład formuła \( \neg \neg q \) ma rozmiar 2, a formuła \( (p\Rightarrow q) \) ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest \( \mathrm {p} \). Ile można skonstruować rożnych formuł o rozmiarze 3?

Rozwiązanie

Oznaczmy przez \( f_n \) liczbę formuł o rozmiarze \( \mathrm {n} \) (czyli liczbę formuł w których jest \( \mathrm {n} \) spójników). Interesuje nas \( f_3 \). Każda formuła o rozmiarze 3 powstaje z dwóch formuł o rozmiarach 1 poprzez połączenie ich spójnikiem \( \Rightarrow \) lub dwóch formuł o rozmiarach odpowiednio 0 i 2 oraz 2 i 0, lub z jednej formuły o rozmiarze 2 poprzez dodanie do niej spójnika \( \neg \). Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność: \( f_3= (f_1)^2+ 2 f_2 +f_2. \) Wiemy, że są tylko dwie formuły o rozmiarze 1, są to \( \neg p \) oraz \( p \Rightarrow p \). Stąd mamy \( f_1=2 \). Dla formuł o rozmiarze 2 możemy zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar 1 a druga 0 za pomocą \( \Rightarrow \), albo jest zbudowana z formuły o rozmiarze 1 za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze 0, jest to \( \mathrm {p} \). Mamy więc następujący wzór dla \( f_2 \) \( f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1. \) Z dwóch ostatnich wzorów otrzymujemy \( f_3= 9 \cdot f_1 + (f_1)^2= 18+4 = 22. \) Skoro jest ich niewiele, to możemy wszystkie wypisać

1. \( \neg \neg \neg p \)

2. \( \neg \neg (p \Rightarrow p) \)

3. \( \neg (p \Rightarrow \neg p) \)

4. \( \neg (p \Rightarrow (p\Rightarrow p)) \)

5. \( \neg (\neg p \Rightarrow p) \)

6. \( \neg ((p\Rightarrow p) \Rightarrow p) \)

7. \( p \Rightarrow (\neg \neg p) \)

8. \( p \Rightarrow (\neg (p \Rightarrow p)) \)

9. \( p \Rightarrow (p \Rightarrow \neg p) \)

10. \( p \Rightarrow (p \Rightarrow (p\Rightarrow p)) \)

11. \( p \Rightarrow (\neg p \Rightarrow p) \)

12. \( p \Rightarrow ((p\Rightarrow p) \Rightarrow p) \)

13. \( (\neg \neg p) \Rightarrow p \)

14. \( (\neg (p \Rightarrow p))\Rightarrow p \)

15. \( (p \Rightarrow \neg p) \Rightarrow p \)

16. \( (p \Rightarrow (p\Rightarrow p)) \Rightarrow p \)

17. \( (\neg p \Rightarrow p) \Rightarrow p \)

18. \( ((p\Rightarrow p) \Rightarrow p)\Rightarrow p \)

19. \( (\neg p)\Rightarrow (\neg p) \)

20. \( (\neg p)\Rightarrow (p \Rightarrow p) \)

21. \( (p \Rightarrow p) \Rightarrow (\neg p) \)

22. \( (p \Rightarrow p)\Rightarrow (p \Rightarrow p) \)

Uwaga 2.4.

Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą tzw. Odwrotnej Notacji Polskiej.