Булеви функции - основни понятия и дефиниции - част II
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Математика › Дискретна математика › Булеви функции
Булеви функции
Свойства, пълнота и теорема на Бул
Комутативност, асоциативност, дистрибутивност, ДДНФ, пълни множества — теорема на Бул, 4 разработени задачи, самостоятелна работа и тест
1. Закони за двоичните функции
Ще разгледаме комутативността, асоциативността и дистрибутивността при основните двоични функции.
Комутативност:
1) \(x_1 \cdot x_2 = x_2 \cdot x_1\) — конюнкцията е комутативна.
2) \(x_1 \lor x_2 = x_2 \lor x_1\) — дизюнкцията е комутативна.
3) \(x_1 + x_2 = x_2 + x_1\) — изключващото или е комутативно.
Асоциативност:
4) \(x_1 \cdot (x_2 \cdot x_3) = (x_1 \cdot x_2) \cdot x_3\) — конюнкцията е асоциативна.
5) \(x_1 \lor (x_2 \lor x_3) = (x_1 \lor x_2) \lor x_3\) — дизюнкцията е асоциативна.
6) \(x_1 + (x_2 + x_3) = (x_1 + x_2) + x_3\) — изключващото или е асоциативно.
Дистрибутивност:
7) \(x_1 \cdot (x_2 \lor x_3) = x_1 \cdot x_2 \lor x_1 \cdot x_3\)
8) \(x_1 \cdot (x_2 + x_3) = x_1 \cdot x_2 + x_1 \cdot x_3\)
1) \(x_1 \cdot x_2 = x_2 \cdot x_1\) — конюнкцията е комутативна.
2) \(x_1 \lor x_2 = x_2 \lor x_1\) — дизюнкцията е комутативна.
3) \(x_1 + x_2 = x_2 + x_1\) — изключващото или е комутативно.
Асоциативност:
4) \(x_1 \cdot (x_2 \cdot x_3) = (x_1 \cdot x_2) \cdot x_3\) — конюнкцията е асоциативна.
5) \(x_1 \lor (x_2 \lor x_3) = (x_1 \lor x_2) \lor x_3\) — дизюнкцията е асоциативна.
6) \(x_1 + (x_2 + x_3) = (x_1 + x_2) + x_3\) — изключващото или е асоциативно.
Дистрибутивност:
7) \(x_1 \cdot (x_2 \lor x_3) = x_1 \cdot x_2 \lor x_1 \cdot x_3\)
8) \(x_1 \cdot (x_2 + x_3) = x_1 \cdot x_2 + x_1 \cdot x_3\)
2. Приоритет на операциите
Ред на изчисляване (от най-висок към най-нисък приоритет):
1) Скоби
2) Отрицание (\(\overline{x}\))
3) Конюнкция (\(\cdot\))
4) Дизюнкция (\(\lor\)) и изключващо или (\(+\)) — ляво надясно
5) Всички останали функции
1) Скоби
2) Отрицание (\(\overline{x}\))
3) Конюнкция (\(\cdot\))
4) Дизюнкция (\(\lor\)) и изключващо или (\(+\)) — ляво надясно
5) Всички останали функции
3. Свойства на отделни булеви функции
Свойства на константите:
\(x+1=\overline{x}\); \(x+0=x\); \(x \cdot 1=x\); \(x \cdot 0=0\).
Свойства на отрицанието: \(x \cdot \overline{x}=0\); \(x \lor \overline{x}=1\); \(\overline{\overline{x}}=x\).
Свойства на еквивалентността: \(x_1 \equiv x_2 = \overline{x_1+x_2} = (x_1 \to x_2)(x_2 \to x_1) = (\overline{x_1}+x_2)(\overline{x_2}+x_1)\).
Свойства на импликацията: \(x_1 \to x_2 = \overline{x_1} \lor x_2\); \(x_1 \to x_2 = \overline{x_2} \to \overline{x_1}\).
Свойства на изключващото или: \(x_1 + x_2 = \overline{x_1 \equiv x_2} = x_1\overline{x_2}+\overline{x_1}x_2 = (x_1 \lor x_2)(\overline{x_2} \lor \overline{x_1})\).
Черта на Шефер: \(x_1 \mid x_2 = \overline{x_1 \cdot x_2} = \overline{x_1} \lor \overline{x_2}\).
Стрелка на Пиърс: \(x_1 \downarrow x_2 = \overline{x_1 \lor x_2} = \overline{x_1} \cdot \overline{x_2}\).
Свойства на отрицанието: \(x \cdot \overline{x}=0\); \(x \lor \overline{x}=1\); \(\overline{\overline{x}}=x\).
Свойства на еквивалентността: \(x_1 \equiv x_2 = \overline{x_1+x_2} = (x_1 \to x_2)(x_2 \to x_1) = (\overline{x_1}+x_2)(\overline{x_2}+x_1)\).
Свойства на импликацията: \(x_1 \to x_2 = \overline{x_1} \lor x_2\); \(x_1 \to x_2 = \overline{x_2} \to \overline{x_1}\).
Свойства на изключващото или: \(x_1 + x_2 = \overline{x_1 \equiv x_2} = x_1\overline{x_2}+\overline{x_1}x_2 = (x_1 \lor x_2)(\overline{x_2} \lor \overline{x_1})\).
Черта на Шефер: \(x_1 \mid x_2 = \overline{x_1 \cdot x_2} = \overline{x_1} \lor \overline{x_2}\).
Стрелка на Пиърс: \(x_1 \downarrow x_2 = \overline{x_1 \lor x_2} = \overline{x_1} \cdot \overline{x_2}\).
4. Формули над множество булеви функции
Определение 2: Формула над \(F\) е: 1) всяка функция от \(F\); 2) всеки израз от вида \(f_i(\phi_1,\ldots,\phi_{n_i})\), където \(f_i \in F\), а \(\phi_j\) е формула над \(F\) или буква на променлива.
Определение 3: На всяка формула се съпоставя единствена функция — казваме, че формулата реализира тази функция.
Определение 4: Ако функция се реализира с формула над \(F\), тя е суперпозиция над \(F\). Множеството от всички суперпозиции над \(F\) се означава \([F]\).
Определение 5: Множество \(F\) е пълно, ако \([F] \equiv P_2\), т.е. ако обвивката му съвпада с множеството от всички двоични функции.
Пример: \(f = x_1 \lor x_2 \cdot \overline{x_3}\) е формула над \(F = \{\lor,\,\cdot\,,\overline{\phantom{x}}\}\). Таблицата за истинност на \(f\):
5. Теорема на Бул и пълни множества
Теорема 1 (Теорема на Бул): Множеството \(\{\cdot,\,\lor,\,\overline{\phantom{x}}\}\) (конюнкция, дизюнкция, отрицание) е пълно.
Доказателство (скица): За произволна ненулева функция \(f(x_1,\ldots,x_n)\) конструираме ДДНФ: \[f(x_1,\ldots,x_n) = \bigvee_{f(a_1,\ldots,a_n)=1} x_1^{a_1} x_2^{a_2}\cdots x_n^{a_n},\] където \(x^a = \overline{x}\) при \(a=0\) и \(x^a = x\) при \(a=1\). Тази формула изразява всяка двоична функция само чрез \(\{\cdot,\lor,\overline{\phantom{x}}\}\). \(\blacksquare\)
Доказателство (скица): За произволна ненулева функция \(f(x_1,\ldots,x_n)\) конструираме ДДНФ: \[f(x_1,\ldots,x_n) = \bigvee_{f(a_1,\ldots,a_n)=1} x_1^{a_1} x_2^{a_2}\cdots x_n^{a_n},\] където \(x^a = \overline{x}\) при \(a=0\) и \(x^a = x\) при \(a=1\). Тази формула изразява всяка двоична функция само чрез \(\{\cdot,\lor,\overline{\phantom{x}}\}\). \(\blacksquare\)
Теорема 2: \(G\) е пълно множество тогава и само тогава, когато всяка функция от дадено пълно \(F\) е суперпозиция над \(G\).
6. Как се реализира булева функция по таблица за истинност
Теоремата на Бул не е само теоретичен резултат. Тя дава и конкретен начин да построим формула за всяка булева функция, когато функцията е зададена чрез таблица за истинност.
Идеята е следната: гледаме редовете, в които функцията приема стойност \(1\). За всеки такъв ред записваме конюнкция от променливите, като се съобразяваме със стойностите им в съответния ред:
Правило за построяване на един член:
ако в даден ред някоя променлива има стойност 1, записваме самата променлива;
ако има стойност 0, записваме нейното отрицание.
След това свързваме всички получени букви с конюнкция.
ако в даден ред някоя променлива има стойност 1, записваме самата променлива;
ако има стойност 0, записваме нейното отрицание.
След това свързваме всички получени букви с конюнкция.
Получената конюнкция има стойност \(1\) точно за този ред и \(0\) за всички останали редове. Накрая свързваме всички такива конюнкции с дизюнкция. Така получаваме формула в ДДНФ (дизюнктивна нормална форма), която реализира дадената функция.
Важно. Ако в ред от таблицата имаме например
\[x_1=1,\qquad x_2=0,\qquad x_3=1,\]
то на този ред съответства членът
\[x_1\overline{x_2}x_3.\]
Тоест нулевата стойност на променливата води до нейното отрицание в конюнкцията.
Разработени задачи
Кликнете върху задача за пълното решение.
1
Пресметнете: \(1\downarrow(\overline{0}\lor 1+\overline{0}(1+\overline{0}))\).
▼
Решение
Прилагаме приоритетите — първо скоби, вътре в тях: отрицание (\(\overline{0}=1\)), после конюнкция, после дизюнкция/събиране:
\[1\downarrow(1\lor 1+1\cdot(1+1))=1\downarrow(1\lor 1+1\cdot 0)=1\downarrow(1\lor 1+0)=1\downarrow(1+0)=1\downarrow 1=0.\]
2
Докажете, че следните множества са пълни:
а) \(A=\{\cdot,\,\overline{\phantom{x}}\}\); б) \(B=\{\overline{\phantom{x}},\lor\}\); в) \(C=\{\downarrow\}\); г) \(D=\{\mid\}\).
а) \(A=\{\cdot,\,\overline{\phantom{x}}\}\); б) \(B=\{\overline{\phantom{x}},\lor\}\); в) \(C=\{\downarrow\}\); г) \(D=\{\mid\}\).
▼
Решение
а) От закона на Де Морган: \(x_1\lor x_2=\overline{\overline{x_1}\cdot\overline{x_2}}\). Реализираме дизюнкцията чрез \(A\), следователно \([A]\) съдържа \(\{\cdot,\lor,\overline{\phantom{x}}\}\) — пълното множество. По Теорема 2 \(A\) е пълно. \(\blacksquare\)
б) От закона на Де Морган: \(x_1\cdot x_2=\overline{\overline{x_1}\lor\overline{x_2}}\). Реализираме конюнкцията чрез \(B\), следователно \([B]\) съдържа \(\{\cdot,\lor,\overline{\phantom{x}}\}\). По Теорема 2 \(B\) е пълно. \(\blacksquare\)
в) \(\overline{x_1}=x_1\downarrow x_1\). Освен това \(x_1\lor x_2=\overline{x_1\downarrow x_2}=(x_1\downarrow x_2)\downarrow(x_1\downarrow x_2)\). Реализирахме отрицание и дизюнкция само чрез \(\downarrow\). По Теореми 1 и 2 \(C\) е пълно. \(\blacksquare\)
г) \(\overline{x_1}=x_1\mid x_1\). Освен това \(x_1\cdot x_2=\overline{x_1\mid x_2}=(x_1\mid x_2)\mid(x_1\mid x_2)\). Реализирахме отрицание и конюнкция само чрез \(\mid\). По Теореми 1 и 2 \(D\) е пълно. \(\blacksquare\)
б) От закона на Де Морган: \(x_1\cdot x_2=\overline{\overline{x_1}\lor\overline{x_2}}\). Реализираме конюнкцията чрез \(B\), следователно \([B]\) съдържа \(\{\cdot,\lor,\overline{\phantom{x}}\}\). По Теорема 2 \(B\) е пълно. \(\blacksquare\)
в) \(\overline{x_1}=x_1\downarrow x_1\). Освен това \(x_1\lor x_2=\overline{x_1\downarrow x_2}=(x_1\downarrow x_2)\downarrow(x_1\downarrow x_2)\). Реализирахме отрицание и дизюнкция само чрез \(\downarrow\). По Теореми 1 и 2 \(C\) е пълно. \(\blacksquare\)
г) \(\overline{x_1}=x_1\mid x_1\). Освен това \(x_1\cdot x_2=\overline{x_1\mid x_2}=(x_1\mid x_2)\mid(x_1\mid x_2)\). Реализирахме отрицание и конюнкция само чрез \(\mid\). По Теореми 1 и 2 \(D\) е пълно. \(\blacksquare\)
3
По дадената таблица за истинност постройте формула, която реализира функцията \(f(x_1,x_2,x_3)\).
▼
Решение
Нека функцията \(f(x_1,x_2,x_3)\) е зададена чрез следната таблица за истинност:
Гледаме само редовете, в които \(f=1\). Това са: \((0,0,1)\), \((0,1,0)\), \((1,0,0)\), \((1,1,1)\).
За всеки такъв ред записваме съответната конюнкция:
за \((0,0,1)\): \(\overline{x_1}\,\overline{x_2}\,x_3\); за \((0,1,0)\): \(\overline{x_1}\,x_2\,\overline{x_3}\); за \((1,0,0)\): \(x_1\,\overline{x_2}\,\overline{x_3}\); за \((1,1,1)\): \(x_1 x_2 x_3\).
Свързваме с дизюнкция: \[f(x_1,x_2,x_3)=\overline{x_1}\overline{x_2}x_3\lor\overline{x_1}x_2\overline{x_3}\lor x_1\overline{x_2}\overline{x_3}\lor x_1x_2x_3.\] Това е ДДНФ, която реализира функцията \(f\). \(\blacksquare\)
| \(x_1\) | \(x_2\) | \(x_3\) | \(f\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
За всеки такъв ред записваме съответната конюнкция:
за \((0,0,1)\): \(\overline{x_1}\,\overline{x_2}\,x_3\); за \((0,1,0)\): \(\overline{x_1}\,x_2\,\overline{x_3}\); за \((1,0,0)\): \(x_1\,\overline{x_2}\,\overline{x_3}\); за \((1,1,1)\): \(x_1 x_2 x_3\).
Свързваме с дизюнкция: \[f(x_1,x_2,x_3)=\overline{x_1}\overline{x_2}x_3\lor\overline{x_1}x_2\overline{x_3}\lor x_1\overline{x_2}\overline{x_3}\lor x_1x_2x_3.\] Това е ДДНФ, която реализира функцията \(f\). \(\blacksquare\)
Полезна идея. Ако в таблицата за истинност функцията има много единици (например повече от четири при три променливи), често е по-удобно да работим не с \(f\), а с нейното отрицание \(\overline{f}\).
Причината е, че тогава \(\overline{f}\) има малко единици — точно там, където \(f\) има нули. Построяваме по идеята на Бул формула за \(\overline{f}\), а след това вземаме отрицание на полученото равенство: \[ \overline{f}=\Phi \quad\Longrightarrow\quad \overline{\overline{f}}=\overline{\Phi} \quad\Longrightarrow\quad f=\overline{\Phi}. \] Тъй като двойното отрицание връща същата функция, така често получаваме по-кратък запис.
Причината е, че тогава \(\overline{f}\) има малко единици — точно там, където \(f\) има нули. Построяваме по идеята на Бул формула за \(\overline{f}\), а след това вземаме отрицание на полученото равенство: \[ \overline{f}=\Phi \quad\Longrightarrow\quad \overline{\overline{f}}=\overline{\Phi} \quad\Longrightarrow\quad f=\overline{\Phi}. \] Тъй като двойното отрицание връща същата функция, така често получаваме по-кратък запис.
4
По дадената таблица за истинност постройте формула за функцията \(f(x_1,x_2,x_3)\), като използвате по-кратък подход чрез отрицанието на функцията.
▼
Решение
Нека функцията \(f(x_1,x_2,x_3)\) е зададена чрез таблицата:
Тук функцията има \(7\) единици и само една нула. Затова е по-удобно да разгледаме отрицанието \(\overline{f}\).
Понеже \(f=0\) само за реда \((0,1,1)\), то \(\overline{f}=1\) само за този ред. Следователно по идеята на Бул: \[\overline{f}(x_1,x_2,x_3)=\overline{x_1}x_2x_3.\] Вземаме отрицание от двете страни: \[f(x_1,x_2,x_3)=\overline{\overline{x_1}x_2x_3}.\] Прилагаме закона на Де Морган и получаваме: \[f(x_1,x_2,x_3)=x_1\lor\overline{x_2}\lor\overline{x_3}.\quad\blacksquare\]
| \(x_1\) | \(x_2\) | \(x_3\) | \(f\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Понеже \(f=0\) само за реда \((0,1,1)\), то \(\overline{f}=1\) само за този ред. Следователно по идеята на Бул: \[\overline{f}(x_1,x_2,x_3)=\overline{x_1}x_2x_3.\] Вземаме отрицание от двете страни: \[f(x_1,x_2,x_3)=\overline{\overline{x_1}x_2x_3}.\] Прилагаме закона на Де Морган и получаваме: \[f(x_1,x_2,x_3)=x_1\lor\overline{x_2}\lor\overline{x_3}.\quad\blacksquare\]
Задачи за самостоятелна работа
Използвайте идеята на Бул и постройте формула по зададената таблица за истинност.
Задача 1
Постройте формула за функцията \(f(x_1,x_2,x_3)\), която приема стойност \(1\) точно за редовете
\[(0,0,1),\qquad (0,1,0),\qquad (1,0,1).\]
Задача 2
Постройте формула за функцията \(f(x_1,x_2,x_3)\), която приема стойност \(1\) точно за редовете
\[(0,1,1),\qquad (1,0,0),\qquad (1,1,0),\qquad (1,1,1).\]
Задача 3
Постройте формула за функцията \(f(x_1,x_2,x_3)\), която има стойност \(0\) само за редовете
\[(0,0,0)\qquad\text{и}\qquad(1,1,1).\]
Упътване: по-удобно е първо да построите \(\overline{f}\).
Задача 4
Постройте формула за функцията \(f(x_1,x_2,x_3)\), която приема стойност \(1\) точно тогава, когато точно една от трите променливи е равна на \(1\).
Задача 5
Постройте формула за функцията \(f(x_1,x_2,x_3)\), която приема стойност \(1\) във всички редове, освен в \((0,1,0)\). Решете задачата по краткия начин чрез отрицанието на функцията.
Задача 6
Пресметнете стойността на израза:
\[\overline{(1\lor\overline{0})\cdot(0+\overline{(1\cdot 1\lor 0)})}.\]
Задача 7
Пресметнете стойността на израза:
\[(\overline{1\downarrow(0\lor\overline{1})}) \mid (\overline{0}\cdot\overline{(1+\overline{(0\lor 1)})}).\]
Задача 8
Пресметнете стойността на израза:
\[1+\overline{(0\mid\overline{(1\lor\overline{(0\cdot 1+\overline{1})})})\cdot(1\downarrow\overline{0})}.\]
Онлайн тест
15 въпроса • 4 точки за верен отговор • максимум 60 точки
Тест: Булеви функции — свойства и пълнота
Изберете верния отговор за всеки въпрос, след което натиснете КРАЙ.
Използвана литература
Видео уроци
Свързани уроци
◀
Булеви функции — въведение и основни операции
Конюнкция, дизюнкция, отрицание, импликация, еквивалентност — таблици за истинност и основни свойства.
Преглед на урока →
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
🎓 Подготовка за изпити
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
📚 Текущо обучение и студенти
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
📞 Онлайн уроци по математика за цялата страна◆
гл.ас. д-р Атанас Илчев◆
Индивидуални и групови уроци • Тел: 0883 375 433◆
Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆
Коментари
Публикуване на коментар