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

Реферат на тему: 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(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(; 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)(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)) або в інфіксному записі (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) називається суттєвою якщо існує хоча б одна пара наборів значень змінних

(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) не має суттєвих змінних.

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

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

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


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)(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 є замкненими класами.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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