Минимизация логических функций

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

       В большинстве случаев для булевых функций имеется несколько различных представлений как ДНФ, так и КНФ. Для функции  от n переменной имеется  различных ДНФ.

       Индексом простоты или сложности булевой функции  является функция , определенная как множество всех ДНФ такой функции и обладающая следующими свойствами:

1. Не отрицательность – для любой ДНФ обозначением R выполнено ;

2. Монотонность - ;

3. Выпуклость - ;

4. Инвариантность – при получении  и  переименованием элементов без отождествления, тогда .

Виды индексов сложности:  – число переменных, встречающихся в формуле M;  – число элементарных конъюнкций в таком R для одного дизъюнкта – ранг логической функции;  – число символов отрицаний переменных в записи R.

       Обычно к сокращенной ДНФ переходят из ДНФ операциями поглощения и склеивания. Логическое произведение любого числа аргументов является элементарным преобразованием, если множители являются либо одиночные элементы, либо их отрицания. Законы поглощения имеют вид

Законы склеивания имеют вид

Перечисленные законы применяются для получения сокращённой ДНФ и скрещённой КНФ.

       Еще одним способом минимизации логических функций является применение карт Карно и Вейна. Данные карты содержат  ячеек со значениями функции в каждой из них. Ячейки сгруппированы так, что соединение ячейки описывается соседними произведениями переменных, отличающихся разными значениями. Два вида отличаются только обозначениями ячеек: карты Вейча – ячейки обозначаются названием переменных или отрицанием; карты Карно – отдельно указываются переменные и ячейки обозначаются набором из 0 и 1. Пример способа минимизации логической функции с помощью карт Карно представлен на рисунке 66.

 

Рисунок 66. Минимизация логической функции с помощью карт Карно.

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

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

       Способ минимизации логической функции на двоичном кубе размерности n подразумевает построение его с вершинами – наборами значений переменных и заполнением значениями функции. При наличии ребра между вершинами, можно по закону склейки получить один дизъюнкт ранга 1. Обычно двоичный куб проецируется на плоскость. В общем случае при наличии ребра при  двух вершин, тогда для них существует общий для них набор значений с прочерком переменных с различными значениями. Набор, полученный после упрощения дизъюнктов, дает сокращенную ДНФ.

       Метод минимизации Квайна-Макласске подразумевает выполнение указанных последовательных действий

1. Для логической функции  составляется таблица истинности;

2. Составляется сокращенная ДНФ или сокращенная КНФ;

3. Составляется набор имплекантов, по которому составляется базисный набор – одна из комбинаций минимальной ДНФ – МДНФ.

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

1. Если при некотором значении имплекант ;

2. Исключение хотя бы одного множителя для  исключает выполнение свойства 1.

Если на некотором наборе  – значений переменных , тогда имплекант накрывает эту единицу для .

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

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

       В общем случае минимизацию логической функции и ТДНФ можно получить методом Петрика. Все имплеканты обозначают латинскими буквами, каждый столбец дает один элемент конъюнкции, для покрывающих элементов дается дизъюнкция. Полученное выражение упрощается логическими тождествами.

 

Логика высказываний

       Логика высказываний является теорией тех логических связей, которые не зависят от структуры простых высказываний или содержания. Такая логика состоит из двух допущений: всякое высказывание является либо истинным, либо ложным с отсутствием других вариантов и значение истина сложного высказывания зависит от значений, входящих в него простых высказываний и от характера связей.

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

       Если высказывание является верным при любых значениях переменных, тогда данное высказывание называется тавтологией. Основные виды связок высказываний, при участии простых высказываний А и B:

1. Отрицание вида «НЕ A»;

2. Конъюнкция вида «A и B», «A, но B» или «A, а B»;

3. Дизъюнкция вида «A или B»;

4. Строгая дизъюнкция вида «A либо B»;

5. Эквиваленция вида «A если и только если B» или «для A необходимо и достаточно B» - для логических тождеств;

6. Импликация вида «если A, то B», «для B достаточно A» или «B является необходимым для A»;

7. Скобки – изменяют порядок действий, допуская более сложные высказывания с применением перечисленных.

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

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

Решением является множество всех пар , при которых каждое неравенство является верным. В данном случае решением системы неравенств являются две полуплоскости с границами  соответственно.

       Системы неравенств и уравнений можно задать конъюнкцией

Эту же область можно задать соотношением значений и переменных. Логическим выражением также можно описать необходимую область на плоскости.

       Предикат – высказывание с логическим значением и его зависимостью от одной или нескольких переменных. Природа переменных даже в одном предикате может быть самой разнообразной. При определенном наборе значений переменных получим одно значение предиката.

       Для обозначения переменных используются специальные символы – кванторы. Кванторы подразделяются на два основных вида: квантор всеобщности  и квантор существования . В сложных высказываниях встречаются отрицания этих кванторов. Привала отрицания да предикатов и кванторов имеют вид

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

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

       Если для многоместного предиката распространяется действие нескольких кванторов, тогда однотипные кванторы можно переставлять

Преставление кванторов разного вида меняет смысл высказывания.

       Можно для множеств значений переменных указывать их подмножества, для элементов которых высказывания с кванторами будет верным, получая их область истинности.