Передповний клас функцій алгебри логіки

Передповний клас функцій алгебри логіки (клас Поста) — замкнений клас функцій алгебри логіки, замикання об'єднання цього класу з довільною функцією алгебри логіки (яка йому не належить) утворює повний клас функцій алгебри логіки — ${\displaystyle P_{2}}$.

Всього є 5 класів:

• клас функцій, що зберігають константу 0:
  ${\displaystyle T_{0}=\left\{f(x_{1},\dots ,x_{n}):\ f(0,\dots ,0)=0\right\}}$.
• клас функцій, що зберігають константу 1:
  ${\displaystyle T_{1}=\left\{f(x_{1},\dots ,x_{n}):\ f(1,\dots ,1)=1\right\}}$.
• клас самодвоїстих функцій:
  ${\displaystyle S=\left\{f(x_{1},\dots ,x_{n}):\ f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\right\}}$.
• клас монотоних функцій:
  ${\displaystyle M=\left\{f(x_{1},\dots ,x_{n}):\ \forall i(a_{i}\leq b_{i})\Rightarrow f(a_{1},\dots ,a_{n})\leq f(b_{1},\dots ,b_{n})\right\}}$.
• клас лінійних функцій:
  ${\displaystyle L=\left\{f(x_{1},\dots ,x_{n}):\ f(x_{1},\dots ,x_{n})=a_{0}\oplus a_{1}x_{1}\oplus \dots \oplus a_{n}x_{n},\;a_{i}\in \{0,1\}\right\}}$.

Довільний замкнутий клас, відмінний від ${\displaystyle P_{2}}$, повністю міститься хоча б в одному передповному класі.

Приклади

Приклади належності булевих функцій до класів.

	Хиба ${\displaystyle \bot }$	Істина ${\displaystyle \top }$	Заперечення, NOT ${\displaystyle \lnot A}$	Кон'юнкція, AND ${\displaystyle A\land B}$	Диз'юнкція, OR ${\displaystyle A\lor B}$	Виключна диз'юнкція, XOR ${\displaystyle A\oplus B}$	Еквівалентність, XNOR ${\displaystyle \ A\leftrightarrow B}$	Імплікація ${\displaystyle \ A\rightarrow B}$	Неімплікація ${\displaystyle \ A\not \rightarrow B}$	Штрих Шефера, NAND ${\displaystyle \ A|B}$	Стрілка Пірса, NOR ${\displaystyle \ A\downarrow B}$
${\displaystyle ~T_{0}}$	•			•	•	•			•
${\displaystyle ~T_{1}}$		•		•	•		•	•
${\displaystyle ~S}$			•
${\displaystyle ~M}$	•	•		•	•
${\displaystyle ~L}$	•	•	•			•	•

Щоб вибрати функціонально повну систему функцій потрібно, щоб таблиця з їхніх стовпців в кожному рядку містила хоча б одну порожню клітинку.

Щоб вибрати базис для класу потрібно, щоб таблиця з їхніх стовпців в кожному рядку (крім рядка цього класу) містила хоча б одну порожню клітинку.

...

В багатозначній логіці ще немає повного опису передповних класів.

Дивись також

• Решітка Поста

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.