Исказна алгебра

Дефиниција

Нека су $\top$ и $\bot$ два различита знака. Уређена шесторка $(\{\top ,\bot \},\wedge ,\vee ,\Rightarrow ,\Leftrightarrow ,\neg )$ назива се исказна алгебра ако су $\wedge ,\vee ,\Rightarrow ,\Leftrightarrow$ бинарне операције скупа $\{\top ,\bot \}$ дате таблицама

$\wedge$ $\top$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\bot$

$\vee$ $\top$ $\bot$ $\top$ $\top$ $\top$ $\bot$ $\top$ $\bot$

$\Rightarrow$ $\top$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\top$ $\top$

$\Leftrightarrow$ $\top$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$

а $\neg$ унарна операциај дата следећом таблицом

$\neg$ $\top$ $\bot$ $\bot$ $\top$

---

Приоритет операција одговара приоритету логичких везника у исказним формулама.

Свако пресликавање $\{\top ,\bot \}^{n}\rightarrow \{\top ,\bot \}$ назива се n-арна операција исказне алгебре.

Поред наведених операција, у исказној алгебри често се користе и следеће две:

• $x\uparrow y=\neg (x\wedge y)$    Шеферова
• $x\downarrow y=\neg (x\vee y)$    Лукасијевичева

Однос исказних формула и исказне алгебре

Исказне формуле интерпретирамо у исказној алгебри.

Валуација $\alpha \,\!$ је пресликавање $Var\rightarrow \{\top ,\bot \}$ које исказним словима додељује вредности из скупа $\{\top ,\bot \}$.

Вредност исказне формуле A у валуацији ${\alpha }\,\!$, у ознаци $\upsilon _{\alpha }(A)\,\!$ дефинисана је на следећи начин:

$\upsilon _{\alpha }(p_{i})=\alpha (p_{i})\,\!$

$\upsilon _{\alpha }(A\wedge B)=\upsilon _{\alpha }(A)\wedge \upsilon _{\alpha }(B)$

$\upsilon _{\alpha }(A\vee B)=\upsilon _{\alpha }(A)\vee \upsilon _{\alpha }(B)$

$\upsilon _{\alpha }(A\Rightarrow B)=\upsilon _{\alpha }(A)\Rightarrow \upsilon _{\alpha }(B)$

$\upsilon _{\alpha }(A\Leftrightarrow B)=\upsilon _{\alpha }(A)\Leftrightarrow \upsilon _{\alpha }(B)$

$\upsilon _{\alpha }(\neg A)=\neg \upsilon _{\alpha }(A)$

Значи, исказној формули $A(p_{1},...,p_{n})\,\!$ додељујемо функцију

${\bar {A}}:\{\top ,\bot \}^{n}\rightarrow \{\top ,\bot \}$

за коју важи $A(x_{1},...,x_{n})=\upsilon _{\alpha }(A(p_{1},...,p_{n}))\,\!$, где је $\alpha$ валуација за коју важи $\alpha (p_{i})=x_{i},i\in \{1,2,...,n\}$.