Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Алгебра Буля

Волинський національний університет імені Лесі Українки

Математичний факультет

Кафедра геометрії і алгебри

Спеціальні форми зображення булевих

функцій у алгебрі Буля

Виконавець курсової роботи:

студентка II курсу

Мартинюк Оксана Володимирівна

Науковий керівник:

Швай Ольга Леонідівна

доцент

Луцьк-2011

Зміст

Вступ………………………………………………………………………………3

Розділ I. Булеві функції…………………………………………………………...5

1.1. Основні поняття та означення…...…………………………………………5

1.2. Поняття формули……………………………………………………………7

1.3. Реалізація функцій формулами…………………………………………….7

1.4. Принцип суперпозиції………………………………………………………8

1.5. Рівносильність формул…………………………………………………....10

Розділ II. Алгебра Буля………………………………………………………….12

2.1. Закони алгебри Буля………………………………………………………12

2.2. Диз’юнктивні нормальні форми………………………………………….13

2.3. Кон’юнктивні нормальні форми………………………………………….17

Висновки...……………………………………………………………………….20

Література………………………………………………………………………..20

Додатки…………………………………………………………………………...22

Вступ

Основи булевої алгебри закладено в працях англійського математика Джорджа Буля(1815 - 1864). Це такі праці як «Математичний аналіз логіки»(1847), «Закони мислення»(1854), де він продовжив ідеї Лейбніца щодо створення символічного обчислення, в якому змістовні доведення мали б стати предметом математичного дослідження. У цих працях Дж. Буль вперше виклав апарат двійкової логіки, що ґрунтується на унарних(функціях вигляду ) і бінарних операціях (функціях вигляду ) з множиною B, що містить лише два елементи, які позначають 0 і 1.

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

Булевою називається функція, значення і кожний аргумент якої можуть дорівнювати одному з двох чисел: 0 або 1. Булеві функції тісно пов'язані з логікою. Дійсно, з точки зору класичної логіки висловлювання може бути істинним (наприклад, Київ - столиця України) або хибним (наприклад, Волга впадає у Чорне море)."Істина" позначається через 1, "хибність" - через 0.

Мета курсової роботи – вивчити основні теоретичні положення теорії булевих функцій, розглянути спеціальні форми зображення мулевих функцій у алгебрі Буля.

Об’єкт дослідження – алгебра Буля.

Методи дослідження – теоретичний аналіз наукової літератури з проблеми, аналіз навчальних програм, підручників.

Завдання дослідження:

1. Означити основні поняття теорії булевих функцій, проілюструвати їх на прикладах і навести зразки задач,які зводяться до встановлення тих чи інших властивостей булевих функцій.

2. Дати означення алгебри Буля та розглянути спеціальні форми зображення булевих функцій у цій алгебрі.

3. Дослідити історичні аспекти розвитку теорії булевих функцій.

Розділ I.Булеві функції

1.1.Основні поняття та означення

Булева функція – це функція ƒ(), область значень якої складається з 0 та 1, і яка залежить від змінних , що приймають також лише ці два значення.

Множину всіх булевих функцій позначають . Булеву функцію від n змінних називають n-місною. Областю її визначення є множина можливих n-місних наборів значень змінних. Ці набори називають двійковими наборами(або наборами). Отже, область визначення n-місної булевої функції є скінченною і складається з наборів значень змінних. Набір (,…,) позначають або .

Норма набору - це число =, яке дорівнює кількості його одиничних компонент.

Віддаль Хемінга між наборами та - це число . Це число рівне кількості компонент, у яких набори та відрізняються. Ці набори називаються сусідніми, якщо та протилежними, якщо .Отже, сусідні набори відрізняються в одній компоненті, а протилежні – в усіх n компонентах. Наприклад, набори (0001) і (0011) – сусідні, а (0001) і (1110) – протилежні.

Скінченність області визначення довільної булевої функції дає змогу задавати таку функцію таблицею. Всі набори значень змінних розташуємо у стовпчик у лексикографічному порядку і вкажемо значення функції на кожному з них. Матимемо таблицю булевої функції (див.табл.1).

Стовпчик значень функції (права частина таблиці) складається з нулів та одиниць. Отже, n-місних булевих функцій існує стільки, скільки існує наборів довжини з 0 та 1.

Таблиця 1

ƒ()

0 0 . . . 0 0

0 0 . . . 0 1

0 0 . . . 1 0

……………

1 1 . . . 1 1

ƒ(0,0,…,0,0)

ƒ(0,0,…,0,1)

ƒ(0,0,…,1,0)

……………

ƒ(1,1,…,1,1)

Теорема1. Кількість всіх функцій з , які залежать від n змінних , дорівнює 2.

Множину наборів значень змінних, на яких булева функція ƒ() приймає значення 1, позначають :

= {‌‌‌‌‌│‌‌‌ , ƒ ()=1}.

Множина повністю визначає функцію ƒ.

Змінна функції ƒ() називається істотною, якщо існує такий набір () значень решти змінних, що

ƒ(

)ƒ().

Змінна, яка не є істотна називається неістотною(фіктивною). Отже, змінна функції ƒ() неістотна, якщо

ƒ(

)=ƒ()

для довільних значень решти змінних. Це означає, що зміна значення в довільному наборі значень не змінює значення функції. У цьому випадку функція ƒ() по суті залежить від змінної, тобто є функцією . У такому разі кажуть, що функція отримана із функції вилученням фіктивної змінної, а функція отримана із уведенням фіктивної змінної.

Функції та називають рівними, якщо функцію можна отримати з шляхом уведення або вилучення фіктивних змінних.

1.2.Поняття формули

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

Нехай L – множина функцій від m змінних, . Кожну функцію ƒ() із L називають формулою алгебри логіки.

Нехай ƒ() – функція з L і є формулами, тоді вираз теж називають формулою.

При побудові формул використовують символи(знаки) трьох категорій:

- символи змінних x,y,z,a,b,c,….;

- символи логічних операцій ;

- пари символів ,- дужки.

На практиці дужки розділяють на внутрішні і зовнішні. Наприклад, формула F=AB без дужок не є формулою. Проте для скорочення запису зовнішні дужки часто пропускають, тому цей вираз означає формулу. Для спрощення запису також змінюють дужки на дужки одного вигляду .

Приклади формул. Нехай L – множина елементарних функцій. Такі вирази є формулами:

- ;

- ,

а наступні виразами не є формулами:

- – незакриті дужки;

- - відсутній символ.

1.3.Реалізація функцій формулами

Нехай F – довільна формула. Тоді формули,що використовувалися для її утворення, називають під формулами формули F.

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

Розглянемо формулу яка випливає з заміною на . У цьому випадку формула має ту ж структуру, що і формула F.

Якщо формула F() описує функцію ƒ(), тобто формула F є формулою для змінних , де , то вважають, що формулі F() відповідає функція ƒ(), а формулі F зіставлена функція ƒ. Якщо функція ƒ відповідає формулі F, то вважають також, що формула F реалізує функцію ƒ. Оскільки функції розглядають з точністю до фіктивних змінних , вважаємо , що формула F реалізує будь-яку функцію рівну ƒ.

Якщо функція ƒ(), що реалізується формулою F(), має неістотну змінну , то змінну можна вилучити, замінивши функцію ƒ рівною їй функцією , а формулу F – формулою , яка випливає з F завдяки ототожненню змінної з будь-якою зі змінних, що залишилися.

Очевидно, формула є формулою, що реалізує функцію .

1.4.Принцип суперпозиції

Суперпозицією функцій з множини функцій називають функцію ƒ, яка відповідає формулі F, а процес отримання функції з множини функцій називають операцією суперпозиції.

Приклад. Функцію будують трьома кроками(див.талб.2):

- ;

- .

Таблиця 2


0	0	0	0	0
0	1	0	0	1
1	0	0	1	1
1	1	1	1	1

Функцію будують також за три кроки (див.табл.3):

- ;

- .

Таблиця 3


0	0	0	0	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	0
1	0	0	0	0	0
1	0	1	1	0	0
1	1	0	1	0	0
1	1	1	1	0	0

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

Принцип суперпозиції дає можливість на основі трьох основних елементарних функцій (заперечення, кон’юнкція, диз’юнкція) отримати складене логічне висловлення, яке описує функціонування цифрових систем і автоматів. Покажемо це стосовно операцій кон’юнкції, диз’юнкції та інверсії.

Якщо і - формули, то ,, , , - також формули.

При перетворенні формул використовують такі операції підстановки змінних і без повторної підстановки функцій:

- операцію підстановки змінних

яка дає змогу виконати підстановку змінних у функцію ƒ() і в результаті отримати функцію . Очевидно, підстановка змінних включає їх перейменування, перестановку і ототожнення;

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

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

1.5. Рівносильність формул

Формули і називаються рівносильними, якщо при будь-яких значеннях змінних , які входять у ці формули, вони набувають однакових значень.

Приклади.

- рівносильне ;

- рівносильне .

Між поняттями еквівалентності і рівносильності існує зв’язок: якщо формули і - рівносильні, то формула (еквівалентність) набуває значення істини при всіх значеннях змінних, і навпаки: якщо формула отримує значення істини при всіх значеннях змінних, то формули і - рівносильні.

При визначенні рівносильності двох формул не обов’язково передбачати, що вони містять одні і ті ж значення змінних.

Приклади важливих рівносильних формул:

- рівносильне ;

- рівносильне .

Розділ II. Алгебра Буля

2.1. Закони алгебри Буля

Булевою алгеброю називається алгебра , якщо складається з:

двох бінарних операцій – (або) і (і);
однієї унарної операції – (заперечення);
двох унарних операцій – 0(нуль) і 1(одиниця),

і для виконується така сукупність співвідношень :

- - комутативність;

- - асоціативність;

- - дистрибутивність;

- - закони для нуля, одиниці і заперечення.

Закони асоціативності:

Закони комутативності:

Дистрибутивний закон для кон’юнкції відносно диз’юнкції:

Дистрибутивний закон для диз’юнкції відносно кон’юнкції:

Закон подвійного заперечення:

Закони де Моргана:

Закони ідемпотентності:

Закони поглинання:

Співвідношення для констант:

Закон виключеного третього:

Закон протиріччя:

2.2. Диз’юнктивні нормальні форми

Спеціальними формами зображення булевих функцій в алгебрі Буля є диз’юнктивні нормальні форми і кон’юнктивні нормальні форми.

Введемо позначення - параметр, який дорівнює 0 або1. Очевидно, що

Зазначимо, що

Закріпимо множину змінних .

Елементарна кон’юнкція – це формула ,де змінні з множини Х, причому всі різні. Число r називають рангом кон’юнкції. У випадку r=0 кон’юнкцію називають порожньою і покладають рівною 0.

Приклад. Елементарними кон’юнкціями є 1, а формули 0,елементарними кон’юнкціями не є.

Елементарну кон’юнкцію, яка містить усі змінні з множини Х, називають конституентою одиниці. Тобто, конституента одиниці – це елементарна кон’юнкція рангу n. Легко побачити, що всіх різних конституент одиниці для фіксованої множини n змінних є стільки, скільки є двійкових наборів з n компонентами, тобто .

Диз’юнктивна нормальна форма (ДНФ) – диз’юнкція елементарних кон’юнкцій , у яких попарно різні.

Існує алгоритм, який дає можливість для будь-якої формули булевої алгебри тотожними перетвореннями знайти рівносильну їй диз’юнктивну нормальну форму.

На першому етапі цього алгоритму формулу перетворюють у рівносильну, побудовану зі змінних та їхніх заперечень за допомогою лише кон’юнкцій та диз’юнкцій (тобто заперечення можуть бути лише над змінними). Для цього використовують закони де Моргана і закон подвійного заперечення.

На другому етапі досягають, щоб усі кон’юнкції виконувались раніше диз’юнкцій, для цього розкривають дужки на основі дистрибутивного закону для кон’юнкції відносно диз’юнкції. Потім, на основі співвідношень для констант і закону протиріччя виключають нулі і, на основі законів ідемпотентності, об’єднують рівні члени. Цим процес побудови диз’юнктивної нормальної форми закінчують.

Приклад. Зведемо до диз’юнктивної нормальної форми.

Використовуючи алгоритм побудови диз’юнктивної нормальної форми, можемо записати

Досконала диз’юнктивна нормальна форма – це диз’юнктивна нормальна форма, у якої кожна елементарна кон’юнкція є конституентою одиниці.

Теорема. Будь-яку булеву функцію ƒ() можна єдиним способом зобразити в досконалій диз’юнктивній нормальній формі.

Доведення. Нехай задано деяку функцію ƒ(). Кожному двійковому набору =(,…,) значень змінних відповідає єдина конституента одиниці,яка перетворюється на цьому наборі в 1 і визначена так: . Усі інші конституанти одиниці на цьому наборі перетворюються в 0. Наприклад, набору 0101 відповідає конституанта .

Нехай - значення функції,яке вона приймає на -му двійковому наборі - конституанта одиниці, що відповідає -му набору. Доведемо рівність

ƒ(

)=.

Для го набору . Нульові члени в диз’юнкції можна опустити. Отже, диз’юнкція конституант одиниці, що відповідають усім двійковим наборам, на яких булева функція приймає значення 1, є ДДНФ функції ƒ():

ƒ(

)=.

Для доведення єдності ДДНФ знайдемо кількість ДДНФ від n змінних . Для цього будь-яким способом занумеруємо конституанти одиниці, їх . Кожній ДДНФ від змінних можна таким взаємно однозначним способом поставити у відповідність набір із нулів і одиниць. Компоненти з номерами конституант одиниці, які входять у ДДНФ, дорівнюють одиниці, а решта компонент – нулю. Нульовий набір при цьому не отримаємо, тому що він відповідав би порожній ДДНФ. Отже, різних ДДНФ буде стільки, скільки існує наборів довжини , відмінних від набору із самих лише нулів, тобто 2. Функцій (за виключенням тотожного нуля) від змінних також є 2. Кожну із цих функцій можна зобразити ДДНФ, отже, це зображення єдине.

Із доведення цієї теореми випливає, що для заданої таблично функції ДДНФ будують наступним способом. Для кожного набору, на якому функція приймає значення 1, будують відповідну цьому набору конституанту одиниці, диз’юнкція всіх цих конституант і є ДДНФ заданої функції.

Алгебра Буля 📙 Курсовая → 🆔 6270