Розкладання булевих функцій за змінними. Розкладання булевої функції за змінними Теорема про розкладання булевої функції

Поділіться роботою у соціальних мережах

Якщо ця робота Вам не підійшла внизу сторінки, є список схожих робіт. Також Ви можете скористатися кнопкою пошук

аранів Віктор Павлович. Дискретна математика.

Розділ 4. Функціональні системи із операціями. Алгебра логіки.

Лекція 21. Принцип двоїстості. Розкладання функцій змінних. Вчинені ДНФ та КНФ

лекція 21. ПРИНЦИП ПОДВІЙНОСТІ. РОЗКЛАДАННЯ БУЛЬОВИХ

ФУНКЦІЙ ЗА ЗМІННИМИ. ДОСЛІДНІ ДИЗ'ЮНКТИВНА І

КОН'ЮНКТИВНА НОРМАЛЬНІ ФОРМИ

План лекції:

Принцип двоїстості.
Розкладання булевих функцій за змінними. Вчинені диз'юнктивна та кон'юнктивна нормальні форми.

Принцип двоїстості

Функція, рівна, називаєтьсядвоїстої функцією до функції.

Очевидно, що таблиця істинності для двоїстої функції виходить з таблиці істинності функції інвертуванням (тобто заміною 0 на 1 і 1 на 0) значень змінних і функції. Наприклад, .

Легко встановити для функцій 0, 1, що

функція 0 подвійна 1;
функція 1 подвійна 0;
функція подвійна;
функція подвійна;
функція подвійна;
функція двояка.

З визначення двоїстості випливає, що

тобто функція є двоїстою до (властивість взаємності).

Принцип двоїстості.Якщо формула реалізує функцію, то формула, тобто формула, отримана із заміною функцій відповідно на, реалізує функцію.

Формулу називатимемо формулою, двоїстою до.

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

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

Тоді

тобто функція виходить з результаті тієї ж самої підстановки змінних.

Доказ справедливості принципу двоїстості для кроку проведемо з прикладу. Нехай

Тоді

тобто функція виходить з і так само, як функція з в.

Принцип двоїстості дозволяє спростити висновок основних тавтологій цілий рядкорисних застосувань, що будуть розглянуті далі.

приклад 1. З тотожності випливає тотожність.

Справді,

;; .

приклад 2. Побудова формули для заперечення функції.

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

Отримуємо таке правило:нехай Формула реалізує функцію. Щоб отримати формулу для функції, потрібно у формулі замінити всі змінні на їх заперечення.

Знайдемо заперечення функції.

Тому що.

Розкладання булевих функцій за змінними. Досконалі

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

Введемо позначення

де параметр, рівний або 0, або 1. Очевидно, що

Легко бачити, що 1 тоді і лише тоді, коли.

Теорема про розкладання функцій змінних. Кожну функцію алгебри логіки за будь-якого () можна представити в наступній формі:

, (1)

де диз'юнкція береться за всілякими наборами значень змінних.

Це уявлення називаєтьсярозкладанням функції змінних.

Доказ. Розглянемо довільний набір значень змінних і покажемо, що ліва та права частини співвідношення (1) приймають на ньому те саме значення. Ліва частинадає. Права |

Як наслідки з теореми розглянемо два спеціальні випадки розкладання.

Розкладання по змінній:

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

Розкладання по всіх змінних:

При тотожно не дорівнює 0 воно може бути перетворено:

В результаті остаточно отримаємо

. (2)

Таке розкладання називаєтьсядосконалою диз'юнктивною нормальною формою(досконалої д. н. ф.).

Безпосередньо до поняття досконалої д. н. ф. примикає така теорема.

Теорема. Кожна функція логіки алгебри може бути представлена формулою в базисі.

Доказ.1) Нехай. Тоді, очевидно,

Нехай тотожно не дорівнює 0. Тоді її можна подати формулою (2).

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

приклад 3. Знайти досконалу д. н. ф. для функції.

Досконала д. н. ф. є вираз типу П. Покажемо, що за тотожно не рівної 1 її можна подати у вигляді. Запишемо для двоїстої функції (очевидно не рівної тотожно 0) розкладання у вигляді досконалої д. н. ф.:

З принципу двоїстості випливає

Таким чином, отримуємо розкладання, яке називаєтьсядосконалою кон'юнктивною нормальною формою(досконалої к. н. ф.):

. (3)

приклад 4. Побудувати досконалу к. н. ф. для функції.

Маємо.

Інші схожі роботи, які можуть вас зацікавити.
200.		Нормальні форми логічних функцій	63.53 KB
	Нормальні форми логічних функцій Подання булевої функції у формі диз'юнкції кон'юнктивних термів конституент одиниці Ki 2.7 називається нормальною диз'юнктивною формою ДНФ цієї функції. містять точно по одній всі логічні змінні взяті з запереченнями або без них така форма подання функції називається досконалою диз'юнктивною нормальною формою СДНФ цієї функції. Як видно при складанні СДНФ функції потрібно скласти диз'юнкцію всіх мінтермів, при яких функція набуває значення 1.
9015.		МЕТОДИ МІНІМІЗАЦІЇ БУЛЬОВИХ ФУНКЦІЙ	81.74 KB
	ДНФ та схеми з ФЕ. Мінімізація булевих функцій на основі побудови тупикових ДНФ. Мінімізація булевих функцій на основі побудови тупикових ДНФ Скорочена тупикова та мінімальна ДНФ перебувають у наступному співвідношенні. Тупикова ДНФ виходить із скороченої шляхом видалення деяких членів.
9017.		ПРОБЛЕМА МІНІМІЗАЦІЇ БУЛЬОВИХ ФУНКЦІЙ. ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ	109.86 KB
	ДНФ та схеми з ФЕ. ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЯ План лекції: Поняття нормальної диз'юнктивної форми ДНФ. Концепція ДНФ. Вираз при де є елементарна кон'юнкція рангу називається диз'юнктивною нормальною формою ДНФ.
14731.		Розкладання сигналів у узагальнений ряд Фур'є по системам ортогональних функцій. Функції Уолша	38.95 KB
	Розкладання сигналів у узагальнений ряд Фур'є по системам ортогональних функцій. Ознайомити з основними характеристиками сигналів та перешкод. Вивчити уявлення сигналів як узагальненого ряду Фур'є по системам ортогональних функций. Розкладання сигналів у узагальнений ряд Фур'є по системам ортогональних функцій.
6707.		Проектування реляційних баз даних. Проблеми проектування у класичному підході. Принципи нормалізації, нормальні форми	70.48 KB
	Що таке проект реляційної базиданих Це набір взаємопов'язаних відносин, в яких визначено всі атрибути, задані первинні ключі відносин і задані ще деякі. додаткові властивостівідносин, які відносяться до принципів підтримки цілісності. Тому проект бази даних має бути дуже точним та вивіреним. Фактично проект бази даних є фундаментом майбутнього програмного комплексу, який буде використовуватися досить довго і багатьма користувачами.
4849.		Форми та методи здійснення функцій держави	197.3 KB
	Термін «функція» має у вітчизняній та зарубіжній науковій літературі далеко не однакове значення. У філософському та загальносоціологічному плані він розглядається як «зовнішній прояв властивостей будь-якого об'єкта в даній системі відносин»; як сукупність звичайних або специфічних дій окремих осіб чи органів
1790.		Розкладання на доданки	180.15 KB
	Саме слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли лише правила виконання чотирьох арифметичних дій над багатоцифровими числами.
2690.		Вивчення працездатності свердел зі змінним кроком гвинтової лінії	18.85 KB
	Моделі процесу різання можуть бути представлені системою математичних рівнянь, що визначають у кожному конкретному випадку оцінну функцію або критерії працездатності різальних інструментів, а також технічні обмеження з кінематики верстата, жорсткості різальних інструментів та в цілому технологічної системи.
17088.		КРИМІНАЛЬНА ВІДПОВІДАЛЬНІСТЬ ЗА ЗЛОЧИНИ, ВЧЕНІ У СКЛАДІ ОРГАНІЗОВАНОЇ ЗЛОЧИННОЇ ГРУПИ	50.97 KB
	Ломтєв ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ Актуальність теми дослідження обумовлюється потребою в подальший розвитокта вдосконаленні теорії та практики реалізації кримінальної відповідальності за злочини, що скоюються у складі організованої злочинної групи. Дослідження у сфері протидії організованій злочинності показують що саме у складі організованих злочинних груп відбуваються найбільш небезпечні злочини, що важко розкриваються. У рамках вирішення завдання підвищення ефективності кримінального закону щодо боротьби з...
11576.		Поняття, види та форми угод. Наслідки недотримання необхідної форми угод	49.82 KB
	Визнання правочину недійсним видом недійсного правочину. Прикладна цінність курсової роботи полягає у спрощенні поняття угоди тобто громадського його подання у доступнішій формі.

Позначимо через . Тоді

x s=

Зокрема, тоді і лише тоді, коли .

За допомогою “ статечної функції” будь-яку булеву функцію можна уявити у вигляді:

званому розкладанням булевої функції по змінній.

Справді, якщо , то , і

Якщо , то , і

приклад 4.

Розкладемо функцію по змінній. Для цього спочатку побудуємо таблицю функції:

З таблиці видно, як і .

Використовуючи формулу розкладання по змінній, знаходимо

Приклад 5.

Розкладемо функцію з прикладу 4 за всіма змінними. Так як функція набуває значення 1 на трьох наборах: , то згідно з слідством з теореми про розкладання, маємо

Визначення 3.

Розкладання булевої функції по всіх змінних у вигляді

називається досконалою диз'юнктивною нормальною формою(СДНФ).

Приклад 6.

- СДНФ для функції (див. приклад 5).

Теорема 2.

Будь-яка булева функція (крім 0) має єдину СДНФ.

Доказ.Відповідно до слідства з теореми про розкладання

Зауваження.Якщо під диз'юнкцією одного доданка розуміти саме це доданок, то диз'юнкції нуля доданків немає, тому немає СДНФ для функції 0.

