Равносильности, выражающие одни логические операции через другие.
1. 4. . 2. . 5. . 3. . 6. . Здесь 3, 4, 5, 6 – законы Моргана. Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4, соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания. Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем одну из них : первую . Так как при одинаковых логических значениях x и y истинными являются формулы , то истинной будет и конъюнкция . Следовательно, в этом случае обе части равносильности имеют одинаковые истинные значения. Пусть теперь x и y имеют различные логические значения. Тогда будут ложными эквивалентность и одна из двух импликаций или . Но при этом будет ложной и конъюнкция . Таким образом, и в этом случае обе части равносильности имеют одинаковые логические значения. Аналогично доказываются равносильности 2 и 4. Из равносительностей этой группы следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание. Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула как отрицание не может быть выражена с помощью операции конъюнкции. Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция “Штрих Шеффера”. Эта операция обозначается символом ½ и определяется следующей таблицей истинности:
Равносильности, выражающие основные законы алгебры логики. 1. - коммутативность конъюнкции. 2. - коммутативность дизъюнкции. 3. - ассоциативность конъюнкции. 4. - ассоциативность дизъюнкции. 5. - дистрибутивность конъюнкции относительно дизъюнкции. 6. - дистрибутивность дизъюнкции относительно конъюнкции. Дополнительные законы. Закон склеивания (расщепления). , ; , . Законы поглощения. ; . Закон Блейка- Порецкого. . Закон свертки логического выражения (СЛВ). . Закон двойственности. Определение. Формулы А и А* называются двойственными, если формула А* получается из формулы А путем замены в ней каждой операции на двойственную. Имеет место следующий закон двойственности: если формулы А и В равносильны, то равносильны и им двойственные формулы, т.е. А* º В*.
Логические выражения можно преобразовывать в соответствии с законами алгебры логики: Законы рефлексивности a ∨ a = a a ∧ a = a Законы коммутативности a ∨ b = b ∨ a a ∧ b = b ∧ a Законы ассоциативности (a ∧ b) ∧ c = a ∧ (b ∧ c) (a ∨ b) ∨ c = a ∨ (b ∨ c)
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (347)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |