«Новочеркасск НОК 2011 1 УДК 512 ББК 87.21:72 М 73 Рецензенты: Галушкин Н.Е., доктор техн. наук, профессор; Кравченко П.Д., доктор техн. наук, профессор. М 73 Коротков А.В., Мешков В.Е., Чураков В.С., Бабкина Т.А., ...»

Сопоставив этим состояниям значения трита 1, -1, 0, которые далее ради удобства будем обозначать +, -, 0, получаем отображение n-тритным вектором не только индивидных конъюнкций и предполных дизъюнкций, но и элементарных n-арных конъюнкций и дизъюнкций произвольного вида. Так, конъюнкциям xyz'u, xz'u, yz', z' будут соответствовать значения 4-тритного конструкта-вектора Ктипа: ++-+, +0-+, 0+-0, 00-0, а дизъюнкциям x' v y' v z v u', x' v z v u', y' v z, z – значения 4-тритного конструкта-вектора Д-типа:

--+-, -0+-, 0-+0, 00+0.

Построенные на n-тритных векторах ДК- и КД-цепи при должным образом пересмотренных наборах интерпретирующих базисных процедур способны отображать теперь не только СНФвыражения, но и произвольное булево выражение в нормальной форме с фиксированным порядком размещения терминов в элементарных конъюнкциях и дизъюнкциях. Например, выражение xy v x'y, отобразимое 2-арной двоичной ДК-цепью 11 01, троичной 2арной цепью отобразимо как в СДНФ ++ -+, так и в минимальной ДНФ 0+, а выражение xy' v x'y v x'y' (двоичная ДК-цепь 10 01 00) троичной ДК-цепью отображается в четырех вариантах: +- -+ --, +т. е. в СДНФ, в двух тупиковых и в минимальной ДНФ.

Угадывается "алгебраическая полнота" троичного отображения, и в булевой алгебре она действительно имеет место: посредством троичных конструктов удается перепоручить компьютеру практически все, что может делать в булевой алгебре человек и даже то, чего еще не может (например, минимизации произвольного булева выражения [7]).

Описанное усовершенствование компьютерной реализации булевой алгебры представляет собой один из результатов конструктного подхода к информатике. Результат фундаментальный, поскольку касается основы и вместе с тем открывает пути совершенствования последующих ступеней – алгебраизации силлогистики, модальной и диалектической логики [8], упорядочения теории вероятностей и нечетких множеств [9, 10].

Брусенцов Н. П., Златкус Т. В., Руднев И. А. ДССП-диалоговая система структурированного программирования // Программное оснащение микрокомпьютеров. – М.: Изд-во Моск. ун-та, 1982. С. 11-40.

Брусенцов Н. П. Микрокомпьютеры. – М.: "Наука", 1985.

С. 141-170.

Развиваемый адаптивный язык РАЯ диалоговой системы программирования ДССП / Н. П. Брусенцов, В. Б. Захаров, И. А. Руднев, С. А. Сидоров, Н. А. Чанышев. – М.: Изд-во Моск. ун-та, 1987. 80 с.

Концептуальная характеристика РИИИС-процессора / Н. П. Брусенцов, С. П. Маслов, Х. Рамиль Альварес, С. А. Сидоров // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во ф-та ВМиК МГУ, 1996 г. С. 16-43.

Владимирова Ю. С. Конструктная реализация булевой алгебры // Интегрированная система обучения, конструирования программ и разработки дидактических материалов. – М.: Изд-во фта ВМиК МГУ, 1996 г. С. 44-69.

Брусенцов Н. П., Владимирова Ю. С. Решение булевых уравнений // Методы математического моделирования. – М.: ДиалогМГУ, 1998. С. 59-68. Solution of Boolean Equations. // Computational mathematics and modeling, Vol. 9, № 4, 1998, pp. 287-295.

Брусенцов Н. П., Владимирова Ю. С. Троичный минимизатор булевых выражений // Программные системы и инструменты.

Тематический сборник № 2. – М.: Факультет ВМиК МГУ, 2001.

Брусенцов Н. П. Трехзначная диалектическая логика // Программные системы и инструменты. Тематический сборник № 2.

– М.: Факультет ВМиК МГУ, 2001. С. 36-44.

Брусенцов Н. П., Деркач А. Ю. Логическая модель теории вероятностей и нечетких множеств Заде // Цифровая обработка информации и управление в чрезвычайных ситуациях. Материалы Второй международной конференции (28-30 ноября 2000 г., Минск.) – Минск: Институт технической кибернетики НАН Беларуси, 2000. Том 1, с. 41-44.

Брусенцов Н. П., Деркач А. Ю. Трехзначная логика, нечеткие 10.

множества и теория вероятностей // Программные системы и инструменты. Тематический сборник № 2. – М.: Факультет ВМиК МГУ, 2001. С. 88-91.

Заметки о трехзначной логике 11.

Доложено на Ломоносовских чтениях 2002 г. на факультете 12.

Опубликовано в: Программные системы и инструменты: Тематический сборник № 3 // Под ред. Л. Н. Королева.М. Издательский отдел ВМиК МГУ, 2002, с. 6-10.

УПОРЯДОЧЕНИЕ БУЛЕВОЙ АЛГЕБРЫ*

