Мат логина. Нормальные формы формул алебры высказываний
 Скачать 206.08 Kb.
|
|
НОРМАЛЬНЫЕ ФОРМЫ ФОРМУЛ АЛЕБРЫ ВЫСКАЗЫВАНИЙ В классе формул, равносильных данной, существуют формулы, содержащие только операции конъюнкции, дизъюнкции и отрицания. Такую форму представления формулы алгебры высказываний называют нормальной. Формула, равносильная данной формуле алгебры высказываний, называется дизъюнктивной нормальной формой (ДНФ), если она содержит конечное число конъюнкций некоторых логических переменных и их отрицаний, соединенных операцией дизъюнкции. Например, R R Q Q P R Q P & & & & Теорема 1. Любую формулу алгебры высказываний можно привести к виду ДНФ. Формула, равносильная данной формуле алгебры высказываний, называется конъюнктивной нормальной формой (КНФ), если она содержит конечное число дизъюнкций некоторых логических переменных и их отрицаний, соединенных операцией конъюнкции. Например, Q R P R Q P & & Теорема 2. Любую формулу алгебры высказываний можно привести к виду КНФ. Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Приведем алгоритм построения ДНФ и КНФ: 1. Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя следующие равносильности: , Y X Y X , & Y X Y X Y X Y X Y X Y X & & 2. Заменить знак отрицания, относящийся к выражениям вида Y X & и Y X , знаками отрицания, относящимися к отдельным переменным, используя законы де Моргана. 3. Избавиться от знаков двойного отрицания. 4. Применить, если нужно, к операциям конъюнкции и дизъюнкции законы дистрибутивности и поглощения. Пример 1. Привести формулу Z Z Y X & & к ДНФ. Решение. Z Z Y X Z Z Y X Z Z Y X & & & & & Z Y X Z Z Y X Пример 2. Привести формулу Z Y X к КНФ. Решение. Z Y X Z Y X Z Y X Z Y X & & Z Y Z X & Как уже было отмечено выше, для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Чтобы исключить эту неоднозначность, формулы на основе их табличного представления записывают в виде совершенных нормальных форм – совершенной дизъюнктивной нормальной формы и совершенной конъюнктивной нормальной формы. Таким образом, формулу алгебры высказываний можно однозначно задать ее таблицей истинности или в виде СДНФ и СКНФ. Совершенной дизъюнктивной нормальной формойформулы алгебры высказываний называется её ДНФ, при этом: 1) в ДНФ нет одинаковых конъюнкций; 2) ни одна конъюнкция не содержит одновременно двух одинаковых переменных; 3) ни одна конъюнкция не содержит одновременно некоторую переменную и её отрицание; 4) в каждой конъюнкции присутствуют все переменные, входящие в формулу, либо их отрицание. Например, R Q P R Q P R Q P & & & & & & Теорема 3 (о полноте СДНФ). Каждая формула алгебры высказываний, отличная от противоречия, может быть представлена в СДНФ единственным образом. Совершенной конъюнктивной нормальной формойформулы алгебры высказываний называется её КНФ, при этом: 1) в КНФ нет одинаковых дизъюнкций; 2) ни одна дизъюнкция не содержит одновременно двух одинаковых переменных; 3) ни одна дизъюнкция не содержит одновременно некоторую переменную и её отрицание; 4) в каждой дизъюнкции присутствуют все переменные, входящие в формулу, либо их отрицание. Например, R Q P R Q P R Q P R Q P & & & Теорема 4 (о полноте СКНФ). Каждая формула алгебры высказываний, отличная от тавтологии, может быть представлена в СКНФ единственным образом. Совершенные нормальные формы могут быть найдены двумя способами: а) по таблице истинности; б) с помощью равносильных преобразований. СДНФ составляется на основе таблицы истинности по следующему правилу: для каждого набора переменных, при котором формула принимает значение «1», записывается конъюнкция, в которой с отрицанием берутся переменные, имеющие значение «0», а затем все полученные конъюнкции соединяют знаками дизъюнкции. СКНФ составляется на основе таблицы истинности по следующему правилу: для каждого набора переменных, при котором формула принимает значение «0», записывается дизъюнкция, в которой с отрицанием берутся переменные, имеющие значение «1», а затем все полученные дизъюнкции соединяют знаками конъюнкции. Пример 3. Привести к СДНФ и СКНФ формулу F, заданную следующей таблицей истинности: P Q R F 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 Формула принимает значения «1» для следующих наборов переменных: P Q R F 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 Запишем конъюнкции, заменяя отрицанием те переменные, которым соответствуют значения «0», и соединим их знаками дизъюнкции: R Q P R Q P R Q P R Q P & & & & & & & & - искомая СДНФ. Формула принимает значения «0» для следующих наборов переменных: P Q R F 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 Запишем дизъюнкции, заменяя отрицанием те переменные, которым соответствуют значения «1», и соединим их знаками конъюнкции: R Q P R Q P R Q P R Q P & & & - искомая СКНФ. Если условием задачи не оговаривается, в виде СДНФ или СНКФ надо по заданной таблице истинности записать соответствующую ей формулу, то в целях уменьшения затрат и при желании получить более короткую запись формулы следует сравнить количество единичных и нулевых значений формулы, заданной таблично. Если единичных значений меньше, то формулу лучше записать в виде СДНФ, иначе – в виде СНКФ. Несмотря на различие записей СДНФ и СНКФ, они равносильны по определению равносильных формул, так как будучи записанными по одной и той же таблице истинности, они реализуют одну и ту же формулу. Тем не менее, может оказаться весьма полезным провести на основании законов логики тождественные преобразования как полученной СДНФ, так и СКНФ. Отметим, что описанный способ нахождения СДНФ и СКНФ по таблице истинности часто бывает трудоемким. В таких случаях для нахождения СДНФ сначала с помощью равносильных преобразований приводим данную формулу к ДНФ, а затем преобразовываем ее конъюнкции с помощью следующих действий: 1) если в конъюнкцию входит некоторая переменная со своим отрицанием, то удаляем эту конъюнкцию из ДНФ; 2) если в конъюнкцию одна и та же переменная входит несколько раз, то все они удаляются, кроме одной; 3) если в какую-либо конъюнкцию не входят некоторые переменные, то для каждой из них в конъюнкцию добавляется формула вида P P ; 4) если в полученной ДНФ имеется несколько одинаковых конъюнкций, то оставляем только одну из них. Для нахождения СКНФ процесс выглядит аналогично. |