Математическая логика
жүктеу/скачать 0.93 Mb.
|
- Бұл бет үшін навигация:
- Определение 2.
| Определение 1. Если А В является истинным высказыванием, то истинность А является достаточным условием истинности В, а истинность В – необходимым условием истинности А.
Определение 2. Теоремы, записанные в виде импликаций А В и В А называются взаимно-обратными. Если верны обе импликации, то истинность А является необходимым и достаточным условием истинности В, и наоборот. Предположим, что утверждение А истинно и докажем, что в этом случае В тоже истинно. Так доказывается теорема вида А В. Однако такая схема доказательства “в лоб” не всегда удобна. Для доказательства истинности импликаций и эквиваленций часто используют свойства эквивалентности формул. Известно, что (А В) (В ) ( ) ( (А ) ). Следовательно, имеем три равносильных способа доказательства, т.к. вместо истинности импликации можно доказывать истинность эквивалентной формулы. Например, А = “отношение R асимметрично”, В = “отношение R антирефлексивно”. Тогда доказательство по схеме выглядит так: R рефлексивно, т.е. (х, х) R, значит, (х, х) R– 1 , т.е. (х, х) R R– 1 . Это означает, что R не асимметрично. Доказательство истинности ( (А )), или, что то же самое, ложности (А ), так называемое доказательство от противного, основано на предположении: А – истинно, а В – ложно. В результате должно быть получено ТЛ-высказывание, или противоречие. Например, предположим, что R асимметрично и рефлексивно. В силу асимметричности неверно одно из следующих соотношений: (х, у) R и (у, х) R. Положим х = у. Тогда, включение (х, х) R неверно, т.е. утверждение – ложно, значит и (А ) – ложно. В автоматическом управлении и при эксплуатации вычислительных машин приходится иметь дело с переключательными схемами (релейно-контактными, полупроводниковыми), состоящие из сотен реле, полупроводников, магнитных элементов. Переключательная схема состоит из переключателей (например, кнопочные устройства, электромагнитные реле, полупроводниковые элементы и т.п.) и соединяющих их проводников. При конструировании таких схем существенную помощь может оказать алгебра высказываний: можно построить схему, выполняющую требуемые функции (синтезирование схемы) или изучить действие построенной схемы и возможно ее упростить (анализ схемы). Каждой схеме ставится в соответствие формула алгебры высказываний, и каждая формула реализуется с помощью некоторой схемы. Покажем, как установить такое соответствие. Каждому переключателю P ставится в соответствие высказывательная переменная P, которая истинна тогда и только тогда, когда переключатель P замкнут. Схеме с последовательным соединением переключателей P и Q соответствует формула, являющаяся конъюнкцией высказавательных переменных, соответствующих этим переключателям, . Схеме с параллельным соединением переключателей P и Q соответствует формула, являющаяся дизъюнкцией высказавательных переменных, соответствующих этим переключателям, . Два переключателя P и могут быть связаны так, что когда P замкнут, то разомкнут. Тогда переключателю ставится в соответствие переменная , являющаяся отрицанием P. Задание. Упростить схему Решение. Запишем формулу, соответствующую схеме, по приведенным выше правилам U = . жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|