Formuła logiczna: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m kat. |
drobna rozbudowa (reorganizacja materialu, dodatki) |
||
Linia 1:
'''Formuła logiczna''' to określenie dozwolonego wyrażenia w wielu systemach [[logika matematyczna|logicznych]], m.in. w [[
▲'''Formuła logiczna''' to określenie dozwolonego wyrażenia w wielu systemach [[logika matematyczna|logicznych]], m.in. w [[rachunek kwantyfikatorów|rachunku kwantyfikatorów]] oraz w [[rachunek zdań|rachunku zdań]].
==
Każda [[zmienna zdaniowa]] <math>p_i</math> jest formułą. Taką formułę nazywa się ''literałem'' lub [[formuła atomowa|formułą atomową]]. Formułami są także [[negacja|negacje]] formuł atomowych, tzn <math>\neg p_i</math>. Ponadto, jeżeli <math>\varphi,\psi</math> są formułami i <math>*</math> jest binarnym [[Funktor zdaniotwórczy|spójnikiem zdaniowym]] ([[alternatywa|alternatywą]] <math>\vee</math>, [[Koniunkcja (matematyka)|koniunkcją]] <math>\wedge</math>, [[implikacja|implikacją]] <math>\Rightarrow</math> lub [[równoważność|równoważnością]] <math>\Leftrightarrow</math>), to <math>(\varphi*\psi)</math> oraz <math>\neg \varphi</math> 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 :<math>(p \vee q \vee r)</math> nie jest formułą
(formułą byłoby np. wyrażenie <math>((p \vee q) \vee r))</math>, lecz interpretacja takiej formuły jest jednoznaczna i wewnętrzne nawiasy w praktyce pomija się.
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 [[kwantyfikator]]y - jeżeli φ jest formułą rachunku kwantyfikatorów, to <math>\
===Formalna definicja===
Niech <math>\tau</math> 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ą [[Argumentowość|arność]] (która jest dodatnią liczbą całkowitą). Niech <math>x_0,x_1,\ldots</math> będzie nieskończoną listą '''zmiennych'''.
Przypomnijmy, że '''termy''' języka <math>{\mathcal L}(\tau)</math> to elementy najmniejszego zbioru <math>{\bold T}</math> takiego, że:
* wszystkie stałe i zmienne należą do <math>{\bold T}</math>,
* jeśli <math>t_1,\ldots,t_n\in {\bold T}</math> i <math>f\in\tau</math> jest <math>n</math>-arnym symbolem funkcyjnym, to <math>f(t_1,\ldots,t_n)\in {\bold T}</math>.
'''Formuły''' języka <math>{\mathcal L}(\tau)</math> są wprowadzane przez indukcję po ich złożoności jak następuje:
*jeśli <math>t_1, t_2\in {\bold T}</math>, to wyrażenie <math>t_1= t_2</math> jest formułą,
*jeśli <math>t_1,\ldots,t_n\in {\bold T}</math> zaś <math>P\in\tau</math> jest <math>n</math>-arnym symbolem relacyjnym, to wyrażenie <math>P(t_1,\ldots,t_n)</math> jest formułą,
*jeśli <math>\varphi,\psi\in {\bold F}</math> i <math>*</math> jest binarnym spójnikiem zdaniowym, to <math>(\varphi*\psi)</math> oraz <math>\neg \varphi</math> są formułami,
*jeśli <math>x_i</math> jest zmienną oraz <math>\varphi</math> jest formułą, to także <math>(\exists x_i)(\varphi)</math> i <math>(\forall x_i)(\varphi)</math> są formułami.
===Zmienne wolne w formule===
W formułach postaci <math>(\exists x_i)(\varphi)</math> i <math>(\forall x_i)(\varphi)</math> mówimy że zmienna <math>x_i</math> znajduje się w zasięgu [[kwantyfikator]]a 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 <math>(\exists x_i)(\varphi)</math> czy też <math>(\forall x_i)(\varphi)</math> pojawia się jako jedna z części użytych w budowie, ale ograniczamy się do występowań zmiennej <math>x_i</math> w <math>\varphi</math> (i mówimy że konkretne wystąpienie zmiennej jest wolne lub związane).
===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 <math>{\mathcal L}(\{\in\})</math> [[teoria mnogości|teorii mnogości]] (czyli <math>\in</math> jest binarnym symbolem relacyjnym) są:
:<math> \forall A \forall B (\forall x (x\in A\iff x\in B)\Rightarrow A=B)</math>
:<math>\exist P \forall Z (Z\in P \iff \forall x (x\in Z \Rightarrow x\in X))</math>
*Przykładami formuł języka <math>{\mathcal L}(\{\star\})</math> [[teoria grup|teorii grup]] (czyli <math>\star</math> jest binarnym symbolem funkcyjnym) są:
:<math>(\forall x_1\in G)((x_1 \star x_2) \star x_3 = x_1 \star (x_2 \star x_3))</math>,
:<math>(\exists e \in G) (\forall a \in G)(e \star a = a)</math>,
:<math>(\forall a \in G)(\exists b \in G)(b \star a = e)</math>,
==Zobacz też==
| |||