Formuła logiczna


Formuła logiczna w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Spis treści

Rachunek zdań | edytuj kod

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

Przykłady | edytuj kod

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 q r ) {\displaystyle (p\vee q\vee r)} nie jest formułą (formułą byłoby np. wyrażenie ( ( p q ) r ) , {\displaystyle ((p\vee q)\vee r),} lecz interpretacja takiej formuły jest jednoznaczna i wewnętrzne nawiasy w praktyce pomija się).

Rachunek kwantyfikatorów | edytuj kod

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 φ {\displaystyle \varphi } jest formułą rachunku kwantyfikatorów, to x φ {\displaystyle \forall x\varphi } oraz x φ {\displaystyle \exists x\varphi } są nią również.

Formalna definicja | edytuj kod

Niech τ {\displaystyle \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 , {\displaystyle x_{0},x_{1},\dots } będzie nieskończoną listą zmiennych.

Przypomnijmy, że termy języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} to 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 języka L ( τ ) {\displaystyle {\mathcal {L}}(\tau )} są wprowadzane przez indukcję po ich złożoności jak następuje:

  • jeśli t 1 , t 2 T , {\displaystyle t_{1},t_{2}\in \mathbf {T} ,} to wyrażenie t 1 = t 2 {\displaystyle t_{1}=t_{2}} jest formułą (tzw. formuła atomową),
  • jeśli 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, to wyrażenie P ( t 1 , , t n ) {\displaystyle P(t_{1},\dots ,t_{n})} jest formułą (tzw. formuła atomową),
  • jeśli φ , ψ {\displaystyle \varphi ,\psi } są formułami oraz {\displaystyle *} jest binarnym spójnikiem zdaniowym, to ( φ ψ ) {\displaystyle (\varphi *\psi )} oraz ¬ φ {\displaystyle \neg \varphi } są formułami,
  • jeśli x i {\displaystyle x_{i}} jest zmienną oraz φ {\displaystyle \varphi } jest formułą, to także ( x i ) ( φ ) {\displaystyle (\exists x_{i})(\varphi )} i ( x i ) ( φ ) {\displaystyle (\forall x_{i})(\varphi )} są formułami.

Zmienne wolne w formule | edytuj kod

W formułach postaci ( x i ) ( φ ) {\displaystyle (\exists x_{i})(\varphi )} i ( x i ) ( φ ) {\displaystyle (\forall x_{i})(\varphi )} mówimy że zmienna x i {\displaystyle 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 ( x i ) ( φ ) {\displaystyle (\exists x_{i})(\varphi )} czy też ( x i ) ( φ ) {\displaystyle (\forall x_{i})(\varphi )} pojawia się jako jedna z części użytych w budowie, ale ograniczamy się do występowań zmiennej x i {\displaystyle x_{i}} w φ {\displaystyle \varphi } (i mówimy że konkretne wystąpienie zmiennej jest wolne lub związane). Bardziej precyzyjnie:

  • każde wystąpienie zmiennej x i {\displaystyle x_{i}} w formule atomowej jest wolne,
  • jeśli ψ {\displaystyle \psi } to formuła postaci ( Q x i ) ( φ ) , {\displaystyle (Qx_{i})(\varphi ),} to każde wystąpienie zmiennej x i {\displaystyle x_{i}} w formule ψ {\displaystyle \psi } jest związane,
  • jeśli ψ , φ {\displaystyle \psi ,\varphi } to formuły i pewne wystąpienie zmiennej x i {\displaystyle x_{i}} w formule ψ {\displaystyle \psi } jest związane (wolne, odpowiednio), to wystąpienie to rozważane w formułach φ ψ , {\displaystyle \varphi *\psi ,} ψ φ {\displaystyle \psi *\varphi } oraz ¬ ψ {\displaystyle \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 , , x n {\displaystyle x_{1},\dots ,x_{n}} formuły φ {\displaystyle \varphi } nazywamy formułę x 1 x n φ . {\displaystyle \forall x_{1}\ldots \forall x_{n}\varphi .}

Przykłady | edytuj kod

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 L ( { } ) {\displaystyle {\mathcal {L}}(\{\in \})} teorii mnogości (czyli {\displaystyle \in } jest binarnym symbolem relacyjnym) są:
A B ( x ( x A x B ) A = B ) {\displaystyle \forall A\forall B(\forall x(x\in A\iff x\in B)\Rightarrow A=B)} P Z ( Z P x ( x Z x X ) ) {\displaystyle \exists P\forall Z(Z\in P\iff \forall x(x\in Z\Rightarrow x\in X))}
  • Przykładami formuł języka L ( { } ) {\displaystyle {\mathcal {L}}(\{\star \})} teorii grup (czyli {\displaystyle \star } jest binarnym symbolem funkcyjnym) są:
( x 1 G ) ( ( x 1 x 2 ) x 3 = x 1 ( x 2 x 3 ) ) , {\displaystyle (\forall x_{1}\in G)((x_{1}\star x_{2})\star x_{3}=x_{1}\star (x_{2}\star x_{3})),} ( e G ) ( a G ) ( e a = a ) , {\displaystyle (\exists e\in G)(\forall a\in G)(e\star a=a),} ( a G ) ( b G ) ( b a = e ) , {\displaystyle (\forall a\in G)(\exists b\in G)(b\star a=e),}

Zobacz też | edytuj kod

Na podstawie artykułu: "Formuła logiczna" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy