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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

Приклади

[ред. | ред. код]

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

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

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

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


...

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

Дивись також

[ред. | ред. код]

Література

[ред. | ред. код]