Definicja

Aby zdefiniować formalnie, czym jest zdanie, najpierw ustalamy zbiór zmiennych zdaniowych (tradycyjnie jest to zbiór liter ${\displaystyle p,q,r,s}$ z indeksami będącymi liczbami naturalnymi, czyli ${\displaystyle p_{0},p_{1},\dots ,q_{0},q_{1},\dots ,r_{0},r_{1},\dots ,s_{0},s_{1},\dots }$). Zmienne zdaniowe mają reprezentować proste zdania, których wartość logiczną 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 zbiór spójników logicznych, z których każdy ma ustaloną arność. Najczęściej używanymi spójnikami logicznymi są: spójnik jednoargumentowy ${\displaystyle \neg }$ (negacja) i cztery spójniki dwuargumentowe: ${\displaystyle \vee }$ (alternatywa), ${\displaystyle \wedge }$ (koniunkcja), ${\displaystyle \Rightarrow }$ (implikacja) i ${\displaystyle \Leftrightarrow }$ (równoważność).

Niech ${\displaystyle {\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 ${\displaystyle {\mathcal {Z}},}$
• jeśli ${\displaystyle \varphi \in {\mathcal {Z}},}$ to również ${\displaystyle \neg \varphi \in {\mathcal {Z}},}$
• jeśli ${\displaystyle \varphi ,\psi \in {\mathcal {Z}}}$ i ${\displaystyle *}$ jest binarnym spójnikiem zdaniowym, to również ${\displaystyle (\varphi *\psi )\in {\mathcal {Z}}.}$

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

Przykłady i własności

Ustalmy zbiór zmiennych zdaniowych i zbiór spójników logicznych jak zaproponowane powyżej.

• Następujące ciągi symboli są zdaniami naszego rachunku zdań: ${\displaystyle {\big (}(p_{0}\wedge p_{0})\vee p_{0}){\big )},}$ ${\displaystyle {\big (}(p_{1}\Rightarrow p_{2})\Leftrightarrow \neg p_{3}{\big )},}$ ${\displaystyle \neg p_{889}.}$
• Często dla poprawienia czytelności naszych napisów omijamy pewne nawiasy i piszemy np. ${\displaystyle p_{0}\vee p_{1}}$ zamiast ${\displaystyle (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ń: ${\displaystyle p_{0}\wedge ),}$ ${\displaystyle \vee p_{889}.}$
• Jeśli każdej zmiennej zdaniowej przyporządkujemy jakąś wartość logiczną, 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ą ${\displaystyle (p_{0}\vee \neg p_{0})}$ i ${\displaystyle {\big (}(p_{0}\wedge p_{0})\Rightarrow p_{0}){\big )}.}$
• Skończone ciągi zdań mogą utworzyć dowód.

Podział zdań

• Zdania proste – w których nie występuje żaden spójnik
• Zdania złożone – w których występuje co najmniej jeden spójnik

Definicja

Ustalmy alfabet ${\displaystyle \tau }$ 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 ${\displaystyle x_{0},x_{1},\dots }$). Najpierw definiujemy termy języka ${\displaystyle {\mathcal {L}}(\tau )}$ jako elementy najmniejszego zbioru ${\displaystyle \mathbf {T} }$ takiego, że:

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

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

• jeśli ${\displaystyle t_{1},t_{2}\in \mathbf {T} ,}$ to ${\displaystyle t_{1}=t_{2}}$ należy do ${\displaystyle \mathbf {F} ,}$
• jeśli ${\displaystyle t_{1},\dots ,t_{n}\in \mathbf {T} }$ zaś ${\displaystyle P\in \tau }$ jest ${\displaystyle n}$-arnym symbolem relacyjnym, to wyrażenie ${\displaystyle P(t_{1},\dots ,t_{n})}$ należy do ${\displaystyle \mathbf {F} ,}$
• jeśli ${\displaystyle \varphi ,\psi \in \mathbf {F} }$ i ${\displaystyle *}$ jest binarnym spójnikiem zdaniowym, to ${\displaystyle (\varphi *\psi )\in \mathbf {F} }$ oraz ${\displaystyle \neg \varphi \in \mathbf {F} ,}$
• jeśli ${\displaystyle x_{i}}$ jest zmienną oraz ${\displaystyle \varphi \in \mathbf {F} ,}$ to także ${\displaystyle (\exists x_{i})(\varphi )\in \mathbf {F} }$ i ${\displaystyle (\forall x_{i})(\varphi )\in \mathbf {F} .}$

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

Zdanie w języku pierwszego rzędu ${\displaystyle {\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.

Przykłady i własności

• Następujące formuły są zdaniami (dla odpowiednio dobranego alfabetu ${\displaystyle \tau }$): ${\displaystyle (\forall x_{1})(\exists x_{2})(x_{2}=f(x_{1})),}$ ${\displaystyle (\forall x_{2})(\exists x_{1})(x_{2}=f(x_{1})),}$ AC, CH
• Następująca formuła nie jest zdaniem ponieważ zmienna ${\displaystyle x_{1}}$ nie jest związana: ${\displaystyle (\forall x_{2})(\exists x_{3})(x_{1}=x_{2}+x_{3}).}$
• Jeśli stałe, symbole funkcyjne i symbole relacyjne alfabetu ${\displaystyle \tau }$ 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.