Читайте также:
|
|
Отметим, что высказывание типа " А, если и только если В " можно заменить высказыванием "Если А, то В и, если В, то А " (обдумайте это на досуге и обратите внимание на символ <=>). Следовательно, функцию эквиваленции можно заменить комбинацией функций импликации и конъюнкции. Запишем таблицу истинности для эквиваленции:
А | В | А<=>В |
И И Л Л | И Л И Л | И Л Л И |
Попробуем записывать сложные высказывания схематически с помощью обозначения логических связок:
15. Отрицание. Примеры
- логическая операция, в результате к-рой из данного высказывания Аполучается новое высказывание "не А". В формализованных языках высказывание, получающееся в результате О. высказывания А, обозначается (читается: "не А", "неверно, что А", "Ане имеет места"). Семантически О. высказывания Аозначает, что допущение Априводит к противоречию. В классической двузначной логике операции О. соответствует следующая истинностная таблица:
16. Формулы алгебры логики. Виды формул.
17. Равносильные формулы. Примеры
Равносильные формулы алгебры логики
Определение. Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).
Обозначение. A≡B.
Пример.
.
Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных (напр., ).
Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных (напр., ).
Утверждение. Отношение равносильности рефлексивно, симметрично, транзитивно.
Связь между понятиями равносильности и эквивалентности: если формулы A и B равносильны, то формула A↔B тавтология, и обратно, если формула A↔B тавтология, то формулы A и B равносильны.
Равносильности алгебры логики можно разбить на 3 группы:
1. Основные равносильности.
· – законы идемпотентности;
· ;
· ;
· ;
· ;
· – закон противоречия;
· – закон исключенного третьего;
· – закон снятия двойного отрицания;
· – законы поглощения.
1. Равносильности, выражающие одни логические операции через другие:
· ;
· ;
· ;
· ;
· ;
· .
Замечание. Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание, или дизъюнкцию и отрицание. Дальнейшее исключение операций невозможно. Например, если использовать только конъюнкцию, то уже такая простая формула, как не может быть выражена с помощью операции конъюнкции.
Существуют операции, с помощью которых может быть выражена любая из 5 логических операций:
1) Связка Шеффера – дизъюнкция отрицаний.
Обозначение. x | y≡ («x не совместно с y»).
Логические значения связки Шеффера описываются следующей таблицей истинности:
x | y | x | y |
Имеют место следующие равносильности: а) ; б) .
2) Связка Лукасевича – конъюнкция отрицаний.
Обозначение. x↓y≡ («ни x, ни y»).
Логические значения связки Лукасевича описываются следующей таблицей истинности:
x | y | x ↓ y |
2. Равносильности, выражающие основные законы алгебры логики:
· – коммутативность конъюнкции;
· – коммутативность дизъюнкции;
· – ассоциативность конъюнкции;
· – ассоциативность дизъюнкции;
· – дистрибутивность конъюнкции относительно дизъюнкции;
· – дистрибутивность дизъюнкции относительно конъюнкции.
Замечание. Равносильности группы 3 показывают, что над формулами алгебры логики можно проводить те же преобразования, что и в алгебре чисел.
18. Законы логики. Способы их применения. Примеры.
Законы логики"
Законы логики отражают наиболее важные закономерности логического мышления, В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений в соответствие с законами логики.
Закон тождества. Всякое высказывание тождественно самомусебе: А = А
Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А — истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должнобыть ложно: A & A = 0
Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: A v A = 1
Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результатемы получим исходное высказывание: A = A
Кроме логических законов, важное значение для выполнения преобразований логических выражений имеют правила алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.
Законы Моргана: (A v B)= А & В
(A & B)= А v В
Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можноменять местами логические переменные при операцияхлогического умноженияи логического сложения:
Логическое умножение Логическое сложение
A & B = B & A A v B = A v B
Правило ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
Логическое умножение Логическое сложение
(A & B) & C = A & (B & C) (A v B) v C = A v (B v C)
Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:
Дистрибутивность умножения Дистрибутивность сложения
относительно умножения относительно сложения
(a x b) + (a x c) = a x (b + c)
(A & B) v (A & C) = A & (B v C) (A v B) & (A v C) = A v (B & C)
Рассмотрим в качестве примера применениязаконов логики и правил алгебрылогики преобразование логического выражения. Пустьнам необходимо упростить логическое выражение:
(А &. В) v (A & В).
Воспользуемся правилом дистрибутивности и вынесем за скобки А:
(А & В) v (А & В) = А & (В v В).
По закону исключенного третьего В vВ =1, следовательно:
А & (В v B) = А &. 1 = А.
Дата добавления: 2015-01-30; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав |