Преобразование логических выражений

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


f(x1,X2...,Xn)- это сумма произведений, в каждое из которых каждая переменная входит ровно один раз, либо с отрицанием, либо без него.

Пример дизъюнктивной нормальной формы:

f (А,В,С)=(А/\В/\)V(/\/\С)

Конъюнктивная нормальная форма выражения


f(x1,X2...,Xn)
- это произведение сумм, в каждое из которых каждая переменная входит ровно один раз, либо с отрицанием, либо без него.

    Пример конъюнктивной нормальной формы:

f(A,B,C)=(AVBV)/\(VVC)
Используя выписанные теоремы (см. Теоремы Булевой алгебры), можно привести любое логическое выражение к нормальной форме - конъюнктивной или дизъюнктивной.
Задача. Привести выражение (А/\В) V) а) к конъюнктивной и б) к дизъюнктивной нормальным формам.
Решение.

  •  
    •  
      •  
          (А /\В) V = (по теореме 10б)
          = (А/\В) V ( V ) = (по теореме 6)
          = (А /\В) V (А V ).= (по теореме 11а)

= (А /\ В) V А V б) Полученное выражение напоминает дизъюнктивную нормальную форму, только в первом слагаемом отсутствует переменная С, во втором - переменные В и С, а в третьем - переменные А и В. Для того, чтобы ввести в эти слагаемые недостающие переменные, проделаем с первым слагаемым следующие преобразования:
(А /\В) = (А /\В) /\1 = (По теореме 2б)
= (А /\В) /\ V ) = (По теореме 5а)
= ((А /\ В) /\ ) V ((А /\ В) /\ ) == (По теореме 12б)
=(А/\В/\С7)У(А/\В/\ )
Теперь проделаем те же действия со вторым слагаемым:
А = (по теореме 26)
= А /\ 1 = (по теореме 5а) = А /\ (В V ) = (по теореме 126) = (А /\ В) V (А /\) = (по теореме 26)
= ((А /\ В) /\ 1) V ((А /\ ) /\ 1) = (по теореме 5а)
= ((А /\ В) /\ (GV)) V ((А /\) /\ (CV)) = (по теореме 12б)
= (((А /\ В) /\ С) V ((А /\В) /\))V(((А/\) /\ С) V ((А /\ ) /\ () = (по теореме 11 б)
= ((A/\B/\G)V(A/\B/\))V((A/\/\C)V(A/\/\))= (по теореме 11а)

=(А/\В/\С)У(А/\В/\)У(А/\/\ С)V (А/\/\)

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


= (А /\ В /\ ) V ( /\ В /\ ) V (А /\ /\ ) V (/\/\ )Теперь сводим результаты преобразования всех слагаемых в одну формулу:
(А/\В/\С) V(А/\В/\)V
V(А/\В/\С)V(А/\В/\)V(А/\/\С)V(А/\/\)V V(А/\В/\)V(/\В/\)V(А/\/\)V(/\/\)
Воспользуемся теоремой 4а V x=x) и сократим одинаковые слагаемые. Получаем ответ б) (дизъюнктивная нормальная форма):
(А /\ В) V = (А /\В /\ С) V (А /\ В /\ ) V (А /\/\ C)V

    У(А/\/\)У(/\В/\)У(/\/\)
    а)

(А /\ В) V А V = (по теореме 11а)
= (А /\ В) V (А V ) == (по теореме 7а)
= (А V ) V (А /\ В) == (по теореме 12а)
= ((А V ) V А) /\ ((А V) V В) = (по теореме 11а)
= (AVVA)A(AVVB)=(no теореме 7а)
= (А V А V ) /\ (А V В V ) = (по теореме 4а)
= (А V) /\ (А V В V) == (по теореме 2а)
= ((А V) V 0) /\ (А V В V) = (по теореме 5б)
= ((А V) V (В /\ )) Л (А V В V) = (по теореме 12а)
= (((А V ) V В) /\ ((А V) V )) /\(А V В V ) = (по теореме 11a)
= ((AVVB) /\ (AVV)) /\(AVBV) = (по теореме 11б)
= (AVVB) /\(AVV) /\ (AVBV) = (по теореме 7а)
= (AVBV)/\ (AVV)/\ (AVBV)=(пoTeopeмe7б) =
= (А V В V) /\ (AV В V) /\ (A VV) = (по теореме 4б) = (А V В V) /\ (А V V) - ответ на задачу а).

Другие записи

10.06.2016. Построение функции по таблице истинности
В задаче дается таблица истинности некоторой функции. Требуется найти эту функцию. Самый простой способ нахождения функции - построение дизъюнктивной нормальной формы (ДНФ) этой функции. Каждой комбинации…