Реферат: Бульові функції
1. Алгебри бульових виразів і бульових функцій
7.1.1. Основні поняття
Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 – Bn . Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.
Означення . Всюди визначена функція з Bn у B називається n-місною функцією алгебри логіки або n-місною бульовою функцією .
Послідовність змінних (x1 , x2 , …, xn ) із значеннями у B позначимо . Бульова функція f() задається у вигляді таблиці , або графіка зі стандартним розташуванням наборів:
| x1 , x2 , …, xn | f(x1 , x2 , …, xn ) |
| 0, 0, …, 0, 0 | f(0, 0, …, 0, 0) |
| 0, 0, …, 0, 1 | f(0, 0, …, 0, 1) |
| 0, 0, …, 1, 0 | f(0, 0, …, 1, 0) |
| 0, 0, …, 1, 1 | f(0, 0, …, 1, 1) |
| … | … |
| 0, 1, …, 1, 1 | f(0, 1, …, 1, 1) |
| 1, 0, …, 0, 0 | f(1, 0, …, 0, 0) |
| … | … |
| 1, 1, …, 1, 0 | f(1, 1, …, 1, 0) |
| 1, 1, …, 1, 1 | f(1, 1, …, 1, 1) |
Зауважимо, що в стандартному розташуванні набори можна розглядати як двійкові записи послідовних чисел від 0 до 2n -1. Функцію, задану зі стандартним розташуванням наборів, можна ототожнити з набором довжини 2n . Наприклад, двомісну функцію, задану таблицею
| x y | f(x, y) |
| 0 0 | 1 |
| 0 1 | 0 |
| 1 0 | 1 |
| 1 1 | 1 |
можна ототожнити з вектором (1011).
Далі іноді будемо позначати n-місну функцію f() як f(n) (), підкреслюючи кількість змінних, від яких вона залежить.
Очевидно, що множина всіх можливих наборів довжини 2n , тобто множина n-місних бульових функцій, складається з 22n елементів. При n=0 це 2, при n=1 – 4, при n=2 – 16, при n=3 – 256 тощо.
Нуль-місними функціями є сталі 0 і 1.
Одномісні функції подано у наступній таблиці разом з виразами, якими ці функції позначаються:
| x | 0 | 1 | x | Øx |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Функції 0 і 1 називаються тотожними нулем і одиницею , функція x – тотожною , Øx – запереченням . Замість виразу Øx вживається ще вираз . Ці вирази читаються як "не x".
Подамо також деякі з 16 двомісних функцій разом із їх позначеннями:
| x y | x Ùy | x Úy | x ®y | x «y | x Åy | x | y | x ¯y |
| 0 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Функція, позначена виразом xÙy, називається кон'юнкцією і позначається ще як x&y, x×y або xy. Усі ці вирази читаються як "x і y".
Функція, позначена виразом xÚy, називається диз'юнкцією . Вираз читається як "x або y".
Функція, позначена виразом x®y, називається імплікацією і позначається ще як xÉy. Ці вирази читаються як "x імплікує y" або "з x випливає y".
Функція, позначена виразом x«y, називається еквівалентністю і позначається ще як x~y або xºy. Ці вирази читаються як "x еквівалентно y", що в даному випадку збігається з "x дорівнює y".
Функція, позначена виразом xÅy, називається додаванням за модулем 2 або "виключним або ". Зауважимо, що її значення є протилежними до значень еквівалентності.
Функція, позначена виразом x|y, називається штрихом Шеффера і має значення, протилежні значенням кон'юнкції. Її вираз читається як "не x або не y".
Функція, позначена виразом x¯y, називається стрілкою Пірса і має значення, протилежні значенням диз'юнкції. Її вираз читається як "не x і не y".
Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f – відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f(x, y), наприклад, Ù(x, y).
З тримісних функцій наведемо лише так звану функцію голосування m(x, y, z), графік якої має такий вигляд:
| x y z | m(x, y, z) |
| 0 0 0 | 0 |
| 0 0 1 | 0 |
| 0 1 0 | 0 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 1 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
Її назва зумовлена тим, що її значення на кожному наборі збігається з більшістю значень змінних у цьому наборі.
Множину всіх n-місних функцій позначимо P(n) , а множину всіх функцій, тобто об'єднання P(n) по всіх n – P2 .
Перейдемо до означення таких понять, як алгебра бульових функцій і алгебра формул.
Алгебри бульових функцій, як і всі інші алгебри, визначаються своїми носіями та сигнатурами операцій. Носіями в алгебрах бульових функцій є множини функцій. Сигнатуру складає операція суперпозиції, або підстановки.
Означення . Нехай є n-місна функція f(n) () і n функцій g1 (y1,1 , y1,2 , …, y1,m1 ), g2 (y2,1 , y2,2 , …, y2,m2 ), …, gn (yn,1 , yn,2 , …, yn,mn ), залежні від змінних з деякої їх множини Y={y1 , y2 , …, yk }. Суперпозицією , або підстановкою функцій g1 , g2 , …, gn у функцію f(n) називається функція h(m) (y1 , y2 , …, ym ), кожне значення якої h(a1 , a2 , …, am ) визначається як
f(n) (g1 (a1,1 , a1,2 , …, a1,m1 ), g2 (a2,1 , a2,2 , …, a2,m2 ), …, gn (an,1 , an,2 , …, an,mn )).
Суперпозиція ще позначається як
--> ЧИТАТЬ ПОЛНОСТЬЮ <--