Język logiki zdaniowej

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]

  1. zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. \( p,q,r \)),
  2. jeśli \( {\phi} \) oraz \( {\psi} \) są formułami to \( (\phi \Rightarrow \psi) \) jest formułą (spójnik \( \Rightarrow \) nazywamy implikacją),
  3. jeśli \( {\phi} \) jest formułą to \( \neg \phi \) jest formułą (spójnik \( \neg \) nazywamy negacją),
  4. 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?

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.