1 Булеві функції Лекція 3 Булеві функції

основний твір Буля “Дослідження законів думки, на яких засновані математичні

теорії логіки й імовірності”. Ця ґрунтовна книга нині зараховується до математичної класики; у ній детально досліджується та система алгебри, яку сьогодні називають “алгеброю висловлювань”.

логіки”, і те глибоке розуміння природи математики і сенсу абстрактних

математичних структур, які він при цьому виявив, не тільки цілком виправдовують загальноприйнятий термін “структура (або алгебра) Буля”, але і зробили можливим крилатий вислів: „Чисту математику відкрив Буль у праці, яка називається Закони думки” (Б. Рассел, англійський математик і філософ).
Буль мав чотирьох доньок, які всі виявилися чудовими людьми (у нашій країні найвідоміша Етель Ліліан Буль, у заміжжі Войнич, автор роману “Овід”).

вихідна множина булевих змінних (аргументів). Вважатимемо, що аргументи визначено на

множині E2 = {0, 1}, і розглядатимемо функції f(x1, x2, ..., xn) такі, що f(1, 2, ..., n)E2 за умови iE2. У такий спосіб f(x1, x2, ..., xn) розумітимемо як запис функції, що залежить від множини аргументів X.

Булеві функції

Означення 2.1. Булева функція n змінних або функція алгебри логіки визначається як відображення

для її задання досить вказати значення функції, які відповідають кожному

з наборів значень аргументів, тобто задати таблицю (наступний слайд).
Якщо існують n змінних, то вони набувають 2n різних значень. Якщо набір аргументів розглядати як запис числа у двійковій системі числення, то розташування наборів відповідає природному розташуванню двійкових чисел у порядку зростання 0, 1, ..., 2n–1.

Табличне задання булевої функції

залежать

від n змінних x1, x2, ..., xn, дорівнює

.

Доведення. Якщо зафіксувати n змінних x1, x2, ..., xn, то таблиця задання функції матиме m = 2n рядків. Таблиці для різних функцій відрізнятимуться тільки значеннями правого

стовпчика, а кількість таблиць складатиме 2m, тобто .

Теорему доведено.

Теорема про кількість булевих функцій

..., xn) із P2 істотно залежить від аргументу xi, якщо

існують такі значення змінних x1, x2, ..., xi–1, xi, xi+1, ..., xn, що
f(1, 2, ..., i–1, 0, i+1,..., n)  f(1, 2, …, i-1, 1, i+1,. .., n).
У цьому випадку змінна xi називається істотною. Якщо xi не є істотною змінною, то вона називається неістотною або фіктивною.

Істотні та фіктивні змінні

є фіктивною. Візьмемо таблицю для функції f(x1, x2, ..., xn)

і згідно з нею побудуємо нову таблицю методом викреслювання всіх рядків, що мають вигляд 1, 2, ..., i-1, 1, i+1, ..., n, а також викреслювання стовпчика для аргументу xi. Отримана таблиця визначатиме деяку функцію
g(x1, x2, ..., xi-1, xi+1, ..., xn).

Вважатимемо, що її здобуто із f(x1, x2, ..., xn) шляхом вилучення фіктивної змінної xi, а функцію
f(x1, x2,..., xn) – із g(x1, x2, ..., xi–1, xi+1, ..., xn) шляхом введення фіктивної змінної xi.

Введення та вилучення фіктивних змінних

x2, ..., xm) називаються рівними, якщо одну з них можна

одержати із другої шляхом додавання або вилучення фіктивних аргументів.

Існують два типи функцій, що не мають істотних змінних: функції першого типу тотожно дорівнюють 0, а другого – тотожно дорівнюють 1. Введемо до подальшого розгляду константи 0 та 1 (як функції від порожньої множини змінних).

Зауваження. Якщо задано скінченну систему функцій з
P2 = {f1, ..., fs}, s1, то можна вважати, що всі ці функції залежать від тих самих змінних x1, ..., xn, тобто мають вигляд f1(x1, ..., xn), ..., fs(x1, ..., xn).

Рівність булевих функцій

= 2. Маємо дві функції: це константи 0 та 1

(тотожні сталі).

= 4. Функції fi(x) наведено у табличному вигляді (для спрощення

таблиць надалі аргументи функцій у них не записуються).

Функції f1(x) = 0 та f4(x) = 1 – константи.

f2(x) = = x – тотожна функція.

Функція f3(x) називається запереченням x, f3(x) = .

Операція називається операцією інверсії та описується як = 1, = 0.

= 16. Функції fi(x) наведено у таблиці.
Функції системи P2

(3)

Для цих функцій, як правило, використовують позначення:
f2 – x1x2 (або x1x2); f3 – x1 x2; f5 – x1 x2;
f7 – x1x2; f8 – x1x2; f9 – x1x2; f10 – x1  x2;
f12 – x1x2; f14 – x1x2; f15 – x1x2.

|p2(4)|= 65536.

тотожних перетворень булевих (логічних) виразів.

Властивості заперечення

= x. Подвійне заперечення

логічної (булевої) змінної еквівалентно булевій змінній.

переставний закон;
x0 = 0 – властивість нульової множини;
x1 = x

– властивість незмінності;
xx = x – властивість повторення;
x = 0 – властивість додатковості;
x1(x2x3) = (x1x2)x3 – сполучний закон
(дужки можна опустити);

(x1x2)( x1 2) = x1 – властивість склеювання.

переставний закон;
x0 = x – властивість незмінності;
x1 = 1 –

властивість універсальної множини;
xx = x – властивість повторення;
x = 1 – властивість додатковості;
x1(x2x3) = (x1x2)x3 – сполучний закон
(дужки можна опустити);

x1x2x1 2 = x1 – властивість склеювання.

;

x1x2 =

.

Правила дозволяють перейти від логічного множення до додавання та навпаки.

логічного множення щодо логічного додавання;
x1(x2x3) = (x1x2)(x1x3) – логічного додавання

щодо логічного множення.

1x2;
x1  x2 = (x1x2)(x2x1);
x1  x2 =

( 1x2)(x1 2);
x1  x2 = ( 1 2)( x1x2).

2

x1x2 =

.

Властивості функцій штрих Шеффера та
стрілка Пірса

x1|x2 = ;

x1|x2 = ( 1 2);

x1x2 = ;

x1x2 = ( 1 2).