Инструментальную основу современной информатики составляет булева алгебра с базисными операциями отрицания, конъюнкции и дизъюнкции, определенными таблицами, в которых набор значений как операндов, так и результатов операций исчерпывается двумя, интерпретируемыми обычно как «истина» и «ложь» и обозначаемыми соответственно цифрами «1» и «0», либо буквами: русскими «И», «Л», латинскими «T», «L». Это алгебра двухзначной «логики высказываний», отождествляющей символ операции отрицания «» с частицей «не-», символ конъюнкции «» – с грамматическим союзом «и», символ дизъюнкции «» – с «или». Истолковываемые таким образом символы операций называют логическими связками.

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

Таким образом, получилось исчисление, необыкновенно благоприятное для исследователей парадоксов, но на практике более чем бесполезное, ибо не соответствует здравому смыслу.

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

Что-то в булевой алгебре не так, как должно быть по логике бытия. Прежде всего подозрение падает на операцию булева отрицания, которая почему-то определена так, что порождает дополнеТекст печатается по изданию: Н.П. Брусенцов. Упорядочение булевой алгебры // ternarycomp.narod.ru>arrangement.doc ние отрицаемого до рассматриваемого многообразия возможностей (до универсума), т.е. в смысле «все то, что не А», где А – отрицаемое. Но ведь по здравому смыслу отрицанием данной определенности признается любая несовместимая с ней (противоречащая ей) определенность из имеющихся в универсуме. И ясно, что отрицание составных (неэлементарных) определенностей неоднозначно.

Например, отрицаниями простейшей составной определенности xy – конъюнкции (совместности) элементарных определенностей x и y – будут: x, y, xy, xy, xy, x y.

В булевой алгебре из этих шести принято последнее, отрицаниедополнение. Оно «замечательно» тем, что не оставляет места промежуточному третьему: все, что не отрицается, утверждается и обратно, так что алгебра булевых выражений сохраняет свойственную элементарным определенностям двухзначность. Но оно не столь элементарно как диаметральная инверсия xy, сводящаяся к инвертированию в отрицаемом выражении всех вхождений каждой элементарной определенности, каждого термина.

Условимся обозначать дополнение префиксом «», а инверсию – постфиксом «штрих». Инверсия и дополнение, например, конъюнкции xy выразятся так:

В отличие от инверсии как потерминного инвертирования выражения, отрицание-дополнение достигается исключением отрицаемого выражения xy из характеризующей универсум полной дизъюнкции xy xy xy xy 1. Затем полученное СДНФ-выражение минимизируется в x y, оказывающееся двойственным (дуалом) тому, что дала инверсия. Таким образом, булево дополнение e выражения e есть дуал его инверсии e:

Операция получения двойственного (дуала) состоит во взаимозамене в выражении-операнде символов на и на.

Данное соотношение обратимо – инверсия в свою очередь есть дуал дополнения:

Однако инверсия, как уже было сказано, элементарней дополнения. Это видно из того, что функциональную полноту булевой алгебры обеспечивает пара дополнение-конъюнкция, либо же пара дополнение-дизъюнкция, тогда как в системе с инверсией необходимы и конъюнкция, и дизъюнкция. Дело в том, что непременный в определении дополнения закон исключенного третьего e e на инверсию не распространяется и поэтому тождество де Моргана определяющее посредством дополнения конъюнкцию через дизъюнкцию и обратно, в случае инверсии не имеет места. В силлогистике инверсии соответствует контрарность, а дополнению – контрадикторность [1].

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

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

Рассмотрим конкретные примеры интенсиональной интерпретации простейшего булева выражения – элементарной конъюнкции.

В n-терминном универсуме, т.е. при различении по n первичным критериям, имеем n-местную (n-арную) конъюнкцию, каждой из компонент которой придается один из трех статусов: необходимо присущее / антиприсущее / привходящее. Булева конъюнкция содержит (необходимо) присущие ей термины непосредственно, без каких-либо функциональных знаков, каждый антприсущий термин – под знаком инверсии, привходящие термины не содержатся (умалчиваются). Например, в трехтерминном x,y,z-универсуме конъюнкции xyz присущи x и y, антиприсуще z, конъюнкции же xz присуще x, антиприсуще z, а умалчиваемое в ней y – привходяще, т.е. необходимо не присуще и не антиприсуще.

Еще одна практически важная интерпретация булевых выражений – теоретико-множественная [2]. Та же конъюнкция xyz истолковывается как множество, которому принадлежат элементы x, y и антипринадлежит (не может принадлежать) элемент z. Конъюнкция xz представляет собой нечеткое множество, которому необходимо принадлежит x, антипринадлежит z, а элемент y не принадлежит и не антипринадлежит с необходимостью (безусловно). Элементы обретают привходящий статус в результате дизъюнкции множеств, например: xyz xyz xz [3].

Конъюнкции без умолчания терминов являются четкими, категорическими множествами в традиционном понимании. Дизъюнкции конъюнкций (ДНФ-выражения) представляют собой нечеткие множества. Множества вообще, четкие и нечеткие, условимся называть совокупностями. Произвольное булево выражение в теоретико-множественной (совокупностной) интерпретации истолковывается как совокупность первичных терминов. Операция инверсии выражения инвертирует представленную этим выражением совокупность терминов, превращая принадлежащие ей в антипринадлежащие, антипринадлежащие в принадлежащие, а привходящие оставляя без изменения.

