Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все
. Множество предполных классов булевых функций исчерпывается списком:
- Класс
функций, сохраняющих константу 0:
.
- Класс
функций, сохраняющих константу 1:
.
- Класс
самодвойственных функций:
.
- Класс
монотонных функций:
.
- Класс
линейных функций — представимых полиномом Жегалкина первой степени:
.
Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс
предполон в классах
и
.
В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством — замыкание объединения этого класса с любой функцией из
, не принадлежащей ему, порождает все
. Но в случае k>2 на данный момент нет общего описания структуры предполных классов в отличие от двузначной логики.
Литература
- Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .