Затворени класове от булеви функции
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Математика › Дискретна математика › Затворени класове \(T_0,T_1,S,M,L\)
Затворени класове от булеви функции.
\(T_0,\;T_1,\;S,\;M,\;L\)
Определения, мощности, таблица за основните функции, 5 разработени задачи и връзка с критерия на Пост
Защо множествата \(T_0,\;T_1,\;S,\;M,\;L\) са специални и защо заслужават отделно изучаване
В теорията на булевите функции има пет особено важни класа функции, които се срещат отново и отново: функции, които запазват нулата, функции, които запазват единицата, самодвойствени функции, монотонни функции и линейни функции. Те описват естествени ограничения върху поведението на логическите операции.
Тези класове са централни и в една от най-важните идеи на дискретната математика — критерия на Пост за функционална пълнота. Ако едно множество булеви функции е изцяло съдържано в някой от тези класове, то не може да реализира всички булеви функции. Следователно \(T_0,\;T_1,\;S,\;M,\;L\) са естествените „бариерни класове", показващи кога едно множество операции не е достатъчно богато.
Какво означава „затворен клас"?
Казваме, че клас от булеви функции е затворен по суперпозиция, ако всеки път, когато комбинираме функции от него, получаваме отново функция от същия клас. Именно в този смисъл всеки от петте класа е затворен.
Казваме, че клас от булеви функции е затворен по суперпозиция, ако всеки път, когато комбинираме функции от него, получаваме отново функция от същия клас. Именно в този смисъл всеки от петте класа е затворен.
Обозначение. Множеството на всички булеви функции на \(n\) променливи означаваме с \(P_2\) и \(|P_2|=2^{2^n}\). Мощностите по-долу се разглеждат в \(P_2\).
1. Класовете \(T_0\) и \(T_1\)
Определение 1. Булева функция \(f(x_1,\dots,x_n)\) запазва нулата, ако
\[f(0,0,\dots,0)=0.\]
Множеството на всички такива функции се означава с \(T_0\).
Определение 2. Булева функция \(f(x_1,\dots,x_n)\) запазва единицата, ако
\[f(1,1,\dots,1)=1.\]
Множеството на всички такива функции се означава с \(T_1\).
Идея. Функциите от \(T_0\) не „създават" единица от пълна нула; функциите от \(T_1\) не „унищожават" единицата, когато всички входове са единици.
Мощности. В \(P_2\) важат:
\[|T_0|=2^{2^n-1},\qquad|T_1|=2^{2^n-1}.\]
В \(T_0\) стойността върху \((0,\dots,0)\) е фиксирана (\(=0\)), а за останалите \(2^n-1\) набора стойностите са произволни. Аналогично за \(T_1\).
Сечение и обединение.
\[|T_0\cap T_1|=\frac{1}{4}\cdot2^{2^n},\qquad|T_0\cup T_1|=\frac{3}{4}\cdot2^{2^n}.\]
В сечението са фиксирани стойностите в две точки: \((0,\dots,0)\) и \((1,\dots,1)\).
1
Намерете мощностите на \(T_0,\;T_1,\;T_0\cap T_1\) и \(T_0\cup T_1\) за булеви функции на две променливи.
▼
Решение
За \(n=2\) имаме \(2^n=4\). Прилагаме формулите:
\[|T_0|=2^{4-1}=8,\qquad|T_1|=2^{4-1}=8,\]
\[|T_0\cap T_1|=2^{4-2}=4,\qquad|T_0\cup T_1|=8+8-4=12.\]
Следователно:
\[\boxed{|T_0|=8,\quad|T_1|=8,\quad|T_0\cap T_1|=4,\quad|T_0\cup T_1|=12.}\]
2. Класът \(S\) — самодвойствени функции
Определение 3. За булева функция \(f(x_1,\dots,x_n)\) нейната двойнствена функция е
\[f^*(x_1,\dots,x_n)=\overline{f(\overline{x_1},\dots,\overline{x_n})}.\]
Определение 4. Булева функция \(f\) се нарича самодвойствена, ако \(f=f^*\), т.е.
\[f(x_1,\dots,x_n)=\overline{f(\overline{x_1},\dots,\overline{x_n})}\]
за всеки набор \((x_1,\dots,x_n)\). Множеството на всички самодвойствени функции се означава с \(S\).
Двойнствени на основни функции:
\[(x_1\cdot x_2)^*=x_1\lor x_2,\qquad(x_1\lor x_2)^*=x_1\cdot x_2,\]
\[(x_1+x_2)^*=x_1\equiv x_2,\qquad(x_1\equiv x_2)^*=x_1+x_2,\]
\[(x_1\to x_2)^*=x_1\cdot\overline{x_2}.\]
Функциите \(x,\overline{x},x_1,x_2,\overline{x_1},\overline{x_2}\) са самодвойствени.
Как се намира двойнствена функция по таблица?
Ако редовете са подредени лексикографски (\(000,001,\dots,111\)) и стойностите на \(f\) са \(a_1,a_2,\dots,a_{2^n}\), то стойностите на \(f^*\) са \(\overline{a_{2^n}},\overline{a_{2^n-1}},\dots,\overline{a_1}\). Тоест обръщаме реда на стойностите и инвертираме всяка от тях.
Ако редовете са подредени лексикографски (\(000,001,\dots,111\)) и стойностите на \(f\) са \(a_1,a_2,\dots,a_{2^n}\), то стойностите на \(f^*\) са \(\overline{a_{2^n}},\overline{a_{2^n-1}},\dots,\overline{a_1}\). Тоест обръщаме реда на стойностите и инвертираме всяка от тях.
2
Намерете двойнствената функция на \(f(x_1,x_2,x_3)=x_1\lor(x_2\cdot x_3)\) чрез формула.
▼
Решение
По определение:
\[f^*(x_1,x_2,x_3)=\overline{f(\overline{x_1},\overline{x_2},\overline{x_3})}.\]
Намираме:
\[f(\overline{x_1},\overline{x_2},\overline{x_3})=\overline{x_1}\lor(\overline{x_2}\cdot\overline{x_3}).\]
Следователно:
\[f^*=\overline{\overline{x_1}\lor(\overline{x_2}\cdot\overline{x_3})}.\]
По закона на Де Морган:
\[f^*=x_1\cdot\overline{\overline{x_2}\cdot\overline{x_3}}=x_1\cdot(x_2\lor x_3).\]
Следователно \(\boxed{f^*(x_1,x_2,x_3)=x_1\cdot(x_2\lor x_3)}\). \(\blacksquare\)
Мощност на \(S\).
\[|S|=2^{2^{n-1}}.\]
Множеството от всички \(2^n\) набора се разбива на \(2^{n-1}\) двойки \((\alpha,\overline{\alpha})\). За всяка двойка изборът на стойността в единия набор еднозначно определя стойността в другия.
Мощност на \(S\cap T_0\). Тъй като за самодвойствена функция \(f(0,\dots,0)=\overline{f(1,\dots,1)}\), получаваме \(S\cap T_0=S\cap T_1\) и
\[|S\cap T_0|=|S\cap T_1|=2^{2^{n-1}-1}.\]
Защо \(S\cap T_0=S\cap T_1\)?
Ако \(f\in S\), то по определение \(f(0,\dots,0)=\overline{f(1,\dots,1)}\). Следователно двете стойности са противоположни — едната е \(0\), другата е \(1\). Не може и двете да са \(0\) (т.е. \(f\) не може едновременно да е в \(T_0\) и да нарушава \(T_1\)), нито и двете да са \(1\). Затова \(f\in S\cap T_0\) тогава и само тогава, когато \(f(0,\dots,0)=0\) и \(f(1,\dots,1)=1\), което е точно условието за \(f\in S\cap T_1\). Следователно двете сечения съвпадат.
Ако \(f\in S\), то по определение \(f(0,\dots,0)=\overline{f(1,\dots,1)}\). Следователно двете стойности са противоположни — едната е \(0\), другата е \(1\). Не може и двете да са \(0\) (т.е. \(f\) не може едновременно да е в \(T_0\) и да нарушава \(T_1\)), нито и двете да са \(1\). Затова \(f\in S\cap T_0\) тогава и само тогава, когато \(f(0,\dots,0)=0\) и \(f(1,\dots,1)=1\), което е точно условието за \(f\in S\cap T_1\). Следователно двете сечения съвпадат.
3. Класът \(M\) — монотонни функции
Определение 5. Булева функция \(f(x_1,\dots,x_n)\) се нарича монотонна, ако за всеки два набора \((\alpha_1,\dots,\alpha_n)\le(\beta_1,\dots,\beta_n)\) по координати следва
\[f(\alpha_1,\dots,\alpha_n)\le f(\beta_1,\dots,\beta_n).\]
Множеството на всички монотонни функции се означава с \(M\).
Интуиция. Монотонните функции описват системи без „отрицателно влияние" на входовете: когато увеличаваме вход от \(0\) към \(1\), изходът не може да „падне" от \(1\) към \(0\).
Примери.
Монотонни са: \(0,\;1,\;x_1,\;x_2,\;x_1\cdot x_2,\;x_1\lor x_2\).
Немонотонни са: \(\overline{x},\;x_1+x_2,\;x_1\equiv x_2,\;x_1\to x_2,\;x_1\mid x_2,\;x_1\downarrow x_2\).
Монотонни са: \(0,\;1,\;x_1,\;x_2,\;x_1\cdot x_2,\;x_1\lor x_2\).
Немонотонни са: \(\overline{x},\;x_1+x_2,\;x_1\equiv x_2,\;x_1\to x_2,\;x_1\mid x_2,\;x_1\downarrow x_2\).
3
Докажете, че импликацията \(x_1\to x_2\) не е монотонна.
▼
Решение
Разглеждаме два набора: \((0,0)\le(1,0)\) по координати. Изчисляваме:
\[(0\to0)=1,\qquad(1\to0)=0.\]
При преминаване от по-малкия набор към по-големия стойността спада от \(1\) към \(0\). Следователно функцията не е монотонна. \(\blacksquare\)
Мощност на \(M\). За \(n\) променливи \(|M|\) е равна на числото на Дедекинд \(D(n)\), за което няма проста обща формула. Първите стойности:
\[D(1)=3,\quad D(2)=6,\quad D(3)=20,\quad D(4)=168.\]
За \(n=2\): \(|M|=6\), а шестте монотонни функции са точно \(0,\;1,\;x_1,\;x_2,\;x_1\cdot x_2,\;x_1\lor x_2\).
4. Класът \(L\) — линейни функции
Определение 6. Булева функция се нарича линейна, ако нейният полином на Жегалкин е от степен най-много \(1\):
\[f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus a_2x_2\oplus\cdots\oplus a_nx_n,\]
където \(a_i\in\{0,1\}\) и \(\oplus\) е събиране по модул \(2\). Множеството на всички линейни функции се означава с \(L\).
Забележка. Алгебрично това са т.нар. афинни функции над \(P_2\).
Кои основни функции са линейни?
Линейни: \(0,\;1,\;x,\;\overline{x},\;x_1,\;x_2,\;x_1+x_2,\;x_1\equiv x_2\).
Нелинейни: \(x_1\cdot x_2,\;x_1\lor x_2,\;x_1\to x_2,\;x_1\mid x_2,\;x_1\downarrow x_2\).
Линейни: \(0,\;1,\;x,\;\overline{x},\;x_1,\;x_2,\;x_1+x_2,\;x_1\equiv x_2\).
Нелинейни: \(x_1\cdot x_2,\;x_1\lor x_2,\;x_1\to x_2,\;x_1\mid x_2,\;x_1\downarrow x_2\).
Мощност на \(L\).
\[|L|=2^{n+1},\]
защото всеки от \(n+1\) коефициента \(a_0,a_1,\dots,a_n\) се избира независимо от \(\{0,1\}\).
Необходимо и достатъчно условие \(f\in L\cap S\). Нека \(f=a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n\). Тогава \(f\in L\cap S\) тогава и само тогава, когато
\[a_1\oplus a_2\oplus\cdots\oplus a_n=1.\]
Тоест броят на ненулевите коефициенти пред променливите е нечетен.
4
Докажете условието за самодвойственост на линейна функция.
▼
Доказателство
Нека \(f=a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n\). Изчисляваме \(f(\overline{x_1},\dots,\overline{x_n})\):
\[f(\overline{x})=a_0\oplus a_1(1\oplus x_1)\oplus\cdots\oplus a_n(1\oplus x_n)=a_0\oplus(a_1\oplus\cdots\oplus a_n)\oplus a_1x_1\oplus\cdots\oplus a_nx_n.\]
Самодвойствеността изисква \(f(\overline{x})=\overline{f(x)}=1\oplus f(x)\), т.е.:
\[a_0\oplus(a_1\oplus\cdots\oplus a_n)\oplus a_1x_1\oplus\cdots\oplus a_nx_n=1\oplus a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n.\]
След съкращаване:
\[a_1\oplus\cdots\oplus a_n=1.\]
Това е необходимото и достатъчно условие. \(\blacksquare\)
Мощност на \(L\cap S\). Условието \(a_1\oplus\cdots\oplus a_n=1\) се изпълнява за точно половината от \(2^n\) избора на \((a_1,\dots,a_n)\), а \(a_0\) е свободен:
\[|L\cap S|=2\cdot2^{n-1}=2^n.\]
5
Намерете мощността на \(L\cap M\) в \(P_2\) (за \(n\) променливи).
▼
Решение
Нека \(f=a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n\) е линейна. Ако поне два коефициента \(a_i\) са равни на \(1\), функцията съдържа XOR на две или повече променливи и не е монотонна (увеличаването на едната може да намали изхода). Следователно монотонна линейна функция може да има най-много един \(a_i=1\). Функцията \(1\oplus x_i=\overline{x_i}\) не е монотонна. Остават само:
\[0,\quad1,\quad x_1,\quad x_2,\quad\dots,\quad x_n.\]
Следователно:
\[\boxed{|L\cap M|=n+2.}\]
За \(n=2\): \(|L\cap M|=4\); за \(n=4\): \(|L\cap M|=6\). \(\blacksquare\)
Обобщена таблица
| Функция | \(T_0\) | \(T_1\) | \(S\) | \(M\) | \(L\) |
|---|---|---|---|---|---|
| \(0\) | Да | Не | Не | Да | Да |
| \(1\) | Не | Да | Не | Да | Да |
| \(x\) | Да | Да | Да | Да | Да |
| \(\overline{x}\) | Не | Не | Да | Не | Да |
| \(x_1\cdot x_2\) | Да | Да | Не | Да | Не |
| \(x_1\lor x_2\) | Да | Да | Не | Да | Не |
| \(x_1+x_2\) (XOR) | Да | Не | Не | Не | Да |
| \(x_1\equiv x_2\) | Не | Да | Не | Не | Да |
| \(x_1\to x_2\) | Не | Да | Не | Не | Не |
| \(x_1\mid x_2\) (Шефер) | Не | Не | Не | Не | Не |
| \(x_1\downarrow x_2\) (Пиърс) | Не | Не | Не | Не | Не |
Задачи за самостоятелна работа
Опитайте сами, след което сравнете с теорията по-горе.
Задача 1За \(n=3\) намерете мощностите на \(T_0,\;T_1,\;T_0\cap T_1,\;T_0\cup T_1\).
Задача 2Намерете двойнствената функция на \(f(x_1,x_2,x_3)=x_1\cdot(x_2\lor x_3)\).
Задача 3Покажете чрез таблица за истинност, че \(x_1+x_2\) не е самодвойствена.
Задача 4Докажете, че \(x_1\lor x_2\) е монотонна, а \(x_1\equiv x_2\) не е монотонна.
Задача 5Кои от следните функции принадлежат на \(L\)?
\[1\oplus x_1\oplus x_2,\qquad x_1\oplus x_2\oplus x_3,\qquad 1\oplus x_1,\qquad x_1\cdot x_2\oplus x_3.\]
Задача 6Намерете необходимо и достатъчно условие линейната функция \(f=a_0\oplus a_1x_1\oplus a_2x_2\oplus a_3x_3\oplus a_4x_4\) да бъде самодвойствена.
Задача 7Намерете \(|L\cap S|\) за \(n=4\) и \(|L\cap M|\) за \(n=4\).
Видео уроци
Свързани уроци
◀
Булеви функции — свойства, пълнота и теорема на Бул
Комутативност, асоциативност, ДДНФ, пълни множества — теорема на Бул, 4 разработени задачи и тест.
Преглед на урока →
◀
Полином на Жегалкин — представяне на булеви функции
Определение, теорема за еднозначност, два метода за намиране — 7 разработени задачи.
Преглед на урока →
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
🎓 Подготовка за изпити
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
📚 Текущо обучение и студенти
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Коментари
Публикуване на коментар