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

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

Содержание слайда: 4.1. Булеві змінні і функції двійкові інтерпретації істотні та фіктивні змінні

Содержание слайда: Розглянемо двохелементну множину В, елементи якої будемо позначати через 0 і 1: В={0,1}. Розглянемо двохелементну множину В, елементи якої будемо позначати через 0 і 1: В={0,1}. Змінні, які можуть приймати значення тільки з множини В, називаються логічними або булевими змінними. Самі значення 0 i 1 булевих змінних називаються булевими константами. В мовах програмування для роботи з такими змінними, як правило, вводиться спеціальний логічний (булевський) тип (наприклад, у мовах Pascal і Java — boolean, у С+ — bool). Змінна цього типу приймає два значення: true і false.

Содержание слайда: Функція виду у = f(x1, х2, ..., хn), аргументи хi і значення у якої належать множині В, називається n-місною булевою функцією. Такі функції також називають логічними або перемикальними функціями. Функція виду у = f(x1, х2, ..., хn), аргументи хi і значення у якої належать множині В, називається n-місною булевою функцією. Такі функції також називають логічними або перемикальними функціями. Кортеж (х1; х2, ..., хn) конкретних значень булевих змінних називається двійковим словом (n-словом) або булевим набором довжини n. Для булевої функції у = f(x1, х2, ..., хn) конкретне значення булевого набору (х1, х2,…, хn) називається також інтерпретацією булевої функції f. Множина всіх двійкових слів, що позначається через Вn, називається n-вимірним булевим кубом і містить 2n елементів-слів: |Вn| = 2n.

Содержание слайда: Функції кількох незалежних змінних можна розглядати як функції від більшої кількості змінних. При цьому значення функції не змінюється при зміні значення цих «додаткових» змінних. Функції кількох незалежних змінних можна розглядати як функції від більшої кількості змінних. При цьому значення функції не змінюється при зміні значення цих «додаткових» змінних. Змінна xi у функції f(x1,…, хi-1, хi, хi+1,..., хn) називається неістотною (або фіктивною), якщо f(x1,…, хi-1, 0, хi+1,..., хn) = f(x1,…, хi-1, 1, хi+1,..., хn) при будь-яких значеннях решти змінних, тобто якщо зміна значення xi у будь-якому наборі значень x1, ..., хn не змінює значення функції. В цьому випадку функція f(x1, ..., хn) фактично залежить від n-1 змінної, тобто зображує функцію g(x1,…, хi-1, хi+1,..., хn).

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

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

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

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

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

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

Содержание слайда: Булева алгебра Булева алгебра (загальна) — це алгебраїчна структура (А, , , ¯, 0, 1) з бінарними операціями , : А2А, унарною операцією «¯»: АА і виділеними елементами 0, 1 в носії А, які задовольняють властивості комутативності, асоціативності, дистрибутивності. Якщо носій алгебраїчної структури В = {0, 1} складається з двох елементів, то така структура (В,,,¯) називається двохелементною булевою алгеброю. Алгеброю логіки називається двохелементна булева алгебра (В, , , ¯, , ~), В={0,1}, в якій множину операцій доповнено двома бінарними операціями: імплікацією та еквівалентністю.

Содержание слайда: Формула — це вираз, що містить булеві функції та їхні суперпозиції. Формула — це вираз, що містить булеві функції та їхні суперпозиції. Суперпозицією називається спосіб одержання нових функцій шляхом підстановки значень одних функцій замість значень аргументів інших функцій, при цьому деякі з функцій можуть тотожно співпадати з однією із змінних. Якщо у формулі відсутні дужки, то операції виконуються у такій послідовності: заперечення ¯ кон'юнкція  диз'юнкція  імплікація  еквівалентність ~

Содержание слайда: На відміну від табличного задання, зображення функції формулою не єдине. На відміну від табличного задання, зображення функції формулою не єдине. Формули, що зображують одну й ту ж функцію, називаються еквівалентними або рівносильними. Приклад. Функцію штрих Шеффера можна зобразити за допомогою основних операцій булевої алгебри формулами: f14 =x1 x2 або

