Алгебра Буля

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

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

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

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

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

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

                                                                 студентка 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

 

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

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

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

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

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

ƒ(

) ƒ( ).

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

ƒ(

)=ƒ( )

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

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

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

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

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

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

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

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

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

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

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

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

- ;

- ,

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

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

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

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

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

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

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

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

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

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

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

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

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

- ;

- ;

- . 
 
 

  Таблиця  2