К булевым выражениям как к совокупностям терминов применимы, помимо инверсии, операции пересечения, объединения и теоретико-множественной разности. Примеры:

(xyz) xyz Вместе с тем, базисные булевы операции (связки) – конъюнкция и дизъюнкция – обретают новое истолкование как конъюнкция и дизъюнкция совокупностей. Четкая совокупность (множество) формируется путем конъюнкции нечетких, например: xz xy xyz.

Нечеткие совокупности суть дизъюнкции четких, например: xyz xyz xz.

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

Посредством базисных связок – инверсии, конъюнкции и дизъюнкции – выразима произвольная n-местная (n-терминная, n-арная) булева функция. Более того, в нормальных формах (ДНФ и КНФ) инвертируются только первичные термины, а в совершенных нормальных формах (СДНФ и СКНФ) нет умалчивания терминов. Выражение в совершенной дизъюнктивной форме представляет собой дизъюнкцию индивидных (n-терминных) конъюнкций, определяющую класс соответствующих этим конъюнкциям четких совокупностей (множеств) терминов. Этому классу соответствует в алгебре 2й ступени (в булевой алгебре дизъюнктов) четкая совокупность nтерминных индивидов, которые в логике предикатов называют «предметами». Нечеткой совокупности таких индивидов, допускающей привходящую принадлежность ей некоторых из них, в алгебре 1-й ступени соответствует класс с привходящей включенностью в него отдельных подклассов – нечеткий класс.

Например, характеристическая функция отношения следования, представленного в аристотелевой силлогистике общеутвердительным суждением «Всякое x есть y» («Всякому x присуще y», «y содержится в x», «y необходимо следует из x»), выражается конъюнкцией дизъюнктов вида:

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

Рассматриваемая нечеткая совокупность 2-й ступени характеризуется необходимой принадлежностью ей индивидов xy и xy, необходимой непринадлежностью (антипринадлежностью) xy и привходящей принадлежностью индивида xy, который в выражении умалчивается. Атрибут соответствующего этой совокупности индивидов класса в алгебре 1-й ступени определяется как общий всем ее членам, т.е. дизъюнкцией атрибутов всех необходимо принадлежащих совокупности, а также привходящих индивидов. В рассматриваемом примере такой нечеткой дизъюнкцией будет где – символ третьего «значения истинности» – привходящего: не-0 и не-1, а нечто небезусловное, некатегоричное, оцениваемое как вероятность, либо как доля (часть, процент) дискретного значения 1: 0 1.

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

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

VxyVxyVxy VxVxyVy Vx(x y)Vy Каждое из этих выражений выявляет в отношении необходимого следования y из x ту или иную его характерную черту, позволяет, так сказать, посмотреть на него с разных сторон. Согласно первому выражению, y следует из x, если в универсуме имеются (существуют) вещи класса xy и класса xy, но не может быть вещей класса xy.

Второе выражение требует существования классов x и y, исключая существование класса xy. В третьем выражении требование несуществования класса xy преобразовано в удовлетворенность каждой из вещей условию материальной импликации x y x y.

То, что всеобщая удовлетворенность импликации равносильна несуществованию (т.е. исключенности) xy, еще раз указывает на несущественность в ее СДНФ-выражении члена xy. А то, что удовлетворенность импликации не означает необходимого следования (кроме нее требуется существование x и существование y), снимает проблему «строгих» и «сильных» импликаций, опровергая вместе с тем общепринятое «положение», будто бы из противоречия следует все что угодно. Импликация действительно удовлетворяется в случае противоречивости антецедента, но ведь противоречивое не существует, а из несуществующего ничто не может следовать.

Однако возвратимся к 1-й ступени, с тем чтобы уточнить и четко сформулировать принципы, положенные в ее основание. Составляя первооснову булевой алгебры, 1-я ступень является тем самым и фундаментом всех последующих, определяемых посредством этой алгебры разделов информатики – теории множеств, арифметики и теории чисел, числовых функций, а главное – искусства достоверного рассуждения (доказательства), которое по Аристотелю «будучи способом исследования, прокладывает путь к началам всех учений» [4, 101b3].

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

Что же называть ее базисом?

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

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

Операция инверсии булева выражения определена как инвертирование каждого вхождения каждого из имеющихся в этом выражении терминов. Например:

Операции конъюнкции и дизъюнкции выражений однозначно определены присущими им законами дистрибутивности и поглощения, однако в оптимально упорядоченной системе они реализуемы более просто и эффективно, например, как соответственно пересечение и объединение представляющих данные выражения совокупностей их СДНФ-членов. Упорядочение (синоним «структурирования») – это выявление в рассматриваемом естественного порядка взаимосвязей и неуклонное подчинение ему в процессе исследования и развития системы. Образцами упорядочения, к сожалению не получившими должного понимания и применения, являются «Упорядочение дел человеческих» и «Великая дидактика» Яна Амоса Коменского, а в наше время – «Структурированное программирование» Эдсгера Дейкстры. Основоположником упорядочения следует признать первооткрывателя диалектики Гераклита, который указал на существование всеобщего естественного миропорядка и назвал его Логосом. С учетом дальнейшей модификации смысла этого слова следует истолковывать его как адекватное отображение указанного миропорядка в сознании и в языке людей, в информатике.

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

