Предполные классы

Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все . Множество предполных классов булевых функций исчерпывается списком:

  • Класс функций, сохраняющих константу 0:
    .
  • Класс функций, сохраняющих константу 1:
    .
  • Класс самодвойственных функций:
    .
  • Класс монотонных функций:
    .
  • Класс линейных функций — представимых полиномом Жегалкина первой степени:
    .

Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс предполон в классах и .

В многозначной логике предполные классы аналогично определяются как замкнутые классы, обладающие свойством — замыкание объединения этого класса с любой функцией из , не принадлежащей ему, порождает все . Но в случае k>2 на данный момент нет общего описания структуры предполных классов в отличие от двузначной логики.

ЛитератураПравить

  • Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986