Булеви функции - основни понятия и дефиниции - част I

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆

Математика › Дискретна математика › Булеви функции

Булеви функции.
Основни понятия, таблици и закони на Де Морган

Пълен урок с теория, таблици на истинност, 5 решени задачи, самостоятелна работа и онлайн тест

Дискретна математика Булеви функции Закони на Де Морган 15 въпроса тест Д-р Атанас Илчев

Какво представляват двоичните функции, как се представят с таблици на истинност и как се използват основните булеви операции

Защо булевите функции са важни

Булевите функции са една от най-важните теми в дискретната математика, защото стоят в основата на логиката, програмирането, цифровата електроника и начина, по който компютрите вземат решения. Те работят само с две стойности — \(0\) и \(1\), които можем да тълкуваме като невярно/вярно, изключено/включено, забранено/разрешено, няма сигнал/има сигнал. Именно затова булевите функции са естественият математически език за описание на условия, логически схеми, електронни устройства и програмни решения.

Исторически началото е поставено от Джордж Бул, който през XIX век показва, че логическите разсъждения могат да се разглеждат алгебрично. По-късно тази идея придобива огромно значение за информатиката и техниката — логическите операции могат да се реализират с електрически схеми, а логическите зависимости да се превръщат в работещи програми и цифрови устройства. Така булевата алгебра се оказва не просто математическа теория, а една от фундаменталните основи на компютърната ера.

Защо тази тема е важна за програмирането? Защото всяка условна конструкция от типа if, всяка проверка за достъп, всяко решение дали дадено действие да се извърши или не, на практика е булева функция. Когато пишем програма, ние много често неусетно реализираме именно такива функции. Затова колкото по-добре разбираме структурата на булевите изрази, толкова по-ясен, по-кратък и по-надежден код можем да пишем.

Какво дава изучаването на булевите функции?
1) Учим се да описваме логически зависимости точно и кратко.
2) Разбираме как от математическа формула се получава логическа схема.
3) Виждаме как един логически израз се превръща в програмен код.
4) Научаваме как чрез опростяване на булева функция можем да опростим и самата програма или схема.