Например, компонентами молекул полагаются атомы, в свою очередь сконструированные из компонент атомного уровня, которые затем декомпонуются на более элементарные составляющие, и т.д.

Хотя можно ведь «слепить» молекулу и непосредственно из элементарных частиц. В «неструктурированном программировании»

именно так и делали, пока Э.Дейкстра не выступил с призывом «Разделяй и властвуй», впрочем, нажлежащего понимания не получившим.

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

Совершенная дизъюнктивная нормальная форма (СДНФ) выражения булевой функции n переменных – это дизъюнкция n-терминных (индивидных) конъюнкций, представляющая собой четкую, альтернативную, совокупность (класс) индивидов в nтерминном универсуме. Кстати, операция отрицания-дополнения булева выражения равносильна инверсии этой совокупности индивидов. Действительно, из составляющих n-терминный универсум 2n индивидных конъюнкций (из полной совокупности их) подсовокупность членов СДНФ-выражения соответствует именуемому данным выражением классу, а инверсия этой совокупности, т.е. дополняющая до 2n подсовокупность, в той же дизъюнктивной форме представляет собой выражение дополнительного класса, является отрицанием-дополнением исходного СДНФ-выражения. Короче говоря, операция отрицания-дополнения СДНФ-выражения сводится к инвертированию совокупности его членов.

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

В совершенной конъюнктивной нормальной форме (СКНФ) выражение представлено конъюнкцией предполных дизъюнкций, т.е. дополнений индивидных конъюнкций. Например, выражение характеристической функции x y отношения эквивалентности, состоящее в СДНФ из двух индивидов: xy xy, в СКНФ оказывается конъюнкцией дизъюнкций: (x y)(x y), причем дизъюнкции эти суть дополнения индивидов xy и xy из СДНФ-выражения функции антиэквивалентности: xy xy. Операция отрицаниядополнения СКНФ-выражения, как и СДНФ, сводится к инвертированию совокупности его членов. Однако конъюнкции СКНФвыражений соответствует не пересечение, а объединение, и дизъюнкции – не объединение, а пересечение совокупности их членов.

Примеры:

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

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

Пересечение и объединение, подобно конъюнкции и дизъюнкции, идемпотентны и коммутативны:

Они взаимно дистрибутивны одно относительно другого, а также относительно конъюнкции и дизъюнкции:

Инверсия булева выражения формально означает инвертирование каждого вхождения каждого из входящих в это выражение терминов с сохранением неизменными всех иных связок. При этом инверсия первичного (элементарного) термина x удовлетворяет аксиомам:

Содержательно инверсия термина означает изменение на противоположный его статуса как члена совокупности. Инвертируются, в сущности, не термины, а их статусы в рассматриваемой совокупности: принадлежность ей термина x заменяется антипринадлежностью (исключенностью принадлежности) – x, антипринадлежность же x заменяется принадлежностью x. Так что инвертируются не термины, а совокупности. Инверсией же отдельного термина называют, допуская «вольность речи», инверсию однотерминной совокупности, однотерминного булева выражения.

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

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

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

Дизъюнкция булевых выражений (ДНФ) определяет характеризуемый ею объект дизъюнктивным (альтернативным) перечнем достаточных, но не необходимых, условий – подвыражений более строгих, чем ДНФ-выражение в целом. Это различные конкретизации объектов обозначенного ДНФ-выражением класса. Из данности класса следует возможность каждого из относящихся к этому классу объектов (подклассов), становящаяся необходимостью при наложении надлежащих дополнительных условий.

Начало иерархически упорядоченной булевой алгебры, или основание ее первой ступени, составляют инверсия и конъюнкция первичных (несоставных, недекомпозируемых) терминов. Комбинация (“суперпозиция”) этих операций порождает простейший тип составного булева выражения – элементарную конъюнкцию. Алгебра элементарных конъюнкций замкнута и функционально полна в том смысле, что инверсии и конъюнкции выражений этого типа суть тоже элементарные конъюнкции, а всякая представимая в виде элементарной конъюнкции функция терминов реализуема посредством операций инверсии и конъюнкции. Порождая элементарные конъюнкции, эти операции применимы затем и к ним самим, наряду с потерминными операциями пересечения и объединения их как совокупностей терминов.

В n-терминном универсуме всего 3n различных элементарных конъюнкций, из которых 2n индивидные (без умалчивания терминов), соответствующие четким совокупностям, т.е. множествам присущих характеризуемым ими индивидам первичных определенностей. Неиндивидные (“нечеткие”) элементарные конъюнкции именуют неиндивидные классы рассматриваемых «предметов», представляя собой нечеткие совокупности присущих им определенностей. Следует заметить, что понятие индивида (“предмета”, “вещи”) относительно: n-терминная элементарная конъюнкция представляет собой индивид только в n-терминном универсуме, т.е.

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

