Презентация на тему: БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ)

БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ). СОВЕРШЕННЫЕ ДНФ и КНФ
Цель лекции – изучить способы представления булевых функций в виде дизъюнктивных и конъюнктивных нормальных форм, а также их совершенных форм, определить связь
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ).
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ).
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ).
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ).
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ).
Теорема Шеннона
Time-Out
Эквивалентность форм ДНФ и КНФ
Сложность формы булевой функции
Пример оценки сложности функции
Пример дизъюнктивного разложения по Шеннону
Выводы
Тест-задание
1/15
Средняя оценка: 4.1/5 (всего оценок: 35)
Код скопирован в буфер обмена
Скачать (1397 Кб)
1

Первый слайд презентации: БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ). СОВЕРШЕННЫЕ ДНФ и КНФ

1 БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ). СОВЕРШЕННЫЕ ДНФ и КНФ ЛЕКЦИЯ 8 В.И.ХАХАНОВ Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА

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

Слайд 2: Цель лекции – изучить способы представления булевых функций в виде дизъюнктивных и конъюнктивных нормальных форм, а также их совершенных форм, определить связь и различие между ними, выявить их назначение

2 Цель лекции – изучить способы представления булевых функций в виде дизъюнктивных и конъюнктивных нормальных форм, а также их совершенных форм, определить связь и различие между ними, выявить их назначение Содержание: ДНФ и КНФ СДНФ и СКНФ Теорема Шеннона Тема: ДНФ и КНФ. СДНФ и СКНФ.

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

Слайд 3

3 Горбатов В.А. Основы дискретной математики. М.: Высш. шк., 1986. 32-61с. Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. 272 с. Беннеттс Р.Д. Проектирование тестопригодных логических схем: Пер. с англ. М.: Радио и связь. 1990. 176 с. Бондаренко М.Ф., Кривуля Г.Ф., Рябцев В.Г., Фрадков С.А., Хаханов В.И. Проектирование и диагностика компьютерных систем и сетей. К.: НМЦ ВО. 2000. 306 с. Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, 1986. 240с. Хаханов В.И. Техническая диагностика элементов и узлов персональных компьюторов. К.: ИСМО, 1997. 308 с. Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с. Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 263-268. Литература

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

Слайд 4

4 Базовые понятия: логические операции логические переменные логические функции Термины Ключевые слова: первичный терм конъюнктивный терм дизъюнктивный терм дизъюнктивная нормальная форма (ДНФ) конъюнктивная нормальная форма (КНФ) совершенная ДНФ совершенная КНФ

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

Слайд 5

5 ДНФ и КНФ Термин Обозначение Пример Первичный терм x 1, x 1 Двоичный набор (0,1,1,0,1) Элементарная конъюнкция (ЭК) x 1 x 2 x 3 x 4 ДНФ x 1 x 2 x 3  x 1 x 2 Элементарная дизъюнкция (ЭД) x 1  x 2  x 3  x 4 КНФ (x 1  x 2  x 3 ) ( x 1  x 2 )

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

Слайд 6

6 Def: Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, от котор ых зависит функция, причем каждую – только один раз (включая вхождения под знаком отрицания). Def: Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, от которых зависит функция, причем каждую переменную – только один раз. Совершенные ДНФ и КНФ (СДНФ и СКНФ). 1

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

Слайд 7

7 Пример получения СДНФ и СКНФ x 1 x 2 x 3 f(x 1, x 2, x 3 ) x 1 x 2 x 3 f(x 1, x 2, x 3 ) 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1

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

Слайд 8: Теорема Шеннона

8 Теорема Шеннона Любая булева функция f 0 представима в виде разложения Шеннона: Следствие Предельное разложение Шеннона ( k=n ) булевой функции f 0 имеет вид

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

Слайд 9: Time-Out

9 Time-Out

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

Слайд 10: Эквивалентность форм ДНФ и КНФ

10 Эквивалентность форм ДНФ и КНФ Привести функцию к ДНФ и КНФ: Получение ДНФ: Получение КНФ

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

Слайд 11: Сложность формы булевой функции

11 Сложность формы булевой функции Оценка сложности функции по Квайну есть Q=L(f)+k, где L(f) – число букв, k – число конъюнктивных термов функции. Уменьшить функцию или ее сложность можно с помощью законов булевой алгебры.

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

Слайд 12: Пример оценки сложности функции

12 Пример оценки сложности функции Уменьшить функцию и оценить ее сложность Оценка сложности по Квайну: Q=L(f)+k=12+4=16 Сложность по Квайну: Q=L(f)+k=7+3=10

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

Слайд 13: Пример дизъюнктивного разложения по Шеннону

13 Пример дизъюнктивного разложения по Шеннону Получить дизъюнктивное разложение функции по переменным x, z: Разложение по указанным переменным имеет вид: Вычисление составляющих дает: Искомое разложение:

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

Слайд 14: Выводы

14 Выводы Всякая ФАЛ может быть реализована формулой, оперирующей символами , , ¬, скобками и знаком равенства Любая булева функция может быть представлена в виде ДНФ, КНФ, СДНФ, СКНФ ДНФ и КНФ есть сокращенная форма записи СДНФ и СКНФ (таблицы истинности) ДНФ есть наиболее распространенная форма описания цифровых систем, максимально приближенная к аппаратурной реализации ДНФ КНФ СДНФ СКНФ

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

Последний слайд презентации: БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ): Тест-задание

15 Тест-задание Определить сложность функции по Квайну

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