Презентация на тему: 1 Булеві функції Лекція 3 Булеві функції

1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1 Булеві функції Лекція 3 Булеві функції
1/22
Средняя оценка: 4.0/5 (всего оценок: 77)
Код скопирован в буфер обмена
Скачать (232 Кб)
1

Первый слайд презентации

1 Булеві функції Лекція 3 Булеві функції

Изображение слайда
2

Слайд 2

Булеві функції 2 Джордж Буль (2.11.1815 - 8.12.1864) У 1854 р. побачив світ основний твір Буля “ Дослідження законів думки, на яких засновані математичні теорії логіки й імовірності ”. Ця ґрунтовна книга нині зараховується до математичної класики; у ній детально досліджується та система алгебри, яку сьогодні називають “ алгеброю висловлювань ”.

Изображение слайда
3

Слайд 3

Булеві функції 3 Джордж Буль Чіткість, з якою підійшов Буль до завдання “алгебраїзації логіки”, і те глибоке розуміння природи математики і сенсу абстрактних математичних структур, які він при цьому виявив, не тільки цілком виправдовують загальноприйнятий термін “структура (або алгебра ) Буля ”, але і зробили можливим крилатий вислів: „ Чисту математику відкрив Буль у праці, яка називається Закони думки ” ( Б. Рассел, англійський математик і філософ). Буль мав чотирьох доньок, які всі виявилися чудовими людьми (у нашій країні найвідоміша Етель Ліліан Буль, у заміжжі Войнич, автор роману “ Овід ”).

Изображение слайда
4

Слайд 4

4 Булеві функції Нехай X = {x 1, x 2,..., x n-1, x n } – вихідна множина булевих змінних (аргументів). Вважатимемо, що аргументи визначено на множині E 2 = {0, 1}, і розглядатимемо функції f(x 1, x 2,..., x n ) такі, що f(  1,  2, ...,  n ) E 2 за умови  i  E 2. У такий спосіб f(x 1, x 2, ..., x n ) розумітимемо як запис функції, що залежить від множини аргументів X. Булеві функції Означення 2.1. Булева функція n змінних або функція алгебри логіки визначається як відображення

Изображение слайда
5

Слайд 5

Булеві функції 5 Із означення функції f(x 1, x 2,..., x n ) випливає, що для її задання досить вказати значення функції, які відповідають кожному з наборів значень аргументів, тобто задати таблицю (наступний слайд). Якщо існують n змінних, то вони набувають 2 n різних значень. Якщо набір аргументів розглядати як запис числа у двійковій системі числення, то розташування наборів відповідає природному розташуванню двійкових чисел у порядку зростання 0, 1,..., 2 n–1. Табличне задання булевої функції

Изображение слайда
6

Слайд 6

Булеві функції 6 x 1 ... x n–1 x n f(x 1, x 2,..., x n–1, x n ) 0 ... 0 0 f(0, 0,..., 0, 0) 0 ... 0 1 f(0, 0,..., 0, 1) 0 ... 1 0 f(0, 0,..., 1, 0) ... ... ... ... ... 1 ... 1 1 f(1, 1,..., 1, 1) Таблиця задання булевої функції

Изображение слайда
7

Слайд 7

Булеві функції 7 Теорема 2.1. Кількість p 2 (n) усіх функцій з P 2, що залежать від n змінних x 1, x 2,..., x n, дорівнює. Доведення. Якщо зафіксувати n змінних x 1, x 2,..., x n, то таблиця задання функції матиме m = 2 n рядків. Таблиці для різних функцій відрізнятимуться тільки значеннями правого стовпчика, а кількість таблиць складатиме 2 m, тобто. Теорему доведено. Теорема про кількість булевих функцій

Изображение слайда
8

Слайд 8

Булеві функції 8 Означення 2.2. Функція f(x 1, x 2,..., x i-1, x i, x i+1,..., x n ) із P 2 істотно залежить від аргументу x i, якщо існують такі значення змінних x 1, x 2,..., x i–1, x i, x i+1,..., x n, що f(  1,  2,...,  i–1, 0,  i+1,...,  n )  f(  1,  2, …,  i-1, 1,  i+1,...,  n ). У цьому випадку змінна x i називається істотною. Якщо x i не є істотною змінною, то вона називається неістотною або фіктивною. Істотні та фіктивні змінні

Изображение слайда
9

Слайд 9

Булеві функції 9 Нехай для функції f(x 1, x 2,..., x n ) змінна x i є фіктивною. Візьмемо таблицю для функції f(x 1, x 2,..., x n ) і згідно з нею побудуємо нову таблицю методом викреслювання всіх рядків, що мають вигляд  1,  2,...,  i-1, 1,  i+1,...,  n, а також викреслювання стовпчика для аргументу x i. Отримана таблиця визначатиме деяку функцію g(x 1, x 2,..., x i-1, x i+1,..., x n ). Вважатимемо, що її здобуто із f(x 1, x 2,..., x n ) шляхом вилучення фіктивної змінної x i, а функцію f(x 1, x 2,..., x n ) – із g(x 1, x 2, ..., x i–1, x i+1,..., x n ) шляхом введення фіктивної змінної x i. Введення та вилучення фіктивних змінних

Изображение слайда
10

Слайд 10