Вторая ступень алгебраической иерархии строится посредством тех же операций инверсии и конъюнкции, но применяемых теперь не к первичным терминам, а к индивидам. Они представлены nтерминными элементарными конъюнкциями и в отличие от терминов, предполагающихся ортогональными, т.е. совмещаемыми друг с другом в любых сочетаниях, попарно несовместимы. Поэтому совокупность индивидов немыслима как нераздельное единство, не может быть «единичной вещью». Она может быть лишь набором, группой взятых вместе, сосуществующих, единичных вещей. Так сказать, конъюнкцией их существований.

Существование в универсуме U «вещи», охарактеризованной булевой функцией первичных терминов (атрибутом) f, есть принадлежность f U – отношение, равносильное присущности U существования f:

Интегральная дизъюнкция (“дизъюнкт”) Vf есть дизъюнкция значений, принимаемых атрибутом f на элементах совокупности U, распространенная на всю эту совокупность, т.е. на весь универсум.

Сосуществование (сопринадлежность совокупности U) «вещей» f и g выражается соответственно конъюнкцией их существований:

Отношения существования и сосуществования выразимы при помощи квантора существования логики предикатов: Vf p f(p), Vf Vg p f(p)g(p), где p – «предметная переменная». Однако ввиду отмеченной выше относительности понятия «предмета» (индивида) и обусловленной им неоправданной усложненности алгебры, вместо кванторов с предметной переменной целесообразней использовать аналоги интегральной суммы и произведения – интегральные дизъюнкцию и конъюнкцию (дизъюнкт и конъюнкт). При этом алгебра совокупностей 2-й ступени (совокупностей индивидов) с базисными операциями инверсии и конъюнкции полностью воспроизводит булеву алгебру 1-й ступени, но теперь применительно не к первичным терминам, а к дизъюнктам и конъюнктам.

Конкретная совокупность индивидов в n-терминном универсуме отображается конъюнкцией неинвертированных и инвертированных дизъюнктов от n-арных элементарных конъюнкций. Например, в x,y-универсуме совокупность индивидов xy и xy, представляющая собой отношение актуальной эквивалентности x y, выражается в виде VxyVxyVxyVxy, а нечеткая совокупность индивидов, соответствующая отношению актуального (необходимого) следования x y, получается элиминацией в этом выражении дизъюнкта Vxy: VxyVxyVxy.

В алгебре 1-й ступени эти совокупности отображены выражениями общих атрибутов принадлежащих им индивидов, т.е. дизъюнкциями n-арных конъюнкций (СДНФ-выражениями), представляющими собой отношения потенциальной эквивалентности x y в виде xy xy и потенциального следования x y в виде xy xy xy. Буква означает привходящий статус индивида xy – не принадлежит с необходимостью и не антипринадлежит. В обычной булевой алгебре подобная возможность отображения привходящего не предусмотрена, поэтому отношение следования представлено в ней «материальной импликацией»: xy xy xy – общим атрибутом совокупности VxyVxyVxyVxy, соответствующей частному случаю отношения следования. Другим частным случаем следования является эквивалентность VxyVxyVxyVxy.

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

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

Установленное соответствие СДНФ-выражения общего атрибута индивидов совокупности ее дизъюнктному выражению означает также равнозначность конъюнкции (дизъюнкции) СДНФ-выражений и пересечения (объединения) их дизъюнктных аналогов. Другими словами, конъюнкция (дизъюнкция) булевых выражений осуществима путем пересечения (объединения) совокупностей членов СДНФ этих выражений, что технически существенно проще традиционной процедуры, использующей законы дистрибутивности.

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

Логическим, или булевым, уравнением называют равенство в котором f, g – булевы функции терминов x1, x2,..., xn, а знак символизирует заданность отношения эквивалентности (равносильности), выполняющегося на тех наборах (n-ках) значений терминов x1, x2,..., xn, на которых значения, принимаемые функциями f и g, совпадают. Совокупность таких n-ок алгебраисты называют отношением равенства функций f и g. Запись f g означает связанность f и g отношением эквивалентности: (f g) 1, подобно тому как x 1 означает данность (наличие) термина x.

Решением булева уравнения относительно термина xi называют рекурсивную функцию xi (x1, x2, x3,..., xn), удовлетворяющую заданному уравнению. Но ведь не лишено смысла и решение относительно одного из индивидов, т.е. совокупности терминов, а также относительно дизъюнкции тех или иных индивидов, т.е. некоторой булевой функции терминов, частным случаем которой является и термин xi.

Положим, что функции f и g (левая и правая части уравнения) представлены СДНФ-выражениями, т.е. дизъюнкцияими индивидов. Ясно, что индивид удовлетворяет уравнению, если он входит в обе его части либо не входит ни в левую, ни в правую часть. Назовем такой индивид парным [6, с.47]. Индивиды же, входящие в одну из частей, но не входящие в другую (непарные индивиды), уравнению не удовлетворяют. Разделение индивидов на парные и непарные радикально упрощает получение решений, а также тождественные преобразования уравнений. Действительно, выражаемое уравнением отношение сохраняется неизменным при переносе непарных индивидов из одной части уравнения в другую, а также при добавлении в обе части либо исключении из обеих частей парных индивидов.

Приведение к так называемой «нулевой» форме, в которой правая часть уравнения представляет собой пустую дизъюнкцию (обозначается цифрой «0»), достигается исключением всех парных индивидов и переносом всех непарных в левую часть. «Единичная»

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

