Булеві функції - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Булеві функції. Доклад-сообщение содержит 67 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

4.7. Мінімізація булевих функцій метод карт Карно метод діаграм Вейча (мінімізація на множині КНФ) мінімізація частково визначених функцій метод Нельсона метод Квайна метод Мак-Класкі метод Порецького — Блейка

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Для знаходження множини простих імплікант функції, що задана СДНФ, використовуються такі перетворення формул булевої алгебри: Для знаходження множини простих імплікант функції, що задана СДНФ, використовуються такі перетворення формул булевої алгебри: операція неповного диз'юнктивного склеювання: А х  Ах = A  A x  Ах. операція диз'юнктивного поглинання: A  А х = А. Виконання обох операцій послідовно - це операція повного диз'юнктивного склеювання: А х  Ах = А. Тут А — деяка елементарна кон'юнкція змінних, х — булева змінна.

Слайд 8

Описание слайда:

Приклад. Нехай є функція f, що задана ДДНФ: Приклад. Нехай є функція f, що задана ДДНФ: f(x, у, z) = х у z x y z xy z xyz. Виконаємо операції повного склеювання : f(x, у, z) = х у z x y z xy z xyz = = (х у z x y z)(x y z xy z )(xy z xyz) = = у z x z xy. Виконаємо операції склеювання іншим способом: f(x, у, z) = (х у z x y z)(xy z xyz) = у z xy. В обох випадках одержані тупикові ДНФ функції f(x,у,z). Друга тупикова ДНФ простіша за першу, оскільки містить меншу кількість символів змінних і знаків операцій.

Слайд 9

Описание слайда:

Таблиця істинності функції f(x,у,z) та її трьох імплікант, що входять до складу ДНФ

Слайд 10

Описание слайда:

Для аналізу різних зображень булевої функції через КНФ і одержання мінімальних КНФ трансформуємо викладені вище поняття за принципом двоїстості: імпліцента, проста імпліцента, повна система імпліцент, скорочена КНФ, тупикова КНФ, мінімальна КНФ. Для аналізу різних зображень булевої функції через КНФ і одержання мінімальних КНФ трансформуємо викладені вище поняття за принципом двоїстості: імпліцента, проста імпліцента, повна система імпліцент, скорочена КНФ, тупикова КНФ, мінімальна КНФ. Використовувані для мінімізації КНФ операції склеювання мають такий вигляд: Операція неповного кон'юнктивного склеювання: (A  x)(A х) = А(А  x)(A x). Операція кон'юнктивного поглинання: А(А  х) = А. Операція повного кон'юнктивного склеювання: (A  x)(A x)=A.

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

Карта Карно для ДНФ (діаграма Вейча — для КНФ) є аналогом таблиці істинності, зображеній у спеціальній формі.

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Приклад. Побудувати карту Карно для функції f(x, у, z) = х у z x y z xy z xyz.

Слайд 15

Описание слайда:

Правило склеювання кліток і запису МДНФ 1. Побудувати карту Карно, що відповідає даній функції. 2. Клітки об'єднуються у групи, що позначають операції склеювання. В об'єднанні беруть участь тільки сусідні клітки, в яких знаходяться одиниці. 3. В групу можні об'єднати кількість кліток, що дорівнює 2n, n = 1, 2, 3, .... При цьому група може мати тільки прямокутну або квадратну форму. 4. Задача склеювання полягає у знаходженні набору максимальних груп кліток. Кількість груп у наборі повинна бути мінімальною, оскільки така група відповідає мінімальній тупиковій ДНФ. Кожна одиниця карти Карно повинна входити хоча б до однієї групи, що забезпечує покриття функції одержаним набором імплікант.

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

Приклад. Побудувати карту Карно для функції f(x, у, z) = х у z x y z xy z xyz. А В Імпліканта А = xy z xyz = xy (z z )= xy. Імпліканта B = х у z x y z = (x x) у z = у z. МДНФ: f(x, у, z) = A  В = xy  у z.

Слайд 18

Описание слайда:

Приклад. Знайти МДНФ для функції f(x, у, z) =х уz  x yz xy z  x y z. А В С МДНФ f(x, у, z) = A  B  C =xy z  yz  x y.

Слайд 19

Описание слайда:

Приклад. Побудувати МДНФ для функції f(x, у, z, t) = x у zt  xу z t x у z t xу z t   xуz t xуz t  xуzt xуzt.

Слайд 20

Описание слайда:

Мінімізація булевих функцій методом діаграм Вейча Для мінімізації булевої функції на множині КНФ використовуються діаграми Вейча. Їх побудова аналогічна картам Карно. На карті позначаються клітки, що відповідають інтерпретаціям, на яких функція дорівнює нулю. Після цього проводиться склеювання кліток, що містять нулі і формування мінімальної КНФ. Склеювання кліток здійснюється за тими ж правилами, що й при диз'юнктивній мінімізації. Кожна група кліток, що одержана в результаті склеювання, відповідає диз'юнкції тільки тих змінних, які мають однакове значення для всіх кліток групи. Змінні беруться без заперечення, якщо їм відповідає нульове значення, і із запереченням — в іншому випадку. Кон'юнкція одержаних елементарних диз'юнкцій є результатом мінімізації формули

Слайд 21

Описание слайда:

Приклад. Побудувати МКНФ для функції f(x, у, z, t) = x у zt  xу z t x у z t xу z t   xуz t xуz t  xуzt xуzt.

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

Приклад. Функція f(x, у, z, t) дорівнює одиниці на наборах (0,0,1,0), (0,1,1,0), (1,0,1,0), (1,0,0,0) і не визначена, якщо ху = 1. Необхідно побудувати МДНФ та МКНФ.

Слайд 24

Описание слайда:

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

Мінімізація булевих функцій методом Нельсона Метод мінімізації Нельсона реалізує перехід від КНФ до скороченої ДНФ. 1. Записати КНФ заданої функції. 2. Розкрити дужки за дистрибутивним законом, спростити і звести подібні (закони ідемпотентності й протиріччя). 3. Виконати всі можливі операції диз'юнктивного поглинання. Результуюча формула є CДНФ функції.

Слайд 27

Описание слайда:

Приклад. Знайти методом Нельсона СДНФ функції f(x, у, z) = (х y)(x  z)(x  y z).

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Мінімізація булевих функцій методом Квайна Метод мінімізації Квайна також реалізує перехід від ДДНФ до мінімальної ДНФ з використовуванням операцій склеювання та поглинання. 1. Записати ДДНФ заданої функції. 2. Виконати всі можливі операції неповного диз'юнктивного склеювання. Результуюча формула є диз'юнкцією всіх можливих імплікант даної функції. 3. Виконати всі можливі операції диз'юнктивного поглинання. Результуюча формула є CДНФ функції.

Слайд 30

Описание слайда:

4. Скласти імплікантну таблицю і знайти диз'юнктивне ядро. 4. Скласти імплікантну таблицю і знайти диз'юнктивне ядро. 5. Спростити імплікантну таблицю за допомогою видалення рядків, що відповідають імплікантам диз'юнктивного ядра, і стовпців, що відповідають тим конституентам одиниці, які покриваються імплікантами ядра. Якщо при мінімізації деякої функції виходить, що спрощена імплікантна таблиця порожня, то тупикова ДНФ цієї функції складається тільки з імплікант диз'юнктивного ядра. 6. Знайти всі тупикові ДНФ даної функції. 7. Знайти мінімальну ДНФ.

Слайд 31

Описание слайда:

Приклад. Знайти методом Квайна МДНФ функції f(x, у, z) = х у z  xyz x y z xy z xyz.

Слайд 32

Описание слайда:

Імплікантна таблиця функції f(x, у, z) = х у z  xyz x y z xy z xyz.

Слайд 33

Описание слайда:

Виділення диз’юнктивного ядра та спрощення імплікантної таблиці

Слайд 34

Описание слайда:

За спрощеною імплікантною таблицею знаходимо тупикові ДНФ

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

1. Згрупувати двійкові коди імплікант з однаковою кількістю одиниць. Число одиниць m - індекс групи. Упорядкувати групи за зростанням m. 1. Згрупувати двійкові коди імплікант з однаковою кількістю одиниць. Число одиниць m - індекс групи. Упорядкувати групи за зростанням m. 2. Починаючи з m = 0, порівнянти кожний двійковий код в групі з індексом m з кожним кодом з групи з індексом m + 1. Якщо вони різні тільки в одному розряді, то у наступний стовпчик таблиці записати відповідний їм двійковий код з порожньою позначкою «-» на місці зазначеного розряду. Імпліканти, що брали участь у заміні, не є простими, позначити їх знаком «V». Решту кодів позначити «Х» (це прості імпліканти). 3. Якщо серед знов одержаних імплікант є однакові, то з них для подальшого використання залишити тільки одну. 4. Повторювати кроки 1-3 доти, доки існує можливість одержувати нові коди імплікант.

Слайд 40

Описание слайда:

Приклад. Знайти за допомогою метода Мак-Класкі мінімальну ДНФ функції: f(x, у, z, t) = xуzt  xуz t xу zt xу z t  x уz t x у z t  xуzt  xу zt  x уzt   xу z t  x уz t.

Слайд 41

Описание слайда:

Двійкові коди конституент одиниці функції

Слайд 42

Описание слайда:

Одержання простих імплікант методом Мак-Класкі

Слайд 43

Описание слайда:

Для знаходження тупикових ДНФ будуємо імплікантну таблицю

Слайд 44

Описание слайда:

Одержання спрощеної імплікантної таблиці

Слайд 45

Описание слайда:

Cпрощена імплікантна таблиця

Слайд 46

Описание слайда:

Характеристика методу Мак-Класкі Метод є формальним, не складний для програмної реалізації. Недолік - необхідність записувати ДДНФ функції, яка вже при семи змінних може містити більше ста конституент одиниці.

Слайд 47

Описание слайда:

Мінімізація булевих функцій методом Блейка — Порецького Метод Блейка — Порецького реалізує перехід від довільної ДНФ функції до скороченої ДНФ за допомогою операцій узагальненого склеювання і поглинання. Операція узагальненого склеювання: Ах  Вх = Ах  Вх  AB. Доведення: АхВх = Ax(lВ)Вх(1А) = АхABxBxABx = = Ах  Bx  АВ(х х) = Ах  Bx  AB. Операція поглинання: Ах  А = А.

Слайд 48

Описание слайда:

Приклад. Знайти скорочену ДНФ за методом Блейка — Порецького для функції f(x, у, z) = xyz  xz xy.

Слайд 49

Описание слайда:

Характеристика методу Блейка — Порецького Метод є формальним, але складний для програмної реалізації. Метод дозволяє здійснювати диз'юнктивну мінімізацію, використовуючи як вихідну довільну ДНФ функції. Результатом є скорочена, а не мінімальна форма. Для отримання мінімальної форми треба скористатися ще якимось методом.

Слайд 50

Описание слайда:

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

Слайд 51

Описание слайда:

Алгебра (В, , , 0, 1), що утворена множиною В={0, 1} разом з операціями  (кон'юнкції),  (XOR — от eXclusive OR, сума за модулем 2) і константами 0, 1, називається алгеброю Жегалкіна. Алгебра (В, , , 0, 1), що утворена множиною В={0, 1} разом з операціями  (кон'юнкції),  (XOR — от eXclusive OR, сума за модулем 2) і константами 0, 1, називається алгеброю Жегалкіна. В алгебрі Жегалкіна операція кон'юнкції повністю ідентична множенню, а операція XOR зображує додавання за модулем для скінченних множин. Приклад. Формула (хуz)(хz1)ху1, де х, у, z — булеві змінні, є прикладом формули алгебри Жегалкіна, тому що вона містить операції кон'юнкції і XOR. Будь-яка логічна функція може бути зображена формулою в алгебрі Жегалкіна.

Слайд 52

Описание слайда:

Тотожності алгебри Жегалкіна Властивості кон'юнкції: 1) х  (у  z) = (х  у)  z — асоціативність 2) х  у = у х — комутативність 3) х  х = х — ідемпотентність 4) х  0 = 0, х  1 = х — дії з константами Властивості операції XOR (додавання за модулем 2): 5) х  (у  z) = (х  у)  z — асоціативність 6) х  у = у  х — комутативність операції XOR 7) х  х = 0 — закон зведення подібних доданків 8) х  0 = х — операція з константою 0 9) х(уz) = хуxz — дистрибутивність  відносно 

Слайд 53

Описание слайда:

Зображення заперечення: Зображення заперечення: х = х  1

Слайд 54

Описание слайда:

Поліном Жегалкіна Поліномом Жегалкіна називається скінченна сума за модулем 2 попарно різних елементарних кон'юнкцій над множиною змінних (x1, x2, ..., xn). Кількість змінних, що входять до елементарної кон'юнкції, називається рангом елементарної кон'юнкції. Кількість попарно різних елементарних кон'юнкцій у поліномі називається довжиною полінома. Зображення у вигляді поліному існує та єдине для кожної булевої функції. Булева функція називається лінійною, якщо її поліном Жегалкіна не містить кон'юнкцій змінних.

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

Приклад. Зобразити поліномами Жегалкіна логічні функції імплікацію () і еквівалентність (~).

Слайд 57

Описание слайда:

Приклад. Визначити, чи лінійні функції імплікації () і еквівалентності (~).

Слайд 58

Описание слайда:

Приклад. Дослідити на лінійність функцію f(х, у, z) = (х  у) z.

Слайд 59

Описание слайда:

Побудова поліному Жегалкіна Побудова поліному Жегалкіна методом невизначених коефіцієнтів Метод невизначених коефіцієнтів засновано на тому, що для будь-якої булевої функції існує єдиний поліном Жегалкіна. Приклад. Побудувати поліном Жегалкіна для функції f13(x, у) — імплікації, використовуючи метод невизначених коефіцієнтів.

Слайд 60

Описание слайда:

Розв'язок. Запишемо поліном для даної функції у вигляді суми за модулем 2 всіх можливих елементарних кон'юнкцій для х, у з невизначеними коефіцієнтами: Розв'язок. Запишемо поліном для даної функції у вигляді суми за модулем 2 всіх можливих елементарних кон'юнкцій для х, у з невизначеними коефіцієнтами: f13(x, у) = х  у = а1ху  а2х  а3у  а4, де коефіцієнти а1, а2, а3, а4 приймають значення з множини {0, 1} і визначають присутність або відсутність елементарної кон'юнкції в поліномі. Шукаємо послідовно значення коефіцієнтів, підставляючи значення змінних і функції на різних інтерпретаціях: f13(0, 0) = 0  0 = 1, 1 = а1  0  0  а2  0  а3  0  а4 = а4 а4 = 1;

Слайд 61

Описание слайда:

Слайд 62

Описание слайда:

Функції, що зберігають нуль та одиницю Булева функція f(x1, x2, ..., хn) називається функцією, що зберігає 0, якщо на нульовому наборі вона дорівнює 0: f(0, 0, ..., 0) = 0. Булева функція f(x1, x2, ..., хn) називається функцією, що зберігає 1, якщо на одиничному наборі вона дорівнює 1: f(1,1, .... 1)=1. Функції х  у і х  у зберігають 0, оскільки 0  0 = 0 і 0  0 = 0. Крім того, дані функції також зберігають 1, оскільки 1  1 = 1 і 1  1 = 1. Функція х не зберігає 0 і не зберігає 1, оскільки 0 = 1, 1 = 0.

