Рис. 23. Переключательная схема, реализующая логическую функцию (а), и упрощенная схема(б).

Любую сложную булеву функцию можно представить некоторой переключательной схемой. На рис. 23,а показана схема, реализующая функцию у = х₁ x̅₂ ∨ x̅₁ x₂x₃ ∨ x₃x₄. Та же функция представляется равносильной формулой у = х₁ x̅₂ ∨ ( x̅₁ x₂ ∨ x₄)x₃, которой соответствует другая более простая схема (рис. 23, б). Следует иметь в виду, что ключи, обозначенные одинаковыми буквами (х или x̅ ), связаны между собой и управляются общей кнопкой.

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

- 66 -

Существенными свойствами контактных схем являются исходные положения ключей (нормально разомкнуты или нормально замкнуты) и способ их соединения между собой и внешними устройствами. Эта информация полностью отображается графом, ребра которого соответствуют ключам, а вершины - точкам их соединения. Ребра нормально разомкнутых ключей обозначаются соответствующей переменной (х), а нормально замкнутых - отрицанием переменной (х). Например, контактная схема (рис. 23, б) изображается графом, как показано на рис. 24, а.

При изображении контактных схем графами принимаются некоторые специфические условия и упрощения. Обычно переменные обозначаются в разрывах линий, изображающих ребра.

Рис. 24. Граф переключательной схемы (а) и его упрощенное изображение (б).

При этом ребрами считаются только такие линии, которые обозначены какой-либо переменной или ее отрицанием. Другие линии, не являющиеся ребрами графа, могут изображать входы и выходы схемы, связи с другими схемами и т. п. Кроме того, вершины второй степени могут не изображаться, так как им инцидентны пары последовательно соединенных ребер, из которых каждое обозначено соответствующей переменной.

На рис. 24,б показана контактная схема в обычно принятом виде.

8. Высказывания.Пусть х₁ и x₂ - некоторые высказывания, которые могут быть истинными (1) или ложными (0), например: «Я пойду в театр» (х₁) и «Я встречу друга» (x₂). Дизъюнкцией х₁ ∨ x₂ является сложное высказывание «Я пойду в театр или встречу друга», а конъюнкцией х₁ ∧ x₂ - высказывание «Я пойду в театр и встречу друга».

Ясно, что если высказывание истинно, то его отрицание ложно. Сложное высказывание, образованное дизъюнкцией двух высказываний, истинно при условии, что истинно хотя бы одно из них. Сложное высказывание, образованное конъюнкцией двух истинных высказываний истинно, если истинны оба эти высказывания одновременно.

Итак, высказывания можно рассматривать как двоичные переменные, а связки «не», «или», «и», с помощью которых образуются сложные высказывания, - как операции над этими переменными.

- 67 -

В алгебре высказываний используются еще две операции: импликация х₁ → x₂, соответствующая связке «если, то» и эквиваленция х₁ ~ x₂, соответствующая связке «если и только если». Они задаются следующими таблицами:

В нашем примере импликацией будет высказывание: «Если пойду в театр, то встречу друга», а эквиваленцией – пойду в театр, если и только если встречу друга». Как видно из таблиц, импликация высказываний ложна только в случае, когда первое из простых высказываний истинно, а второе ложно. Эквиваленция является истинным высказыванием, если оба простые высказывания истинны или ложны одновременно.

Обозначив буквами простые высказывания, можно представить сложное высказывание формулой с помощью соответствующих связок. Например, высказыванию «Если давление масла на шарик клапана больше усилия его пружины (х₁), то масло открывает клапан (х₂) и частично перетекает из нагнетательной полости во впускную (х₃)» соответствует формула х₁ → х₂ х₃.

9. Предикаты. Обычно высказывания выражают свойства одного или нескольких объектов. Содержательная часть высказывания играет роль определяющего свойства совокупности объектов, для которых это высказывание истинно, и называется предикатом. Например, высказывание «Иванов - отличник» истинно или ложно в зависимости от оценок, которые имеет данный студент. В то же время предикат «х - отличник» определяет подмножество отличников на некотором множестве студентов (группа, курс, факультет). Подставив вместо х фамилии студентов, получим множество высказываний. Совокупность истинных высказываний и будет соответствовать подмножеству отличников.

Предикат представляет собой логическую функцию Р(х), принимающую, как и булевы функции, значение 0 или 1, но в отличие от них, значения аргумента х выбираются из некоторого множества М объектов (х ∈ М). В общем случае такая функция может зависеть от многих аргументов х₁, х₂, . . .,х_n, принимающих значения из одного и того же или различных множеств. Ее записывают Р(х₁, х₂, ...,х_n) и называют n-местным предикатом. Например: «х - четное число», «х - компонент цепи» - одноместные предикаты Р(х);

- 68 -

«х брат у», «х меньше у» — двуместные предикаты Р(х, у); «х и у - родители z»,

«х - сумма y и z» - трехместные предикаты Р(х, y, z) и т. д. Если аргументы х₁, х₂, ... ,х_n замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривают как 0 - местный предикат.

Так как предикаты способны принимать только значения 0 и 1, то их, как и булевы переменные, можно связывать логическими операциями. В результате получаем формулы, определяющие более сложные предикаты. Так, если Р(х) означает «х - инженер», а Q(х) - «x - сотрудник нашего отдела», то Р(х) ∧ Q(х) = R(х) есть одноместный предикат «х - инженер и сотрудник нашего отдела» или проще «х - инженер нашего отдела». Очевидно, если Р - множество инженеров, а 0 - множество сотрудников данного отдела, то этот предикат соответствует пересечению Р ∩ Q. Таким образом, имеет место тесная связь между логикой предикатов и операциями над множествами.

10. Двоичная арифметика. В позиционной системе счисления с основанием m любое целое неотрицательное число a записывается последовательностью различных цифр x₁x₂ ... x_n, что означает a = x₁m^n-1 + x₂m^n-2 + ... + x_nm⁰. Десятичная система использует цифры 0, 1, ..., 9, например: 2907 = 2·10³ + 9·10² + 0·10¹ + 7·10⁰. Для двоичной системы счисления достаточно двух цифр, которые обозначаются 0 и 1. При этом последовательность x₁x₂ ... x_n таких цифр является записью двоичного n-разрядного числа x₁·2^n-1 + x₂·2^n-2+ ... + x_n·2⁰.

Перевод целых десятичных чисел в двоичные осуществляется последовательным делением исходного числа и каждого частного на два. Получаемые при этом остатки (0 или 1), записанные в обратном порядке, и дают представление десятичного числа в двоичной системе счисления. Например: