Відкрити головне меню

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

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

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

  • клас функцій, що зберігають константу 0:
    .
  • клас функцій, що зберігають константу 1:
    .
  • клас самодвоїстих функцій:
    .
  • клас монотоних функцій:
    .
  • клас лінійних функцій:
    .

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

ПрикладиРедагувати

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

Хиба
 
Істина
 
Заперечення,
NOT
 
Кон'юнкція,
AND
 
Диз'юнкція,
OR
 
Виключна диз'юнкція,
XOR
 
Еквівалентність,
XNOR
 
Імплікація
 
Неімплікація
 
Штрих Шефера,
NAND
 
Стрілка Пірса,
NOR
 
 
 
 
 
 

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

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


...

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

Дивись такожРедагувати