Презентация на тему: Практическое занятие №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. Базисы булевых функций. Вывод.

2

Слайд 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

4

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

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

5

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

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

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

7

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

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

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

9

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

10

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

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

11

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

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

12

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

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

13

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

14

Слайд 14

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

15

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

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

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

17

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

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

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

19

Слайд 19

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

20

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

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

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

22

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

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

23

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

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

24

Слайд 24

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

25

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

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

26

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

27

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

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

28

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

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

29

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

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

Похожие презентации

Ничего не найдено