Реферат Булеві функції
Булева функція(абологічна функція, абофункція алгебри логіки) відnзмінних — у дискретній математиці відображенняBn→B, деB= -бульова безліч. Елементи булева множини 1 і 0 зазвичай інтерпретують як логічні значення "істинно" і "хибно", хоча в загальному випадку вони розглядаються як формальні символи, що не несуть певного сенсу. Невід'ємне ціле числоnназивають арністю або місцевістю функції, у разіn= 0 булева функція перетворюється набулеву константу. Елементи декартового творуBnназиваютьбулевими векторами. Безліч всіх булевих функцій від будь-якого числа змінних часто позначаєтьсяP2, а відnзмінних -P2(n). Булеві функції названо так на прізвище математика Джорджа Буля.
1. Основні відомості
Кожна булева функція арностіnповністю визначається завданням своїх значень у своїй області визначення, тобто всіх булевих векторах довжиниn. Число таких векторів дорівнює 2n. Оскільки на кожному векторі булева функція може набувати значення або 0, або 1, то кількість всіхn-арних булевих функцій дорівнює 2 2n. Тому в цьому розділі розглядаються лише найпростіші та найважливіші булеві функції. Те, що кожна булева функція задається кінцевим масивом даних, дозволяє представляти їх у вигляді таблиць. Такі таблиці звуться таблиць істинності й у випадку мають вид:
Майже всі булеви функції малих арностей (0, 1, 2 і 3) склалися історично і мають конкретні імена. Якщо значення функції не залежить від однієї зі змінних (тобто строго кажучи для будь-яких двох булевих векторів, що відрізняються лише у значенні цієїзмінної, значення функції на них збігається), то ця змінна називаєтьсяфіктивною.
1.1. Нульарні функції
Приn= 0 кількість булевих функцій зводиться до двох 2 2 0 = 2 1 = 2, перша їх тотожно дорівнює 0, а друга 1. Їх називають булевими константами — тотожний нуль і тотожна одиниця.
1.2. Унарні функції
Приn= 1 число булевих функцій дорівнює 221=22=4. Визначення цих функцій міститься в наступній таблиці.
Таблиця значень булевих функцій від однієї змінної:
Назви булевих функцій від однієї змінної:
1.3. Бінарні функції
Приn= 2 число булевих функцій дорівнює 22² = 24 = 16.
Таблиця значень булевих функцій від двох змінних:
Назви булевих функцій від двох змінних:
1.4. Тернарні функції
Приn= 3 число булевих функцій дорівнює 2 2 ³ = 2 8 = 256. Деякі з них визначені в наступній таблиці:
Назви булевих функцій трьох змінних:
2. Повні системи булевих функцій
2.1. Суперпозиція та замкнуті класи функцій
Результат обчислення булевої функції може бути використаний як один з аргументів іншої функції. Результат такої операції суперпозиції можна розглядати як нову функцію булева зі своєю таблицею істинності. Наприклад, функції (суперпозиція кон'юнкції, диз'юнкції та двох заперечень) відповідатиме наступна таблиця:
Кажуть, що безліч функцій замкнено щодо операції суперпозиції, якщо будь-яка суперпозиція функцій з даної множини теж входить до цієї множини. Замкнуті множини функцій називають також замкнутими класами.
Як найпростіші приклади замкнутих класів булевих функцій можна назвати безлічx> , Що складається з однієї тотожної функції, або безліч, всі функції з якого тотожно дорівнюють нулю незалежно від своїх аргументів. Замкнуто також безліч функцій та безліч усіх унарних функцій. А ось об'єднання замкнутих класів може таким уже не бути. Наприклад, об'єднавши класи і ми за допомогою суперпозиції зможемо отримати константу 1, яка у вихідних класах була відсутня.
Зрозуміло, безлічP2 всіх можливих булевих функцій теж є замкнутим.
2.2. Тотожність та двоїстість
Дві булеві функції тотожні один одному, якщо на будь-яких однакових наборах аргументів вони набувають рівних значень. Тотожність функцій f і g можна записати, наприклад, так:
Переглянувши таблиці істинності булевих функцій, легко отримати такі тотожності:
А перевірка таблиць, побудованих для деяких суперпозицій, дасть такі результати:
(дистрибутивність кон'юнкції та диз'юнкції)
Функція називається двоїстою функцією, якщо . Легко показати, що у цій рівності f і g можна поміняти місцями, тобто функції f і g двояко один одному. З найпростіших функцій двоїсти один одному константи 0 і 1, та якщо з законів де Моргана слід двоїстість кон'юнкції і диз'юнкції. Тотожна функція, як і функція заперечення, двояка сама собі.
Якщо в булевому тотожності замінити кожну функцію двоїстою їй, знову вийде правильне тотожність. У наведених вище формулах легко знайти двоїсті один одному пари.
2.3. Повнота системи, критерій Поста
Система булевих функцій називаєтьсяповною, якщо можна побудувати їхню суперпозицію, тотожну будь-якої іншої заздалегідь заданої функції. Говорять ще, що замикання даної системи збігається збезліччюP2.
Американський математик Еміль Пост ввів у розгляд такі замкнуті класи булевих функцій:
- Функції, що зберігають константуT0 іT1;
- Самодвійні функціїS;
- Монотонні функціїM;
- Лінійні функціїL.
Їм було доведено, що будь-який замкнутий клас булевих функцій, що не збігається зP2 , цілком міститься в одному з цих п'яти так званихпредполных класів, але при цьому жоден з п'яти не міститься цілком у поєднанні чотирьох інших. Таким чином критерій Посту для повноти системи зводиться до з'ясування, чи не вся ця система повністю в одному з предполных класів. Якщо для кожного класу в системі знайдеться функція, що не входить до нього, то така система буде повною, і за допомогою функцій, що входять до неї, можна буде отримати будь-яку іншу булеву функцію.
Зауважимо, що існують функції, що не входять до жодного з класів Посту. Будь-яка така функція сама собою утворює повну систему. Як приклади можна назвати штрих Шеффера або стрілку Пірса.
3. Подання булевих функцій
Теорема Посту відкриває шлях до представлення булевих функцій синтаксичним способом, який у ряді випадків виявляється набагато зручнішим за таблиці істинності. Відправною точкою тут служить знаходження певної повної системи функцій. Тоді кожна булева функція може бути представлена деяким термом в сигнатурі Σ , який у разі називають також формулою. Щодо обраної системи функцій корисно знати відповіді такі питання:
- Як побудувати за цією функцією формулу, що її представляє?
- Як перевірити, що дві різні формули еквівалентні, тобто задають одну й ту самуфункцію?
- Зокрема: чи існує спосіб приведення довільної формули до еквівалентної її канонічної форми, такий що, дві формули еквівалентні тоді і тільки тоді, коли їх канонічні форми збігаються?
Позитивні відповіді ці та інші питання істотно збільшують прикладне значення обраної системи функцій.
3.1. Диз'юнктивна нормальна форма (ДНФ)
Простий кон'юнкцієюабокон'юнктомназивається кон'юнкція деякого кінцевого набору змінних або їх заперечень, причому кожна змінна зустрічається не більше одного разу.Диз'юнктивною нормальною формоюабоДНФназивається диз'юнкцією простих кон'юнкцій. Елементарна кон'юнкція
- правильна, якщо до неї кожна змінна входить не більше одного разу (включаючи заперечення);
- повна, якщо до неї кожна змінна (або її заперечення) входить рівно 1 раз;
- монотонна, якщо вона не містить заперечень змінних.
Наприклад, є ДНФ.
Здійсненою диз'юнктивною нормальною формоюабоСДНФщодо деякого заданого кінцевого набору змінних називається така ДНФ, у якої в кожну кон'юнкцію входять всі змінні даного набору, причому в тому самому порядку. Наприклад: .
Легко переконатися, що кожній булевій функції відповідає деяка ДНФ, а функції, яка відрізняється від тотожного нуля, — навіть СДНФ. Для цього достатньо в таблиці істинності цієї функції знайти всі булеві вектори, на яких значення дорівнює 1, і для кожного такого вектора побудувати кон'юнкцію , де . Диз'юнкціяцих кон'юнкцій є СДНФ вихідної функції, оскільки всіх булевих векторах її значення збігаються зі значеннями вихідної функції. Наприклад, для імплікації результатом є те, що можна спростити до .
3.2. Кон'юнктивна нормальна форма (КНФ)
Кон'юнктивна нормальна форма1(КНФ) визначається подвійно до ДНФ.Простою диз'юнкцієюабодиз'юнктомназивається диз'юнкція однієї або декількох змінних або їх заперечень, причому кожна змінна входить до неї не більше одного разу. КНФ це кон'юнкція простих диз'юнкцій.
Довершеної кон'юнктивної нормальної формою(СКНФ), щодо деякого заданого кінцевого набору змінних, називається така КНФ, у якої в кожну диз'юнкцію входять всі змінні даного набору, причому в тому самому порядку. Оскільки (С)КНФ та (С)ДНФ взаємодвійні, властивості (С)КНФ повторюють всі властивості (С)ДНФ, грубо кажучи, «з точністю до навпаки».
КНФ може бути перетворена до еквівалентної їй ДНФ шляхом розкриття дужок за правилом:
яке виражає дистрибутивність кон'юнкції щодо диз'юнкції. Після цього необхідно в кожній кон'юнкції видалити змінні, що повторюються, або їх заперечення, а також викинути з диз'юнкції всі кон'юнкції, в яких зустрічається змінна разом зі своїм запереченням. При цьому результатом не обов'язково буде СДНФ, навіть якщо вихідна КНФ була СКНФ. Так само можна завжди перейти від ДНФ до КНФ. Для цього слід використовувати правило
що виражає дистрибутивність диз'юнкції щодо кон'юнкції. Результат слід перетворити описаним вище способом, замінивши слово «кон'юнкція» на «диз'юнкція» і навпаки.
3.3. Поліноми Жегалкіна
Поліном Жегалкіна це форма представлення логічної функції за допомогою функціїЖегалкіна (Виключає АБО). Для отримання полінома Жегалкіна слід виконати такі дії:
- Отримати ДНФ функції
- Все АБО замінити на Виключне АБО
- У всіх термах замінити елементи із запереченням на конструкцію: («елемент» «що виключає АБО» 1)
- Розкрити дужки за правилами алгебри Жегалкіна і привести попарно однакові терми
Література
- Гаврилов Г. П., Сапоженко А. А.Збірник завдань з дискретної математики. - М.: Наука, 1969.
- Кузнєцов О. П., Адельсон-Вельський Г. М.Дискретна математика для інженера. - М.: "Енергія", 1980. - 344 с.
- Марченко С. С.Замкнуті класи булевих функцій. - М.: Фізматліт, 2000.
- Яблонський С. В.Введення в дискретну математику. - М.: Наука, 1986.
- Алексєєв В. Б. Дискретна математика (курс лекцій, ІІ семестр). Упоряд. А. Д. Поспєлов