Wersja z 12:42, 13 lis 2009 edytuj JAnDbot (dyskusja \| edycje) 115 771 edycji m robot usuwa: ca, en, es, fr ← poprzednia edycja		Wersja z 11:03, 27 mar 2010 edytuj anuluj edycję MastiBot (dyskusja \| edycje) Boty 3 413 312 edycji m Wspomagane przez robota ujednoznacznienie: Przegląd zagadnień z zakresu logiki - Zmieniono link(i) Wikipedia:Skarbnica Wikipedii/Przegląd zagadnień z zakresu logiki; zmiany kosmetyczne następna edycja →
Linia 1: '''Formuła logiczna''' to określenie dozwolonego wyrażenia w wielu systemach [[logika matematyczna\|logicznych]], m.in. w [[Rachunek predykatów pierwszego rzędu\|rachunku kwantyfikatorów]] oraz w [[rachunek zdań\|rachunku zdań]]. == Rachunek zdań == [[Zdanie logiczne\|Zdania]] rachunku zdań są formułami tegoż rachunku. Tak więc, 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 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>\forall x \phi</math> oraz <math>\exist x \phi</math> są nią również. === Formalna definicja === Niech <math>\tau</math> będzie ustalonym alfabetem, czyli zbiorem '''stałych''', '''[[symbol funkcyjny\|symboli funkcyjnych]]''' i '''[[symbol relacyjny\|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'''. Linia 19: '''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łą (tzw formuła atomową), * 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łą (tzw formuła atomową), * jeśli <math>\varphi,\psi</math> są formułami oraz <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). Bardziej precyzyjnie: * każde wystąpienie zmiennej <math>x_i</math> w formule atomowej jest wolne, * jeśli <math>\psi</math> to formuła postaci <math>(Qx_i)(\phi)</math>, to każde wystąpienie zmiennej <math>x_i</math> w formule <math>\psi</math> jest związane, * jeśli <math>\psi,\varphi</math> to formuły i pewne wystąpienie zmiennej <math>x_i</math> w formule <math>\psi</math> jest związane (wolne, odpowiednio), to wystąpienie to rozważane w formułach <math>\varphi\psi</math>, <math>\psi\varphi</math> oraz <math>\neg \psi</math> 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 [[Zdanie logiczne\|zdaniami]] (danego języka). === 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ż == * [[Koniunktywna postać normalna]], * [[Dysjunktywna postać normalna]], * [[Prawa de Morgana]], * [[Logika]], * [[Wikipedia:Skarbnica Wikipedii/Przegląd zagadnień z zakresu logiki\|Przegląd zagadnień z zakresu logiki]], [[Kategoria:Logika matematyczna]]

Formuła logiczna: Różnice pomiędzy wersjami