Влияние теории релейно-контактных схем на развитие математической логики

ВЕСТН. МОСК. УН-ТА. СЕР. 7. ФИЛОСОФИЯ. 2009. № 1

З.А. Кузичева*

ВЛИЯНИЕ ТЕОРИИ РЕЛЕЙНО-КОНТАКТНЫХ СХЕМ

НА РАЗВИТИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ**

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

Ключевые слова: подклассы универсума, алгебра логики, релейно-кон-тактные схемы.

This article gives a retrospective of ideas on designing and making technical devices to solve logical problems, in particular, problems of algebra logic. In the twentieth century the process was being reversed: projects of implication of logic in making relay-contact circuits were arising in order to have even more sophisticated control systems created. New logical tools were needed to solve those problems that stimulated the development of logic itself.

Key words: subclasses of mundus, algebra of logic, relay-contact circuits.

В.И. Шестаков в статье, посвященной исследованию А-схем1, отмечает, что идея применения булевой алгебры в конструировании и упрощении релейных схем была высказана физиком П. Эрен-фестом в 1910 г. в рецензии на «Алгебру логики» Л. Кутюра2. В этом небольшом сочинении Кутюра подводит своего рода итог развития алгебры логики в XIX столетии, а также указывает ее характерные свойства. В частности, автор подчеркивает, что «эта алгебра допускает в самой логике две различные, почти параллельные интерпретации, в зависимости от того, выражают ли буквы понятия или предложения»3. Если буквы «выражают понятия», то дело сводится к исследованию соотношений их объемов, т.е. к оперированию с подклассами универсума. Этот вариант алгебры логики был развит раньше, чем исчисление предложений, хотя и его созданию предшествовал довольно длительный подготовительный период, в течение которого было выявлено преимущество «объемной точки зрения» на понятия для введения и уточнения операций алгебры

* Кузичева Зинаида Андреевна — кандидат физ.-мат. наук, старший научный сотрудник механико-математического ф-та МГУ, 312-64-11.

** Работа выполнена при поддержке РФФИ (проект № 040680382).

логики. Преимущество объемной трактовки, конечно, связано с тем, что «объем понятия» — подкласс универсума, и соотношения между понятиями сводятся к представлению их в виде комбинаций таких подклассов. Но отчетливое выявление этого обстоятельства отнюдь не было «одномоментным» действием. Непосредственные предшественники этого варианта алгебры логики — И. Ламберт (1728—1777) и Л. Эйлер (1707—1783). Первый из них делал попытки оперировать и с признаками понятий, которые, однако, не увенчались успехом. При оперировании с признаками понятий основная трудность возникает в связи с тем, что фактически у любого объекта неопределенно много признаков. Это существенно затрудняет, например, задачу точно отделить друг от друга операции сложения и умножения классов, скажем, у Ламберта они фактически совпадали. С объемной же точки зрения сложение и умножение — это соответственно объединение и пересечение классов (т.е. множеств)4. Заметим, кстати, что И. Г. Ламберт, по-видимому, первый использовал словосочетание «алгебра логики». Оно встречается в его заметках, в которых он ежемесячно обозначал темы своих основных занятий.

Л. Эйлер в «Письмах к одной немецкой принцессе...» изложил геометрическую интерпретацию силлогистики Аристотеля5. Причем он проводит здесь последовательную «объемную точку зрения», пригодную для графического представления соотношений между понятиями и формулирует два главных свойства, касающихся «содержимого» и «содержащего»:

1. Все, что имеется в содержимом, имеется в содержащем.

2. Все, что находится вне содержащего, находится и вне содержимого.

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

Первым явно употребил термин «универсум» А. де Морган (1806—1871) не позднее 1839 г. Он же, а не Ст. Джевонс, как это общепринято утверждать, впервые в трактате «Формальная логика» сформулировал систему, которую теперь принято называть булевой алгеброй6. Обозначение 1 и 0 соответственно для универсального и пустого классов ввел Дж. Буль в работе, озаглавленной «Матема-