1) xyz xyz xyz xyz тождественно xyz xyz 2) xy xy xy тождественно xy xy xy xy xy xy xy, тождественно xy xy xy 1, тождественно xy 0.

Решение уравнения относительно одного из индивидов, либо термина, либо произвольного атрибута получается путем тождественного преобразования, формирующего в левой части СДНФвыражение искомого объекта.

Например, решение уравнения из примера 2) относительно термина x получается преобразованием к виду:

т.е. решение в канонической форме будет:

Решение этого же уравнения относительно термина y:

Решение относительно индивида xy:

Решение относительно x y:

Решение уравнения из примера 1) относительно термина x:

Как видно, решение уравнения относительно заданного атрибута заключается в преобразовании уравнения к виду, при котором СДНФ-выражение атрибута составляет левую часть в СДНФвыражении уравнения, обе части которого затем минимизируются.

Сущность минимизации СДНФ-выражений в том, что булевы функции терминов, представленные дизъюнкциями индивидных конъюнкций, переводятся обратно в неиндивидное (“несовершенное”) представление [3]. Дизъюнкции индивидов порождают термины и неиндивидные классы терминов, подобно тому как конъюнкцией терминов образуются индивиды.

Впрочем, так называемая двойственность дизъюнкции и конъюнкции этим не исчерпывается: индивидным конъюнкциям однозначно соответствуют их «дуалы» – предполные дизъюнкции, конъюнкция которых порождает совершенную конъюнктивную нормальную форму (СКНФ) булевых выражений. Возникает точно такая же иерархия ступеней, как рассмотренная выше ассоциирующаяся с СДНФ, однако полностью двойственная, т.е. вместо индивидных конъюнкций теперь предполные n-арные дизъюнкции терминов, дизъюнкция индивидов, составляющая СДНФ, стала конъюнкцией двойственных индивидам предполных дизъюнкций, дизъюнкты индивидов – конъюнктами предполных дизъюнкций.

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

Поэтому для преобразования выражения e в двойственную форму надо выполнить над ним (в любом порядке) операции инверсии, дополнения и дуалирования, т.е. взаимозамены конъюнкций с дизъюнкциями. Например, перевод в КНФ выражения xy xy xy:

перевод в КНФ выражения xy xy xy:

перевод в ДНФ выражения (x y)(x y)(x y):

Проще получается дополнение выражения e, представленное в двойственной форме:

Это дуал инверсии данного выражения либо инверсия дуала его – процедура, унифицирующая правила де Моргана отрицания конъюнкции (xy) x y и отрицания дизъюнкции (x y) x y.

Существенно, что КНФ есть совокупность необходимых, а ДНФ – достаточных условий того, что представлено выражением в целом. Двойственность формы сопряжена с фундаментальной парой содержательных критериев – необходимости и достаточности.

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

Прочие функторы, такие как дополнение, дуалирование, пересечение объединение, подчинение, обозначают операции над выражениями, в нормальных формах не используемые (“небазисные”).

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

Дизъюнктивная форма начинается с элементарной конъюнкции, выражающей в ее n-арном варианте единичное (индивид) в nтерминном универсуме. Все прочие, нечеткие (неиндивдные) выражения в ДНФ суть дизъюнкции элементарных конъюнкций. В частности, дизъюнкция 2n-1 индивидов есть «предполная дизъюнкция», составляющая дополнение недостающего в ней 2n-го индивида, в совокупности с которым она становится «полной», т.е. универсумом.

Конъюнктивная форма устроена аналогично, но начинается с противоположного – с элементарной дизъюнкции, которая в n-арном варианте является предполной дизъюнкцией, т.е. дополнением противоположного ей индивида до универсума. Совершенной нормальной формой предполной дизъюнкции называется дизъюнкция 2n-1 индивидов, а минимальной формой – n-арная элементарная дизъюнкция.

1. Брусенцов Н.П. Искусство достоверного рассуждения. Неформальная реконструкция аристотелевой силлогистики и булевой математики мысли. – М.: Фонд «Новое тысячелетие», 1998.

2. Брусенцов Н.П., Деркач А.Ю. Трехзначная логика, нечеткие множества и теория вероятности // Программные системы и инструменты. Тематический сборник № 2. Под редакцией чл.-корр.

РАН Л.Н. Королева. – М.: Факультет ВМиК МГУ, 2001. (С. 88-91).

3. Брусенцов Н.П., Владимирова Ю.С. Трехзначный минимизатор булевых выражений // Программные системы и инструменты.

Тематический сборник № 2. Под редакцией чл.-корр. РАН Л.Н. Королева. – М.: Факультет ВМиК МГУ, 2001. (С. 205-207).

4. Аристотель. Топика. // Сочинения в четырех томах. Том 2. – М.: «Мысль», 1978.

5. Брусенцов Н.П., Владимирова Ю.С. Решение булевых уравнений // Методы математического моделирования. – М.: «Диалог МГУ», 1998. (С. 59-68).

6. Брусенцов Н.П. Начала информатики. – М.: Фонд «Новое тысячелетие», 1994.

Доложено на Ломоносовских чтениях 2002 г. на факультете ВМиК МГУ. Опубликовано в «Программные системы и инструменты». Тематический сборник № 3. Под ред. Л.Н.Королева. – М.: Издательский отдел ВМиК МГУ, 2002. – (С. 11-27). А также «Реставрация логики». – М.: Фонд «Новое тысячелетие», 2005. (С. 50-68).

