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

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

• Класс [math]\displaystyle{ T_0 }[/math] функций, сохраняющих константу 0:
  [math]\displaystyle{ T_0=\left\{f(x_1,\dots,x_n)|f(0,\dots,0)=0\right\} }[/math].
• Класс [math]\displaystyle{ T_1 }[/math] функций, сохраняющих константу 1:
  [math]\displaystyle{ T_1=\left\{f(x_1,\dots,x_n)|f(1,\dots,1)=1\right\} }[/math].
• Класс [math]\displaystyle{ S }[/math] самодвойственных функций:
  [math]\displaystyle{ S=\left\{f(x_1,\dots,x_n)|f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}\right\} }[/math].
• Класс [math]\displaystyle{ M }[/math] монотонных функций:
  [math]\displaystyle{ M=\left\{f(x_1,\dots,x_n)|\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)\right\} }[/math].
• Класс [math]\displaystyle{ L }[/math] линейных функций — представимых полиномом Жегалкина первой степени:
  [math]\displaystyle{ L=\left\{f(x_1,\dots,x_n)|f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus\dots\oplus a_nx_n,a_i\in\{0,1\}\right\} }[/math].

Также говорят о предполноте одного замкнутого класса в другом. Класс A предполон в классе B, если замыкание класса A с любой функцией, принадлежащей B, но не принадлежащей A, порождает класс B. Например, класс [math]\displaystyle{ M\cap T_0 }[/math] предполон в классах [math]\displaystyle{ T_0 }[/math] и [math]\displaystyle{ M }[/math].

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

Литература

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