тический анализ логики, являющийся опытом исчисления дедуктивного рассуждения»7. Именно с этой работой Буля обычно связывают начало формирования математической логики как логики классов. «Формальная логика» А. де Моргана каким-то образом осталась вне внимания исследователей.

Но, подчеркнем, исчисление предложений — та интерпретация, которая могла послужить источником идеи применения логики к решению задач техники, в особенности же наделение предложений истинностными значениями. Однако алгебра логики в форме исчисления предложений появилась значительно позже, чем логика классов, — только в конце XIX в. Как известно, первое строгое построение этого исчисления принадлежит Г. Фреге (1879). Он же дал представление о том, насколько существенны истинностные значения предложений. И Буль, и де Морган пытались вводить операции над предложениями, ибо цель логики — выведение истинных следствий из истинных посылок. «Мы рассматриваем, — говорит А. де Морган, — само предложение как один из объектов, не подразделяемых на подобъекты, в которых имена сравнивались бы между собой»8. Поскольку в исследовании предложений принципиально учитывать значение истинности, де Морган пытается как-то включить его в исчисление, для чего он вводит универсум истинности или ложности предложений, однако связать этот универсум с операциями над предложениями ему все-таки не удается.

Дж. Буль (1815—1864) поступал иначе. В своем капитальном труде «Исследование законов мышления»9 он связывает с каждым предложением интервал времени, в течение которого предложение истинно. Всегда ложному предложению соответствует отрезок нулевой длины, или просто 0, а всегда истинному предложению — «вся временная прямая», 1. Тем самым он сводит исследование отношений между предложениями к отношениям между промежутками времени, иными словами, к уже созданному в 1847 г. исчислению классов, и это не дает ему фактически ничего нового в интересующем нас аспекте.

Исчисления предложений (высказываний) появились в конце XIX в., и к началу XX в. они были сравнительно хорошо изучены. Поэтому человек, не являющийся специалистом в этой области, мог усмотреть, что существенным для исчисления предложений является именно соотношение истина—ложь, т.е. значения «и», «л», или 1, 0. Тогда-то и стала возможной мысль «обернуть проблему»: если до тех пор предпринимались попытки использовать технические средства для решения задач логики, теперь возникает идея применить логику к решению задач техники.

С.А. Яновская в своем обзоре исследований по основаниям математики и математической логики писала: «Математическая логика возникла первоначально в результате логического анализа

используемых в математике средств доказательства. Тем интереснее для нас, что построенный ею аппарат в руках инженеров и физиков-конструкторов оказался орудием синтеза конструируемых ими механизмов. Он был использован в области электро- и радиотехники, точной механики и счетно-решающих устройств телемеханики и автоматики»10.

Однако имеет смысл несколько подробнее остановиться на том этапе становления математической логики, когда пытались использовать технические средства для решения задач логики. Мы имеем в виду прежде всего построение так называемых логических машин.

Построение «логических машин» в XIX в. было довольно широко распространенным увлечением. Так, в 1800 г. англичанин Ч. Стенхоп (1753—1816) построил так называемый «демонстратор», позволяющий чисто механически проверять силлогизмы и получать следствия из посылок. Впрочем, это устройство и самим создателем использовалось скорее как забавная игрушка, которую он демонстрировал в салонах. Правда, при создании «демонстратора» Стенхоп предвосхитил методы количественного определения предиката и составления логических равенств, предложенные позднее У. Гамильтоном (1788—1856) и А. де Морганом (1806—1871) независимо друг от друга11.

