Теорем и построении электронных схем

Использование законов логики в доказательстве

Эквиваленция и импликация играют важную роль в математике при построении логического вывода, в частности, при доказательстве различных высказываний (теорем).

Рассмотрим, например, следующую теорему: асимметричное бинарное отношение антирефлексивно. С точки зрения алгебры высказываний теорема имеет структуру следования А Þ В, где А = “отношение R асимметрично”, В = “отношение R антирефлексивно”.

Следующая теорема. Для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина v была достижима из всех вершин, имеет вид двойного следования А Û В (А Þ В, В Þ А), где А = “граф G – связный”, В = “вершина v достижима из всех вершин”.

Согласно теоремам 2.1 и 2.2, следование А Þ В имеет место тогда и только тогда, когда импликация А ® В является ТИ-формулой, а двойное следование А • В выполняется, когда ТИ-формулой является эквиваленция А ~ В. Таким образом, для доказательства какой-либо теоремы надо доказать ТИ соответствующей импликации или эквиваленции. Рассмотрим основные приёмы таких доказательств, использующие законы математической логики.

Определение 1. Если А®В является истинным высказыванием, то истинность А является достаточным условием истинности В, а истинность В – необходимым условием истинности А.

Определение 2. Теоремы, записанные в виде импликаций А®В и В®А называются взаимно-обратными. Если верны обе импликации, то истинность А является необходимым и достаточным условием истинности В, и наоборот.

Определение 3. Теоремы, записанные в виде импликаций А®В и называются взаимно-противоположными.

Теорема вида А ® В доказывается так. Предположим, что утверждение А истинно и докажем, что в этом случае В тоже истинно. Однако такая схема доказательства “в лоб” не всегда удобна. Для доказательства истинности импликаций и эквиваленций часто используют свойства эквивалентности формул.

Известно, что А ® В º В Úº º Ø (А Ù ).

Следовательно, имеем три равносильных способа доказательства, т.к. вместо истинности импликации можно доказывать истинность эквивалентной формулы.

Например, А = “отношение 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 = (.

Преобразуем эту формулу, используя соответствующие эквивалентности. Из первой пары скобок вынесем P, из второй – Q.

U º .

Воспользуемся эквиваленцией (по дистрибутивности)

º º .

Аналогично для вторых скобок: .

Окончательно: U º .

Изобразим схему, соответствующую заключительной формуле

Дата добавления: 2014-01-11