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

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

Функція виду у = 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.

Слайд 5

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

Функції кількох незалежних змінних можна розглядати як функції від більшої кількості змінних. При цьому значення функції не змінюється при зміні значення цих «додаткових» змінних. Функції кількох незалежних змінних можна розглядати як функції від більшої кількості змінних. При цьому значення функції не змінюється при зміні значення цих «додаткових» змінних. Змінна 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).

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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

Слайд 18

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

Нехай функція 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;

Слайд 19

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

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

Слайд 20

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

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

Слайд 21

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

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

Слайд 22

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

Закони булевої алгебри Закони де Моргана

Слайд 23

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

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

Слайд 24

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

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

Слайд 25

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

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

Слайд 26

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

за змінними х, z. за змінними х, z.

Слайд 27

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

Слайд 28

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

за змінною х. за змінною х.

Слайд 29

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

Слайд 30

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

Слайд 31

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

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

Слайд 32

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

Елементарна кон'юнкція Елементарна кон'юнкція

Слайд 33

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

Слайд 34

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

за змінними х, z. за змінними х, z.

Слайд 35

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

Слайд 36

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

за змінною х. за змінною х.

Слайд 37

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

Слайд 38

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

Слайд 39

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

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

Слайд 40

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

Елементарна диз'юнкція Елементарна диз'юнкція

Слайд 41

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

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