Formuła logiczna

Formuła logiczna – określenie dozwolonego wyrażenia w wielu systemach logicznych, m.in. w rachunku kwantyfikatorów oraz w rachunku zdań.

Rachunek zdań

Zdania rachunku zdań są formułami tegoż rachunku. Tak więc każda zmienna zdaniowa $p_i$ jest formułą. Taką formułę nazywa się też formułą atomową. Formułami są także negacje formuł atomowych, tzn. $\mathrm{\neg }{p}_i.$ Formuły atomowe i ich negacje nazywa się też literałami. Ponadto jeżeli $\phi ,\psi$ są formułami i $*$ jest binarnym spójnikiem zdaniowym (alternatywą $\vee ,$ koniunkcją $\wedge ,$ implikacją $\Rightarrow$ lub równoważnością $\iff$), to $(\phi *\psi )$ oraz $\mathrm{\neg }\phi$ są formułami. Żadne inne wyrażenie nie może być formułą.

Przykłady

Wbrew definicji formalnej, w sytuacjach, gdy nie prowadzi to do nieporozumień, część nawiasów w formule opuszcza się. Przykładowo, zgodnie z definicją formalną wyrażenie: $(p\vee q\vee r)$ nie jest formułą (formułą byłoby np. wyrażenie $((p\vee q)\vee r),$ lecz interpretacja takiej formuły jest jednoznaczna i wewnętrzne nawiasy w praktyce pomija się).

Rachunek kwantyfikatorów

Rachunek kwantyfikatorów (rachunek predykatów pierwszego rzędu), jako uogólnienie rachunku zdań, posługuje się podobną definicją formalną formuły, rozszerzając ją o kwantyfikatory – jeżeli $\phi$ jest formułą rachunku kwantyfikatorów, to $\mathrm{\forall }x\phi$ oraz $\mathrm{\exists }x\phi$ są nią również.

Formalna definicja

Niech $\tau$ będzie ustalonym alfabetem, czyli zbiorem stałych, symboli funkcyjnych i symboli relacyjnych (predykatów). Każdy z tych symboli ma jednoznacznie określony charakter (tzn. wiadomo czy jest to stała, czy symbol funkcyjny czy też predykat) i każdy z symboli funkcyjnych i predykatów ma określoną arność (która jest dodatnią liczbą całkowitą). Niech $x_0,x_1,\dots$ będzie nieskończoną listą zmiennych.

Przypomnijmy, że termy języka $ℒ(\tau )$ to elementy najmniejszego zbioru $𝐓$ takiego, że:

• wszystkie stałe i zmienne należą do $𝐓,$
• jeśli $t_1,\dots ,t_n\in 𝐓$ i $f\in \tau$ jest $n$-arnym symbolem funkcyjnym, to $f(t_1,\dots ,t_n)\in 𝐓.$

Formuły języka $ℒ(\tau )$ są wprowadzane przez indukcję po ich złożoności jak następuje:

• jeśli $t_1,t_2\in 𝐓,$ to wyrażenie $t_1=t_2$ jest formułą (tzw. formuła atomową),
• jeśli $t_1,\dots ,t_n\in 𝐓$ zaś $P\in \tau$ jest $n$-arnym symbolem relacyjnym, to wyrażenie $P(t_1,\dots ,t_n)$ jest formułą (tzw. formuła atomową),
• jeśli $\phi ,\psi$ są formułami oraz $*$ jest binarnym spójnikiem zdaniowym, to $(\phi *\psi )$ oraz $\mathrm{\neg }\phi$ są formułami,
• jeśli $x_i$ jest zmienną oraz $\phi$ jest formułą, to także $(\mathrm{\exists }{x}_i)(\phi )$ i $(\mathrm{\forall }{x}_i)(\phi )$ są formułami.

Zmienne wolne w formule

W formułach postaci $(\mathrm{\exists }{x}_i)(\phi )$ i $(\mathrm{\forall }{x}_i)(\phi )$ mówimy, że zmienna $x_i$ znajduje się w zasięgu kwantyfikatora i jako taka jest związana. Przez indukcję po złożoności formuł, rozszerzamy to pojęcie na wszystkie formuły w których $(\mathrm{\exists }{x}_i)(\phi )$ czy też $(\mathrm{\forall }{x}_i)(\phi )$ pojawia się jako jedna z części użytych w budowie, ale ograniczamy się do występowań zmiennej $x_i$ w $\phi$ (i mówimy, że konkretne wystąpienie zmiennej jest wolne lub związane). Bardziej precyzyjnie:

• każde wystąpienie zmiennej $x_i$ w formule atomowej jest wolne,
• jeśli $\psi$ to formuła postaci $(Q{x}_i)(\phi ),$ to każde wystąpienie zmiennej $x_i$ w formule $\psi$ jest związane,
• jeśli $\psi ,\phi$ to formuły i pewne wystąpienie zmiennej $x_i$ w formule $\psi$ jest związane (wolne, odpowiednio), to wystąpienie to rozważane w formułach $\phi *\psi ,$ $\psi *\phi$ oraz $\mathrm{\neg }\psi$ także jest związane (wolne, odpowiednio; tutaj * jest binarnym spójnikiem zdaniowym).

Formuły w których nie ma wolnych występowań żadnych zmiennych są nazywane zdaniami (danego języka).

Domknięciem (lub domknięciem ogólnym) względem zmiennych $x_1,\dots ,x_n$ formuły $\phi$ nazywamy formułę $\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_n\phi .$

Przykłady

W praktyce, podobnie jak w rachunku zdań, gdy nie prowadzi to do niejasności, stosuje się zasadę opuszczania nawiasów.

• Przykładami formuł języka $ℒ(\{\in \})$ teorii mnogości (czyli $\in$ jest binarnym symbolem relacyjnym) są:

$\mathrm{\forall }A\mathrm{\forall }B(\mathrm{\forall }x(x\in A⟺x\in B)\Rightarrow A=B)$

$\mathrm{\exists }P\mathrm{\forall }Z(Z\in P⟺\mathrm{\forall }x(x\in Z\Rightarrow x\in X))$

• Przykładami formuł języka $ℒ(\{\star \})$ teorii grup (czyli $\star$ jest binarnym symbolem funkcyjnym) są:

$(\mathrm{\forall }{x}_1\in G)((x_1\star x_2)\star x_3=x_1\star (x_2\star x_3)),$

$(\mathrm{\exists }e\in G)(\mathrm{\forall }a\in G)(e\star a=a),$

$(\mathrm{\forall }a\in G)(\mathrm{\exists }b\in G)(b\star a=e),$

Zobacz też

• dysjunkcyjna postać normalna
• koniunkcyjna postać normalna
• logika
• prawa De Morgana