Zdanie logiczne

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Ten artykuł dotyczy terminu w logice matematycznej. Zobacz też: inne znaczenia słowa zdanie.

Zdanie to jeden z podstawowych obiektów rozważanych w logice matematycznej. Dokładne określenie do czego ten termin się odnosi zależy od kontekstu w którym jest on używany.

Spis treści

1 Intuicje
2 Zdania w rachunku zdań
- 2.1 Definicja
- 2.2 Przykłady i własności
3 Zdania w logice pierwszego rzędu
- 3.1 Definicja
- 3.2 Przykłady i własności
4 Zdania w innych logikach
5 Zobacz też

[edytuj] Intuicje

Naszą intencją jest zdefiniowanie zdania logicznego jako zdania oznajmującego, któremu można przypisać jedną z dwóch ocen, nazywane wartościami logicznymi. Są nimi prawda albo fałsz. Ponieważ język logiki i matematyki znacznie różnią się od języków naturalnych, możemy modyfikować określenie podane w poprzednim zdaniu tak aby dopasować je do wymogów języków w logice. I tak możemy określać zdanie logiczne jako wyrażenie (niekoniecznie o skończonej długości), złożone z symboli danego języka połączonych relacjami iloczynu logicznego, sumy logicznej i negacji, któremu można (przynajmniej teoretycznie) podporządkować jedną z dwu wartości logicznych: prawda lub fałsz.

Określenia podobne do powyższych są często spotykane w podręcznikach, ale mają one tę podstawową wadę, że odwołują się do wartości logicznej. Ustalenie tej wartości logicznej w pewnych sytuacjach może być nie tylko że trudne, ale wręcz niemożliwe. Poza tym, jakkolwiek jej nie zdefiniujemy, prawdziwość zdania jest własnością zdania, więc najpierw powinniśmy wiedzieć czym są zdania.

[edytuj] Zdania w rachunku zdań

W rachunku zdań wszystkie rozważane obiekty są zdaniami.

[edytuj] Definicja

Aby zdefiniować formalnie czym jest zdanie, najpierw ustalamy zbiór zmiennych zdaniowych (tradycyjnie jest to zbiór liter $p, q, r, s$ z indeksami będącymi liczbami naturalnymi, czyli $p_0,p_1,\ldots,s_0,s_1,\ldots, r_0,r_1,\ldots,s_0,s_1,\ldots$ ). Zmienne zdaniowe mają reprezentować proste zdania których prawdziwość możemy łatwo rozstrzygnąć, ale ta interpretacja nie jest w ogóle potrzebna w rachunku zdań. Zmienne zdaniowe mogą być (i często są) traktowane jako formalne symbole bez specjalnego znaczenia poza budowaną teorią.

Następnie ustalamy listę spójników logicznych, z których każdy ma ustaloną arność. Najczęściej zbiór spójników logicznych składa się z jednego spójnika unarnego $\neg$ (negacja) i czterech spójników binarnych $\vee$ (alternatywa), $\wedge$ (dysjunkcja), $\Rightarrow$ (implikacja) i $\Leftrightarrow$ (równoważność). Możliwe są również inne wybory (niekoniecznie ograniczone do spójników unarnych i binarnych), ale dla ustalenia uwagi przyjmijmy że rozważane przez nas spójniki logiczne to właśnie $\neg$ , $\vee$ , $\wedge$ , $\Rightarrow$ i $\Leftrightarrow$ .

Niech ${\mathcal Z}$ będzie zbiorem ciągów symboli, który jest najmniejszym zbiorem o następujących własnościach:

każda zmienna zdaniowa należy do ${\mathcal Z}$ ,
jeśli $\varphi \in {\mathcal Z}$ , to również $\neg\varphi\in {\mathcal Z}$ ,
jeśli $\varphi,\psi\in {\mathcal Z}$ i $*$ jest binarnym spójnikiem zdaniowym, to również $(\varphi*\psi)\in {\mathcal Z}$ .

Elementy zbioru ${\mathcal Z}$ są nazywane zdaniami.

[edytuj] Przykłady i własności

Ustalmy zbiór zmiennych logicznych i zbiór spojników logicznych jak zaproponowane powyżej.

