Законы алгебры высказываний отражают наиболее важные
закономерности логического мышления, они записываются в
виде формул, которые позволяют проводить эквивалентные
преобразования логических выражений.
Закон тождества. Всякое высказывание
тождественно самому себе.
Закон не противоречия. Высказывание не
может быть одновременно истинным и ложным. Если
высказывание А истинно, то его отрицание не А
должно быть ложным. Следовательно, логическое
произведение высказывания и его отрицания должно быть
ложно.
Закон исключенного третьего. Высказывание
может быть либо истинным, либо ложным, третьего не дано.
Это означает, что результат логического сложения
высказывания и его отрицания всегда принимает значение
«истина».
Закон двойного отрицания. Двойное отрицание
некоторого высказывания дает исходное высказывание.
¬(¬А)=А
Закон коммутативности. Перемена мест
логических переменных при выполнении операций конъюнкции
и дизъюнкции не приводит к изменению результата.
Закон ассоциативности. Если в логическом
выражении используются только операция логического
умножения (конъюнкция) или только операция логического
сложения (дизъюнкция), то можно пренебрегать скобками
или произвольно их расставлять. Скобки в алгебре
высказываний применяются в сложных составных
высказываниях с участием трех и более логических
переменных с целью задания порядка выполнения операций
(говорят определить приоритет операций).
Закон дистрибутивности. В алгебре
высказываний за скобки можно выносить как общие
множители, так и общие слагаемые.
В качестве примера применения законов алгебры
высказываний упростим выражение:
(A & B)
\/ (А & ¬B)
Воспользуемся законом дистрибутивности и вынесем за
скобки А:
A & (B
\/ ¬B)
По закону исключающего третьего B
\/¬ B =1, следовательно:
A & (B
\/¬ B)= А & 1=A
Алгебра высказываний позволяет решать логические задачи.
Такие задачи обычно формулируются на естественном языке,
затем они формализуются – переводятся на язык алгебры
высказываний. Полученное логическое выражение упрощается
и анализируется.
Если в результате выполненных преобразований получается
высказывание истинное при любом наборе переменных
входящих в это высказывание, то исходное высказывание
называется тождественно-истинным. Если же в результате
преобразований получается высказывание ложное при любом
наборе входящих переменных, то исходное высказывание
называется тождественно-ложным. Если высказывание не
является ни тождественно истинным, ни
тождественно-ложным, то говорят, что это высказывание
выполнимо.
Если в результате преобразований, получена формула
равносильная исходной и представляющая собой конъюнкции
основных дизъюнкций, то такая форма называется
конъюнктивной нормальной формой (КНФ).
Например, (А+В)(В+Ā+С)
Если же полученная формула представляет собой дизъюнкции
основных конъюнкций, то такая форма называется
дизъюнктивной нормальной формой (ДНФ).
Например, АВ+С+ĀВ
|