Приоритет выполнения логических операций

Для логических операций в одном логическом выражении установлен следующий порядок вычислений:

· отрицание – первый, наивысший приоритет;

· конъюнкция – второй приоритет;

· дизъюнкция, разделительная дизъюнкция – третий приоритет;

· импликация, эквивалентность – низший приоритет.

Изменить порядок выполнения операций можно с помощью расстановки скобок.

В алгебре логики дизъюнкция (логическое сложение) играет роль, аналогичную сложению в алгебре действительных чисел, конъюнкция (логическое умножение) – умножению, а отрицание (инверсия значения логической формулы) – унарному минусу (инверсия знака обычной формулы). Операция эквивалентность аналогична операции отношения “=”, а операция импликация – операции отношения “ ”.

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Исходными, из соображений удобства последующих преобразований, приняты следующие две канонические формы представления функций: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые.

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые

Всякую дизъюнкцию элементарных конъюнкций называют дизъюнктивной нормальной формой, то есть ДНФ.

Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ.

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

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

Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи – минимизации.

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

Существуют два направления минимизации:

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

2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу).

Но ни один из способов минимизации не является универсальным

Для минимизации функций алгебры логики был разработан ряд методов:

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

2. метод минимизации логических функций при помощи карт Карно;

3. метод Квайна-Мак-Класки;

4. метод Блейка-Порецкого;

5. метод Петрика и другие.

Остановимся более подробно на первых двух методах.

Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики [11].

При применении данного метода:

1. Записываются СДНФ логических функций,

2. Форма преобразуется и упрощается с использованием аксиом алгебры логики, при этом, в частности, выявляются в исходном СДНФ соседние термы (члены), в которых есть по одной не совпадающей переменной.