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

Предполный класс в теории булевых функций — замкнутый класс булевых функций, обладающий следующим свойством — замыкание объединения этого класса с любой булевой функцией, не принадлежащей ему, порождает все <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

Отрывок, характеризующий Предполные классы

– Да что же?
– Ну я теперь скажу. Ты знаешь, что Соня мой друг, такой друг, что я руку сожгу для нее. Вот посмотри. – Она засучила свой кисейный рукав и показала на своей длинной, худой и нежной ручке под плечом, гораздо выше локтя (в том месте, которое закрыто бывает и бальными платьями) красную метину.
– Это я сожгла, чтобы доказать ей любовь. Просто линейку разожгла на огне, да и прижала.
Сидя в своей прежней классной комнате, на диване с подушечками на ручках, и глядя в эти отчаянно оживленные глаза Наташи, Ростов опять вошел в тот свой семейный, детский мир, который не имел ни для кого никакого смысла, кроме как для него, но который доставлял ему одни из лучших наслаждений в жизни; и сожжение руки линейкой, для показания любви, показалось ему не бесполезно: он понимал и не удивлялся этому.
– Так что же? только? – спросил он.
– Ну так дружны, так дружны! Это что, глупости – линейкой; но мы навсегда друзья. Она кого полюбит, так навсегда; а я этого не понимаю, я забуду сейчас.
– Ну так что же?
– Да, так она любит меня и тебя. – Наташа вдруг покраснела, – ну ты помнишь, перед отъездом… Так она говорит, что ты это всё забудь… Она сказала: я буду любить его всегда, а он пускай будет свободен. Ведь правда, что это отлично, благородно! – Да, да? очень благородно? да? – спрашивала Наташа так серьезно и взволнованно, что видно было, что то, что она говорила теперь, она прежде говорила со слезами.
Ростов задумался.
– Я ни в чем не беру назад своего слова, – сказал он. – И потом, Соня такая прелесть, что какой же дурак станет отказываться от своего счастия?
– Нет, нет, – закричала Наташа. – Мы про это уже с нею говорили. Мы знали, что ты это скажешь. Но это нельзя, потому что, понимаешь, ежели ты так говоришь – считаешь себя связанным словом, то выходит, что она как будто нарочно это сказала. Выходит, что ты всё таки насильно на ней женишься, и выходит совсем не то.