Пример: булева функция като логическа схема.
Нека имаме бариера на паркинг с три входни условия: \[x_1=\text{„има валидна карта"},\quad x_2=\text{„разрешен е нормален достъп"},\quad x_3=\text{„включен е специален режим"}.\] Бариерата се вдига само когато има карта и е изпълнено поне едно от условията \(x_2\) или \(x_3\): \[f(x_1,x_2,x_3)=x_1 x_2\lor x_1 x_3.\] Булевата алгебра ни позволява да опростим: \[x_1 x_2\lor x_1 x_3=x_1(x_2\lor x_3).\] Вместо две отделни проверки с карта — само една. Опростяването е еднакво валидно за логическата схема, за програмния код и за математическия израз.

Двата варианта в програмен код правят едно и също, но вторият е по-кратък, по-лесен за четене и по-малко податлив на грешки:

Преди опростяване:
if ((card && normalAccess) || (card && specialMode)) { openBarrier(); }

След опростяване:
if (card && (normalAccess || specialMode)) { openBarrier(); }

Ето защо изучаването на булевите функции не е само теория. То ни учи как да мислим за условията по ясен математически начин, как да превеждаме реални ситуации на езика на логиката и как чрез опростяване на булеви изрази да правим кода и схемите по-ефективни.

---

Определения и основни факти

Множеството \(B_2^n = B_2\times B_2\times\cdots\times B_2\) се състои от всички наредени \(n\)-торки от нули и единици. Булевата функция \(f:B_2^n\to B_2\) съпоставя на всяка такава \(n\)-торка \((x_1,x_2,\ldots,x_n)\) стойност от \(\{0,1\}\).

Определение 1. Нека \(B_2=\{0,1\}\). Булева (двоична) функция се нарича функция от вида \(f:B_2^n\to B_2\), където \(n\in\mathbb{Z}^+\).

Всяка двоична функция може да се представи с таблица на истинност:

Представяне на двоична функция чрез таблица

Всички двоични функции се представят в обща таблица:

Таблица на всички двоични функции

Множеството на всички булеви функции на \(n\) променливи означаваме с \(P_2\).

Теорема 1. Броят на всички булеви функции на \(n\) променливи е \[|P_2|=2^{2^n}.\]

Всички булеви функции на една променлива:

Таблица на всички булеви функции на една променлива

\(f_0(x)=0\) и \(f_3(x)=1\) са константи;  \(f_1(x)=x\) е идентитет;  \(f_2(x)=\overline{x}\) е отрицание.

Всички булеви функции на две променливи:

Булеви функции на две променливи

Вместо \(f(x_1,x_2)\) пишем \(x_1\,f\,x_2\) (инфиксен запис). Имена на основните функции:

1. \(f_0=\mathbf{0}\) и \(f_{15}=\mathbf{1}\) — константи
2. \(f_1\) — конюнкция (логическо и), означение \(\mathbf{\cdot}\)
3. \(f_3=x_1\), \(f_5=x_2\) — идентитети
4. \(f_6\) — изключващо или, означение \(\mathbf{+}\)
5. \(f_7\) — дизюнкция (логическо или), означение \(\lor\)
6. \(f_8\) — стрелка на Пиърс, означение \(\downarrow\)
7. \(f_9\) — еквивалентност, означение \(\equiv\)
8. \(f_{10}=\overline{x_2}\), \(f_{12}=\overline{x_1}\) — отрицания
9. \(f_{13}\) — импликация, означение \(\to\)
10. \(f_{14}\) — черта на Шефер, означение \(\mid\)

Броят на всички булеви функции на две променливи е \(|P_2|=2^{2^2}=16\).

---

Разработени задачи

Кликнете върху задача, за да видите решението.

1

Да се пресметне \(x_1\cdot 0\).

▼

Решение

Тъй като \(0\cdot0=0\) и \(1\cdot0=0\), следователно \(\mathbf{x_1\cdot0=0}\).

2

Да се пресметне \(x_1+x_1\) (изключващо или).

▼

Решение

Тъй като \(0+0=0\) и \(1+1=0\), следователно \(\mathbf{x_1+x_1=0}\).

3

Да се пресметне \(x_1+1\).

▼

Решение

Тъй като \(0+1=1\) и \(1+1=0\), следователно \(\mathbf{x_1+1=\overline{x_1}}\).

4

Да се пресметне \(x_1\lor 1\).

▼

Решение

Тъй като \(0\lor1=1\) и \(1\lor1=1\), следователно \(\mathbf{x_1\lor1=1}\).

Теорема (Закони на Де Морган). В сила са равенствата: \[\overline{x_1\cdot x_2}=\overline{x_1}\lor\overline{x_2}=x_1\mid x_2\] и \[\overline{x_1\lor x_2}=\overline{x_1}\cdot\overline{x_2}=x_1\downarrow x_2.\]

5

Докажете закона на Де Морган чрез таблица на истинност.

▼

Доказателство

От таблицата се вижда, че колоните на \(\overline{x_1\cdot x_2}\) и \(\overline{x_1}\lor\overline{x_2}\) съвпадат, а колоните на \(\overline{x_1\lor x_2}\) и \(\overline{x_1}\cdot\overline{x_2}\) също съвпадат. ■

---

Задачи за самостоятелна работа

Опитайте да решите сами, преди да потърсите помощ.

Задача 1Да се пресметне \(x_1\lor0\).

Задача 2Да се пресметне \(x_1+\overline{x_1}\).

Задача 3Да се пресметне \(x_1\lor\overline{x_1}\).

Задача 4Да се пресметне \(x_1\lor x_1\).

Задача 5Да се пресметне \(x_1\cdot\overline{x_1}\).

---

Онлайн тест

15 въпроса • 4 точки за верен отговор • максимум 60 точки

Тест: Булеви функции

Изберете верния отговор за всеки въпрос, след което натиснете КРАЙ.

1Какво е \(B_2\)?

\(\{0,1\}\) \(\{1,2\}\) \(\mathbb{N}\) \(\mathbb{Z}\)

2Булева функция е функция от вида:

\(f:\mathbb{R}^n\to\mathbb{R}\) \(f:B_2^n\to B_2\) \(f:\mathbb{N}\to\mathbb{N}\) \(f:\mathbb{Z}^n\to\mathbb{Z}\)

3Колко са всички булеви функции на \(n\) променливи?

\(2^n\) \(n^2\) \(2^{2^n}\) \(n!\)

4Коя функция на една променлива се нарича идентитет?

\(f_0(x)=0\) \(f_1(x)=x\) \(f_2(x)=\overline{x}\) \(f_3(x)=1\)

5Коя функция на една променлива се нарича отрицание?

\(f_2(x)=\overline{x}\) \(f_1(x)=x\) \(f_0(x)=0\) \(f_3(x)=1\)

6Как се называ функцията \(f_1(x_1,x_2)\)?

Дизюнкция Конюнкция Импликация Еквивалентност

7Как се означава изключващото или?

\(\lor\) \(\downarrow\) \(+\) \(\to\)

8Как се nazywa функцията \(f_7(x_1,x_2)\)?

Конюнкция Дизюнкция Импликация Черта на Шефер

9Как се nazywa функцията \(f_8(x_1,x_2)\)?

Стрелка на Пиърс Еквивалентност Импликация Идентитет

10Колко са всички булеви функции на две променливи?

4 8 16 32

11Какъв е резултатът от \(x_1\cdot0\)?

\(x_1\) \(1\) \(0\) \(\overline{x_1}\)

12Какъв е резултатът от \(x_1+1\)?

\(1\) \(x_1\) \(\overline{x_1}\) \(0\)

13Какъв е резултатът от \(x_1\lor1\)?

\(x_1\) \(0\) \(1\) \(\overline{x_1}\)

14Кое равенство е закон на Де Морган?

\(\overline{x_1\cdot x_2}=\overline{x_1}\lor\overline{x_2}\) \(x_1\lor1=0\) \(x_1+x_1=1\) \(x_1\cdot0=1\)

15Как се бележи чертата на Шефер?

\(\mid\) \(\downarrow\) \(+\) \(\equiv\)

---

Видео уроци

🎥

Видео урок — очаквайте скоро

Следете канала за нови публикации.

▶ Абонирайте се за канала

---

Свързани уроци

▶

Булеви функции — свойства, пълнота и теорема на Бул

Комутативност, асоциативност, ДДНФ, пълни множества — теорема на Бул, 4 разработени задачи и тест.

Преглед на урока →

---

Използвана литература

• 1.Дискретна математика, С. Бойчева, С. Толева-Стоименова, изд. Сиела, 2018
• 2.Увод в дискретната математика, К. Манев, изд. КЛМН, 2012
• 3.Въведение в дискретната математика, Хр. Кискинов, ПУИ

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

• ›НВО по математика след 7 клас
• ›НВО по математика след 10 клас
• ›Кандидатстудентски изпити по математика
• ›Софийски университет „Св. Климент Охридски“
• ›УАСГ – Университет по архитектура, строителство и геодезия
• ›Технически университет – София и др.
• ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)

📚 Текущо обучение и студенти

• ›Усвояване на текущия учебен материал (всички класове)
• ›Студенти по всички математически дисциплини:
  Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ Подготовка за НВО, ДЗИ, кандидатстудентски изпити◆