Математический аппарат инженера
Шрифт:
= (1 y) (x 1) = 1 1 = 1, а также
(х у) ( x y ) = (х ( x y ) = (у ( x y ) = ((x x ) y ) ((y y ) x ) =
= (0 y ) ( x 0) = 0 0 = 0.
Следовательно, соотношение x y = x y доказано. Аналогично доказывается и второй закон.
Упрощение записи формул.Операции дизъюнкции и конъюнкции удовлетворяют законам коммутативности и ассоциативности. Поэтому если переменные или формулы связаны только посредством одной из этих операций, то их можно выполнять в лгсбом порядке, а формулы записывать без скобок. Например:
((х1 x2) (х3 x4) х5 =
а также (х1 x2) (x3 (х4 x5) = х1 x2 x3 х4 x5.
Если считать, что операция конъюнкции должна предшествовать операции дизъюнкции (конъюнкция связывает сильнее дизъюнкции), то можно опустить скобки, в которые заключены формулы со знаком конъюнкции. При наличии скобок в первую очередь должны выполняться операции внутри скобок, независимо от их старшинства. Обычно опускают также скобки, в которые заключены формулы со знаком отрицания.
Еще одно упрощение связано с символикой. Знак конъюнкции в формулах можно опустить и вместо х у писать ху. Операцию конъюнкции часто называют логическим умножением, а операцию дизъюнкции - логическим сложением.
С учетом приведенных условий запись существенно упрощается. Например, формуле (x (y z )) (( x y ) z) соответствует запись xyz x y z.
7. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х1 и x2). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается.
– 65 -
Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т. е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим через x1 и x2.
При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х1 и x2, а состояние лампочки — со значением функций этих переменных.
Рис. 22. Переключательные схемы, соответствующие операциям отрицания (а), дизъюнкции (б) и конъюнкции (в)
Операции отрицания соответствует схема с одним нормально замкнутым ключом (рис. 22, а). Если кнопка нажата (х = 1), ключ разомкнут и лампочка не горит, т. е. f(х) = 0; при отпущенной кнопке (х = 0) ключ замкнут и лампочка горит, т. е. f(x) = 1. Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис. 22, б, в). Легко убедиться, что в схеме рис. 22, б лампочка горит при нажатии хотя бы одной из кнопок, а в схеме рис. 22, в - только при нажатии обеих кнопок одновременно.
Рис. 23. Переключательная
Любую сложную булеву функцию можно представить некоторой переключательной схемой. На рис. 23,а показана схема, реализующая функцию у = х1 x2 x1 x2x3 x3x4. Та же функция представляется равносильной формулой у = х1 x2 ( x1 x2 x4)x3, которой соответствует другая более простая схема (рис. 23, б). Следует иметь в виду, что ключи, обозначенные одинаковыми буквами (х или x ), связаны между собой и управляются общей кнопкой.
В реальных устройствах используются ключи различной конструкции и физической природы (механические, электромагнитные, электронные, гидравлические, пневматические и т. д.) Однако при реализации логических функций многие технические особенности не имеют значения.
– 66 -
Существенными свойствами контактных схем являются исходные положения ключей (нормально разомкнуты или нормально замкнуты) и способ их соединения между собой и внешними устройствами. Эта информация полностью отображается графом, ребра которого соответствуют ключам, а вершины - точкам их соединения. Ребра нормально разомкнутых ключей обозначаются соответствующей переменной (х), а нормально замкнутых - отрицанием переменной (х). Например, контактная схема (рис. 23, б) изображается графом, как показано на рис. 24, а.
При изображении контактных схем графами принимаются некоторые специфические условия и упрощения. Обычно переменные обозначаются в разрывах линий, изображающих ребра.
Рис. 24. Граф переключательной схемы (а) и его упрощенное изображение (б).
При этом ребрами считаются только такие линии, которые обозначены какой-либо переменной или ее отрицанием. Другие линии, не являющиеся ребрами графа, могут изображать входы и выходы схемы, связи с другими схемами и т. п. Кроме того, вершины второй степени могут не изображаться, так как им инцидентны пары последовательно соединенных ребер, из которых каждое обозначено соответствующей переменной.
На рис. 24,б показана контактная схема в обычно принятом виде.
8. Высказывания.Пусть х1 и x2– некоторые высказывания, которые могут быть истинными (1) или ложными (0), например: «Я пойду в театр» (х1) и «Я встречу друга» (x2). Дизъюнкцией х1 x2 является сложное высказывание «Я пойду в театр или встречу друга», а конъюнкцией х1 x2– высказывание «Я пойду в театр и встречу друга».
Ясно, что если высказывание истинно, то его отрицание ложно. Сложное высказывание, образованное дизъюнкцией двух высказываний, истинно при условии, что истинно хотя бы одно из них. Сложное высказывание, образованное конъюнкцией двух истинных высказываний истинно, если истинны оба эти высказывания одновременно.
Итак, высказывания можно рассматривать как двоичные переменные, а связки «не», «или», «и», с помощью которых образуются сложные высказывания, - как операции над этими переменными.