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

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

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

• клас функцій, що зберігають константу 0:
  $T_{0}=\left\{f(x_{1},\dots ,x_{n}):\ f(0,\dots ,0)=0\right\}$.
• клас функцій, що зберігають константу 1:
  $T_{1}=\left\{f(x_{1},\dots ,x_{n}):\ f(1,\dots ,1)=1\right\}$.
• клас самодвоїстих функцій:
  $S=\left\{f(x_{1},\dots ,x_{n}):\ f({\overline {x_{1}}},\dots ,{\overline {x_{n}}})={\overline {f(x_{1},\dots ,x_{n})}}\right\}$.
• клас монотоних функцій:
  $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\}$.
• клас лінійних функцій:
  $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\}$.

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

Приклади

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

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

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

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

...

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

Дивись також

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

Література

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