Презентация на тему: Практическое занятие №3. Минимизация булевых функций. Реализация булевых

Реклама. Продолжение ниже
Практическое занятие №3. Минимизация булевых функций. Реализация булевых функций в заданном базисе
Основные соотношения булевой алгебры.
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Формулы Огастеса де Моргана
Минтерм. Совершенная дизъюнктивная нормальная форма.
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Макстерм. Совершенная конъюнктивная нормальная форма.
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Все методы минимизации основаны на применении трёх операций:
Склеивание
Поглощение
Неполное склеивание
Базис
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Практическое занятие №4. Минимизация частично определённых булевых функций с помощью карт Карно
Частично определённая булева функция
МЕТОД МИНИМИЗАЦИИ С ПОМОЩЬЮ КАРТ КАРНО
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Соседние клетки карты Карно
Заполнение карты Карно
Покрытия карты Карно
Формирование покрытий
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
Минимизация частично определенных булевых функций
Термы, контермы, дизтермы и их порядки.
Дизъюнктивные нормальные формы.
Конъюнктивные нормальные формы.
Практическое занятие №3. Минимизация булевых функций. Реализация булевых
1/29
Средняя оценка: 4.7/5 (всего оценок: 83)
Код скопирован в буфер обмена
Скачать (2189 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Практическое занятие №3. Минимизация булевых функций. Реализация булевых функций в заданном базисе

Цель:  получение навыков минимизации булевых функций с использованием операций склеивания, поглощения и неполного склеивания, а также знакомство с реализацией булевых функций в различных базисах. 1. Основные соотношения булевой алгебры. 2. Формулы Огастеса де Моргана. 3. Минтерм. Совершенная дизъюнктивная нормальная форма. 4. Макстерм. Совершенная конъюнктивная нормальная форма. 5. Операции склеивания, поглощения и неполного склеивания. 6. Базисы булевых функций. Вывод.

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

Слайд 2: Основные соотношения булевой алгебры

Двойное отрицание переменной равно самой переменной :

Изображение слайда
Изображение для работы со слайдом
1/2
3

Слайд 3

Иные соотношения получены из таблицы истинности двух переменных : & 0 x 0=x x&0=0 x 0=x = =1 = 1 x 1=1 x&1=x x 1= =x = =0 x x x=x x&x=x x x=0 =1 = = x =1 x& =0 x =1 =0 =1 =0 & 0 x&0=0 1 x&1=x x x&x=x

Изображение слайда
Изображение для работы со слайдом
1/2
4

Слайд 4: Формулы Огастеса де Моргана

устанавливают связь между функциями конъюнкции и дизъюнкции : Отрицание дизъюнкции равно конъюнкции отрицаний : Отрицание конъюнкции равно дизъюнкции отрицаний : Формулы де Моргана справедливы и для n переменных.

Изображение слайда
Изображение для работы со слайдом
1/2
5

Слайд 5: Минтерм. Совершенная дизъюнктивная нормальная форма

При переходе от табличного описания комбинационного устройства к алгебраическому описанию в СДНФ каждому i -ому набору входных переменных ставится в соответствие минтерм ( конституента единицы), представляющий собой логическое произведение всех входных переменных. СДНФ – представление функции в виде логической суммы минтермов, для которых = 1, где i – номер набора логических переменных

Изображение слайда
Изображение для работы со слайдом
1/2
6

Слайд 6

Совершенная дизъюнктивная нормальная форма операции F( )=1 0 F( )= i 0 0 0 1 1 0 1 0 2 1 0 1 3 1 1 0 i 0 0 0 1 1 0 1 0 2 1 0 1 3 1 1 0

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
7

Слайд 7: Макстерм. Совершенная конъюнктивная нормальная форма

При переходе от табличного описания комбинационного устройства к алгебраическому описанию в СКНФ каждому i -ому набору входных переменных ставится в соответствие макстерм ( конституента нуля), представляющий собой логическую сумму всех входных переменных, причём, если = 0, то переменная входит в сумму в прямом виде, а если = 1, то – в инверсном. СКНФ – представление функции в виде логического произведения макстермов, для которых = 0, где i – номер набора логических переменных.

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
8

Слайд 8

Совершенная конъюнктивная нормальная форма операции F( ) = ) ) (0 ) (0 ) F( ) = ( ) i 0 0 0 1 1 0 1 1 2 1 0 0 3 1 1 0 i 0 0 0 1 1 0 1 1 2 1 0 0 3 1 1 0

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
9

Слайд 9: Все методы минимизации основаны на применении трёх операций:

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

Слайд 10: Склеивание

Две конъюнкции называются соседними, если они имеют одинаковую длину и отличаются знаком инверсии только одной переменной. Две соседние конъюнкции склеиваются, т.е. вместо них можно записать одну конъюнкцию, длина которой на единицу меньше длины исходных конъюнкций где P – конъюнкция произвольной длины, i – номер логической переменной. Например : Назад

Изображение слайда
Изображение для работы со слайдом
1/2
11

Слайд 11: Поглощение

Конъюнкция, входящая в другие конъюнкции большей длины, «поглощает» их : где P – конъюнкция произвольной длины, i – номер логической переменной. Например : Назад

Изображение слайда
Изображение для работы со слайдом
1/2
12

Слайд 12: Неполное склеивание

