Лабораторная работа № 2

ТЕМА: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. КАРТЫ КАРНО.

ЦЕЛЬ:

1. Освоение способов минимизации булевых функций с использованием карт Карно и алгоритма Квайна.

2. Изучение способов приведения формул к ДНФ, КНФ, СДНФ и СКНФ.

ВОПРОСЫ ДЛЯ ПОВТОРЕНИЯ:

1. Понятие ДНФ и КНФ. Алгоритм приведения формулы к ДНФ и КНФ.
2. Совершенный одночлен. Понятие СДНФ и СКНФ. Алгоритм приведения формул к СДНФ и СКНФ.
3. Алгоритм нахождения СДНФ и СКНФ формулы по известным таблицам истинности.
4. Понятие элементарного произведения формул
5. Определение импликанты формулы и импликанты функции. Понятие простой импликанты. Способ нахождения импликант формулы.
6. Определение сокращенной ДНФ. Понятие тупиковой и минимальной ДНФ.
7. Определение операций полного поглощения, неполного и полного склеивания формул. Теорема Квайна.
8. Использование матрицы Квайна для нахождения сокращенной и минимальной ДНФ формулы.
9. Понятие о картах Карно. Изображение булевых функций с использованием карт Карно.
10. Алгоритм нахождения минимальной ДНФ с использованием карт Карно.

ЛИТЕРАТУРА:

1. В.Н. Нефедов, В.А. Осипова Курс дискретной математики. – М.: МАИ, 1992.–264 с.: ил.
2. О. П. Кузнецов, Г.М. Адельсон-Вельский Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.– 480 с.: ил.
3. Ф.А. Новиков Дискретная математика для программистов.– СПб.: Питер, 2004.– 302 с.: ил.
4. С.В. Судоплатов, Е.В. Овчинникова Элементы дискретной математики: Учебник. – М.: ИНФРА-М; Новосибирск: НГТУ, 2003.– 280 с.
5. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики. – М.:Форум-Инфра-М, 2004. – 128 с.
6. А.Н. Колмогоров, А.Г. Драгрлин Математическая логика. –М.: Едиториал УРСС, 2004. – 240 с.
7. Г.П. Гаврилов, А.А. Сапоженко Сборник задач по дискретной математике. –М.: Наука, 1977. – 368 с.

Краткая теория

Если х – логическая переменная, dÎ{0,1}, то выражение называется литерой.

Литеры х и называются контрарными литерами.

Элементарной конъюнкцией или конъюнктором называется конъюнкция литер.

Элементарной дизъюнкцией или дизъюнктором называется дизъюнкция литер.

Пример: -дизъюнктор

- конъюнктор

- одновременно конъюнктор и дизъюнктор

Дизъюнктивной нормальной формой (ДНФ) – называется дизъюнкция конъюнкторов.

Конъюнктивной нормальной формой (КНФ) – называется конъюнкция дизъюнкторов.

Теорема:

1. Для любой формулы существует эквивалентная ей дизъюнктивная нормальная форма.
2. Для любой формулы существует эквивалентная ей конъюнктивная нормальная форма.

Одночлен называется совершенным, если каждая входящая в него переменная входит в него точно один раз со знаком отрицания или без него.

Нормальная форма от некоторых переменных называется совершенной нормальной формой, если каждый входящий в нее одночлен является совершенным одночленом от тех же переменных.

Пусть имеем некоторый набор логических переменных (х₁х₂…х_n) и набор нулей и единиц D=(d₁d₂…d_n).

Конституентой единицы набора D называется конъюнктор вида:

Конституентой нуля набора D называется дизъюнктор вида: .

Заметим, что и тогда и только тогда, когда , , … .

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. Совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых

Конструктивно СДНФ и СКНФ для каждой формулы алгебры высказываний, приведенной к ДНФ или КНФ можно определить следующими свойствами.

Совершенной дизъюнктивной нормальной формой(СДНФ) формулы называется ее ДНФ, обладающая следующими свойствами:

1. ДНФ не содержит двух одинаковых конъюнкторов.

2. Ни один из конъюнкторов не содержит одновременно двух одинаковых переменных.

3. Ни один из конъюнкторов не содержит одновременно некоторую переменную и ее отрицание.

4. Каждый конъюнктор содержит либо переменную, либо ее отрицание для всех переменных входящих в формулу.

Дата добавления: 2017-02-01