Алгебри бульових функцій

Алгебри бульових функцій

1. Алгебри бульових виразів і бульових функцій

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	xy	xy	xy	xy	xy	x | y	xy
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

Функція, позначена виразом xy, називається кон'юнкцією і позначається ще як x&y, xy або xy. Усі ці вирази читаються як "x і y".

Функція, позначена виразом xy, називається диз'юнкцією. Вираз читається як "x або y".

Функція, позначена виразом xy, називається імплікацією і позначається ще як xy. Ці вирази читаються як "x імплікує y" або "з x випливає y".

Функція, позначена виразом xy, називається еквівалентністю і позначається ще як x~y або xy. Ці вирази читаються як "x еквівалентно y", що в даному випадку збігається з "x дорівнює y".

Функція, позначена виразом xy, називається додаванням за модулем 2 або "виключним або". Зауважимо, що її значення є протилежними до значень еквівалентності.

Функція, позначена виразом x|y, називається штрихом Шеффера і має значення, протилежні значенням кон'юнкції. Її вираз читається як "не x або не y".

Функція, позначена виразом xy, називається стрілкою Пірса і має значення, протилежні значенням диз'юнкції. Її вираз читається як "не 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(1, 2, …, m) визначається як f(n)(g1(1,1, 1,2, …, 1,m1), g2(2,1, 2,2, …, 2,m2), …, gn(n,1, n,2, …, n,mn)).

Суперпозиція ще позначається як S(f(n); g1(y1,1, y1,2, …, y1,m1), g2(y2,1, y2,2, …, y2,m2), …, gn(yn,1, yn,2, …, yn,mn)).

Приклади.

1. h1(x, y, z)=S(; xy, yz) задається наступною таблицею:

x y z	xy	yz	h1(x, y, z)
0 0 0	0	1	0
0 0 1	0	1	0
0 1 0	1	0	0
0 1 1	1	1	1
1 0 0	1	1	1
1 0 1	1	1	1
1 1 0	1	0	0
1 1 1	1	1	1

2. h2(x, y)=S(; xy, yx) задається таблицею:

x y	xy	yx	h2(x, y)
0 0	0	1	0
0 1	1	0	0
1 0	1	1	1
1 1	1	1	1

Нехай є множина бульових функцій F. Утворюючи з них та їх суперпозицій усі можливі суперпозиції, ми одержимо множину функцій, яку позначимо [F]. Отже, маємо алгебру ([F]; S), породжену множиною функцій F. Інша множина функцій F1 буде породжувати, взагалі кажучи, іншу алгебру ([F1]; S). Наприклад, алгебри ({(0111), (0001)}; S) і ({(10), (0001)}; S).

Розглянемо тепер поняття алгебри формул (термів, або виразів). Нехай є множина функцій F. Кожній n-місній функції з F поставимо у взаємно однозначну відповідність символ, що її позначає (функціональний символ) f(n). Нехай X - зліченна множина змінних (точніше, їх імен).

Означення.

1. Ім'я змінної є формулою.

2. Якщо f(n) - функціональний символ, а T1, T2, …, Tn є формулами, то f(n)( T1, T2, …, Tn) є формулою.

3. Інших формул немає.

Це означення задає множину формул із функціональними символами з множини F, які одержуються за допомогою підстановок, тобто суперпозицій. Таким чином, ми маємо алгебру формул, породжену множиною функціональних символів F. Інша множина функціональних символів буде породжувати й іншу алгебру формул.

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

Означення. Значенням формули T на наборі значень змінних з множини X є:

1) значення змінної x, якщо T є змінною x;

2) f(n)(1, 2, …, n), якщо T=f(n)(T1, T2, …, Tn), а формули T1, T2, …, Tn мають на цьому наборі значення відповідно 1, 2, …, n.

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

Звідси випливає інше означення суперпозиції функцій.

Означення. n-місна бульова функція f(n) є суперпозицією функцій f1, f2, …, fn, якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f1, f2, …, fn.

З наведених прикладів 1 і 2 видно, що функція h1(x, y, z) задається формулою ((x, y), (y, z)), або в інфіксному записі (xy)(yz). Аналогічно функція h2(x, y) задається формулою ((x, y), (y, x)), або (xy)(yx). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами , , , тобто є суперпозиціями цих функцій.

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

1.2 Суттєві та несуттєві змінні

Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x, y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від y. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.