где P – конъюнкция произвольной длины, i – номер логической переменной. Из операции неполного склеивания следует, что каждая из склеиваемых конъюнкций может быть использована для склеивания с другими соседними конъюнкциями. Например : Назад

Изображение слайда
Изображение для работы со слайдом
1/2
13

Слайд 13: Базис

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

Слайд 14

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

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: Практическое занятие №4. Минимизация частично определённых булевых функций с помощью карт Карно

Цель:  получение основных навыков минимизации частично определённых булевых функций с помощью карт Карно. 1. Частично определённая булева функция, заданная с помощью таблицы истинности. 2. Карты Карно. 3. Термы, контермы, дизтермы и их ранги. 4. Дизъюнктивные нормальные формы. 5. Конъюнктивные нормальные формы. Вывод.

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

Слайд 16: Частично определённая булева функция

Не полностью определенной называют такую булеву функцию n переменных, значения которой определены не на всех 2 n наборах значений переменных. Неопределенность значения функции обозначают символом «~», либо «х». i F 0 0 0 0 0 1 0 0 1 1 2 0 1 0 x 3 0 1 1 x 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 x i F 0 0 0 0 0 1 0 0 1 1 2 0 1 0 x 3 0 1 1 x 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 x

Изображение слайда
Изображение для работы со слайдом
1/2
17

Слайд 17: МЕТОД МИНИМИЗАЦИИ С ПОМОЩЬЮ КАРТ КАРНО

Карты Карно представляют собой таблично-графический метод минимизации булевых функций, позволяющий получить минимальную дизъюнктивную нормальную форму. Карта Карно - это таблица специального вида, имеющая клеток, где n - число логических переменных. Каждой клетке карты Карно соответствует определенный минтерм. Пример карты Карно 3 -х переменных : 0 1 5 4 2 3 7 6

Изображение слайда
Изображение для работы со слайдом
1/2
18

Слайд 18

Каждая клетка карты Карно имеет уникальный номер (адрес), который является десятичным эквивалентом соответствующего минтерма. i 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 i 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
19

Слайд 19

Зоной называется часть карты Карно, в которую соответствующая переменная входит либо только без знака инверсии, либо только со знаком инверсии. В карте Карно n переменных имеется зон. Линии, разделяющие карту Карно на зоны называются осями карты Карно ( O ). Увеличение размера карты Карно происходит последовательно и циклически : сначала добавляется новая зона по вертикали, затем – по горизонтали. Увеличение размера происходит до тех пор, пока не будут использованы все логические переменные.

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
20

Слайд 20: Соседние клетки карты Карно

Каждой клетке карты Карно n переменных соответствует n соседних клеток. Все соседние клетки симметричны относительно какой-либо оси карты. Соседние клетки соответствуют соседним конъюнкциям при выполнении операции склеивания.

Изображение слайда
Изображение для работы со слайдом
1/2
21

Слайд 21: Заполнение карты Карно

i F 0 0 0 0 1 1 0 0 1 1 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 1 6 1 1 0 0 7 1 1 1 1 i F 0 0 0 0 1 1 0 0 1 1 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 1 6 1 1 0 0 7 1 1 1 1

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
22

Слайд 22: Покрытия карты Карно

Покрытием единичных значений булевой функции в карте Карно называется набор клеток, в которых проставлены единицы. При этом покрытие должно состоять из клеток, где называют рангом покрытия карты Карно n переменных. Например, две единичные клетки составляют покрытие первого ранга (одна ранее найденная и любая симметричная ей относительно какой-либо оси карты).

Изображение слайда
Изображение для работы со слайдом
1/2
23

Слайд 23: Формирование покрытий

При нанесении покрытий на карту Карно следует руководствоваться следующими принципами: число покрытий должно быть минимальным ; покрытия должны быть максимально возможного ранга. Необходимо взять произвольную клетку с единичным значением и просмотреть соседние к ней клетки на предмет увеличения ранга покрытия.

Изображение слайда
Изображение для работы со слайдом
1/2
24

Слайд 24

Производить увеличение ранга покрытия до тех пор, пока дальнейшее увеличение будет невозможным. Если осталась хотя бы одна не покрытая единица, то необходимо создать новое покрытие на её базе. М Д Н Ф

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
25

Слайд 25: Минимизация частично определенных булевых функций

Не полностью определенная булева функция должна быть доопределена таким образом, чтобы все единичные значения функции накрывались минимальным числом покрытий как можно более высокого ранга. После того как все единичные значения функции накрыты покрытиями, во все остальные клетки проставляют нули.

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

Слайд 26: Термы, контермы, дизтермы и их порядки

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

Слайд 27: Дизъюнктивные нормальные формы

Формула G имеет  дизъюнктивную нормальную форму  (сокращенно: ДНФ), если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций. G = ∧ ∧…∧ Например

Изображение слайда
Изображение для работы со слайдом
1/2
28

Слайд 28: Конъюнктивные нормальные формы

Формула G имеет  конъюнктивную нормальную форму  (сокращенно: КНФ)Б если она является элементарной дизъюнкцией или конъюнкцией элементарных дизъюнкций. G = … Например

Изображение слайда
Изображение для работы со слайдом
1/2
29

Последний слайд презентации: Практическое занятие №3. Минимизация булевых функций. Реализация булевых

Данный практикум позволяют получить базовые знания о минимизации частично определённых булевых функций с помощью карт Карно.

Изображение слайда
1/1
Реклама. Продолжение ниже