Слайд 63

Описание слайда:

Приклад. Визначте, чи зберігає 0 та 1 функція f(x, у, z) = x уz. Розв'язок. Перевіримо значення даної функції на нульовому та одиничному наборах. Приклад. Визначте, чи зберігає 0 та 1 функція f(x, у, z) = x уz. Розв'язок. Перевіримо значення даної функції на нульовому та одиничному наборах. f(0, 0, 0) = 0 0 0 = 0  1  1 = 0  1 = 1, f(1, 1, 1)=1 1 1 = 1  0  0 = 1  0 = 1. Отже, дана функція зберігає 1 і не зберігає 0.

Слайд 64

Описание слайда:

Монотонні функції Розглянемо важливий клас булевих функцій — монотонні булеві функції. Для цього введемо відношення порядку, яке будемо позначати символом , для інтерпретацій =(а1, а2, ..., аn), =(b1, b2, ..., bn) таким чином:   , якщо аi  bi для всіх і = 1, ..., n. Якщо хоча б для однієї пари (аi,bi) відношення аibi не виконується, то відповідні їм набори  i  у відношенні порядку не беруть участі, тобто є непорівнянними, наприклад, (0, 1) і (1, 0). Булева функція f називається монотонною, якщо для будь-яких пар наборів значень змінних (а1,а2,...,аn) і (b1,b2,...,bn), для яких виконується відношення (а1,а2,...,аn)  (b1,b2,...,bn), правильна і нерівність f(а1,а2,...,аn)  f(b1,b2,...,bn).

Слайд 65

Описание слайда:

Приклад. Дослідити на монотонність функцію Приклад. Дослідити на монотонність функцію f(x, y) = x  у. Розв'язок. Для функції f(x, у) запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх: (0, 0)  (0, 1), f(0, 0) = 0, f(0, 1) = 0, f(0, 0)  f(0, 1). (0, 0)  (1, 0), f(0, 0) = 0, f(1, 0) = 0, f(0, 0)  f(1, 0). (0, 0)  (1, 1), f(0, 0) = 0, f(1, 1) = 1, f(0, 0)  f(1, 1). (0, 1)  (1, 1), f(0, 1) = 0, f(1, 1) = 1, f(0, 1)  f(1, 1). (1, 0)  (1, 1), f(1, 0) = 0, f(1, 1) = 1, f(1, 0)  f(1, 1). Висновок: функція f(x, y) = x  у є монотонною.

Слайд 66

Описание слайда:

Приклад. Дослідити на монотонність функцію Приклад. Дослідити на монотонність функцію g(x, у) = х  у. Розв'язок. Для функції g(x, у) запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх: (0,0)  (0,1), g(0,0) = 0, g(0,1) = 1, g(0,0)  g(0,1). (0,0)  (1,0), g(0,0) = 0, g(l,0) = 1, g(0,0)  g(l,0). (0,0)  (1,1), g(0,0) = 0, g(l,1) = 0, g(0,0)  g(l,1). (0,1)  (1,1), g(0,1) = 1, g(l,1) = 0, g(0,1)  g(l,1). Висновок: функція g(x, у) = х  у не є монотонною.

Слайд 67

Описание слайда:

Теорема. Булева функція, відмінна від констант 0 і 1, є монотонною, якщо і тільки якщо вона припускає зображення формулою булевої алгебри без заперечень. Теорема. Булева функція, відмінна від констант 0 і 1, є монотонною, якщо і тільки якщо вона припускає зображення формулою булевої алгебри без заперечень. Приклад. Визначити, чи є функція f(x, у, z, t) = (x y)(z  t) монотонною. Розв'язок. Виразимо f(x, у, z, t) через елементарні функції булевої алгебри: (x y)(z  t) = = ху  z  t. Одержана формула булевої алгебри не містить заперечень, отже функція f(x, у, z, t) є монотонною.

Теги Булев функц

Похожие презентации