При побудові СДНФ має місце таке

Правило одиниці. набуває значення 1; для кожного такого набору в СДНФ робиться заготівля доданку . Якщо в даному наборіаргументів , то над змінною в заготовленому доданку навішується заперечення: .

Теорема 3.

Будь-яка булева функція може бути виражена через диз'юнкцію, кон'юнкцію та заперечення:

Доказ.

Якщо , то . Якщо , то

Теорема 4.

Будь-яка булева функція (крім 1) може бути єдиним чином виражена у вигляді досконалої кон'юнктивної нормальної форми (СКНФ):

Доказ.

Якщо , то і

Застосувавши до останньої тотожності принцип двоїстості, знаходимо

При побудові СКНФ має місце таке

Правило нуля.Розглядаються лише набори аргументів, у яких функція набуває значення 0; для кожного такого набору в СКНФ робиться заготівля співмножника. Якщо в цьому наборі аргументів, то над змінною в заготовленому співмножнику навішується заперечення: .

Приклад 7.

Побудуємо функцію для імплікації: . Імплікація набуває значення 0 на одному наборі:

Так як в цьому наборі і , то за правилом нуля отримуємо

Отже, - потрібна функція для імплікації.

Повнота системи

Визначення 4.Система функцій ( f 1 , f 2 , ..., f s , ...)Ì P 2 називається повною в Р 2 , якщо будь-яка функція f(x 1 , ..., x n) Î P 2 може бути записана у вигляді формули через функції системи.

Повні системи

1. P 2 – повна система.

2. Система M={x 1 &x 2 , x 1 Ú x 2 , ) - повна система, т.к. Будь-яка функція алгебри логіки може бути записана у вигляді формули через ці функції.

Приклад 8.Неповні системи: ( }, {0,1}.

Лемма(достатня умова повноти)

Нехай система U = {f 1 , f 2 , ..., f s, ...) повна в Р 2 . Нехай B = {g 1 , g 2 , ..., g k, ...) – деяка система з Р 2 , причому будь-яка функція f i Î Uможе бути виражена формулою над Bтоді система Bповна в Р 2 .

7. Система ( x 1 &x 2 , x 1 Å x 2 , 0, 1) повна в Р 2 , U = {x 1 &x 2 , }, = x 1 Å1.

Поліном Жегалкіна

f(x 1 , ..., x n) Î P 2 , представимо її у вигляді формули через кон'юнкцію та суму за модулем два, використовуючи числа 0 і 1. Це можна зробити, так як ( x 1 &x 2 , x 1 Å x 2 , 0, 1) повна в Р 2 . З огляду на властивості x & (yÅ z) = xy Å xzможна розкрити всі дужки, привести подібні члени, і вийде поліном від nзмінних, що складається з членів виду х х ...х, з'єднаних знаком Å. Такий поліном називається поліномом Жегалкіна.

Загальний вигляд полінома Жегалкіна:

де , s = 0, 1, ..., n, причому при s= 0 отримуємо вільний член а 0 .

Подання функції у вигляді полінома Жегалкіна

1. Представимо будь-яку функцію формулою над ( x 1 &x 2 , ) і зробимо заміну = xÅ1. Цей спосіб зручний, якщо функція задана формулою.

Приклад 9. (x 1 (x 2 x 3))(x 1 Ú x 2) x 3 = (x 1 Ú x 2 Ú x 3)(x 1 Ú x 2) x 3 = (`x 1 x 2 Ú x 1 x 3 Ú x 1 x 2 Ú x 2 Ú x 2 x 3)x 3 = (`x 1 x 3 Ú x 2)x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3 Å1) x 2 Å1) x 3 = x 1 x 2 x 3 Å x 2 x 3 Å x 3 .

Треба пам'ятати, що парне число однакових доданків у сумі по mod 2 дає 0.

2. Метод невизначених коефіцієнтів. Він зручний, якщо функція задано таблицею.

Приклад 10.

Запишемо з невизначеними коефіцієнтами поліном Жегалкіна для функції трьох змінних f(x 1 , x 2 , x 3) = (01101001) = а 0 Å а 1 х 1 Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Å b 3 x 1 x 3 Å cx 1 x 2 x 3 . Потім знаходимо коефіцієнти, використовуючи значення функції всіх наборах. На наборі (0, 0, 0) f(0, 0, 0) = 0, з іншого боку, підставивши цей набір у поліном, отримаємо f(0, 0, 0) = а 0 , звідси а 0 = 0. f(0, 0, 1) = 1, підставивши набір (0, 0, 1) у поліном, отримаємо: f(0, 0, 1) = а 0 Å а 3, т.к. а 0 = 0, звідси а 3 = 1. Аналогічно, f(0, 1, 0) = 1 = а 2 , f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 , b 3 = 0; 0 = а 1 Å а 2 Å b 1 , b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c= 0; тоді поліном Жегалкіна для цієї функції набуде вигляду: f(x 1 , x 2 , x 3) = x 1 Å x 2 Å x 3 .

