Уроки математики / Презентация / Презентация "Минимизация булевых функций" по дисциплине "Элементы математической логики"

Презентация "Минимизация булевых функций" по дисциплине "Элементы математической логики"

Минимизация булевых функций Беляева Татьяна Юрьевна ГБПОУ КК «Армавирский маш...
Упрощение булевых функций Непосредственно с помощью логических тождеств Алгор...
Упрощение булевых функций Для минимизации булевых функций используется закон...
Карты Карно являются графическим способом минимизации булевых функций
Требования к картам Карно • Число клеток карты равно 2ⁿ, где п - число переме...
Карты Карно для 2-х переменных х2 х2 х1 х1
Карты Карно для 3-х переменных х2 х2 х2 х2 х1 х1 х3 х3 х3 х3
Карты Карно для 4-х переменных х2 х2 х2 х2 х1 х3 х1 х3 х1 х3 х1 х3 х4 х4 х4 х4
Алгоритм работы с картами Карно Для получения минимальной функции охватывают...
ПРИМЕР 1. Пусть функция задана таблицей истинности: СДНФ: f = (x1 /\ x2) \/ (...
ПРИМЕР 2. Пусть задана функция: f = (x1 /\ x2 /\ x3) \/ (x1 /\ x2 /\ x3) \/ (...
ПРИМЕР 3. Пусть задана функция: f = (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3...
1 из 12

Описание презентации по отдельным слайдам:

№ слайда 1

Минимизация булевых функций Беляева Татьяна Юрьевна ГБПОУ КК «Армавирский машиностроительный техникум» Преподаватель математических дисциплин

№ слайда 2

Упрощение булевых функций Непосредственно с помощью логических тождеств Алгоритмическими методами карты Карно (при числе переменных не более шести) метод Квайна–Мак–Класки (если переменных больше шести)

№ слайда 3

Упрощение булевых функций Для минимизации булевых функций используется закон попарного склеивания и поглощения: «Если переменная изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения» Операция попарного склеивания осуществляется между 2-мя членами (термами), у которых совпадают вхождения для всех переменных, кроме одной. Т.о., главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением. Например: 1) f = (x1 /\ x2) \/ (x1 /\ x2) = x1 /\ (x2 \/ x2) = x1 /\ 1 = x1 2) f = (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3 /\ x4) = (x1 /\ x2 /\ x4) /\ (x3 \/ x3) = x1 /\ x2 /\ x4

№ слайда 4

Карты Карно являются графическим способом минимизации булевых функций

№ слайда 5

Требования к картам Карно • Число клеток карты равно 2ⁿ, где п - число переменных функции. • Столбцы и строки карты обозначаются прямыми и инверсными переменными данной функции таким образом, чтобы любые соседние клетки по строкам или столбцам отличались бы между собой значением только одной переменной. • Каждая клетка карты соответствует произведению переменных, на пересечении которых она находится. (!!) Клетки, находящиеся на границах одной строки или столбца, также считаются соседними.

№ слайда 6

Карты Карно для 2-х переменных х2 х2 х1 х1

№ слайда 7

Карты Карно для 3-х переменных х2 х2 х2 х2 х1 х1 х3 х3 х3 х3

№ слайда 8

Карты Карно для 4-х переменных х2 х2 х2 х2 х1 х3 х1 х3 х1 х3 х1 х3 х4 х4 х4 х4

№ слайда 9

Алгоритм работы с картами Карно Для получения минимальной функции охватывают областями все соседние клетки, имеющие значение 1, и исключают переменные, имеющие прямое и инверсное включения. Объединяют клетки по следующим правилам: 1) Число объединяемых клеток может быть равно 2, 4, 8, 16,… 2) Объединять надо как можно больше клеток 3) Самих объединений должно быть как можно меньше

№ слайда 10

ПРИМЕР 1. Пусть функция задана таблицей истинности: СДНФ: f = (x1 /\ x2) \/ (x1 /\ x2) Составим для этой функции карту Карно: f = x1 1 1 х1 х2 f 1 1 1 1 0 1 0 1 0 0 0 0 х2 х2 х1 1 1 х1 0 0

№ слайда 11

ПРИМЕР 2. Пусть задана функция: f = (x1 /\ x2 /\ x3) \/ (x1 /\ x2 /\ x3) \/ (x1 /\ x2 /\ x3) \/ (x1 /\ x2 /\ x3) \/ (x1 /\ x2 /\ x3) Составим для этой функции карту Карно: Прямоугольник, содержащий 4 единицы в 1-й строке, позволяет исключить переменные х2 и х3. Прямоугольник, содержащий 2 единицы в 1-м столбце, - переменную х1. Т.о.: f = x1 \/ (x2 /\ x3) 1 1 1 1 1 1 х2 х2 х2 х2 х1 1 1 1 1 х1 1 х3 х3 х3 х3

№ слайда 12

ПРИМЕР 3. Пусть задана функция: f = (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3 /\ x4) \/ (x1 /\ x2 /\ x3 /\ x4) Составим для этой функции карту Карно: 4 единицы по углам таблицы позволяет исключить переменные х1 и х2. 2 соседние единицы в 1-й строке - переменную х4. Т.о.: f = (x3 /\ x4) \/ (x1 /\ x2 /\ x3) 1 1 1 1 1 1 x2 x2 x2 x2 x1 1 1 1 x3 x1 x3 x1 x3 x1 1 1 x3 x4 x4 x4 x4

Автор
Дата добавления 21.12.2018
Раздел Высшая математика
Подраздел Презентация
Просмотров95
Номер материала 6000
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.