Критерий на Пост
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Математика › Дискретна математика › Критерий на Пост
Критерий на Пост.
Функционална пълнота на множества от булеви функции
Теорема, подробно доказателство, бази на пълно множество, алгоритъм за проверка, 7 разработени задачи, самостоятелна работа и тест
Как да разберем дали дадено множество булеви функции може да реализира всички останали
Критерият на Пост е един от най-важните резултати в теорията на булевите функции. Той дава ясен и практически приложим отговор на фундаменталния въпрос: „Дали дадено множество булеви функции е достатъчно богато, за да породи чрез суперпозиция всички булеви функции?"
Това не е само теоретичен въпрос. В цифровата логика той означава дали даден набор логически елементи е достатъчен, за да се построи произволна схема. В програмирането — дали даден набор логически операции е достатъчен, за да се изрази всяко условие. След изучаването на петте специални затворени класа \(T_0,\;T_1,\;S,\;M,\;L\) идва естественият следващ въпрос: каква е тяхната роля при пълнотата? Именно тези пет класа са решаващи.
1. Напомняне: основни понятия
Определение 1. Нека \(F\) е множество от булеви функции. С \([F]\) означаваме множеството на всички функции, получени от \(F\) чрез суперпозиция.
Определение 2. Множество \(F\) се нарича пълно (функционално пълно), ако \([F]=P_2\), където \(P_2\) е множеството на всички булеви функции.
Определение 3. Клас булеви функции \(K\) се нарича затворен, ако от функции в \(K\) чрез суперпозиция се получават само функции от \(K\).
Напомняне за петте специални класа:
\[T_0=\{f:f(0,\dots,0)=0\},\qquad T_1=\{f:f(1,\dots,1)=1\},\]
\[S=\{f:f(x)=\overline{f(\overline{x})}\},\qquad M=\{\text{монотонни функции}\},\qquad L=\{\text{линейни функции}\}.\]
Ключов факт. Всеки от класовете \(T_0,\;T_1,\;S,\;M,\;L\) е собствен (не съвпада с \(P_2\)) и затворен по суперпозиция. Следователно, ако \(F\subseteq K\) за някой от тях, то \([F]\subseteq K\neq P_2\), и \(F\) не може да бъде пълно.
2. Теорема на Пост и критерий на Пост
Фундаментален факт на Пост. Всеки собствен затворен клас булеви функции е съдържан в поне един от класовете \(T_0,\;T_1,\;S,\;M,\;L\). Еквивалентно: \(T_0,\;T_1,\;S,\;M,\;L\) са точно максималните собствени затворени класове в \(P_2\).
Забележка. Това е дълбокият структурен резултат на Пост. В рамките на този урок го използваме като известен факт и доказваме подробно критерия на Пост — основният практически инструмент.
Теорема (Критерий на Пост). Нека \(F\) е множество от булеви функции. Тогава \(F\) е пълно тогава и само тогава, когато
\[F\nsubseteq T_0,\qquad F\nsubseteq T_1,\qquad F\nsubseteq S,\qquad F\nsubseteq M,\qquad F\nsubseteq L.\]
Тоест \(F\) е пълно точно тогава, когато не е изцяло съдържано в нито един от петте класа.
3. Доказателство на критерия на Пост
Необходимост (\(\Rightarrow\)).
Нека \(F\) е пълно, т.е. \([F]=P_2\). Допуснем, че \(F\subseteq T_0\). Понеже \(T_0\) е затворен, следва \([F]\subseteq T_0\). Но \(T_0\) е собствен клас, така \([F]\neq P_2\) — противоречие. Следователно \(F\nsubseteq T_0\). По абсолютно същия аргумент — за всеки от останалите четири класа — получаваме \[F\nsubseteq T_1,\qquad F\nsubseteq S,\qquad F\nsubseteq M,\qquad F\nsubseteq L.\] Необходимостта е доказана. \(\blacksquare\)
Достатъчност (\(\Leftarrow\)).
Нека \(F\nsubseteq T_0,\;F\nsubseteq T_1,\;F\nsubseteq S,\;F\nsubseteq M,\;F\nsubseteq L\). Допуснем, че \(F\) не е пълно, т.е. \([F]\neq P_2\). Тогава \([F]\) е собствен затворен клас. По фундаменталния факт на Пост: \[[F]\subseteq T_0\quad\text{или}\quad [F]\subseteq T_1\quad\text{или}\quad [F]\subseteq S\quad\text{или}\quad [F]\subseteq M\quad\text{или}\quad [F]\subseteq L.\] Понеже \(F\subseteq[F]\), би следвало \(F\subseteq T_0\) (или съответно в друг клас) — противоречие с условието. Следователно \([F]=P_2\), т.е. \(F\) е пълно. \(\blacksquare\)
Практически извод. Критерият на Пост превръща въпроса „дали \(F\) е пълно?" в пет прости проверки:
1) има ли във \(F\) функция, която не запазва нулата;
2) има ли функция, която не запазва единицата;
3) има ли функция, която не е самодвойствена;
4) има ли функция, която не е монотонна;
5) има ли функция, която не е линейна.
Ако на всеки въпрос отговорът е „да" — множеството е пълно.
1) има ли във \(F\) функция, която не запазва нулата;
2) има ли функция, която не запазва единицата;
3) има ли функция, която не е самодвойствена;
4) има ли функция, която не е монотонна;
5) има ли функция, която не е линейна.
Ако на всеки въпрос отговорът е „да" — множеството е пълно.
Важна забележка. Може да се докаже, че всяка линейна функция, която не запазва нулата и не запазва единицата, е самодвойствена. Следователно:
\[L\setminus(T_0\cup T_1)\subseteq S.\]
Аналогично, всяка монотонна функция, която не запазва нулата и не запазва единицата, е константа — а константите принадлежат на \(S\) само тривиално. По-точно:
\[M\setminus(T_0\cup T_1)\subseteq S.\]
Оттук следва: ако \(F\nsubseteq T_0\), \(F\nsubseteq T_1\) и \(F\nsubseteq S\), то автоматично \(F\nsubseteq L\) и \(F\nsubseteq M\). С други думи:
Множество \(F\) е пълно тогава и само тогава, когато \(F\nsubseteq T_0\cup T_1\cup S\) — т.е. когато \(F\) не е изцяло съдържано в обединението на трите класа \(T_0\), \(T_1\) и \(S\).
Непринадлежността към \(T_0\cup T_1\cup S\) автоматично гарантира непринадлежността към \(L\) и \(M\). Това означава, че на практика е достатъчно да проверим само трите класа \(T_0\), \(T_1\) и \(S\), ако имаме функции, гарантиращи „изходи" от тях.
Множество \(F\) е пълно тогава и само тогава, когато \(F\nsubseteq T_0\cup T_1\cup S\) — т.е. когато \(F\) не е изцяло съдържано в обединението на трите класа \(T_0\), \(T_1\) и \(S\).
Непринадлежността към \(T_0\cup T_1\cup S\) автоматично гарантира непринадлежността към \(L\) и \(M\). Това означава, че на практика е достатъчно да проверим само трите класа \(T_0\), \(T_1\) и \(S\), ако имаме функции, гарантиращи „изходи" от тях.
4. Алгоритъм за проверка на пълнота
Алгоритъм. За дадено множество \(F\) проверяваме последователно:
1) \(F\subseteq T_0\)? — ако да, \(F\) не е пълно. Ако не — продължаваме.
2) \(F\subseteq T_1\)? — ако да, \(F\) не е пълно.
3) \(F\subseteq S\)? — ако да, \(F\) не е пълно.
4) \(F\subseteq M\)? — ако да, \(F\) не е пълно.
5) \(F\subseteq L\)? — ако да, \(F\) не е пълно.
Ако нито едно от включванията не е изпълнено — по критерия на Пост \(F\) е пълно.
1) \(F\subseteq T_0\)? — ако да, \(F\) не е пълно. Ако не — продължаваме.
2) \(F\subseteq T_1\)? — ако да, \(F\) не е пълно.
3) \(F\subseteq S\)? — ако да, \(F\) не е пълно.
4) \(F\subseteq M\)? — ако да, \(F\) не е пълно.
5) \(F\subseteq L\)? — ако да, \(F\) не е пълно.
Ако нито едно от включванията не е изпълнено — по критерия на Пост \(F\) е пълно.
Разработени задачи
Кликнете върху задача, за да видите подробно решение.
1
Докажете, че множеството \(F=\{\cdot,\;\overline{\phantom{x}}\}\) е пълно.
▼
Решение
Проверяваме петте класа за всяка функция от \(F\).
\(T_0\): \(\overline{0}=1\neq0\), следователно \(\overline{x}\notin T_0\), и \(F\nsubseteq T_0\).
\(T_1\): \(\overline{1}=0\neq1\), следователно \(\overline{x}\notin T_1\), и \(F\nsubseteq T_1\).
\(S\): двойнствената на \(x_1\cdot x_2\) е \(x_1\lor x_2\neq x_1\cdot x_2\), следователно \(x_1\cdot x_2\notin S\), и \(F\nsubseteq S\).
\(M\): \(\overline{x}\) не е монотонна, следователно \(F\nsubseteq M\).
\(L\): \(x_1\cdot x_2\) не е линейна, следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\cdot,\overline{\phantom{x}}\}\text{ е пълно.}}\) \(\blacksquare\)
\(T_0\): \(\overline{0}=1\neq0\), следователно \(\overline{x}\notin T_0\), и \(F\nsubseteq T_0\).
\(T_1\): \(\overline{1}=0\neq1\), следователно \(\overline{x}\notin T_1\), и \(F\nsubseteq T_1\).
\(S\): двойнствената на \(x_1\cdot x_2\) е \(x_1\lor x_2\neq x_1\cdot x_2\), следователно \(x_1\cdot x_2\notin S\), и \(F\nsubseteq S\).
\(M\): \(\overline{x}\) не е монотонна, следователно \(F\nsubseteq M\).
\(L\): \(x_1\cdot x_2\) не е линейна, следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\cdot,\overline{\phantom{x}}\}\text{ е пълно.}}\) \(\blacksquare\)
2
Докажете, че множеството \(F=\{\lor,\;\overline{\phantom{x}}\}\) е пълно.
▼
Решение
\(T_0\): \(\overline{0}=1\), следователно \(F\nsubseteq T_0\).
\(T_1\): \(\overline{1}=0\), следователно \(F\nsubseteq T_1\).
\(S\): двойнствената на \(x_1\lor x_2\) е \(x_1\cdot x_2\), следователно \(x_1\lor x_2\notin S\), и \(F\nsubseteq S\).
\(M\): \(\overline{x}\notin M\), следователно \(F\nsubseteq M\).
\(L\): \(x_1\lor x_2\notin L\), следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\lor,\overline{\phantom{x}}\}\text{ е пълно.}}\) \(\blacksquare\)
\(T_1\): \(\overline{1}=0\), следователно \(F\nsubseteq T_1\).
\(S\): двойнствената на \(x_1\lor x_2\) е \(x_1\cdot x_2\), следователно \(x_1\lor x_2\notin S\), и \(F\nsubseteq S\).
\(M\): \(\overline{x}\notin M\), следователно \(F\nsubseteq M\).
\(L\): \(x_1\lor x_2\notin L\), следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\lor,\overline{\phantom{x}}\}\text{ е пълно.}}\) \(\blacksquare\)
3
Определете дали множеството \(F=\{+,\;\overline{\phantom{x}}\}\) е пълно.
▼
Решение
Тук \(+\) означава изключващо или.
Функцията \(x_1+x_2\) е линейна (полином на Жегалкин без членове от степен \(\geq2\)). Функцията \(\overline{x}=1+x\) също е линейна. Следователно: \[F\subseteq L.\] Понеже \(L\) е собствен затворен клас, \(F\) не може да бъде пълно.
\(\boxed{\{+,\overline{\phantom{x}}\}\text{ не е пълно.}}\) \(\blacksquare\)
Функцията \(x_1+x_2\) е линейна (полином на Жегалкин без членове от степен \(\geq2\)). Функцията \(\overline{x}=1+x\) също е линейна. Следователно: \[F\subseteq L.\] Понеже \(L\) е собствен затворен клас, \(F\) не може да бъде пълно.
\(\boxed{\{+,\overline{\phantom{x}}\}\text{ не е пълно.}}\) \(\blacksquare\)
4
Определете дали множеството \(F=\{\to,\;0\}\) е пълно.
▼
Решение
\(T_0\): \(0\to0=1\neq0\), следователно \(\to\notin T_0\), и \(F\nsubseteq T_0\).
\(T_1\): константата \(0\) не запазва единицата, следователно \(F\nsubseteq T_1\).
\(S\): импликацията не е самодвойствена, следователно \(F\nsubseteq S\).
\(M\): импликацията не е монотонна: \((0,0)\leq(1,0)\), но \(0\to0=1\gt0=1\to0\), следователно \(F\nsubseteq M\).
\(L\): импликацията не е линейна, следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\to,0\}\text{ е пълно.}}\) \(\blacksquare\)
\(T_1\): константата \(0\) не запазва единицата, следователно \(F\nsubseteq T_1\).
\(S\): импликацията не е самодвойствена, следователно \(F\nsubseteq S\).
\(M\): импликацията не е монотонна: \((0,0)\leq(1,0)\), но \(0\to0=1\gt0=1\to0\), следователно \(F\nsubseteq M\).
\(L\): импликацията не е линейна, следователно \(F\nsubseteq L\).
По критерия на Пост: \(\boxed{\{\to,0\}\text{ е пълно.}}\) \(\blacksquare\)
5
За кой избор на константа \(c\in\{0,1\}\) множеството \(F_c=\{\lor,+,c\}\) е пълно?
▼
Решение
Случай \(c=0\): дизюнкцията \(\lor\), XOR и константата \(0\) — всички запазват нулата, т.е. \(F_0\subseteq T_0\). Следователно \(F_0\) не е пълно.
Случай \(c=1\):
\(T_0\): \(1\notin T_0\) (\(f(0)=1\)), следователно \(F_1\nsubseteq T_0\).
\(T_1\): \(0+1=1\), \(1+1=0\neq1\), следователно \(x_1+x_2\notin T_1\), и \(F_1\nsubseteq T_1\).
\(S\): \(x_1\lor x_2\notin S\), следователно \(F_1\nsubseteq S\).
\(M\): \(x_1+x_2\notin M\), следователно \(F_1\nsubseteq M\).
\(L\): \(x_1\lor x_2\notin L\), следователно \(F_1\nsubseteq L\).
\(\boxed{F_c\text{ е пълно точно при }c=1.}\) \(\blacksquare\)
Случай \(c=1\):
\(T_0\): \(1\notin T_0\) (\(f(0)=1\)), следователно \(F_1\nsubseteq T_0\).
\(T_1\): \(0+1=1\), \(1+1=0\neq1\), следователно \(x_1+x_2\notin T_1\), и \(F_1\nsubseteq T_1\).
\(S\): \(x_1\lor x_2\notin S\), следователно \(F_1\nsubseteq S\).
\(M\): \(x_1+x_2\notin M\), следователно \(F_1\nsubseteq M\).
\(L\): \(x_1\lor x_2\notin L\), следователно \(F_1\nsubseteq L\).
\(\boxed{F_c\text{ е пълно точно при }c=1.}\) \(\blacksquare\)
6
Докажете, че едноелементното множество \(F=\{\downarrow\}\) е пълно.
▼
Решение
Стрелката на Пиърс: \(x_1\downarrow x_2=\overline{x_1\lor x_2}\).
\(T_0\): \(0\downarrow0=\overline{0\lor0}=1\neq0\), следователно \(\downarrow\notin T_0\).
\(T_1\): \(1\downarrow1=\overline{1\lor1}=0\neq1\), следователно \(\downarrow\notin T_1\).
\(S\): \(\downarrow\) не е самодвойствена, следователно \(\downarrow\notin S\).
\(M\): \((0,0)\leq(1,0)\), но \(0\downarrow0=1\gt0=1\downarrow0\), следователно \(\downarrow\notin M\).
\(L\): \(\downarrow\) не е линейна (полиномът й съдържа \(x_1x_2\)), следователно \(\downarrow\notin L\).
По критерия на Пост: \(\boxed{\{\downarrow\}\text{ е пълно.}}\) \(\blacksquare\)
\(T_0\): \(0\downarrow0=\overline{0\lor0}=1\neq0\), следователно \(\downarrow\notin T_0\).
\(T_1\): \(1\downarrow1=\overline{1\lor1}=0\neq1\), следователно \(\downarrow\notin T_1\).
\(S\): \(\downarrow\) не е самодвойствена, следователно \(\downarrow\notin S\).
\(M\): \((0,0)\leq(1,0)\), но \(0\downarrow0=1\gt0=1\downarrow0\), следователно \(\downarrow\notin M\).
\(L\): \(\downarrow\) не е линейна (полиномът й съдържа \(x_1x_2\)), следователно \(\downarrow\notin L\).
По критерия на Пост: \(\boxed{\{\downarrow\}\text{ е пълно.}}\) \(\blacksquare\)
5. Бази на пълно множество
Определение 4. Подмножество \(B\subseteq F\) се нарича база на пълното множество \(F\), ако \(B\) е пълно и нито едно негово истинско подмножество не е пълно.
Как се намират базите на пълно множество \(F\).
1) Проверяваме всички едноелементни подмножества — ако \(\{f\}\) е пълно, то то е база.
2) Проверяваме двуелементните подмножества, чиито едноелементни части не са пълни.
3) Продължаваме нагоре, докато намерим всички минимални пълни подмножества.
Подмножество \(B\) е база тогава и само тогава, когато е пълно и не съдържа пълно собствено подмножество.
1) Проверяваме всички едноелементни подмножества — ако \(\{f\}\) е пълно, то то е база.
2) Проверяваме двуелементните подмножества, чиито едноелементни части не са пълни.
3) Продължаваме нагоре, докато намерим всички минимални пълни подмножества.
Подмножество \(B\) е база тогава и само тогава, когато е пълно и не съдържа пълно собствено подмножество.
Теорема. Всяко пълно множество \(F\) съдържа пълно подмножество от не повече от четири функции. Тоест всяка база на \(F\) има мощност най-много 4.
Идея на доказателството. Тъй като \(F\) е пълно, в него има \(f_0\notin T_0\), \(f_1\notin T_1\), \(f_s\notin S\), \(f_m\notin M\), \(f_l\notin L\). Подмножеството \(F'=\{f_0,f_1,f_s,f_m,f_l\}\) е пълно и се състои от не повече от 5 функции (някои могат да съвпадат). Освен това може да се покаже, че 4 са достатъчни — от двата случая на \(f_0(1,\dots,1)\) следва, че или \(f_0\notin M\), или \(f_0\notin S\), и така броят се намалява с 1.
6. Решен пример с таблична форма
Следващата задача демонстрира стандартния метод за проверка на пълнота и намиране на бази с помощта на таблица. За всяка функция от \(F\) попълваме „+" ако принадлежи на класа, и „−" ако не принадлежи.
7
Нека
\[F=\{f_1,f_2,f_3,f_4\}=\{(x\lor y)(\overline{x}\lor\overline{y}),\;xy+z,\;(x+y)\equiv z,\;xy\lor xz\lor yz\}.\]
Определете дали \(F\) е пълно и намерете всички бази.
▼
Решение
Попълваме таблицата за петте класа. За всяка функция намираме стойността в \((0,\dots,0)\) и в \((1,\dots,1)\), двойнствената функция, полинома на Жегалкин и проверяваме монотонност.
\(f_1(x,y)=(x\lor y)(\overline{x}\lor\overline{y})\): таблицата на истинност дава стойностите \((0,1,1,0)\).
\(f_1(0,0)=0\Rightarrow f_1\in T_0\); \(f_1(1,1)=0\Rightarrow f_1\notin T_1\).
Двойнствената \(f_1^*(x,y)\) има стойности \((1,0,0,1)\neq(0,1,1,0)\Rightarrow f_1\notin S\).
От \((0,1)\prec(1,1)\) и \(f_1(0,1)=1\gt0=f_1(1,1)\Rightarrow f_1\notin M\).
Полином на Жегалкин: \(f_1=x+y\Rightarrow f_1\in L\).
\(f_2(x,y,z)=xy+z\):
\(f_2(0,0,0)=0\Rightarrow f_2\in T_0\); \(f_2(1,1,1)=(1+1)\%2=0\Rightarrow f_2\notin T_1\).
\(f_2^*(x,y,z)=\overline{f_2(\overline{x},\overline{y},\overline{z})}=\overline{(1-x)(1-y)+(1-z)}=1+xy+z\neq xy+z\Rightarrow f_2\notin S\).
От \((0,0,1)\prec(1,1,1)\) и \(f_2(0,0,1)=1\gt0=f_2(1,1,1)\Rightarrow f_2\notin M\).
Полиномът \(xy+z\) съдържа \(xy\Rightarrow f_2\notin L\).
\(f_3(x,y,z)=(x+y)\equiv z=1+x+y+z\):
\(f_3(0,0,0)=1\Rightarrow f_3\notin T_0\); \(f_3(1,1,1)=0\Rightarrow f_3\notin T_1\).
\(f_3^*(x,y,z)=\overline{f_3(\overline{x},\overline{y},\overline{z})}=\overline{1+(1-x)+(1-y)+(1-z)}=\overline{1+x+y+z}=f_3\Rightarrow f_3\in S\).
\(f_3\notin M\) (от \((0,0,0)\prec(1,0,0)\): \(f_3(0,0,0)=1\gt0=f_3(1,0,0)\)).
Полиномът \(1+x+y+z\) е линеен \(\Rightarrow f_3\in L\).
\(f_4(x,y,z)=xy\lor xz\lor yz\):
\(f_4(0,0,0)=0\Rightarrow f_4\in T_0\); \(f_4(1,1,1)=1\Rightarrow f_4\in T_1\).
Полином на Жегалкин: \(f_4=xy+xz+yz\). Двойнствената \(f_4^*=xy+xz+yz=f_4\Rightarrow f_4\in S\).
Задава се с дизюнкция без отрицание \(\Rightarrow f_4\in M\). Полиномът е нелинеен \(\Rightarrow f_4\notin L\).
Обобщена таблица:
Всяка колона съдържа поне едно „−" (\(f_3\notin T_0\), \(f_1,f_2,f_3\notin T_1\), \(f_1,f_2\notin S\), \(f_1,f_2,f_3\notin M\), \(f_2,f_4\notin L\)). Следователно \(F\nsubseteq T_0,\;F\nsubseteq T_1,\;F\nsubseteq S,\;F\nsubseteq M,\;F\nsubseteq L\) и по критерия на Пост \(F\) е пълно.
Намираме базите:
Едноелементни: \(\{f_1\}\subset T_0\), \(\{f_2\}\subset T_0\), \(\{f_3\}\subset S\), \(\{f_4\}\subset T_0\) — нито едно не е пълно.
Двуелементни (\(C_4^2=6\)): \(\{f_1,f_2\}\subset T_0\), \(\{f_1,f_3\}\subset L\), \(\{f_1,f_4\}\subset T_0\), \(\{f_2,f_4\}\subset T_0\), \(\{f_3,f_4\}\subset S\) — не са пълни. Единствено \(\{f_2,f_3\}\) не се съдържа в нито един от петте класа (в \(T_0\): \(f_3\notin T_0\); в \(T_1\): \(f_2,f_3\notin T_1\); в \(S\): \(f_2\notin S\); в \(M\): \(f_2,f_3\notin M\); в \(L\): \(f_2\notin L\)) — следователно \(\{f_2,f_3\}\) е пълно. Понеже не съдържа пълни едноелементни подмножества, то е база.
Триелементни: \(\{f_1,f_2,f_3\}\) и \(\{f_2,f_3,f_4\}\) са пълни, но съдържат базата \(\{f_2,f_3\}\) — не са бази. \(\{f_1,f_2,f_4\}\subset T_0\) — не е пълно. Единствено \(\{f_1,f_3,f_4\}\) не се съдържа в нито един клас и не съдържа пълно собствено подмножество — то е база.
\(F\) съдържа точно две бази: \(\boxed{\{f_2,f_3\}\text{ и }\{f_1,f_3,f_4\}.}\) \(\blacksquare\)
\(f_1(x,y)=(x\lor y)(\overline{x}\lor\overline{y})\): таблицата на истинност дава стойностите \((0,1,1,0)\).
\(f_1(0,0)=0\Rightarrow f_1\in T_0\); \(f_1(1,1)=0\Rightarrow f_1\notin T_1\).
Двойнствената \(f_1^*(x,y)\) има стойности \((1,0,0,1)\neq(0,1,1,0)\Rightarrow f_1\notin S\).
От \((0,1)\prec(1,1)\) и \(f_1(0,1)=1\gt0=f_1(1,1)\Rightarrow f_1\notin M\).
Полином на Жегалкин: \(f_1=x+y\Rightarrow f_1\in L\).
\(f_2(x,y,z)=xy+z\):
\(f_2(0,0,0)=0\Rightarrow f_2\in T_0\); \(f_2(1,1,1)=(1+1)\%2=0\Rightarrow f_2\notin T_1\).
\(f_2^*(x,y,z)=\overline{f_2(\overline{x},\overline{y},\overline{z})}=\overline{(1-x)(1-y)+(1-z)}=1+xy+z\neq xy+z\Rightarrow f_2\notin S\).
От \((0,0,1)\prec(1,1,1)\) и \(f_2(0,0,1)=1\gt0=f_2(1,1,1)\Rightarrow f_2\notin M\).
Полиномът \(xy+z\) съдържа \(xy\Rightarrow f_2\notin L\).
\(f_3(x,y,z)=(x+y)\equiv z=1+x+y+z\):
\(f_3(0,0,0)=1\Rightarrow f_3\notin T_0\); \(f_3(1,1,1)=0\Rightarrow f_3\notin T_1\).
\(f_3^*(x,y,z)=\overline{f_3(\overline{x},\overline{y},\overline{z})}=\overline{1+(1-x)+(1-y)+(1-z)}=\overline{1+x+y+z}=f_3\Rightarrow f_3\in S\).
\(f_3\notin M\) (от \((0,0,0)\prec(1,0,0)\): \(f_3(0,0,0)=1\gt0=f_3(1,0,0)\)).
Полиномът \(1+x+y+z\) е линеен \(\Rightarrow f_3\in L\).
\(f_4(x,y,z)=xy\lor xz\lor yz\):
\(f_4(0,0,0)=0\Rightarrow f_4\in T_0\); \(f_4(1,1,1)=1\Rightarrow f_4\in T_1\).
Полином на Жегалкин: \(f_4=xy+xz+yz\). Двойнствената \(f_4^*=xy+xz+yz=f_4\Rightarrow f_4\in S\).
Задава се с дизюнкция без отрицание \(\Rightarrow f_4\in M\). Полиномът е нелинеен \(\Rightarrow f_4\notin L\).
Обобщена таблица:
| \(T_0\) | \(T_1\) | \(S\) | \(M\) | \(L\) | |
|---|---|---|---|---|---|
| \(f_1\) | + | − | − | − | + |
| \(f_2\) | + | − | − | − | − |
| \(f_3\) | − | − | + | − | + |
| \(f_4\) | + | + | + | + | − |
Всяка колона съдържа поне едно „−" (\(f_3\notin T_0\), \(f_1,f_2,f_3\notin T_1\), \(f_1,f_2\notin S\), \(f_1,f_2,f_3\notin M\), \(f_2,f_4\notin L\)). Следователно \(F\nsubseteq T_0,\;F\nsubseteq T_1,\;F\nsubseteq S,\;F\nsubseteq M,\;F\nsubseteq L\) и по критерия на Пост \(F\) е пълно.
Намираме базите:
Едноелементни: \(\{f_1\}\subset T_0\), \(\{f_2\}\subset T_0\), \(\{f_3\}\subset S\), \(\{f_4\}\subset T_0\) — нито едно не е пълно.
Двуелементни (\(C_4^2=6\)): \(\{f_1,f_2\}\subset T_0\), \(\{f_1,f_3\}\subset L\), \(\{f_1,f_4\}\subset T_0\), \(\{f_2,f_4\}\subset T_0\), \(\{f_3,f_4\}\subset S\) — не са пълни. Единствено \(\{f_2,f_3\}\) не се съдържа в нито един от петте класа (в \(T_0\): \(f_3\notin T_0\); в \(T_1\): \(f_2,f_3\notin T_1\); в \(S\): \(f_2\notin S\); в \(M\): \(f_2,f_3\notin M\); в \(L\): \(f_2\notin L\)) — следователно \(\{f_2,f_3\}\) е пълно. Понеже не съдържа пълни едноелементни подмножества, то е база.
Триелементни: \(\{f_1,f_2,f_3\}\) и \(\{f_2,f_3,f_4\}\) са пълни, но съдържат базата \(\{f_2,f_3\}\) — не са бази. \(\{f_1,f_2,f_4\}\subset T_0\) — не е пълно. Единствено \(\{f_1,f_3,f_4\}\) не се съдържа в нито един клас и не съдържа пълно собствено подмножество — то е база.
\(F\) съдържа точно две бази: \(\boxed{\{f_2,f_3\}\text{ и }\{f_1,f_3,f_4\}.}\) \(\blacksquare\)
Задачи за самостоятелна работа
Опитайте сами да приложите критерия на Пост.
Задача 1Покажете, че множеството \(\{\cdot,\lor\}\) не е пълно.
Задача 2Покажете, че множеството \(\{\mid\}\) е пълно.
Задача 3Определете дали \(\{x_1\equiv x_2,\;\overline{\phantom{x}}\}\) е пълно.
Задача 4Определете дали \(\{\to,1\}\) е пълно.
Задача 5За кое \(c\in\{0,1\}\) множеството \(\{+,\cdot,c\}\) е пълно?
Задача 6Определете дали \(\{\overline{\phantom{x}},+\}\) е пълно, като обосновете отговора чрез критерия на Пост.
Задача 7Намерете по една функция от \(\{\to,0\}\), показваща, че множеството не е съдържано в \(T_0,\;T_1,\;S,\;M,\;L\).
Задача 8Докажете, че ако \(F\subseteq M\), то \(F\) не е пълно.
Задача 9Намерете всички бази на множеството \(F=\{0,\;1,\;x_1x_2,\;x_1+x_2+x_3\}\).
Онлайн тест
15 въпроса • 4 точки за верен отговор • максимум 60 точки
Тест: Критерий на Пост
Изберете верния отговор за всеки въпрос и натиснете КРАЙ.
Видео уроци
Свързани уроци
◀
Затворени класове \(T_0,T_1,S,M,L\)
Определения, мощности, таблица за основните функции и 5 разработени задачи.
Преглед на урока →
◀
Булеви функции — свойства, пълнота и теорема на Бул
ДДНФ, пълни множества, теорема на Бул — 4 разработени задачи и тест.
Преглед на урока →
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
🎓 Подготовка за изпити
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
📚 Текущо обучение и студенти
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Коментари
Публикуване на коментар