Лекция 4
 Скачать 0.53 Mb.
|
Элементы математической логикиРаздел 2. Логика (алгебра) высказыванийНормальные формы для формул алгебры высказыванийЛекция 42.1. Нормальные формы для формул алгебры высказыванийОдна и та же логическая формула может быть записана различным образом. Например, функция F(A,B) может быть записана следующими эквивалентными выражениями: Эквивалентность этих формул легко проверить по таблицам истинности или выполнив необходимые преобразования. Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно, так как приходится перебирать большое количество вариантов. В таких случаях формулы удобно привести к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, при этом знаки отрицания находятся только при логических переменных. В алгебре высказываний используют две нормальные формы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы (КНФ). В элементарной конъюнкции нет двух одинаковых пропозициональных переменных, так как AA ≡ A. Определение. Высказывательная форма, состоящая из элементарных конъюнкций, применением только одной операции дизъюнкции называется дизъюнктивной нормальной формой (ДНФ). Например, ДНФ Определение. Высказывательная форма, состоящая из переменных или отрицательных переменных, применением только одной операции конъюнкции, называется элементарной конъюнкцией (или конъюнктом). Например, В элементарной дизъюнкции нет двух одинаковых пропозициональных переменных, так как А∨А ≡ А Определение. Высказывательная форма, состоящая из элементарных дизъюнкций, применением только одной операции конъюнкции называется конъюнктивной нормальной формой (КНФ). Например, КНФ Определение. Высказывательная форма, состоящая из переменных или отрицания переменных применением только одной операции дизъюнкции, называется элементарной дизъюнкцией (или дизъюнктом). Например, Алгоритм приведения к НФ Для приведения формулы к нормальной форме используют законы логики и правила логических преобразований по следующему алгоритму:
Примеры:
F=F1˄(F2∨¬F2)∨F2˄(F1∨¬F1) Примеры:
F=F1˄(F1∨F2)∨¬F2˄(F1∨F2) Примеры:
F=((F1→(F2∨¬F3))→F4) Примеры:
F=¬(F1˄F2)˄(F1∨F2) Совершенные НФ Использование нормальных форм не устраняет полностью неоднозначности записи логических функций, например Поэтому среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными. Применяются совершенная дизъюнктивная и совершенная конъюнктивная формы (СДНФ и СКНФ). СДНФ Совершенная дизъюнктивная нормальная форма (СДНФ) - ДНФ, удовлетворяющая условиям:
Примеры СДНФ: (XY)(XY) (XY) (XYZ) (XYZ) (XYZ) (XYZ) (XYZ) (X1X2X3X4) (X1X2X3X4) (X1X2X3X4) СКНФ Совершенная конъюнктивная нормальная форма (СДНФ): КНФ - удовлетворяющая условиям:
Теорема 2.4.1 (о представлении формулы алгебры высказываний совершенными дизъюнктивными нормальными формами). Каждая не тождественно ложная формула алгебры высказываний от n аргументов имеет единственную (с точностью до перестановки дизъюнктивных членов) СДНФ. Теорема 2.4.2 (о представлении формулы алгебры высказываний совершенными конъюнктивными нормальными формами). Каждая не являющаяся тавтологией формула алгебры высказываний от n аргументов имеет единственную (с точностью до перестановки конъюнктивных членов) СКНФ. Единственность совершенных нормальных форм у выполнимой ПФ обуславливает их использование для доказательства равносильностей, идея которого состоит в следующем: если у двух ПФ их СДНФ (СКНФ) совпадают, то они равносильны. 2.5. Приведение формулы алгебры высказываний к совершенной нормальной формеСпособы приведения формул к совершенным формам следуют из способов задания формул алгебры высказываний – либо с помощью таблицы, либо аналитически. Аналитический способ приведения к совершенным формам Для приведения ПФ к СДНФ выполняются равносильные преобразования, описанные следующей последовательностью шагов:
Аналитический способ приведения к совершенным формам Приведение к СКНФ осуществляется аналогично, но только к элементарным дизъюнкциям, содержащим слагаемыми не все переменные, прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием. Пример Пусть ПФ, содержащая переменные X, Y, Z, имеет ДНФ вида Используя аналитический способ привести к СДНФ. Решение: В соответствии с процедурой приведения к СДНФ умножим первую и вторую конъюнкции на 1 Табличный способ приведения к совершенным формам Табличный способ приведения к СДНФ
Табличный способ приведения к СКНФ Пример Найти СКНФ и СДНФ для формулы Решение: Построим таблицу истинности и на ее основе составим СДНФ и СКНФ
Критерии тождественной истинности и тождественной ложности формул алгебры высказываний Теорема 2.6.1 (признак тождественной истинности формулы). Формула алгебры высказываний тождественно истинна тогда и только тогда, когда в каждой элементарной дизъюнкции её КНФ имеется, по меньшей мере, одна пропозициональная переменная, входящая в этот одночлен вместе со своим отрицанием. Теорема 2.6.2 (признак тождественной ложности формулы). Формула алгебры высказываний тождественно ложна тогда и только тогда, когда в каждой элементарной конъюнкции её ДНФ имеется, по меньшей мере, одна пропозициональная переменная, входящая в этот одночлен вместе со своим отрицанием. Примеры:
(P(PQ))Q ( P(PQ))Q P(PQ)Q P(PQ)Q (PPQ)(PQQ). По теорем 2.6.1 формула тождественно истинна. Примеры: 2. Показать, что формула P(Q(PQ)) – тождественно ложна P(Q(PQ)) (P QP)( (PQQ). По теорем 2.6.2 формула тождественно ложна. Задания для закрепления 5. Построить простейшую логическую формулу по заданной таблице истинности, которая имеет нулевые значения при следующих наборах переменных A, B, C: (001), (010), (011), (110). 5. Построить простейшую логическую формулу по заданной таблице истинности, которая принимает значение 1 при следующих наборах переменных A, B, C: (010), (101), (111). Домашнее задание Контрольные вопросы
|