ПОСТРОЕНИЕ ЛОГИЧЕСКИХ СХЕМ НА МАГНИТНЫХ

УСИЛИТЕЛЯХ С ПИТАНИЕМ ИМПУЛЬСАМИ ТОКА*

В 1956–1957 гг. в Вычислительном центре Московского государственного университета были разработаны элементы для построения цифровых схем1, являющихся вариантом магнитных усилителей с питанием импульсами тока [1]. В последующие годы опыт применения этих элементов в ряде устройств показал, что они могут надежно работать в цифровых схемах с тактовой частотой 200 кгц при нормальных климатических условиях.

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

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

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

* Текст печатается по изданию: Н. П. Брусенцов. Построение логических схем на магнитных усилителях с питанием импульсами тока // Магнитные элементы систем автоматики, телемеханики, измерительной и вычислительной техники. – Киев: Изд-во АН У СССР, 1964. – (с.361-367).

В работе, связанной с созданием элементов, на различных этапах участвовали сотрудники Вычислительного центра МГУ В. М. Березин, В. Я. Бедрединов, Л. М. Бедрединова, В. В. Веригин, В. В. Веригина, Н. Д. Дмитриади, Е.

В. Журавлева, Н. С. Карцева, С. П. Маслов, В. П. Розин, А. М. Тишулина, Б.

Я. Фельдман.

Диод предотвращает возникновение тока в цепи нагрузки трансформатора при намагничивании сердечника управляющими импульсами. Напряжение Е предотвращает возникновение токов в цепях связи трансформаторов под действием э. д. с. управляющих обмоток.

Введением этого напряжения достигается коренное улучшение характеристик усилителя: 1) необходимая для уверенного срабатывания энергия управляющего импульса не зависит от количества связанных со входами усилителя цепей и определяется практически только потерями на перемагничивание сердечника; 2) выход усилителя является совершенным генератором тока, причем амплитуда выходных импульсов iCB в первом приближении пропорциональна амплитуде импульсов тока питания. В реальных схемах напряжение Е получается пропусканием токов питания iI и iII через общее для всех цепей связи нелинейное сопротивление, обладающее характеристикой стабилитрона [2].

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

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

На рис. 1 усилитель с трансформатором Тр2, выполняющий операцию, имеет положительную обмотку и отрицательную обмотку. Импульс тока на выходе усилителя появляется только в том случае, если была возбуждена обмотка и не была возбуждена обмотка.

При изображении магнитных усилителей на логических схемах применяются следующие условные обозначения: усилитель представляется квадратиком, положительные входы – стрелками, направленными к квадратику, обмотки запрета – линиями, перечеркивающими квадратик, выход усилителя – стрелкой, направленной от квадратика. Принадлежность усилителя к первому или второму каналу питания обозначается черточкой, помещенной соответственно под квадратиком или над ним. Схема, данная на рис. 1, может быть изображена условно, как показано на рис. 2.

Наряду с операцией запрета, при построении логических схем на магнитных усилителях используются операции «И», «ИЛИ» и непрерывные серии импульсов.

Операция «И» осуществляется при помощи усилителя с постоянно возбужденной обмоткой запрета. Эта обмотка условно обозначается перечеркивающей квадратик линией с кружком на конце (рис. 3). Импульс тока на выходе такого усилителя получается только в том случае, когда на его входы поступят одновременно два совпадающих по времени сигнала. Операция «ИЛИ» может быть реализована двумя способами: 1) присоединением нескольких выходов к одному входу благодаря наличию диода в выходной цепи каждого усилителя (рис. 4,а); 2) использованием отдельных входных обмоток (рис. 4,6), если соединение выходов нежелательно.

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

Непрерывная серия импульсов получается при помощи усилителя с постоянно возбужденной положительной обмоткой (генератор единиц). Условное обозначение такого усилителя дано на рис. 5.

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

Использование реальных элементов связано с рядом ограничений, существенно усложняющих построение схем.

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

Например, если стандартный усилитель, рассчитанный на возбуждение одного входа, нагрузить двумя входами, то длительность его входного импульса уменьшится на 30%. Эту нестабильность можно ослабить, увеличив потребляемую мощность, однако это приведет к удорожанию элементов, поэтому признано целесообразным допустить значительную нестабильность, учитывая ее при составлении схем. Для построения схем необходимыми оказались усилители с двумя значениями нагрузочной способности: 1) простой усилитель, – обеспечивающий номинальную длительность импульса при нагрузке одним положительным входом; 2) более мощный усилитель, – обеспечивающий номинальную длительность при нагрузке двумя положительными входами.

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

Такую же длительность имеет импульс более мощного усилителя при нагрузке на один вход, а режим короткого замыкания для более мощного усилителя недопустим.

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

Кроме того, имеются менее строгие ограничения, являющиеся следствием несовершенства гистерезисной характеристики реальных сердечников.

Перечисленные ограничения могут быть сформулированы в виде правил, которые необходимо соблюдать при составлении схем:

1. Выход простого элемента не должен возбуждать одновременно более одного положительного входа.