Означення. Змінна xi функції f(n)(x1, x2, …, xi, …, xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних

(1, 2, …, i-1, 0, i+1, …, n) і (1, 2, …, i-1, 1, i+1, …, n),

така, що

f(n)(1, 2, …, i-1, 0, i+1, …, n) f(n)(1, 2, …, i-1, 1, i+1, …, n).

Змінна xi називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень

(1, 2, …, i-1, 0, i+1, …, n) і (1, 2, …, i-1, 1, i+1, …, n)

мають місце рівності:

f(n)(1, 2, …, i-1, 0, i+1, …, n) = f(n)(1, 2, …, i-1, 1, i+1, …, n).

Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну x і несуттєву y. Функція двох змінних, задана як вектор (1111), не має суттєвих змінних.

1.3 Еквівалентні формули та закони

Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули xy і xy обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул.

1.4 Канонічні формули для подання бульових функцій

Задачі

1. Побудувати графік функції за формулою, що її задає:

((xy)z)x

x((xy)z);

((xy)z)x;

((xy)z)x;

((xy)z)x;

((xy)z)x;

x(y(zx));

x(y(zx);

x(y(zx));

x(yzx);

x(y(zx));

x(y(yx));

x(y(zx));

x(y(zx));

x(y(zx));

x(y(zx));

x(y(zx));

x(y(zx));

2. Указати суттєві та несуттєві змінні функції, заданої вектором значень при стандартному розташуванні наборів (за зростанням у лексикографічному порядку):

(0000 1111 1100 0011);

(0000 1111 1111 0010);

(0000 1111 0110 0101);

(0000 1111 0011 1010);

(0000 1111 0011 0110);

(0000 1111 1100 1010);

(0000 1100 0011 0101);

(0000 0011 0011 1101);

(0000 0011 1100 0010);

(0000 0011 1001 0101);

(0000 0011 0101 1111);

(0011 1100 0111 1100);

(0011 1100 1001 0101);

(0011 0011 0011 1010);

(0011 0011 1100 1100);

(0011 0011 1001 1001);

(1001 1001 1100 1100);

(1001 1001 1001 0001).

3. За виразом побудувати еквівалентні йому вирази у ДДНФ, ДКНФ, у вигляді полінома Жегалкіна (варіанти 1-18 відповідають варіантам задачі 1).

4. Побудувати формулу з трьома змінними, істинну тоді й тільки тоді, коли:

рівно одна змінна має значення 1;

не менше ніж одна змінна має значення 1;

рівно дві змінні мають значення 1;

не менше двох змінних мають значення 1;

непарна кількість змінних має значення 1;

парна кількість змінних має значення 1.

5. Побудувати формулу з чотирма змінними, істинну тоді й тільки тоді, коли:

рівно одна змінна має значення 1;

не менше ніж одна змінна має значення 1;

рівно дві змінні мають значення 1;

не менше двох змінних мають значення 1;

рівно три змінні мають значення 1;

не менше трьох змінних мають значення 1;

непарна кількість змінних має значення 1;

парна кількість змінних має значення 1.

Розглянемо реалізацію бульових функцій у вигляді комбінаційних схем. Найпростішими з них є логічні елементи, відповідні бульовим функціям: кон'юнкції , диз'юнкції , додавання за модулем 2 та заперечення . Вони позначаються й зображаються таким чином:

Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон'юнкція, диз'юнкція та додавання за модулем 2.

З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:

Тут

bj=fj(a1, a2, …, an), j=1, 2, …, m..

Приклади.

1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору {, , }:

xy = xyxy.

Звідси відповідна схема має вигляд:

2. Побудуємо схему з І- та -елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору {, , 1}:

xy = xyxy.

Звідси відповідна схема має вигляд:

3. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує так званий "однорозрядний напівсуматор"[****] з двома симетричними входами x, y і двома виходами: s = xy, d = xy. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору {, , }: s = xyxy. Тоді схема має вигляд:

Задачі

6. З використанням І-, АБО- та НЕ-елементів накреслити комбінаційну схему, відповідну:

функції ;

функції ;

функції ;

функції |;

функції голосування xyxzyz;

арифметичному додаванню двох однорозрядних двійкових чисел із переносом, складену з функціональних елементів у мінімальній кількості;

арифметичному додаванню трьох однорозрядних двійкових чисел із переносом;

арифметичному додаванню двох дворозрядних двійкових чисел із переносом у третій розряд;

додаванню 1 до дворозрядного двійкового числа із втратою переносу зі старшого розряду;

порівнянню "=" двох дворозрядних двійкових чисел;

порівнянню ">" двох дворозрядних двійкових чисел;

порівнянню "" двох дворозрядних двійкових чисел.

7. З використанням І- та -елементів, а також входів, на які подається 1, накреслити комбінаційну схему, відповідну:

функції ;

функції ;

функції ;

функції |;

функції голосування xyxzyz;

арифметичному додаванню двох однорозрядних двійкових чисел із переносом;

арифметичному додаванню трьох однорозрядних двійкових чисел із переносом;

арифметичному додаванню двох дворозрядних двійкових чисел із переносом у третій розряд;

додаванню 1 до дворозрядного двійкового числа із втратою переносу зі старшого розряду;

порівнянню "=" двох дворозрядних двійкових чисел;

порівнянню ">" двох дворозрядних двійкових чисел;

порівнянню "" двох дворозрядних двійкових чисел.

3. Замкнені та повні набори функцій. Критерій Поста повноти набору функцій

У підрозділі 7.1 ми побачили, що будь-яку бульову функцію можна задати як суперпозицію функцій з набору {, , } або з набору {, , 1}.

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

Таким чином, якщо P2 позначає множину всіх бульових функцій, то

{, , } = [{, , 1}] = P2.

Означення. Множина функцій F називається функціонально повною, якщо F=P2.

Отже, множини {, , } і {, , 1} є функціонально повними.

Природним є питання про те, які властивості повинні мати функціонально повні множини функцій.

Видатний математик Еміль Пост сформулював і обгрунтував критерій повноти множини функцій у загальному випадку алгебри функцій з операцією суперпозиції. У цьому критерії, тобто необхідній і достатній умові, використовується поняття передповного класу. Розглянемо його.

Нехай F позначає множину всіх можливих функцій деякої алгебри функцій A з операцією суперпозиції.

Означення. Множина функцій S називається передповним класом алгебри A, якщо SF і за будь-якої функції f з множини F\S набір S{f} є повним: S{f}=F.

Критерій Поста. Нехай S1, S2, … - усі передповні класи алгебри функцій F. Множина функцій M є повною тоді й тільки тоді, коли для кожного передповного класу Si множина M містить fM\Si.

Приймемо це твердження без доведення.

Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 5. Це множини всіх функцій:

що зберігають сталу 0,

що зберігають сталу 1,

самодвоїстих,

лінійних,

монотонних.

Означимо вказані функції.

Означення. Функція f(n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.

Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.

Наприклад, тотожна функція f(x)=x зберігає сталі 0 і 1, функція f(x)=x не зберігає жодної.

Означення. Функція f(n) є самодвоїстою, якщо для всіх пар протилежних наборів вона приймає на них протилежні значення:

f(n)(1, 2, …, n) = ****f(n)(1, 2, …, n)

зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.

Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.

Неважко переконатися, що множини означених функцій, позначені відповідно T0, T1, S, L, M, є замкненими класами.

Задачі

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

{0, 1};

{x};

{1, x};

{x1…xn, n1};

{1, x1…x2n, n1}

{0, x1…xn, n1}

{0, x1…x2n, n1}

{x1…xn, n1}

{0, x1…x2n, n1}

9. Визначити, чи істинно, що за будь-яких замкнених класів(будь-якого замкненого класу):

їх перетин є замкненим класом;

їх об'єднання є замкненим класом;

їх різниця є замкненим класом;

його доповнення не є замкненим класом.

10. Поставити один із знаків , , =, , , , яким за будь-яких множин F1 і F2 найточніше виражається теоретико-множинне відношення між множинами:

[F1F2] і [F1][F2];

[F1F2] і [F1][F2];

[F1\F2] і [F1]\[F2].

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

xy і xy;

xy і yx;

xyxzyz і xyxzyz;

xyz і xyz;

xy і xy;

xy і xy;

xy і x|y;

xy і x|y.

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

{, , };

{, , };

{, , };

{, 0, , };

{, 1, , };

{, 0, , };

{, , };

{, , };

{|, , };

{|, , };

{, 1, , };

{1, , , };

{1, , , };

{, 1, , };

{1, , , };

{1, , , };

{, , };

{, , };

{, 0, , };

{0, , , };

{0, , , };

{, 0, , };

{0, , , };

{0, , , }.

8. Обчислити кількість функцій від n змінних у множині:

T0T1;

T0T1;

T0L;

T0L;

L\(T0T1);

L\(T0T1);

Lk - лінійних функцій, що мають k суттєвих змінних;

ST1;

T0\S;

LST1;

S(T0T1);

S(T0\T1);

S\(T0T1);

Sk - самодвоїстих функцій, що мають k суттєвих змінних;

M\(T0T1);

M\(T0T1);

ML;

MLS;

L\(MS).