Содержание слайда: 4.3. Двоїстість двоїсті та самодвоїсті булеві функції принцип двоїстості побудова двоїстої функції за таблицею побудова двоїстої функції за формулою

Содержание слайда: Функція f*(х1, ..., хn) називається двоїстою до функції f(х1, ..., хn), якщо Функція f*(х1, ..., хn) називається двоїстою до функції f(х1, ..., хn), якщо f*(х1, ..., хn) = f(х1, ..., хn). Для будь-якої функції двоїста їй визначається однозначно. (f*)* = f

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

Содержание слайда: Нехай функція F задана як суперпозиція функцій f0 і функцій f1, ..., fn: F = f0(f1, ..., fn). Функцію F*, що двоїста F, можна одержати, замінивши в формулі F функції f0; f1, ..., fn на двоїсті до них . Нехай функція F задана як суперпозиція функцій f0 і функцій f1, ..., fn: F = f0(f1, ..., fn). Функцію F*, що двоїста F, можна одержати, замінивши в формулі F функції f0; f1, ..., fn на двоїсті до них . Вкажемо функції, що двоїсті до «елементарних» функцій логіки , , ¯, константа 0, константа 1: f(x, у) = х  у; f*(x, у) = х  у; f(x) = х; f*(х) = х = f(x); f(x) = 0; f*(х) =0 = 1;

Содержание слайда: 4.4. Закони булевої алгебри Комутативні закони х  у = у  х х  у = у  х

Содержание слайда: Закони булевої алгебри Тотожності з константами х  0 = х х  1 = x x  1 = 1 х  0 = 0

Содержание слайда: Закони булевої алгебри Закон подвійного заперечення

Содержание слайда: Закони булевої алгебри Закони де Моргана

Содержание слайда: 4.5. Диз'юнктивні та кон'юктивні розкладання булевих функцій теореми розкладання елементарні кон'юнкція і диз'юнкція конституенти нуля та одиниці нормальні форми

Содержание слайда: Для спрощення математичних викладень введемо двійковий параметр  і позначення х таким чином: Для спрощення математичних викладень введемо двійковий параметр  і позначення х таким чином: х,   В = {0, 1},

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

Содержание слайда: за змінними х, z. за змінними х, z.

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

Содержание слайда: за змінною х. за змінною х.

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

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

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

Содержание слайда: Елементарна кон'юнкція Елементарна кон'юнкція

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

Содержание слайда: за змінними х, z. за змінними х, z.

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

Содержание слайда: за змінною х. за змінною х.

Содержание слайда: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі: Будь-яку булеву функцію f(x1, x2, ..., хn) можна зобразити в такій формі:

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

Содержание слайда: Елементарною диз'юнкцією називається диз'юнкція будь-якого числа булевих змінних, що взяті із запереченням або без нього, в якій кожна змінна зустрічається не більше одного разу. Елементарною диз'юнкцією, що містить нуль змінних, будемо вважати константу 0. Елементарною диз'юнкцією називається диз'юнкція будь-якого числа булевих змінних, що взяті із запереченням або без нього, в якій кожна змінна зустрічається не більше одного разу. Елементарною диз'юнкцією, що містить нуль змінних, будемо вважати константу 0. Приклад. Елементарними диз'юнкціями для функції від однієї змінної можуть бути у,z, від двох змінних — х  у, х z, від трьох змінних — х у  z, х у z, х  у  z Кон'юнктивною нормальною формою (КНФ) називається формула, що зображена у вигляді кон'юнкції елементарних диз'юнкцій.

Содержание слайда: Елементарна диз'юнкція Елементарна диз'юнкція

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

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

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

Содержание слайда: Приклад. Одержати ДДНФ та ДКНФ для функції Приклад. Одержати ДДНФ та ДКНФ для функції

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

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

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

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

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

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

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

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

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

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