2. Выход более мощного элемента не должен возбуждать одновременно менее одного и более двух положительных 3. Выход, возбуждающий положительный вход элемента, обладающего обмоткой запрета, должен быть нагружен не менее чем выход, работающий на эту обмотку запрета.

4. Если обмотки запрета нескольких элементов соединены в общую цепь, то недопустимо одновременное срабатывание более чем одного из этих элементов.

5. Количество параллельно соединенных выходов не должно 6. Количество последовательно соединенных входных обмоток не должно превышать десяти.

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

Простейшей иллюстрацией этого приема является схема, где сигнал А при отсутствии сигнала В проходит через верхний усилитель, а под действием сигнала В переключается в нижний канал (рис. 6,а). Как видно, в схеме этого переключателя соблюдены все перечисленные выше правила. Аналогичный переключатель на п выходов (рис. 6,б) получается простым добавлением усилителей, выполняющих операцию «И». Два других полезных приема – применение взаимного запрета сигналов и использование генератора единиц для получения инвертированного сигнала – показаны на примере схемы двухзарядного двоичного дешифратора (рис. 7).

При осуществлении цифровых схем, работающих в троичном коде, элементарная троичная ячейка образуется соединением двух магнитных усилителей таким образом, что импульс, поданный на положительный вход первого усилителя, запрещает второй усилитель, а импульс, поданный на положительный вход второго усилителя, запрещает первый усилитель (рис. 8). Применительно к использованию троичной системы счисления с цифрами 1; 0; – можно условиться, что наличие импульса на первом (верхнем) входе элемента обозначает цифру 1, наличие импульса на втором входе обозначает цифру –1, отсутствие импульсов на обоих входах соответствует цифре 0. Очевидно, что при одновременном поступлении импульсов на оба входа также получается нулевой эффект, что вполне логично: 1+(–1) = 0. Следует отметить, что наличие этой взаимной компенсации сигналов в троичном элементе существенно повышает устойчивость его работы – в случае, когда сигналы ни на один из входов не подаются, происходит взаимная компенсация поступающих на оба входа элемента паразитных сигналов.

В качестве примера троичной схемы (рис. 9) показан двухразрядный троичный дешифратор. Импульсы, представляющие двухразрядный троичный код, подаются одновременно на входы дешифратора «младший разряд» и «старший разряд». В зависимости от поступившей на входы комбинации получается импульс на одном из девяти выходов дешифратора. При отсутствии импульсов на входах происходит непрерывная выдача импульсов на выход «00».

Интересно отметить, что исключением из схемы троичного дешифратора усилителей и соединений, связанных с «отрицательными единицами», получается двоичный дешифратор, приведенный на рис. 7.

Другими примерами троичных схем являются представленный на рис. 10 полусумматор и построенные на основе его сумматор и счетчик [3, 4]. Работа троичного полусумматора описывается выражениями, определяющими цифру разряда суммы S и переноса Q в зависимости цифр соответствующего разряда слагаемых А и В:

Знаки «+» и «–» – употреблены в их обычном арифметическом значении.

Представление троичной переменной в виде разности двух двоичных переменных соответствует реализации троичного элемента в виде двух взаимно скомпенсированных двоичных элементов.

Троичный сумматор (рис. 11) производит сложение чисел с учетом их знаков, т. е. является алгебраическим.

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

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

Н. П. Брусенцов, Цифровые элементы типа магнитных усилителей с питанием импульсами тока. Всесоюзное совещание по магнитным элементам автоматики, телемеханики и вычислительной техники, М., 1957 (аннотация).

Н. П. Брусенцов, Логический элемент. Авторское свидетельство № 145070, «Бюллетень изобретений», 1962, № 4.

Н. П. Брусенцов, Сумматор последовательного действия. Авторское свидетельство № 133679, «Бюллетень изобретений», Н.П. Брусенцов, С.П. Маслов, Троичный счетчик. Авторское свидетельстве, № 145065, «Бюллетень изобретений», 1962, № 4.

ОПЫТ РАЗРАБОТКИ ТРОИЧНОЙ

ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ*

В процессе разработки вычислительной машины «Сетунь» [1, 2] был решен ряд вопросов, связанных с использованием в цифровых маршах троичной системы счисления. В частности, были уточнены достоинства применения троичной системы в цифровых машинах, создан метод синтеза троичных переключательных схем, разработана система элементов, обеспечивающая экономную реализацию троичных схем.

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

Троичное кодирование несколько экономнее (на 5,4%) двоичного, причем для представления произвольного числа с одной и той же точностью троичных разрядов требуется в 1,58 раза меньше, чем двоичных (и только в 2,10 раза больше, чем десятичных).

Следует отметить частный случай, в котором троичное кодирование оказывается экономнее двоичного на 25%. В симметричной троичной системе для представления чисел 0, 1 и 1 достаточно одного разряда, то время как в двоичной системе требуется два разряда, причем оба используются полностью, то есть никакое число, помимо трех указанных, этими разрядами не может быть представлено.

Определенным достоинством симметричной троичной системы является возможность в случае представления чисел с порядками * Текст печатается по изданию: Брусенцов Н.П. Опыт разработки троичной вычислительной машины// Вестник Московского университета. 1965. №2.

(с.39-48).

выбрать Для значений нормализованной мантиссы х интервал