Булеві функції 10 Означення 2. 3. Функції f 1 (x 1, x 2,..., x n ) і f 2 (x 1, x 2,..., x m ) називаються рівними, якщо одну з них можна одержати із другої шляхом додавання або вилучення фіктивних аргументів. Існують два типи функцій, що не мають істотних змінних: функції першого типу тотожно дорівнюють 0, а другого – тотожно дорівнюють 1. Введемо до подальшого розгляду константи 0 та 1 (як функції від порожньої множини змінних). Зауваження. Якщо задано скінченну систему функцій з P 2 = {f 1,..., f s }, s  1, то можна вважати, що всі ці функції залежать від тих самих змінних x 1, ..., x n, тобто мають вигляд f 1 (x 1,..., x n ),..., f s (x 1,..., x n ). Рівність булевих функцій

Изображение слайда
11

Слайд 11

Булеві функції 11 Функції системи P 2 (1) 1. n = 0. |p 2 (0)| = 2. Маємо дві функції: це константи 0 та 1 (тотожні сталі).

Изображение слайда
12

Слайд 12

Булеві функції 12 Функції системи P 2 (2) 2. n = 1. |p 2 (1)| = 4. Функції f i (x) наведено у табличному вигляді (для спрощення таблиць надалі аргументи функцій у них не записуються). x f 1 f 2 f 3 f 4 0 0 0 1 1 1 0 1 0 1 Функції f 1 (x) = 0 та f 4 (x) = 1 – константи. f 2 (x) = = x – тотожна функція. Функція f 3 (x) називається запереченням x, f 3 (x) =. Операція називається операцією інверсії та описується як = 1, = 0.

Изображение слайда
13

Слайд 13

Булеві функції 13 Функції системи P 2 (3) 3. n = 2. |p 2 (2)| = 16. Функції f i (x) наведено у таблиці. x 1 x 2 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 10 f 11 f 12 f 13 f 14 f 15 f 16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Константа 0 Кон'юнкція Пряма антиімплікація Тотожна функція Обернена антиімплікація Тотожна функція Додавання за модулем 2 Диз'юнкція Стрілка Пірса Рівнозначність Заперечення Обернена імплікація Заперечення Імплікація Штрих Шеффера Константа 1 Функції системи P 2 (3) Для цих функцій, як правило, використовують позначення: f 2 – x 1  x 2 (або x 1  x 2 ); f 3 – x 1 x 2 ; f 5 – x 1 x 2 ; f 7 – x 1  x 2 ; f 8 – x 1  x 2 ; f 9 – x 1  x 2 ; f 10 – x 1  x 2 ; f 12 – x 1  x 2 ; f 14 – x 1  x 2 ; f 15 – x 1  x 2.

Изображение слайда
14

Слайд 14

Булеві функції 14 Функції системи P 2 (4) 4. n=3; |p 2 (3)|= 256. 5. n =4 ; |p 2 ( 4 )|= 6 5 53 6.

Изображение слайда
15

Слайд 15

Булеві функції 15 Основні властивості булевих операцій (1) Властивості булевих операцій використовуються для тотожних перетворень булевих (логічних) виразів. Властивості заперечення = x. Подвійне заперечення логічної (булевої) змінної еквівалентно булевій змінній.

Изображение слайда
16

Слайд 16

Булеві функції 16 Основні властивості булевих операцій ( 2 ) Властивості кон'юнкції x 1  x 2 = x 2  x 1 – переставний закон; x 0 = 0 – властивість нульової множини; x 1 = x – властивість незмінності; x x = x – властивість повторення; x = 0 – властивість додатковості ; x 1  (x 2  x 3 ) = (x 1  x 2 )  x 3 – сполучний закон (дужки можна опустити); (x 1  x 2 )  ( x 1  2 ) = x 1 – властивість склеювання.

Изображение слайда
17

Слайд 17

Булеві функції 17 Основні властивості булевих операцій ( 3 ) Властивості диз'юнкції x 1  x 2 = x 2  x 1 – переставний закон; x 0 = x – властивість незмінності; x 1 = 1 – властивість універсальної множини; x x = x – властивість повторення; x = 1 – властивість додатковості; x 1  (x 2  x 3 ) = (x 1  x 2 )  x 3 – сполучний закон (дужки можна опустити); x 1 x 2  x 1 2 = x 1 – властивість склеювання.

Изображение слайда
18

Слайд 18

Булеві функції 18 Основні властивості булевих операцій ( 4 ) Правила де Моргана x 1  x 2 = ; x 1  x 2 =. Правила дозволяють перейти від логічного множення до додавання та навпаки.

Изображение слайда
19

Слайд 19

Булеві функції 19 Основні властивості булевих операцій ( 5 ) Розподільна властивість: x 1  (x 2  x 3 ) = (x 1  x 2 ) (x 1  x 3 ) – логічного множення щодо логічного додавання; x 1  (x 2  x 3 ) = (x 1  x 2 ) (x 1  x 3 ) – логічного додавання щодо логічного множення.

Изображение слайда
20

Слайд 20

Булеві функції 20 Основні властивості булевих операцій ( 6 ) Властивості імплікації і рівнозначності x 1  x 2 = 1 x 2 ; x 1  x 2 = (x 1 x 2 )(x 2 x 1 ); x 1  x 2 = ( 1 x 2 )(x 1  2 ); x 1  x 2 = ( 1  2 )( x 1 x 2 ).

Изображение слайда
21

Слайд 21

Булеві функції 21 Основні властивості булевих операцій ( 7 ) Властивості функції додавання за модулем 2 x1  x2 =. Властивості функцій штрих Шеффера та стрілка Пірса x 1 |x 2 = ; x 1 |x 2 = ( 1  2 ); x 1  x 2 = ; x 1  x 2 = ( 1  2 ).

Изображение слайда
22

Последний слайд презентации: 1 Булеві функції Лекція 3 Булеві функції

Булеві функції 22

Изображение слайда