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ć

$\neg \neg \neg p$

$\neg \neg (p \Rightarrow p)$

$\neg (p \Rightarrow \neg p)$

$\neg (p \Rightarrow (p\Rightarrow p))$

$\neg (\neg p \Rightarrow p)$

$\neg ((p\Rightarrow p) \Rightarrow p)$

$p \Rightarrow (\neg \neg p)$

$p \Rightarrow (\neg (p \Rightarrow p))$

$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.