Тема 4. Відображення та функції
Відношення R між множинами X і Y (RXY) є функціональним, якщо всі його елементи (упорядковані пари) різні за першим елементом: кожному xX або відповідає тільки один елемент yY, такий, що xRy, або такого елемента y взагалі не існує.
Нехай
F –
функціональне відношення, FXY.
Відповідність x
y від першого до другого
елемента кожної пари (x,y)F
відношення F
називається функцією f
або відображення f
множини Df
в Y і
позначається як f:
DfY,
або як Df
Y.
Види зображень.
1. Функція f: XY називається сюр’єктивним відображенням, якщо Rf=Y.
2. Функція f: XY називається ін’єктивним відображенням, якщо з x1x2 випливає f(x1) f(x2).
3. Функція f: XY називається бієктивним відображенням, якщо вона сюр’єктивна та ін’єктивна.
Під час підготовки вивчення теми необхідно ознайомитися з матеріалом підручників [1, c. 54-62; 2, c. 54-62; 4, c. 23-28; 9, c. 11-17].
Тема 5. Булеві функції та алгебра логіки
Для зображення інформації в комп’ютерах використовується двійкова система числення. Таким чином, всі операції, які виконує комп’ютер, проводяться на множині {0,1}. Ці перетворення зручно формально зобразити за допомогою апарата двійкової логіки, який був розроблений Джорджем Булем у середині ХІХ століття.
Функція виду y=f(x1,x2,…,xn), аргументи xi і значення y якої належить множині В, називається n-місною булевою функцією. Такі функції також називають логічними або перемикальними функціями.
Таблиці, в яких кожній інтерпретації (тобто набору аргументів) функції поставлено у відповідність її значення, називаються таблицями істинності булевої функції.
Булева алгебра – це алгебраїчна структура (А, , +, ,0,1) з бінарними операціями , +: А2А, унарною операцією « »: АА і виділеними елементами 0,1 в носії А. При вивченні теми рекомендується використовувати [1, c. 99-111, c. 115-120; 2, c. 99-111, c. 115-120; 4, c. 52-58; 9, c. 31-35, c. 37-39; 12, c. 36-54; 17, c. 23-63].
Тема 6. Двоїстість булевих функцій
Функція
f*(x1,…,xn)
називається двоїстою до функції
f(x1,…,xn),
якщо f*(x1,…,xn)=
.
Функція, двоїста сама собі, тобто f=f*, називається самодвоїстою.
Нехай функція F задана як суперпозиція функцій f0 і функцій f1,…,fn: F=f0 (f1,…,fn). Функцію F*, що двоїста F, можна одержати, замінивши у формулі F функції f0; f1,…,fn на двоїсті до них f*0; f*1,…,f*n.
Зазначимо функції, що двоїсті до „елементарних” функцій логіки ,, , константа 0, константа 1:
f(x,y)=xy;
f*(x,y)=
=xy;
f(x)=
;
f*(x)=
=f(x);
f(x)=0;
f*(x)=
=1=
.
Під час вивчення теми рекомендується використовувати [1, c. 111-115; 2, c. 111-115; 4, c. 60-61; 9, c. 41-42; 12, 54-55; 17, 23-63].
Тема 7. Нормальні форми
Серед множин еквівалентних формул, що зображують обрану функцію f, виділяється одна формула, яка називається досконалою нормальною формою функції f. Вона має регламентовану логічну структуру і однозначно визначається за функцією f, а її побудова заснована на рекурентному застосуванні теореми про спеціальні розкладання булевої функції за змінними.
Теорема 1. Про диз’юнктивне розкладання булевої функції f(x1,x2,…,xn) за k змінними.
Будь-яку булеву функцію f(x1,x2,…,xn) можна зобразити в такій формі:
f(x1,…,xk,
xk+1,…,xn)=
.
Досконалою диз’юнктивною нормальною формою (ДДНФ) булевої функції називається формула, зображена у вигляді диз’юнції конституент одиниці даної функції.
Теорема 2. Про кон’юнктивне розкладання булевої функції f(x1,x2,…,xn) за k змінними.
Будь-яку булеву функцію f(x1,x2,…,xn) можна зобразити у такій формі:
f(x1,…,xk,
xk+1,…,xn)=
.
Досконалою кон’юнктивною нормальною формою (ДКНФ) функції називається формула, зображена у вигляді кон’юнкції конституент нуля даної функції.
Для кожної інтерпретації функції існують єдині відповідні їй конституента одиниці та конституента нуля. Тому різних конституент одиниці та нуля для функції n змінних f(x1,x2,…,xn) існує стільки ж, скільки й інтерпретацій цієї функції – 2n.
Кількість
різних булевих функцій від n
змінних також становить
.
Отже, для кожної булевої функції існує
єдина ДДНФ. Аналогічно доводиться, що
різних ДКНФ функції від n
змінних існує
і, отже, кожній булевій функції відповідає
єдина ДКНФ.
При вивченні теми рекомендується використовувати [1, c. 120-138; 2, c. 120-138; 4, c. 59-61; 9, c.35-37, 39-41; 12, c.62-68; 17, c.23-63].