|
Минимизация логических функций
Высказывание – это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет; это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками)
Различные логические выражения (высказывания) могут принимать только два значения: «истинно» или «ложно». Каждая логическая переменная может принимать только одно значение.
Высказывания могут быть простыми и сложными. Простые – соответствуют алгебраическим переменным, а сложные являются аналогом алгебраических функций. Функции могут получаться путем объединения переменных с помощью логических действий (операций) .
Логические операции для двух простых высказываний
Результат функции а/ b
Логическая функция – это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.
Каждая логическая функция может быть задана большим количеством различных по виду функций. Но даже любую достаточно сложную логическую функцию можно реализовать, имея относительно простой набор базовых логических операций. Наиболее известный базис – это набор функций «и», «или», «не».
Для операций конъюнкции, дизъюнкции и инверсии определены законы, позволяющие производить тождественные (равносильные) преобразования логических выражений:
Законы и правила для преобразований сложных высказываний:
1. 9.
2. 10.
3. 11.
4. 12.
5. 13.
6. 14.
7. 15.
8. 16.
Приоритет выполнения логических операций
Для логических операций в одном логическом выражении установлен следующий порядок вычислений:
· отрицание – первый, наивысший приоритет;
· конъюнкция – второй приоритет;
· дизъюнкция, разделительная дизъюнкция – третий приоритет;
· импликация, эквивалентность – низший приоритет.
Изменить порядок выполнения операций можно с помощью расстановки скобок.
В алгебре логики дизъюнкция (логическое сложение) играет роль, аналогичную сложению в алгебре действительных чисел, конъюнкция (логическое умножение) – умножению, а отрицание (инверсия значения логической формулы) – унарному минусу (инверсия знака обычной формулы). Операция эквивалентность аналогична операции отношения “=”, а операция импликация – операции отношения “ ”.
Основываясь на законах, можно выполнять упрощение сложных логических выражений. Исходными, из соображений удобства последующих преобразований, приняты следующие две канонические формы представления функций: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые .
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые
Всякую дизъюнкцию элементарных конъюнкций называют дизъюнктивной нормальной формой, то есть ДНФ .
Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ .
Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .
Совершенной КНФ (СКНФ) называется КНФ, в которой нет равных элементарных дизъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .
Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации.
Определение :Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией.
Существуют два направления минимизации:
1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.
2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу).
Но ни один из способов минимизации не является универсальным
Для минимизации функций алгебры логики был разработан ряд методов:
1. метод непосредственных преобразований логических функций;
2. метод минимизации логических функций при помощи карт Карно;
3. метод Квайна-Мак-Класки;
4. метод Блейка-Порецкого;
5. метод Петрика и другие.
Остановимся более подробно на первых двух методах.
Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики [11].
При применении данного метода:
1. Записываются СДНФ логических функций,
2. Форма преобразуется и упрощается с использованием аксиом алгебры логики, при этом, в частности, выявляются в исходном СДНФ соседние термы (члены), в которых есть по одной не совпадающей переменной.
Выполнить минимизацию следующих логических функций:
Воспользуемся методом непосредственных преобразований, для чего сгруппируем элементарные конъюнкции и вынесем общие множители за скобку, после чего применим преобразование (13):
Повторим операцию группировки, вынесения общего множителя и преобразования:
Применим преобразование (5):
Задания для самостоятельного решения:
Выполнить минимизацию следующих логических функций:
| 