Заметим, что Гамильтон также демонстрировал некую «логическую машину» собственной конструкции, о чем он упоминал в своих «Лекциях по метафизике и логике», но не дал описания этого устройства. Дж. Венн — автор знаменитых диаграмм — предлагал схему «машины», в которой использовалось бы устройство, имитирующее деление заданными классами универсума на подклассы. С помощью пружинного механизма подклассы, которые в силу условий задачи оказывались пустыми, спускались ниже рабочей поверхности «машины», оставшиеся на поверхности давали ответ на вопрос о соотношении подклассов, о которых спрашивалось в задаче. Однако большую известность получила машина Джевонса.

Решение задач с использованием разложений универсума на подклассы (конституенты) было весьма трудоемким. И связано это было не с идейными трудностями, а с тем, что требовало огромного перебора, хотя сводилось к повторению однообразных и в принципе несложных операций. Требовалось выписывать кон-ституенты (их число 2т, где т — число классов, участвующих в задаче), сравнивать их с посылками задачи и отбрасывать те из них, которые противоречат условиям задачи.

Джевонс понял, что для каждого данного (небольшого) числа классов набор подклассов (его Джевонс называет логическим алфавитом) можно заготовить заранее. Например, на одном из гори-56

зонтальных выступов доски он устанавливал подходящий для задачи «алфавит», на другом — фигурирующие в задаче подклассы. Подклассы, противоречащие посылкам, снимались с верхней линии, после чего на ней оставалась так называемая «единица задачи» и можно было находить ответы на вопросы, касающиеся отдельных классов. Джевонс решил полностью механизировать описанные выше процессы. Потратив примерно десять лет, он построил логическую машину, которая решала задачи, касающиеся четырех классов. Это, конечно, была также своего рода игрушка, не имевшая большого практического значения. Смысл ее заключался в том, что она положительно отвечала на вопрос: возможно ли механизировать решение идейно несложных задач, требующих большой рутинной работы, связанной с составлением и перебором конститу-ентов. Но «решала» эта машина задачи только о четырех классах. Для любого другого числа классов следовало бы строить другую машину. В XIX в. в России также проектировались логические машины, аналогичные машине Джевонса.

Однако поиск технических средств решения задач логики в тот период не привел к существенным результатам, несмотря на все остроумие предлагаемых и используемых устройств. Иначе обстояло дело с проблемой использования логики в решении определенных технических задач. К тому времени математическая логика сформировалась как самостоятельная математическая дисциплина со своим специфическим аппаратом. Повторим, исчисление высказываний и исчисление предикатов были впервые сформулированы в явном виде Г. Фреге в 1879 г.12 Но важность высказанных им идей была понята и оценена далеко не сразу13. Поэтому весьма своевременной оказалась работа Л. Кутюра. Идея же использования логики в исследовании и построении релейно-контактных схем была высказана в 1910 г., о чем сказано в начале статьи. Но реализация этой идеи относится лишь к 30-м годам прошлого века. И это тоже объяснимо: технические устройства, к которым могли быть применены логические средства, должны были достигнуть определенного уровня, стать совершеннее и разнообразнее, на это потребовалось около двух десятилетий. Как это часто бывало в истории науки, назревшие, актуальные идеи практически одновременно приходят в голову разным людям в разных странах. Так было и на этот раз. Практически одновременно идеи применения логики в теории релейно-контактных схем были высказаны нашим соотечественником В.И. Шестаковым, а также японцем А. Накашимой и американцем К. Шенноном14. В данной ситуации решение вопроса о приоритете отнюдь не является простым и однозначным. Мы не станем касаться этого важного и даже драматического вопроса. Заметим только, что С.А. Яновская в упомянутой выше статье горячо (и не без оснований) защищала первенство В.И. Шестакова15.

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

