Презентация Булеві функції онлайн

Содержание слайда: Розділ 4. Булеві функції

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

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

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

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

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

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

Содержание слайда: Приклад. Нехай є функція 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). Друга тупикова ДНФ простіша за першу, оскільки містить меншу кількість символів змінних і знаків операцій.

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

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

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

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

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

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

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

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

Содержание слайда: Приклад. Побудувати карту Карно для функції 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.

Содержание слайда: Приклад. Знайти МДНФ для функції 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.

Содержание слайда: Приклад. Побудувати МДНФ для функції 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.

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

Содержание слайда: Приклад. Побудувати МКНФ для функції 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.

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

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

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

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

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

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

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

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

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

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

Содержание слайда: Імплікантна таблиця функції f(x, у, z) = х у z  xyz x y z xy z xyz.

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

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

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

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

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

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

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

Содержание слайда: Приклад. Знайти за допомогою метода Мак-Класкі мінімальну ДНФ функції: 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.

Содержание слайда: Двійкові коди конституент одиниці функції

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

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

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

Содержание слайда: Cпрощена імплікантна таблиця

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

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

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

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

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

Содержание слайда: Алгебра (В, , , 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. Будь-яка логічна функція може бути зображена формулою в алгебрі Жегалкіна.

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

Содержание слайда: Зображення заперечення: Зображення заперечення: х = х  1

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

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

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

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

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

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

Содержание слайда: Розв'язок. Запишемо поліном для даної функції у вигляді суми за модулем 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;

Содержание слайда:

Содержание слайда: Функції, що зберігають нуль та одиницю Булева функція 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.

Содержание слайда: Приклад. Визначте, чи зберігає 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.

Содержание слайда: Монотонні функції Розглянемо важливий клас булевих функцій — монотонні булеві функції. Для цього введемо відношення порядку, яке будемо позначати символом , для інтерпретацій =(а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).

Содержание слайда: Приклад. Дослідити на монотонність функцію Приклад. Дослідити на монотонність функцію 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  у є монотонною.

Содержание слайда: Приклад. Дослідити на монотонність функцію Приклад. Дослідити на монотонність функцію 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, у) = х  у не є монотонною.

Содержание слайда: Теорема. Булева функція, відмінна від констант 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) є монотонною.