Сигнал о некоторых понятиях кибернетики - Полетаев И.А.
Скачать (прямая ссылка):
Несомненно, что область аналогий между положениями теоретической логики и решающими схемами не ограничит-
206
ся исчислением высказываний. Усложнение вычислительных схем приводит и приведет в дальнейшем к расширению соответствующего логического аппарата, подлежащего использованию в машинной логике.
В исчислении высказываний изучаются простейшие утверждения или высказывания, каждое из которых может быть либо ложным, либо истинным. Например, такими высказываниями могут быть:
Х=Дверь в лифт закрыта,
Y=Пассажир находится в лифте,
Z=Мотор вращается,
V=Ha фотоэлемент падает свет,
W=Кнопка электрического контакта нажата и т. д.
Из этих простых высказываний посредством сопоставления их друг с другом в различных связях могут быть построены новые высказывания, которые также могут быть либо истинными, либо ложными.
Принимаются следующие связи между высказываниями:
1) Конъюнкция X&Y (читается: икс и игрек). Например, Дверь в лифт закрыта, и пассажир находится в лифте. Сложное высказывание X&Y истинно в том и только в том случае, если истинны X и Y.
2) Дизъюнкция X\JY (читается: икс или игрек). Например, Кнопка контакта нажата или на фотоэлемент падает свет. Высказывание X\JY истинно тогда, когда истинно по крайней мере одно из высказываний X, Y (или оба вместе). Слово или, применяемое для обозначения дизъюнкции, не следует понимать в смысле исключения — либо-ли-бо («либо пан, либо пропал»), а только в смысле или X, или У, или оба вместе. Для исключающего или в смысле либо-либо можно составить особое выражение, более сложного вида.
3) Отрицание X (читается: не икс). Не икс истинно, когда икс ложно, и наоборот. Например, Х=Мотор вращается— ложно; тогда X—Мотор не вращается — истинно.
4) Импликация X—> Y (читается: если икс, то игрек.) Например; Если кнопка нажата, то мотор вращается,. Однако это соотношение не следует понимать в смысле причины и следствия, т. е. в смысле: Если кнопка нажата, то тогда и только тогда мотор вращается. Высказывание X —* Y истинно всегда, когда X ложно или когда Y истинно. Оно ложно только тогда, когда X истинно, a Y ложно.
Можно ввести еще и другие элементарные связи между высказываниями.
207
Применяя основные связи несколько раз, можно образовать из данных высказываний все более сложные, например:
[{V\/W)&X&Y]-+Z или (X&Y\J~Z) и т. д. (7.1)
Каждое такое сложное высказывание — логическая функция — может быть либо истинным, либо ложным в зависимости от комбинаций истинности и ложности входящих в него логических аргументов—независимых переменных X, У, Z, V, W. Можно перечислить все комбинации значений аргументов и для каждого вычислить значение функции (в приведенном примере их всего 25 = 32).
Значения сложного логического высказывания ф(Х, Y) — логической функции от двух аргументов — можно наглядно представить в виде квадратной таблицы. Два столбца этой таблицы соответствуют значениям независимого переменного X, а две строки — значениям У. На пересечениях строк и столбцов помещено соответствующее значение функции Ф(*. Y).
Обычно истинное высказывание обозначается единицей, а ложное нулем в двоичном алфавите, поскольку значения каждого высказывания укладываются в этот алфавит.
Для конъюнкции, дизъюнкции и импликации таблицы значений выглядят следующим образом:
X&Y X\JY X^Y
Любую четырехзначную таблицу такого вида можно представить с помощью некоторого логического высказывания. Так, например, таблица сложения в двоичной системе счисления, которая записывается
совпадает с таблицей для логического выражения X\fY&(X&Y).
208
Двоичная таблица умножения совпадает с таблицей конъюнкций.
Вообще, любую функцию от k аргументов W (Хи Xk)> если сама функция и каждый из её аргументов может принимать только два значения, обозначаемые 0 и 1 соответственно, можно задать в виде таблицы:
X, х2 .... Xk W(XltX2,...,Xk)
0 0 О W (0,0______ 0)
0 0 1 1Г(0,0, . . 1)
1 ‘ i 'Г W(
Число значений данной функции от k аргументов (число строк в таблице) равно 2к. Общее число всех возможных функций от k аргументов равно 22*.
Любую функцию, заданную таблицей, можно выразить с помощью формулы, используя элементарные логические функции: конъюнкцию, дизъюнкцию и отрицание и, наоборот, любую формулу можно записать в виде таблицы.
Таблица, состоящая только из единиц или только из нулей задается так называемыми всегда истинными и всегда ложными высказываниями, примерами которых могут служить
Х&Х = 0; Х&Х\/У&?ее\ и т. д. (7.2)
Можно показать, что для составления всех сложных высказываний, которые получаются с применением отрицания, конъюнкции, дизъюнкции и импликации, достаточно только двух операций — отрицания и конъюнкции. Тогда, например, импликация выразится так:
X-+Y==X\/Yt (7.3)
