4 Булеві функції та перетворення

4.1 Мета заняття

Ознайомлення на практичних прикладах з основними поняттями булевої алгебри. Вивчення способів задання булевих функцій. Аналіз формул і тотожностей, які визначають властивості операцій булевої алгебри. Вивчення і використання методів доведення тотожностей булевої алгебри.

4.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-8] з наступних питань: булеві змінні і булеві функції (основні поняття); область визначення та область значень булевої функції; способи задання булевих функцій; побудова таблиць істинності булевих функцій; реалізація булевих функцій формулами; принцип двоїстості в булевій алгебрі; булеві алгебри, закони і тотожності булевої алгебри.

Підготовка і виконання практичного заняття проводиться за два етапи.

Перший етап пов’язаний з вивченням на практичних прикладах наступних основних понять і визначень булевої алгебри: булеві змінні; булеві функції; номери булевих функцій та інтерпретацій; інтерпретація булевої функції; n-мірний булевий куб; область визначення булевої функції; таблиця істинності (відповідності) булевої функції; заперечення, кон’юнкція, диз’юнкція, еквіваленція, імплікація, стрілка Пірса, штрих Шеффера; булева формула; суперпозиція булевих функцій; пріоритет операцій булевої алгебри; інфіксний запис формул; еквівалентні формули та перетворення булевих функцій; двоїста функція; самодвоїста функція; принцип двоїстості; двохелементна булева алгебра; алгебра логіки; еквівалентні (рівносильні) формули булевих функцій.

Під час виконання першого етапу практичного заняття студент повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, представлених у підрозділі 4.3, на основі запропонованих типових прикладів (див. підрозділ 4.4).

4.3 Контрольні запитання і завдання

4.3.1 Контрольні запитання

1. Які змінні називаються булевими або логічними змінними?

2. Яка функція називається логічною (булевою, перемикальною)?

3. Наведіть приклади завдання (використання) булевих змінних у мовах програмування.

4. Як називається сукупність конкретних значень аргументів булевої функції?

5. Скільки елементів-слів містить -мірний булевий куб?

6. Що являє собою область визначення та область значень булевої функції?

7. Як визначити число всіх булевих функцій, що залежать від змінних?

8. Перелічить способи задання булевих функцій.

9. Що являє собою таблиця істинності (відповідності) булевої функції. Назвіть правила її побудови.

10. Перелічить булеві функції від однієї змінної, від двох змінних.

11. Яким чином визначається номер булевої функції? Як визначається номер інтерпретації?

12. Дайте визначення формули для задання булевої функції. Що таке суперпозиція булевих функцій?

13. Які знаки використовуються при побудові формул? Який пріоритет визначений для операцій алгебри логіки?

14. Який запис формул називається інфіксним? Наведіть приклади.

15. Чим відрізняється табличний і формульний спосіб задання булевих функцій? У яких випадках застосовується кожний з них?

16. Які формули називаються рівносильними або еквівалентними?

17. Перелічить основні методи визначення рівносильності формул.

18. Надайте визначення двоїстої і самодвоїстої функції.

19. Яким чином формується таблиця істинності двоїстої функції?

20. Сформулюйте принцип двоїстості булевих функцій.

21. Надайте визначення двохелементної булевої алгебри та алгебри логіки.

22. Перелічить основні закони булевої алгебри.

23. Яким способом можна довести закони булевої алгебри.

24. Сформулюйте і запишіть тотожності для законів булевої алгебри.

4.3.2 Контрольні завдання

Завдання 1. У скільки разів більше різних двійкових слів треба аналізувати для булевої функції , чим для булевої функції?

Завдання 2. У скільки разів більше можна побудувати булевих функцій, що залежать від 6-и змінних, чим від 4-х змінних?

Завдання 3. Побудувати таблиці істинності наступних функцій і визначити їхній порядковий номер:

а) ;

б) ;

в) ;

г) ;

д) .

Завдання 4. Перевірити за допомогою таблиць істинності, чи справедливі наступні співвідношення:

а) ;

б) ;

в) ;

г) ;

д) .

Завдання 5. При ;;;знайдіть значення функційі.

Завдання 6. Довести, що імплікація та еквіваленція може бути визначена через інші функції: ;.

Завдання 7. Використовуючи основні еквівалентності, довести еквівалентність формул і, якщо,.

Завдання 8. Знайти двоїсті формули до наступних функцій:

а) ;

б) ;

в) .

Завдання 9. Визначити, чи є наступні функції самодвоїстими:

а) ;

б) ;

в) .

Завдання 10. Спростити за допомогою законів булевої логіки наведені нижче вирази. Потім за допомогою таблиць істинності зрівняти отримані вирази із заданими:

а) ;

б) ;

в) .

Завдання 11. Булева функція визначається таким чином: вона дорівнює 1 при, або, якщоіприймають різні значення, а значення змінноїменше значення змінної. В інших випадках функція дорівнює 0. Скласти таблицю істинності функціїі записати множину.

4.4 Приклади аудиторних і домашніх завдань

Завдання 1. Визначити потужність множини двійкових слів (інтерпретацій), на яких визначена булева функція .

Розв’язок.

Кількість аргументів заданої булевої функції дорівнює 6 (). Потужність множини двійкових слів, на яких визначена булева функція, обчислюється за формулою.

Усього двійкових слів (інтерпретацій), на яких визначена булева функція , будеслова.

Завдання 2. Визначити кількість булевих функцій, які залежать від 5-ти булевих змінних.

Розв’язок.

Число всіх булевих функцій, що залежать від булевих змінних, дорівнює, отже, число всіх булевих функцій, що залежать від 5-ти булевих змінних, дорівнює.

Завдання 3. Побудувати таблицю істинності булевої функції і визначити її порядковий номер.

Розв’язок.

Побудуємо таблицю істинності булевої функції (табл. 4.1). Використаємо додаткові позначенняі. Отже.

Таблиця 4.1  Таблиця істинності булевої функції

0	0	0	1	1	1	0	1
0	0	1	1	1	0	0	1
0	1	0	0	0	1	0	0
0	1	1	0	0	0	1	1
1	0	0	0	1	1	0	0
1	0	1	0	1	0	0	0
1	1	0	1	1	1	0	1
1	1	1	1	1	0	0	1

Двійковий код, що відповідає значенням цієї функції, дорівнює 11010011 (останній стовпець таблиці 4.1).

Двійкове число в десятковій системі числення буді мати вигляд:

.

Порядковий номер функції дорівнює .

Завдання 4. Побудувати таблицю істинності для бінарної функції з порядковим номером 14.

Розв’язок.

Знайдемо двійкове число, що відповідає десятковому числу 14.

Запишемо це десяткове число як суму степенів числа 2, тобто .

Таким чином, відповідає двійковому числу.

Побудуємо таблицю істинності, для цього запишемо отримане число в стовпці значення функції таким чином, щоб молодший розряд був у нижньому рядку.

Таблиця 4.2  Таблиця істинності функції

0	0	1
0	1	1
1	0	1
1	1	0

Завдання 5. Чи еквівалентні формули і, якщо, а?

Розв’язок.

Побудуємо таблиці істинності для формули (табл. 4.1) і формули(табл. 4.3). Перевіримо еквівалентність формул за допомогою цих таблиць (табл. 4.3).

Таблиця 4.3  Узагальнена таблиця істинності функцій, які реалізовані формулами і

0	0	0	1	1
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	0
1	1	0	0	1
1	1	1	1	1

Аналіз показав, що таблиці істинності функцій не збігаються (стовпці ірізні), отже, формули нееквівалентні.

Завдання 6. Перевірити, чи справедливі наступні відношення:

а) ;

б) .

Розв’язок.

а) за допомогою еквівалентних перетворень перетворимо праву і ліву частину відношення . Спочатку перетворимо ліву частину:

.

Ліва і права частина відношення виявилися рівними, отже, відношення справедливе.

б) перетворимо ліву частину відношення:

.

Перетворимо праву частину відношення:

.

Результатом перетворення є . Це можна перевірити за допомогою таблиці істинності (табл. 4.4), позначивши,.

Таблиця 4.4  Таблиця істинності функцій і

0	0	0	0	1	1	0	1
0	0	1	0	1	0	0	1
0	1	0	0	0	0	0	1
0	1	1	1	0	1	0	1
1	0	0	0	1	1	1	1
1	0	1	0	1	0	0	0
1	1	0	0	1	0	0	0
1	1	1	1	1	1	1	1

Стовпці іне є рівними, отже, відношення несправедливе.

Завдання 7. Знайти функцію, двоїсту функції , якщо відомо, щотільки на інтерпретаціях (001), (011), (111).

Розв’язок.

Побудуємо таблицю істинності функції (табл. 4.5). Для стовпця значень функціїгенеруємо набір протилежних (інверсних) значень (10101110). Записавши цей набір у зворотній послідовності, отримаємо, таким чином, стовпець значень двоїстої функції.

Таблиця 4.5  Таблиця істинності двоїстих функцій

0	0	0	0	0
0	0	1	1	1
0	1	0	0	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	1
1	1	0	0	0
1	1	1	1	1

Завдання 8. Знайти булеву функцію, яка є двоїстою булевій функції .

Розв’язок.

Використовуючи правило знаходження двоїстих формул булевої алгебри (принцип двоїстості), тобто замінивши всі кон’юнкції на диз’юнкції, всі диз’юнкції на кон’юнкції, поставивши дужки, де необхідно, щоб порядок виконання операцій залишився таким, як був, знаходимо двоїсту булеву функцію .

Завдання 9. Булеві функції ізадаються таблицями істинності (табл. 4.6). Визначити, чи є дані булеві функції самодвоїстими.

Таблиця 4.6 – Таблиця істинності функцій і

0	0	0	0	0
0	0	1	1	1
0	1	0	1	0
0	1	1	1	1
1	0	0	0	1
1	0	1	0	1
1	1	0	0	0
1	1	1	1	0

Розв’язок.

З таблиці 4.6 видно, що кожне значення булевої функції є запереченням симетричного йому значення, наприклад: булева функція на інтерпретаціїдорівнює нулю, тобто, симетричне значення цієї функції на інтерпретаціїдорівнює одиниці, тобто.

Отже, функція є самодвоїстою.

Для булевої функції є такі значення функції, які не є рівними запереченню симетричних їм значень, наприклад: булева функція на інтерпретаціїдорівнює нулю, тобто, а симетричне значення цієї функції на інтерпретаціїтеж дорівнює нулю, тобто.

Отже, функція не є самодвоїстою.