Бульові функції

Реферат

на тему:

Бульові функції

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
)).

Суперпозиція ще позначається як

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(Ù; xÚy, y®z) задається наступною таблицею:

x y z	x Úy	y ®z	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(Ù; xÚy, y®x) задається таблицею:

x y	x Úy	y ®x	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)
(a1
, a2
, …, an
), якщо T=f(n)
(T1
, T2
, …, Tn
), а формули T1
, T2
, …, Tn
мають на цьому наборі значення відповідно a1
, a2
, …, an
.

Означення
. n-місна бульова ф

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

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

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

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

Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами Ø, Ù, Ú, ®, Å, «, |, ¯ записувати не всі необхідні дужки. ****

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

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

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

(a1
, a2
, …, ai-1
, 0, ai+1
, …, an
) і (a1
, a2
, …, ai-1
, 1, ai+1
, …, an
),

така, що

f(n)
(a1
, a2
, …, ai-1
, 0, ai+1
, …, an
) ¹ f(n)
(a1
, a2
, …, ai-1
, 1, ai+1
, …, an
).

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

(a1
, a2
, …, ai-1
, 0, ai+1
, …, an
) і (a1
, a2
, …, ai-1
, 1, ai+1
, …, an
)

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

f(n)
(a1
, a2
, …, ai-1
, 0, ai+1
, …, an
) = f(n)
(a1
, a2
, …, ai-1
, 1, ai+1
, …, an
).

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

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

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

Означення
. Нехай **** Формули F1
і F2
називаються еквівалентними
, якщо

2. Бульові функції та комбінаційні схеми

І-елемент АБО-елемент Å-елемент НЕ-елемент a a a b r b r b r a r r = aÙb r = aÚb r = aÅb r = Øa

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

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

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

a1 b1 a2 b2 . . . an bm

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

Приклади.

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

xÅy = xÙØyÚØxÙy.

x y

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

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

xÚy = xÅyÅxÙy.

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

x y

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

x s d y

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

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

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

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

[{Ù, Ú, Ø}] = [{Å, Ù, 1}] = P2
.

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

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

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

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

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

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

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

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

Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 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)
(a1
, a2
, …, an
) = ****f(n)
(a1
, a2
, …, an
) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)
(0, 0, …, 0)=0.

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

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

Список рекомендованої літератури

1. Виленкин Н.Я. Популярная комбинаторика.–М.: Наука, 1975.

2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.–М.: Наука, 1973.

3. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.–М.: Наука, 1982

4. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование.–К.: Наукова думка, 1988.

5. Ершов Ю.Л., Палютин Е.А., Математическая логика.–М.:Наука, 1979.

6. Карри Х.Б. Основания математической логики.–М.: Мир, 1969.

7. Клини С.К. Математическая логика.– М.: Мир, 1973.

8. Колмогоров А.Н. Фомин С.В. Элементы теории функций и функционального анализа.–М.: Наука, 1981.

9. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.–М.:Энергоатомиздат, 1988.

10. Курош А.Г. Лекции по общей алгебре.–М.: Наука, 1973.

11. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.–М.: Наука, 1984.

12. Линдон Р. Заметки по логике.– М.: Мир, 1968.

13. Мендельсон Э. Введение в математическую логику.–М.: Наука, 1984.

14. Новиков П.С. Элементы математической логики.–М.: Наука, 1973.

15. Ставровський А.Б., Коваль Ю.В. Методичні рекомендації та вказівки до курсу "Дискретна математика" (розділ "Множини та відповідності").– К.:"Київський університет", 1994.

16. Трохимчук Р.М. Збірник задач з дискретної математики (розділ "Множини і відношення") для студентів факультету кібернетики.–К.:"Київський університет", 1997.

17. Трохимчук Р.М. Множини і відношення. Навчальний посібник для студентів факультету кібернетики.–К.:"Київський університет", 1993.

18. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

19. Липский В. Комбинаторика для программистов. М.: Мир, 1988.