Если обозначить переменные, представляющие контакты, буквами а, Ь, с, ..., принимающими значение 0 (контакт разомкнут) и 1 (контакт замкнут), то произведение а • Ь представляет последовательное, а сумма а + Ь — параллельное соединение контактов. Произведение а  Ь равно 1 (схема замкнута) тогда и только тогда, когда оба контакта а и Ь замкнуты (равны 1), сумма а + Ь равна 1 (замкнута) тогда и только тогда, когда замкнут (равен 1) хотя бы один контакт. Контакт, противоположный данному контакту а, равен 0 (разомкнут), если данный контакт равен 1 (замкнут) и наоборот. Контакт, противоположный а, обозначается а'. С помощью этих трех операций можно строить различные булевы функции от контактов, подобно построению функций алгебры высказываний. Эти функции называют иногда переключательными. Эквивалентными естественно считать две схемы, если при одних и тех же значениях входящих в них контактов они будут одновременно замкнуты или одновременно разомкнуты. Другими словами, две схемы эквивалентны тогда и только тогда, когда эквивалентны представляющие их переключательные функции. Но это логическая эквивалентность. В техническом отношении логически эквивалентные схемы могут быть различными. Таким образом, возникает проблема упрощения схемы, поиска оптимальной (в каком-либо заданном отношении). Эта задача описанным способом сводится к упрощению переключательных функций, т.е. к некоторой проблеме логики, точнее, исчислению высказываний.

Здесь сразу возникает вопрос о соответствии между исчислением переключательных функций, или релейно-контактных схем, и исчислением высказываний. С конъюнкцией, дизъюнкцией, отрицанием и отношением эквивалентности (равносильности), с одной стороны, и последовательным, параллельным, соединением, «отключением» и отношением эквивалентности переключательных функций, с другой стороны, имеется очевидное полное соответствие. Но в исчислении высказываний есть импликация. Что ей соответствует в исчислении переключательных функций? Вопрос как будто бы снимается, если вместо импликации а ^ Ь использовать эквивалентную ей дизъюнкцию —а V Ь. Однако этим не снимается вопрос о сущности импликации. С содержательной точки зрения импликация формализует оборот «если..., то», что

сразу же порождает целый спектр вопросов, которым посвящена обширная литература. Одним из первых вопросов, касающихся импликации, является вопрос: импликация — это функция или отношение?16 Да, импликация — это функция, являющаяся суперпозицией отрицания и дизъюнкции. А как же быть с «если..., то»? В ранних исследованиях по теории релейно-контактных схем импликация воспринималась как отношение на множестве высказываний. Например, в известной монографии М.А. Гаврилова «Основные соотношения алгебры логики» отмечается, что импликация — это отношение (соотношение) (на множестве высказываний, суждений — в терминологии автора). Этому «соотношению», однако, не ставится в соответствие никакого отношения «соотношения» между схемами:

«В релейно-контактных схемах нас будет интересовать исключительно только соотношение равносильности, так как при преобразованиях релейно-контактных схем необходимо, как уже указывалось выше, уметь заменять одну схему другой, равносильной ей по действию»17.

Здесь уместно отметить также особенности соответствия отрицания, с одной стороны, и «выключения» — с другой. Отрицание — это тоже своего рода «особая точка» в логике. Классическое контрадикторное отрицание формализует, представляет лишь один из содержательных смыслов отрицания в естественных языках. В естественном языке отрицание богато оттенками, которые игнорируются при этой формализации. Но и с состояниями схемы «включено» — «выключено» ситуация аналогична, поскольку включение (и выключение) контактов не происходит мгновенно, а продолжается в течение некоторого времени. Поэтому технические устройства констатируют «включено» лишь при определенном состоянии сети.

В.И. Шестаков показал в своей кандидатской диссертации, защищенной в 1938 г., существенная часть которой была опубликована в его уже упоминавшейся здесь статье, что непосредственное применение готового аппарата исчисления высказываний возможно лишь для сравнительно простых схем, которые можно представлять состоящими из контактных двухполюсников. Эти схемы он назвал схемами класса А (А-схемами), они включают лишь параллельные и последовательные соединения и не содержат мостиковых соединений, необходимых в схемах с переключателями. М.А. Гав-рилов определяет мостиковое соединение как «многополюсное соединение, при котором один или несколько многополюсников, присоединенных к входному и выходному полюсам, связываются между собой, или с входным или выходным полюсом, или с тем и другим одновременно, релейно-контактными цепями, присоединенными к промежуточным узлам»18.

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

M (a, b, c, d, e) = d v ace v bcd v be,

соответствующей некоторой мостиковой схеме, не существует такого представления через двухместные функции, чтобы в нем ни одна из букв не встречалась более одного раза. Такое представление А.В. Кузнецов назвал бесповторной суперпозицией и доказал не только справедливость предположения В.И. Шестакова, но и то, что функцию M (a, b, c, d, e) нельзя представить бесповторной суперпозицией через функции от меньшего числа аргументов19. Отечественными учеными в середине прошлого столетия были получены важные результаты, существенно обогатившие арсенал функций алгебры логики и расширившие круг проблем, решение которых имело не только теоретическое значение, но находило важные приложения в различных разделах молодой кибернетики.

Таким образом, оказалось, что требования техники не просто подтверждают пригодность логики для использования в практике. Они понуждают логику к дальнейшему развитию, к развитию не произвольному, а отвечающему вполне определенным потребностям практики. Потребность исследования сложных схем явилась стимулом для постановки и решения новых проблем алгебры логики. Значительный вклад в решение этих проблем внесли отечественные специалисты, в их числе В.И. Шестаков в серии своих работ, опубликованных в 40—50-е гг. прошлого века. Характерной чертой работ В.И. Шестакова, особенно ранних, является их тесная связь с конкретными техническими объектами, действия которых поставляли ему теоретические задачи. При этом часто оказывалось, что в логике нет соответствующего аппарата для решения более сложных задач. Но вместе с тем уже в первой опубликованной работе наблюдается его стремление к наибольшей общности в постановке проблем. Для части из них он предложил свои оригинальные решения. Например, в одной из своих работ20 он показал, что характеристическая функция любой операции я-значного исчисления предложений представима алгебраическими выражениями, которые можно рассматривать как изоморфные образы релейно-контактных схем с я-позиционными переключателями. Тем самым многозначные логики также нашли важные технические приложения. Однако вклад В.И. Шестакова, как и других отечественных специалистов, в развитие указанной области

до сих пор недостаточно исследован. В то время как трудам Шеннона посвящена обширная литература, сочинения Шестакова все еще остаются малоизученными. Поэтому проблема исследования его творчества и сегодня остается актуальной.

В заключение хочется еще раз подчеркнуть, что общие закономерности взаимодействия, казалось бы, самых отвлеченных теорий и актуальных (на соответствующем историческом этапе) технических проблем явственно выступают и в нашем конкретном случае взаимодействия логики и техники. Грандиозные достижения техники в XIX в. принципиально увеличили количество вычислительной работы, в результате рационализации которой были не только изобретены логарифмы и предложены новые вычислительные методики, но и были построены первые арифмометры (В. Шиккард, Б. Паскаль, Г.В. Лейбниц). Тогда же возникают идеи «механизировать» процессы рассуждения, которые хотя и не дают удовлетворительных решений проблемы, однако и не исчезают бесследно. В XIX в. уже наблюдаются заметные результаты: появляются не только усовершенствованные вычислительные устройства, но и различного рода логические машины, призванные облегчить рутинную часть процессов вывода. Но дальнейшее развитие науки показывает, что логика (соответственно изменившаяся к тому времени) уже может служить решению технических задач, что в свою очередь ставит перед ней новые проблемы и содействует ее развитию.

ПРИМЕЧАНИЯ

1 См.: Шестаков В.И. Алгебра двухполюсных схем, построенных исключительно из двухполюсников // Журн. технич. физики. 1941. Т. XI, вып. 6. С. 532—549. Эта статья является более подробным изложением статьи, опубликованной несколько ранее в том же 1941 г. под тем же самым заголовком в журнале «Автоматика и телемеханика (Т VI, № 2. С. 15—24).

2 Couturat L. L'Alg'ebra de la logique, Paris, 1905; Кутюра Л. Алгебра логики / Пер. с фр.; Под ред. и с прибавлениями проф. И. Слешинского. Одесса, 1909.

3 Ibid. P. 1.

4 Lambert J. Sechs Versuche einer Zeichenkunst in der Vernunftlehre // Lambert J. Logische und philosophishe Abchandlungen. Bd. 1—2. Berlin, 1782—1788. Bd. 1. S. 1—180. См., например: Кузичева З.А. Символическая логика в сочинениях И. Ламберта // Историко-математические исследования. М., 1980. Вып. 25. С. 225—247.

5 Eiler L. Letteres 'a une princesse d'Allemange sur divers sujets de physique et de philosophique. СПб., 1768. T. 1—2. Перевод на русский язык см. по изданию: Эйлер Л. Письма к одной немецкой принцессе о разных физических и философских материях. СПб., 2002.

6 Morgan A. de. Formal logic, or the calculus of inference, necessary and probable. L., 1847; см., например: Кузичева З.А. Становление и развитие математической логики // Очерки по истории математики. М., 1997. С. 339—422.

7 Boole G. The mathematical analysis of logic, being an essay towards a calculus of deductive reasoning. Cambridge, 1847.

8 Morgan A. de. Op. cit. P. 149.

9 Boole G. An investigation of the laws of thought, on which are founded the mathematical theories of logic and probability. L., 1854.

10 Яновская С.А. Основания математики и математическая логика // Математика в СССР за тридцать лет. М., 1948. С. 40—41.

11 Свои идеи и методы Стенхоп не публиковал, с ними знакомились по рукописям, которые ходили в тесном кругу его близких знакомых. Устройство Стенхопа описал Р. Герли в статье «Демонстратор Стенхопа» (The Sten-hope's Demonstrator.: Mind. 1879. Vol. 4. April).

12 Frege G. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle, 1879. Имеется перевод на русский язык: Фреге Г. Логика и логическая семантика: Сб. трудов. М., 2000. С. 65—143.

13 Заметим, что иногда время создания той или иной теории указывается, можно сказать, произвольно. Например, в широко известной книге М.А. Гаврилова «Теория релейно-контактных схем» (М.; Л., 1950) утверждается: «Таким аппаратом оказалось так называемое исчисление высказываний, получившее достаточное развитие еще в конце прошлого (XIX. — З.К.) века» (с. 8). В указанное здесь время не была достаточно развита даже алгебра логики.

14 Nakashima A. Theory of reley circuits composition // Nippon Elect. Commun. Eng. 1936. N 3; Shannon C. A symbolic analysis of relay and switching circuits // Trans. of the Amer. Inst. of Electr. Eng. 1938. Vol. 57. Впрочем, этот момент требует дальнейшего изучения. Например, имеются высказывания о том, что вклад Накашимы в развитие рассматриваемых идей сильно преувеличен.

15 Шестаков В.И. Алгебра двухполюсных систем... С. 41.

16 Мы оставляем без обсуждения тот факт, что каждую функцию (операцию) можно истолковывать как отношение, поскольку это не касается напрямую рассматриваемых нами вопросов.

17 Гаврилов М.А. Теория релейно-контактных схем. С. 49.

18 Там же. С. 158.

19 Результат был доложен в МГУ на семинаре по математической логике в 1951 г., опубликован в сб.: Труды Математического ин-та им. В.А. Сте-клова. 1958. № 51. С. 186—200.

20 См.: Шестаков В.И. Представление характеристических функций предложений посредством выражений, реализуемых релейно-контактными схемами // Изв. АН СССР. Сер. Математика. 1946 № 10. С. 529—565.