Багаточлен Жегалкіна можна отримати також за допомогою трикутника Паскаля по одиницях його лівої сторони по таблиці в такий спосіб. Побудуємо багаточлен Жегалкіна для функції f= (10011110). Верхня сторона трикутника є функцією f. Будь-який інший елемент трикутника є сумою по модулю для двох сусідніх елементів попереднього рядка. Ліва сторона трикутника для функції fмістить шість одиниць. Багаточлен Жегалкіна міститиме шість доданків. Перша одиниця трикутника відповідає набору (000). Перше складова багаточлена є 1. Третя знизу одиниця в лівій стороні трикутника відповідає набору (101). Як складник багаточлена беремо x 1 x 3 . Аналогічно інших одиниць трикутника. Зліва від наборів показані складові багаточлена Жегалкіна.

Теорема Жегалкіна

Кожна функція може бути представлена у вигляді полінома Жегалкіна єдиним чином.

Тут єдиність розуміється з точністю до порядку доданків у сумі та порядку співмножників у кон'юнкціях:

, s = 0, 1, ..., n.

Доказ.

Будь-яка функція з Р 2 може бути представлена формулою над ( x 1 & x 2 , x 1 Å x 2 , 0, 1), а ця формула після розкриття всіх дужок та приведення подібних членів дає поліном Жегалкіна. Доведемо єдиність уявлення. Розглянемо функції f(x 1 , ..., x n) від nзмінних. Ми знаємо, що таких функцій, тобто. їх таблиць істинності, 2 n. Підрахуємо кількість різних поліномів Жегалкіна від nзмінних, тобто. кількість варіацій виду: . Число наборів дорівнює числу всіх підмножин множини ( x 1 , ..., x n), сюди входить і порожня безліч (якщо s= 0). Число підмножин множини з n елементів дорівнює 2 n, Оскільки кожен набір входить з коефіцієнтом , що приймає два значення: 0 або 1, то число всіляких поліномів буде . Оскільки кожному поліному відповідає єдина функція, число функцій від nзмінних дорівнює числу поліномів, то кожній функції відповідатиме єдиний поліном.

Визначення.

Функція f(x 1 , ..., x n), поліном Жегалкіна для якої має наступний лінійний щодо змінних вигляд: f = а 0 Å а 1 х 1 Å а 2 х 2 Å ... Å а n х nназивається лінійною.

Лемма про нелінійну функцію .

Суперпозицією нелінійної функції, заперечення та константи 1 можна отримати кон'юнкцію.

Доказ.

Нехай f(x 1 , ..., x n) – нелінійна функція. Тоді поліном Жегалкіна містить для неї доданок, в якому присутній твір x i x j. Вважатимемо для простоти, що x 1 x 2 у багаточлені Жегалкіна є цим твором. Зробивши угруповання доданків, функцію fпредставимо у вигляді

Функція h 0 не є тотожний нуль, інакше в поліномі Жегалкіна відсутній доданок з твором x 1 x 2 . Тоді існує набір ( a 3 , …, a n) з 0 та 1, для якого h 0 (a 3 , …, a n) = 1. Нехай h 1 (a 3 , …, a n) = a, h 2 (a 3 , …, a n) = b, h 3 (a 3 , …, a n) = c. Тоді

Побудуємо функцію:

Де d = ab Å c. Якщо d= 0, то h(x 1 , x 2) = x 1 x 2 . Якщо d= 1, то h(x 1 , x 2) = x 1 x 2 Å 1 і тоді Лемма доведена.

Функція f(x 1 , ..., x n) зберігає константу aÎ (0, 1), якщо f(a, …, a) = a.

Приклад 11.

Функція xyзберігає 0, зберігає 1. Функція x® yзберігає 1 та не зберігає 0.

Мінімізація булевих функцій

Мінімізація нормальних форм

Мінімальної ДНФ (МДНФ)функції f(x 1 , ... ,x n) називається ДНФ, що реалізує функцію fта містить мінімальну кількість символів змінних у порівнянні з усіма іншими видами ДНФ, що реалізують функцію f.

Якщо для будь-якого набору = ( a 1 , ..., a n) значень змінних умова g()=1 тягне , то функція gназивається частиною функції f(або функція fнакриває функцію g). Якщо при цьому для деякого набору = ( c 1 , ..., c n) функція g()=1, то кажуть, що функція gнакриває одиницю функції fна наборі (або що gнакриває конституенту одиниці функції f). Зауважимо, що конституант одиниці функції fє частина функції f, що накриває єдину одиницю функції f.

Елементарна кон'юнкція Kназивається імплікантом функції fякщо для будь-якого набору =( a 1 , ..., a n) з 0 та 1 умова K()=1 тягне f()=1.

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

Зрозуміло, що будь-який імплікант функції fє частина функції f.

Теорема 5.

Будь-яка функція реалізується диз'юнкцією всіх своїх найпростіших імлікантів (ПІ).

Отже, f = A. Теорему доведено.

Скорочена ДНФфункції fє диз'юнкція всіх простих імплікант функції f. Будь-яка функція fреалізується своєю скороченою ДНФ. Для будь-якої функції, що не дорівнює тотожному нулю, існує єдина скорочена ДНФ.

