Formuła atomowa

Formuła atomowa (formuła prosta) – formuła, która nie ma żadnych właściwych podformuł. Rodzaje formuł atomowych zależą od rodzaju używanej logiki.

Formuły, które nie są atomowe nazywamy złożonymi.

Rachunek zdań

W rachunku zdań jedynymi rodzajami atomów są zmienne zdaniowe: p , q , r , … {\displaystyle p,q,r,\dots }

Rachunek kwantyfikatorów

W klasycznym rachunku predykatów (logice pierwszego rzędu) określamy formuły atomowe w następujący sposób:

Niech τ {\displaystyle \tau } będzie ustalonym alfabetem (tzn. zbiorem stałych, symboli funkcyjnych i symboli relacyjnych) i niech x 0 , x 1 , … {\displaystyle x_{0},x_{1},\dots } będzie (nieskończoną) listą używanych zmiennych. Przypomnijmy, że termy języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} są zdefiniowane jako elementy najmniejszego zbioru T {\displaystyle \mathbf {T} } takiego, że:

  • wszystkie stałe i zmienne należą do T , {\displaystyle \mathbf {T} ,}
  • jeśli t 1 , … , t n ∈ T {\displaystyle t_{1},\dots ,t_{n}\in \mathbf {T} } i f ∈ τ {\displaystyle f\in \tau } jest n {\displaystyle n} -arnym symbolem funkcyjnym, to f ( t 1 , … , t n ) ∈ T . {\displaystyle f(t_{1},\dots ,t_{n})\in \mathbf {T} .}

Formuły atomowe języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} to wyrażenia

  • t 1 = t 2 {\displaystyle t_{1}=t_{2}} gdzie t 1 , t 2 ∈ T , {\displaystyle t_{1},t_{2}\in \mathbf {T} ,} oraz
  • P ( t 1 , … , t n ) {\displaystyle P(t_{1},\dots ,t_{n})} gdzie t 1 , … , t n ∈ T {\displaystyle t_{1},\dots ,t_{n}\in \mathbf {T} } zaś P ∈ τ {\displaystyle P\in \tau } jest n {\displaystyle n} -arnym symbolem relacyjnym.
Przykłady
  • Rozważmy język L ( { ∈ } ) {\displaystyle {\mathcal {L}}(\{\in \})} teorii mnogości (czyli ∈ {\displaystyle \in } jest binarnym symbolem relacyjnym). Formuły atomowe w tym języku to fomuły postaci x i = x j {\displaystyle x_{i}=x_{j}} oraz x i ∈ x j . {\displaystyle x_{i}\in x_{j}.}
  • Przykładami formuł atomowych w języku L ( { ∗ } ) {\displaystyle {\mathcal {L}}(\{*\})} teorii grup (czyli ∗ {\displaystyle *} jest binarnym symbolem funkcyjnym) są:
x 1 ∗ x 1 = x 1 , {\displaystyle x_{1}*x_{1}=x_{1},}
x 1 ∗ x 2 = x 2 ∗ x 1 , {\displaystyle x_{1}*x_{2}=x_{2}*x_{1},}
( x 1 ∗ x 2 ) ∗ x 3 = x 1 ∗ ( x 2 ∗ x 3 ) . {\displaystyle (x_{1}*x_{2})*x_{3}=x_{1}*(x_{2}*x_{3}).}
  • Rozważmy teraz język L ( { + , ⋅ , 0 , 1 , ⩽ } ) {\displaystyle {\mathcal {L}}(\{+,\cdot ,0,1,\leqslant \})} ciał uporządkowanych (zatem + , ⋅ {\displaystyle +,\cdot } są binarnymi symbolami funkcyjnymi, a ⩽ {\displaystyle \leqslant } jest binarnym symbolem relacyjnym). Następujące wyrażenia są formułami atomowymi w tym języku:
0 ⩽ x 1 ⋅ x 1 , {\displaystyle 0\leqslant x_{1}\cdot x_{1},}
x 1 + x 2 = x 2 ⋅ x 1 , {\displaystyle x_{1}+x_{2}=x_{2}\cdot x_{1},}
x 1 ⩽ ( x 1 + x 2 ) ⋅ ( x 2 + 1 ) . {\displaystyle x_{1}\leqslant (x_{1}+x_{2})\cdot (x_{2}+1).}

Zobacz też