Następujące ciągi symboli są zdaniami naszego rachunku zdań: $\big((p_0\wedge p_0)\vee p_0)\big)$ , $\big((p_1\Rightarrow p_2)\Leftrightarrow \neg p_3\big)$ , $\neg p_{889}$ .
Często dla poprawienia czytelności naszych napisów omijamy pewne nawiasy i piszemy np $p_0\vee p_1$ zamiast $(p_0\vee p_1)$ . Istnieją również umowy co do kolejności wykonywanych operacji pozwalające na jeszcze poważniejsze omijanie nawiasów. Jednak ściśle biorąc nawiasy są potrzebne czy nawet niezbędne i lepiej jest je wszystkie zanotować niż zbyt wiele ominąć.
Następujące ciągi symboli nie są zdaniami naszego rachunku zdań: $p_0\wedge)$ , $(p 1)$ , $\vee p_{889}$ .
Jeśli każdej zmiennej zdaniowej przyporządkujemy jakąś wartość logiczna, to to przyporządkowanie jest rozszerzane na wszystkie zdania (przez indukcję po złożoności zdania). Niektóre zdania otrzymają wartość logiczną prawda bez względu na to jakie jest początkowe przyporządkowanie. Takie zdania nazywamy tautologiami rachunku zdań. Przykładami tautologii są $(p_0\vee \neg p_0)$ i $\big((p_0\wedge p_0)\Rightarrow p_0)\big)$ .
Skończone ciągi zdań mogą utworzyć dowód.

[edytuj] Zdania w logice pierwszego rzędu

W rachunku kwantyfikatorów struktura studiowanych wyrażeń jest o wiele bogatsza niż w rachunku zdań i zdania są tylko specjalnym rodzajem tychżesz wyrażeń.

[edytuj] Definicja

Ustalmy alfabet $τ$ który jest zbiorem stałych, symboli funkcyjnych i symboli relacyjnych (predykatów). Każdy z symboli ma określoną arność (która jest dodatnią liczbą całkowitą). Ustalamy też listę zmiennych (zwykle $x_0,x_1,\ldots$ ). Najpierw definiujemy termy języka ${\mathcal L}(\tau)$ jako elementy najmniejszego zbioru ${\bold T}$ takiego, że:

wszystkie stałe i zmienne należą do ${\bold T}$ ,
jeśli $t_1,\ldots,t_n\in {\bold T}$ i $f\in\tau$ jest $n$ -arnym symbolem funkcyjnym, to $f(t_1,\ldots,t_n)\in {\bold T}$ .

Następnie określamy zbiór formuł języka ${\mathcal L}(\tau)$ jako najmniejszy zbiór ${\bold F}$ taki, że:

jeśli $t_1, t_2\in {\bold T}$ , to $t 1 = t 2$ należy do ${\bold F}$ ,
jeśli $t_1,\ldots,t_n\in {\bold T}$ zaś $P\in\tau$ jest $n$ -arnym symbolem relacyjnym, to wyrażenie $P(t_1,\ldots,t_n)$ należy do ${\bold F}$ ,
jeśli $\varphi,\psi\in {\bold F}$ i $*$ jest binarnym spójnikiem zdaniowym, to $(\varphi*\psi)\in {\bold F}$ oraz $\neg \varphi\in {\bold F}$ ,
jeśli $x i$ jest zmienną oraz $\varphi\in {\bold F}$ , to także $(\exists x_i)(\varphi)\in {\bold F}$ i $(\forall x_i)(\varphi)\in {\bold F}$ .

W formułach postaci $(\exists x_i)(\varphi)$ i $(\forall x_i)(\varphi)$ mówimy że zmienna $x i$ znajduje się w zasięgu kwantyfikatora i jako taka jest związana.

Zdanie w języku pierwszego rzędu ${\mathcal L}(\tau)$ to taka formuła, w której każda zmienna jest związana, tj. znajduje się w zasięgu działania jakiegoś kwantyfikatora.

[edytuj] Przykłady i własności

Następujące formuły są zdaniami (dla odpowiednio dobranego alfabetu $τ$ ): $(\forall x_1)(\exists x_2)(x_2=f(x_1))$ , $(\forall x_2)(\exists x_1)(x_2=f(x_1))$ , AC, CH
Następująca formuła nie jest zdaniem ponieważ zmienna $x 1$ nie jest związana: $(\forall x_2)(\exists x_3)(x_1=x_2+x_3)$ .
Jeśli stałe, symbole funkcyjne i symbole relacyjne alfabetu $τ$ zostaną zinterpretowane (czyli gdy zbudujemy model dla naszego języka), to o każdym zdaniu możemy rozstrzygnąć czy jest ono spełnione w tym modelu czy też nie.

[edytuj] Zdania w innych logikach

Definicja zdania sformułowana powyżej dla logiki pierwszego rzędu może być w naturalny sposób przeniesiona na grunt innych logik. W szczególności w bardzo podobny sposób określamy czym jest zdanie w

logikach nieskończonościowych (zezwalających na użycie nieskończonych koniunkcji czy też nieskończenie wielu kwantyfikatorów),
logikach ze specjalnymi kwantifikatorami (takimi jak kwantyfikator Magidora-Malitza),
logice z $\varepsilon$ -symbolem Hilberta,
logikach wyższych rzędów