Нехай Aі B- Довільні формули. З властивостей булевих операцій випливають такі оборотні правила перетворення ДНФ:

1) - Повне склеювання (розгортання);

2) - неповне склеювання;

3) - узагальнене склеювання;

4) - Поглинання;

5) - ідемпотентність (видалення дублюючих членів).

Теорема Квайна. Якщо в СДНФ функції fпровести всі операції неповного склеювання, а потім усі операції поглинання та видалення дублюючих членів, то в результаті вийде скорочення ДНФ функції f.

Доказ.

Нехай маємо скорочену ДНФ функції f. Проведемо всі операції розгортання до кожного простого імпліканта для отримання відсутніх змінних у кожному диз'юнктивному доданку скороченої ДНФ. В отриманому виразі з декількох однакових диз'юнктивних доданків залишимо лише по одному екземпляру. В результаті отримаємо СДНФ функції f. Тепер, виходячи з отриманої СДНФ, у зворотному порядку проведемо операції додавання однакових диз'юнктивних доданків (за допомогою правил ідемпотентності), неповного склеювання та поглинання. У результаті отримаємо вихідну скорочену ДНФ.

Безліч В, на якому визначено дві бінарні операції (кон'юнкція та диз'юнкція) та одна унарна операція (заперечення) та виділено два елементи 0 та 1 називається булевою алгеброю.

Причому цих операцій необхідне виконання таких свойств:

Асоціативність

Комутативність

Дистрибутивність кон'юнкції щодо диз'юнкції

Дистрибутивність диз'юнкції щодо кон'юнкції

Ідемопотентність

Подвійне заперечення

Властивості констант

Правила де Моргана

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

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

У алгебрі логіки ці закони називаються рівносильностями.

Досконалі нормальні форми

Досконала диз'юнктивна нормальна форма

Введемо позначення:

; А А = 1; Х А = 1, якщо Х = А, Х А = 0, якщо ХА.

Формула Х А 1…… Х А n , де А=- якийсь двійковий набір, серед змінних Хi може бути збігаються називається елементарної кон'юнкцією.

Будь-яка диз'юнкція елементарних кон'юнкцій називається нормальною диз'юнктивною формою (ДНФ).

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

Наприклад: 1) (значок кон'юнкції у разі опущений).

1), 4) - правильні елементарні кон'юнкції;

2)- змінна х входить один раз сама і вдруге під знаком заперечення;

Змінна y входить тричі: один раз сама і двічі під знаком заперечення.

Правильна елементарна кон'юнкція називається повною щодо змінних х 1 .

Наприклад: із перелічених у попередньому прикладі кон'юнкцій повною є тільки 4) щодо змінних x,y,z t; а щодо змінних x,y,z повноїє лише 1).

Досконала диз'юнктивна нормальна форма (СДНФ) щодо змінних х 1 …..х n називається диз'юнктивна нормальна форма, в якій немає однакових елементарних кон'юнкцій і всі елементарні кон'юнкції правильні і повні щодо змінних х 1 …..х n

Розкладання по змінним

Теорема 1. Будь-яка логічна функція може бути представлена в СДНФ:

де m, а диз'юнкція береться за всіма 2 m наборами значень змінних х 1, ... х m. Функція f розкладена за першими n-змінними. Ця рівність називається розкладанням по змінним. х 1, ... х m. Наприклад, при n=4, m=2 розкладання має вигляд:

теорема доводиться підстановкою обидві частини рівності (1) довільного набору (b 1 ,…,b m , b m+1 ,…,b n) всіх n-змінних.

При m = 1 із (1) отримуємо розкладання функції по одній змінній:

Очевидно, що аналогічне розкладання справедливе для будь-якої з n-змінних.

Інший важливий випадок, коли n=m. При цьому всі змінні у правій частині (1) отримують фіксовані значення і функції кон'юнкції правої частини стають рівними 0 або 1, що дає:

де диз'юнкція береться за всіма наборами (b 1 … b n), у яких f=1. При f=0 безліч кон'юнкцій у правій частині порожньо. Таке розкладання називається досконалою диз'юнктивною нормальною формою. СДНФ функції f містить рівно стільки кон'юнкцій, скільки одиниць виходить у таблиці істинності f. Кожному одиничному набору (b 1, ..., b n) відповідає кон'юнкція всіх змінних, в якій x i взято з запереченням, якщо b i = 0 b і без заперечення, якщо b i = 1. Таким чином, існує взаємно однозначна відповідність між таблицею істинності функції f та її СДНФ, і, отже, СДНФ для будь-якої логічної функції єдина. Єдина функція не має СДНФ – це константа 0.

Теорема 2. Будь-яка логічна функція може бути представлена у вигляді булевої формули.

Дійсно, для будь-якої функції, крім константи 0, таким поданням може служити СДНФ. Константу 0 можна уявити булевою формулою.

Розклад Шеннона Розглянемо розкладання булевої функції f (x 1, x 2, . . . , xn) по змінній xi. Розкладання Шеннона: f (x 1, x 2, . . . , xn) = xi f (x 1, . . . , xi 1, 1, xi+1, . . . . Доказ (не благаючи спільності, для i = 1). Якщо x 1 = 0, то f(0, x 2, . . . , xn) = 0 f (1, x 2, . . . , xn) 1 f(0, x 2, . . . , xn) = f (0, x 2, . . . , xn). Якщо x 1 = 1, то f(1, x 2, . . . , xn) = 1 f(1, x 2, . . . , xn) 0 f(1, x 2, . . . , xn) = f(0, x 2, . . . , xn). ЧТД Приклад. Булеву функцію f (x, y, z) = x y / y z розкладемо по змінній z: f (x, y, z) = z (x y / y 1) z (x y / y 0) = [за властивостями 0 і 1 ] = z z (x y / y). Співмножник f (x 1, . . . , xi -1, 1, xi+1, . . . , xn) у формулі Шеннона називається коефіцієнтом розкладання функції f (x 1, x 2, . . . , xn) по змінній xi при xi, а співмножник f (x 1, . . . , xi -1, 0, xi+1, . . . , xn) - коефіцієнтом розкладання функції f (x 1, x 2, . . при xi. приклад. f(x, y, z) = xy/y = y(x1/0) y(x0/1). x 1 / 0 - коефіцієнт розкладання функції f (x, y, z) по y при y; x 0 / 1 - коефіцієнт розкладання функції f (x, y, z) по y при y.

Розкладання функції по k змінним Доказ. Підставимо в ліву та праву частини рівності довільний набір a 1 a 2. . . an: Спростимо праву частину, розмірковуючи так. Неважко перевірити, що 1, якщо і тільки якщо ai = 0 = 1, 11 = 1, але 0 1 = 0 і 10 = 0), ci (справді: 0 тому кон'юнкція дорівнює одиниці лише в одному випадку, коли набори a 1 a 2. . сk і в якому сама звертається в одиницю.

Досконала диз'юнктивна нормальна форма (Рад. ДНФ) Застосувавши формулу розкладання булевої функції f (x 1, x 2, . . . , xn) по k змінним при k = n, отримаємо: Оскільки коефіцієнтами розкладання f (c 1, c 2, . . cn) у цій формулі є значення функції f (x 1, x 2, . . cn, можливі два випадки: якщо набір c 1 c 2. . . cn M 0 (f), то f (c 1, c 2, . . . , cn) = 0 і тому звертається в 0 відповідне доданок правої частини; якщо набір c1c2. . cn M 1 (f), то f(c 1, c 2, . . . , cn) = 1 і доданок спрощується. В результаті маємо: Досконала диз'юнктивна нормальна форма булевої функції, або Рад. ДНФ - це формула виду:

Твердження про єдиність Рад. ДНФ Будь-яка функція булева, крім константи 0, представима досконалою диз'юнктивною нормальною формою, і вона єдина для даної функції. Алгоритм побудови Рад. ДНФ (по таблиці істинності) випливає з визначення Рад. ДНФ і полягає у циклічному виконанні наступного кроку: у векторі стовпці значень функції вибирається чергова 1 і за набором значень аргументів цього рядка формується кон'юнкція всіх аргументів з дотриманням наступного правила: якщо i-я компонента набору дорівнює 0, то змінна xi входить до кон'юнкції 0 (з інверсією), інакше у ступені 1 (без інверсії); отримана кон'юнкція додається у формулу як черговий доданок. приклад. Звернімо увагу на те, що нам вперше вдалося від табличного способу завдання функції перейти до формульного!

Твердження про єдиність Рад. КНФ Будь-яка функція булева, крім константи 1, представима досконалою кон'юнктивною нормальною формою, і вона єдина для даної функції. Алгоритм побудови Рад. КНФ за таблицею істинності випливає з визначення Рад. КНФ і полягає у циклічному виконанні наступного кроку: у векторі стовпці значень функції вибирається черговий 0 і за набором значень аргументів цього рядка формується диз'юнкція всіх аргументів з дотриманням наступного правила: якщо i-я компонента набору дорівнює 0, то змінна xi входить до диз'юнкції 1 (без інверсії), інакше у ступені 0 (з інверсією); отримана диз'юнкція додається в Рад. КНФ як черговий співмножник. приклад.

Елементарна кон'юнкція та ДНФ Розглянемо безліч змінних x 1, x 2, . . . , xn. Елементарною кон'юнкцією назвемо кон'юнкцію, куди кожна змінна входить трохи більше разу (з інверсією чи інверсії). приклади. x 1 x 2 x 3 x 4, x 1 x 2 x 4, x 3 – елементарні кон'юнкції, x 1 x 2 x 4, x 1 x 3 – неелементарні. Зокрема, 1 - це елементарна кон'юнкція, яка не містить жодної змінної. Число змінних, що утворюють елементарну кон'юнкцію, назвемо її рангом. приклад. Ранг елементарної кон'юнкції x 1 x 2 x 4 дорівнює трьом. Повною кон'юнкцією назвемо елементарну кон'юнкцію, що складається з усіх змінних, тобто кон'юнкцію рангу n. приклад. При n = 4 кон'юнкція x 1 x 2 x 3 x 4 – повна. Диз'юнктивною нормальною формою (ДНФ) назвемо диз'юнкцію різних елементарних кон'юнкцій. приклад. x 1 x 2 x 4 x 1 x 2 x 3 x 4 x 3 – ДНФ. Очевидно, що скоєна ДНФ є окремим випадком ДНФ. Довжиною ДНФ назвемо число кон'юнкцій у цій ДНФ. Рангом ДНФ назвемо суму рангів її кон'юнкцій. приклад. Довжина ДНФ із попереднього прикладу дорівнює трьом, а ранг – восьми.

Розкладання булевих функцій за змінними.

Нехай G - параметр, що дорівнює 0 або 1. Введемо позначення:

Перевіркою легко встановити, що x G = 1, тоді і лише тоді, коли x= G. Звідси випливає, що кон'юнкція дорівнює 1 (тут G дорівнює 0 або 1) тоді і тільки тоді, коли . Наприклад, кон'юнкція (у якій G 2 = G 1 = 0, G 3 = G 4 = 1) дорівнює 1 тільки у випадку, коли x 1 = x 2 = 0, x 3 = x 4 = 1.

Теорема 1Будь-яка булева функція f(x 1 ,x 2 ,...,x n) повинна бути представлена в наступній формі:

де 1 ≤ k ≤ n, у диз'юнкції береться за всіма наборами значень змінних.

Це уявлення зветься розкладання функції по змінним. Наприклад, при n = 4, k = 2 розкладання (3.1) має вигляд:

Доведемо справедливість розкладання (3.1). Для цього візьмемо довільний набір змінних значень . Покажемо, що ліва і права частини співвідношення (3.1) приймають при ньому те саме значення. Справді, оскільки x G = 1 тоді і лише тоді, коли x= G, то серед 2 До кон'юнкції правої частини (3.1) в одиницю звертається лише одна, в якій . Всі інші кон'юнкції дорівнюють нулю.

З цієї причини. Як наслідок з розкладання (3.1) отримуємо наступні два спеціальні розкладання.

Розкладання по змінній x n:

Якщо булева функція не є константа 0, то справедливе розкладання

Розкладання по всіх змінних:

, (3.3)

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

Розкладання (3.3) прийнято називати досконалою диз'юнктивною нормальною формою (скорочений запис СДНФ) функції.

Розкладання (3.3) дає спосіб побудови СДНФ. Для цього в таблиці істинності відзначаємо всі рядки , в яких . Для кожного такого рядка утворюємо кон'юнкцію і потім усі отримані кон'юнкції з'єднуємо знаком диз'юнкції.

Τᴀᴋᴎᴎᴀᴀᴈᴏᴍ, існує взаємно однозначна відповідність між таблицею істинності функції та її СДНФ. А це означає, що СДНФ для булевої функції єдина.

Єдина булева функція, яка має СДНФ, є константа 0.

Приклад 1Знайти досконалу диз'юнктивну форму для функції .

Складемо таблицю істинності для цієї функції:

Звідси отримуємо: = = .

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

Теорема 2Будь-яка булева функція має бути представлена в наступній формі:

де 1≤k≤n, а кон'юнкція береться за всіма 2 k наборами значень змінних.

Справді, нехай - Довільний набір значень змінних. Покажемо, що ліва і права частини співвідношення (3.4) приймають при ньому те саме значення. Оскільки тільки тоді, коли , то серед 2 k диз'юнкцій правої частини (3.4) у 0 звертається лише одна, в якій . Всі інші диз'юнкції дорівнюють 1.

З цієї причини = = .

Безпосередньо з розкладання (3.4) випливають розкладання булевих функцій:

Останнє розкладання зветься досконалої кон'юнктивної нормальної форми (СКНФ). Розкладання (3.6) дає спосіб побудови СКНФ. Для цього в таблиці істинності відзначаємо всі рядки, в яких. Для кожного такого рядка утворюємо диз'юнкцію і потім усі отримані кон'юнкції з'єднуємо знаком кон'юнкції. Τᴀᴋᴎᴎᴀᴀᴈᴏᴍ, існує взаємно однозначна відповідність між таблицею істинності функції та її СКНФ. А це означає, що СКНФ для булевої функції єдина.

Єдина булева функція, яка має СКНФ, є константа 1.

Приклад 2Знайти досконалу кон'юнктивну нормальну форму для функції .

Складемо таблицю істинності цієї функції.

Звідси отримуємо СКНФ

Формула виду (короткий запис), де - Кон'юнкції прийнято називати диз'юнктивною нормальною формою (ДНФ).

З наведеного визначення ДНФ будуть, наприклад, висловлювання: , .

Як зазначено в пункті 2.2, всі логічні операції можна звести до трьох: кон'юнкції, диз'юнкції та заперечення. Причому з огляду на закон де Моргана знак заперечення можна припускати віднесеним тільки до змінних.

Тепер, використовуючи дистрибутивний закон, розкриваємо дужки та отримуємо диз'юнктивну нормальну форму. Отже, справедлива така теорема.

Теорема 3 Для будь-якої алгебри формули логіки існує рівносильна їй диз'юнктивна нормальна форма.

Доказ цієї теореми дає спосіб побудови нормальної диз'юнктивної форми для будь-якої формули алгебри логіки.

Приклад 3Знайти диз'юнктивну нормальну форму для наступної формули: .

Виключаючи знак за законом та застосовуючи закони де Моргана та подвійного заперечення, отримуємо:

Потім, застосовуючи закон дистрибутивності, розкриємо дужки

Остання вираз є диз'юнктивна нормальна форма.

Форма виду (короткий запис), де - диз'юнкції прийнято називати кон'юнктивною нормальною формою (КНФ).

Такими є, наприклад, вирази:

, .

Як показано вище, для будь-якої алгебри формули логіки існує рівносильна їй диз'юнктивна форма. Використовуючи дистрибутивний закон, з цієї ДНФ легко отримати КНФ.

Отже, справедлива така теорема.

Теорема 4 Для будь-якої алгебри формули логіки існує рівносильна їй кон'юнктивна нормальна форма.

Доказ цієї теореми дає спосіб побудови кон'юнктивної нормальної форми будь-якої формули алгебри логіки.

Приклад 4Знайти диз'юнктивну та кон'юнктивну нормальні форми для наступної формули: .

Використовуючи закон , виключаємо знак . Отримуємо формулу.

Використовуючи закон де Моргана, отримуємо формулу . Розкриваючи дужки, отримуємо диз'юнктивну нормальну форму

Щоб отримати кон'юнктивну нормальну форму, застосуємо до формули дистрибутивний закон, отримуємо:

Останній вираз є кон'юнктивною нормальною формою. Так як і , то отримана КНФ дорівнює наступній КНФ:

Серед усіх нормальних формул даної формули виділимо досконалу нормальну форму як диз'юнктивну, так і кон'юнктивну. Враховуючи розкладання (3), неважко помітити, що досконала диз'юнктивна нормальна форма алгебри формули логіки, що містить рівно n різних змінних, є її диз'юнктивна нормальна форма, в якій:

1) всі кон'юнкції попарно різні;

2) кожна кон'юнкція містить рівно n змінних;

3) у кожній кон'юнкції зустрічаються всі n змінних.

На прикладі 1 ми розглянули один із способів побудови СДНФ, заснований на складанні таблиці істинності. Наступний спосіб побудови СДНФ ґрунтується на застосуванні законів алгебри логіки.

Приклад 5Знайти досконалу диз'юнктивну форму формули.

Використовуючи, що , Отримуємо . Зважаючи на закони де Моргана і подвійного заперечення маємо діз'юнктивну нормальну форму. Ця ДНФ рівносильна формулі.

Розкриваючи дужки, отримуємо: .

Використовуючи закон ідемпотентності, отримуємо необхідну СДНФ:

Враховуючи розкладання (3.6), неважко помітити, що досконала кон'юнктивна нормальна форма алгебри формули логіки, що містить рівно nрізних змінних, є її кон'юнктивна нормальна форма, в якій:

1) всі диз'юнкції попарно різні;

2) кожна диз'юнкція містить рівно n членів; тотожно істинної, у разі якщо вона при всіх значеннях вхідних до неї змінних набуває значення істинно.

Прикладами тотожних формул є формули:

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

Прикладами тотожно неправдивих формул є формули:

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

Прикладами здійснених формул є такі формули:

В алгебрі логіки можна поставити таке завдання: вказати спосіб (алгоритм), що дозволяє для кожної формули логіки алгебри дізнатися, є вона тотожно істинною чи ні. Поставлене завдання зветься проблеми вирішення.

