Русская Википедия:Предполные классы

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

• Класс <math>T_0</math> функций, сохраняющих константу 0:
  <math>T_0=\left\{f(x_1,\dots,x_n)|f(0,\dots,0)=0\right\}</math>.
• Класс <math>T_1</math> функций, сохраняющих константу 1:
  <math>T_1=\left\{f(x_1,\dots,x_n)|f(1,\dots,1)=1\right\}</math>.
• Класс <math>S</math> самодвойственных функций:
  <math>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>M</math> монотонных функций:
  <math>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>L</math> линейных функций — представимых полиномом Жегалкина первой степени:
  <math>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>M\cap T_0</math> предполон в классах <math>T_0</math> и <math>M</math>.

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

Литература

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