Similar presentations:
Нормальные формы для формул алгебры высказываний
1. Нормальные формы для формул алгебры высказываний
2. Нормальные формы для формул алгебры высказываний
Нормальные формы для формул алгебрывысказываний
Одна и та же логическая формула может быть записана
различным образом. Например, функция F(A,B) может быть
записана следующими эквивалентными выражениями:
F ( A, B) A B A B A B
F ( A, B) A A B
F ( A, B) A ( A B )
Эквивалентность этих формул легко проверить по таблицам
истинности или выполнив необходимые преобразования.
3.
Если логическое выражение содержит большое числоопераций, то составлять для него таблицу истинности
достаточно сложно, так как приходится перебирать большое
количество вариантов. В таких случаях формулы удобно
привести к нормальной форме.
Формула имеет нормальную форму, если в ней отсутствуют
знаки эквивалентности, импликации, двойного отрицания,
при этом знаки отрицания находятся только при логических
переменных.
В алгебре высказываний используют две нормальные
формы: дизъюнктивную (ДНФ) и конъюнктивную
нормальные формы (КНФ).
4.
ДНФОпределение. Высказывательная форма, состоящая из
переменных или отрицаний переменных, с применением
только
одной
операции
конъюнкции,
называется
элементарной конъюнкцией (или конъюнктом).
Например, A B C
В
элементарной
конъюнкции
нет
двух
пропозициональных переменных, так как A A ≡ A.
одинаковых
Определение. Дизъюнкция элементарных конъюнкций
называется дизъюнктивной нормальной формой (ДНФ).
Например, A B C A B A C
5.
КНФОпределение.
Высказывательная форма, состоящая из
переменных или отрицания переменных, с применением
только
одной
операции
дизъюнкции,
называется
элементарной дизъюнкцией (или дизъюнктом).
Например, A B C
В элементарной дизъюнкции
нет
пропозициональных переменных, так как А∨А ≡ А
двух
одинаковых
Определение.
Конъюнкция элементарных дизъюнкций
называется конъюнктивной нормальной формой (КНФ).
Например, ( A B C) ( A B) ( A C)
6.
Алгоритм приведения к ДНФДля приведения формулы к нормальной форме
используют законы логики и правила логических
преобразований по следующему алгоритму:
1. Устранить «↔» и «→».
2. Применив законы де Моргана отнести отрицания
к переменным.
3. Избавиться от двойных отрицаний.
4. Применив закон дистрибутивности, добиться того,
чтобы все конъюнкции встречались раньше
дизъюнкций.
7.
Алгоритм приведения к КНФДля приведения формулы к нормальной форме
используют законы логики и правила логических
преобразований по следующему алгоритму:
1. Устранить «↔» и «→».
2. Применив законы де Моргана отнести отрицания
к переменным.
3. Избавиться от двойных отрицаний.
4. Применив закон дистрибутивности, добиться того,
чтобы все дизъюнкции встречались раньше
конъюнкций.
8.
Критерии тождественной истинности и тождественнойложности формул алгебры высказываний
Теорема 1 (признак тождественной истинности формулы).
Формула алгебры высказываний тождественно истинна тогда и
только тогда, когда в каждой элементарной дизъюнкции её КНФ
имеется, по меньшей мере, одна переменная, входящая в этот
одночлен вместе со своим отрицанием.
Теорема 2 (признак тождественной ложности формулы).
Формула алгебры высказываний тождественно ложна тогда и
только тогда, когда в каждой элементарной конъюнкции её ДНФ
имеется, по меньшей мере, одна переменная, входящая в этот
одночлен вместе со своим отрицанием.