Розглянемо такі два способи вирішення цього завдання.

Спосіб 1 (табличний)Для того, щоб визначити, є ця формула тотожно істинною чи ні, достатньо скласти її таблицю істинності.

При цьому даний спосіб, хоч і дає принципове вирішення проблеми розв'язності, він досить громіздкий.

Спосіб 2ґрунтується на приведенні формул до нормальної форми.

Теорема 4Формула алгебри логіки тоді й тільки тоді є тотожно істинною, коли кожна диз'юнкція у її кон'юнктивній нормальній формі містить певну змінну разом із її запереченням.

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

Нехай тепер ця формула є тотожно істинною, і нехай є деяка диз'юнкція у КНФ цієї формули. Припустимо, що ця диз'юнкція не містить змінної разом з її запереченням. У такому разі ми можемо кожній змінній, що не стоїть під знаком заперечення, дати значення 0, а кожній змінній, що стоїть під знаком заперечення – значення 1. Після зазначеної підстановки всі диз'юнкції стануть рівними 0, отже, формула не є тотожно істинною. Набули протиріччя.

Приклад 7З'ясувати, чи тотожно буде істинною формула

Використовуючи, що , Отримуємо .

Застосовуючи закон дистрибутивності, отримуємо КНФ:

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

Аналогічно попередній теоремі доводиться теорема:

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

Розкладання булевих функцій за змінними. - Поняття та види. Класифікація та особливості категорії "Розкладання булевих функцій за змінними." 2017, 2018.