Игошин Математическая логика и теория алгоритмов (1019110), страница 29
Текст из файла (страница 29)
Задача упрощения релейно-контактной схемы состоит в нахождении более простой равносильной ей схемы. Обычно она решается следующим образом. Для данной релейно- контактной схемы записывается ее функция проводимости. Затем эта функция с помощью тождественных преобразований, использующих известные свойства булевых функций, упрощается, т.е. сводится к функции, имеющей меньшее число вхождений переменных, нежели исходная функция. Наконец строится релейно-контактная схема, отвечающая упрощенной булевой функции.
Рассмотрите решенные в Задачнике примеры 1ча 7.5, л и 7.9. й 13. Релейно-контактные схемы в ЭВМ Первая электронно-вычислительная машина была создана в 1946 г. в США. Для записи и обработки в ЭВМ числовой и символьной информации удобным с технической точки зрения оказался язык двоичных чисел — нулей и единиц.
Поэтому естественно было ожидать, что методы математической науки, исследовавшей двузначные функции, рано или поздно найдут применение в процессе создания такой техники. Впервые предположение о возможности применения алгебры логики в технике было высказано в 1910 г. известным физиком П. Эренфестом (1880 — 1933). Булевы функции стали математическим аппаратом для исследования релейно-контактных схем (эта связь окончательно была осознана в 1930-х гг.), а сами схемы к середине ХХ в. нашли многочисленные пРименения в автоматической технике — в телефонии, железно- 115 дорожной сигнализации, централизации и блокировке, релейной защите, телемеханике и, наконец, — при проектировании быстродействующих ЭВМ. 0 некоторых простых, но очень важных релейно-контактных схемах, используемых в ЭВМ, и пойдет речь в настоящем параграфе.
Двоичный полусумматор. Числа в ЭВМ хранятся в двоичной системе в ячейках памяти поразрядно. С технической точки зрения в двоичной системе оказалось удобно не только хранить числа, но и выполнять над ними различные действия. Так, сложение двоичных чисел осуществляется на основе следующих правил: О+ О = О, О + 1 = 1, 1+ О = 1, 1 + 1 = !О. Сложение по этим правилам делается по каждому разряду двух ячеек, в которых хранятся слагаемые. Если же происходит переполнение данного разряда (что возможно только при сложении ! + 1), то происходит перенос единицы в следующий разряд. Таким образом, процесс сложения в одном разряде может быть охарактеризован двумя булевыми функциями: Ю(х, у) и Р(х, у), зависящими от складываемых чисел х и у.
Первая функция Ю(х, у) представляет собой значение суммы, записываемое в тот же разряд соответствующей ячейки, в котором происходит сложение. Вторая функция — функция переноса Р(х, у) — дает значение числа, переносимого в следующий, более старший разряд при переполнении разряда, в котором происходит сложение. Таблица истинности этих функций следующая: Используя СДН-формы, выписываем для них выражения, по которым легко построить соответствующие релейно-контактные схемы: Ю(х, у) = х'у ~ ху', Р(х, у) = ху. Одноразрядный двоичный сумматор.
При сложении двух чисел описанные в предыдущем пункте действия совершаются лишь в первом (самом младшем) разряде ячеек, хранящих слагаемые. Во всех же остальных разрядах, начиная со второго, в процессе сложения участвуют уже не два слагаемых хь и ум но еще и число, переносимое из предыдущего разряда и равное значению функции переноса Р„,(х, „у„,) в этом разряде. Таким образом, функция сумма 5~ в к-м разряде (1г > 2) зависит от трех аргументов, т.е. Я„= Яг(хм уь, Рь,). От этих же аргументов зависит и функция переноса из 1г-го разряда Р,(х„у,, Ры,). Составим таблицу значений этих функций: 116 Используя СДН-формы, найдем для них выражения, которые затем упростим, преобразуя тождественным образом: я(х, у, р) = '4 х у»р» = х"у'р' ч х"у1р" ч х~уора ч х~у1р~ = 5(а, !1, у) = ! = х'у'р ч х'ур' ч ху р' ч хур = (х'у' ч ху)р' ч (х'у ч ху")р', Р(х, у, р) = '4 х»уар» = х»у'р' ч х'уор' ч х'у'ро ч х'у'р' = Р(а, !3, у) = ! = х'ур ч хур ч хур' ч хур = (х'ур ч хур) ч (ху'р ч хур) ч (хур' ч ч хур) = (х ч х)ур ч (у' ч у)хр ч (р' ч р)ху = хр ч ур ч ху.
Соответствующие схемы предлагается нарисовать самостоятельно. Построив такие схемы для каждого разряда и обеспечив их надлежащее соединение, можно получить схему многоразрядного двоичного сумматора, осушествляющего сложение двоичных чисел в ЭВМ. Шифратор и дешифратор. Человек привык оперировать с числами в десятичной системе счисления. Для ЭВМ более удобна двоичная система. Поэтому важную роль в ЭВМ играют устройства, обеспечивающие взаимопонимание человека и машины, т.е. устройства, переводящие информацию с языка человека на язык машины и обратно.
Такими устройствами являются, например, шифраторы, осушествляюшие перевод чисел из десятичной системы в двоичную, и дешифраторы, осуществляющие обратный перевод. Покажем, как конструируется шифратор. Имеется следующее соответствие между десятичной и двоичной записями: Каждую колонку из нулей и единиц в правом столбце таблицы можно мыслить себе как колонку значений одной из булевых функций: Яо ~~, ~4, Г8.
Нужно лишь отчетливо усмотреть булеву (т. е. двузначную) природу ее аргументов. В самом деле, можем считать, что каждая из этих функций зависит от десяти аргументов хО, х„х2, хз, х4, х5, хб, х„, хб, хм Причем зависимость следующая (она обусловлена предыдущей таблицей соответствий): Каждая из функций~, ~2, ~4 и.г8 зависит от десяти аргументов. Поэтому таблица их значений должна содержать (что установлено при доказательстве теоремы 10.3) 2га строк.
Отсутствие остальных строк в приведенной таблице означает, что на указанных десяти наборах значений аргументов хб,хн х2,хЗ,х4,х,,хб, х,, х,, х, функции должны принимать указанные значения, а на остальных наборах их значения могут быть какими угодно. Это, в свою очередь, означает, что в качестве каждой из функций )и /2,~4, 78 можно взять довольно много (но все же конечное число) функций. Используя СДН-форму, найдем, например, выражение для Г8 (считая, что на всех не указанных наборах значений ее аргументов она принимает значение О): .78(ХО, Х1, Х2, ХЗ, Х4, ХЗ, Хб, Х7, Х8, «9) = ХОХ!Х2ХЗХ4ХЗХОХЗХОХО ~ХОХ1ХЗХЗХ4ХЗХОХЗХОХО = ХОХ1ХЗХЗХ4хбхбх7(ХОХО ~ ХОХО).
Для остальных функций ~, Я2 и 74 найти соответствующие выражения предлагается самостоятельно. По учебному пособию [9.121 можно достаточно подробно познакомиться с современным применением булевых функций при конструировании ЭВМ. 118 5 14. О некоторых других приложениях теории булевых функций Важнейшее применение теории булевых функций (в теории релейно-контактных схем) рассмотрено в Э 12, 13. Здесь кратко охарактеризуем еше одну сферу применения теории булевых функций, выявленную уже во второй половине ХХ в. Это так называемая теория распознавания образов. На ее примере можно увидеть, как математика пытается своими методами смоделировать еще один вид мыслительной деятельности, свойственный человеческому мозгу, и что при этом снова оказываются задействованы методы математической логики.
Диагностика (распознаванне) заболеваний. Начнем с анализа одной конкретной ситуации. Как известно, различные заболевания сопровождаются теми или иными симптомами. Эта связь устанавливается экспериментально на основе многолетних медицинских обследований тысяч больных. С помощью математики эти связи можно определенным образом систематизировать, используя аппарат булевых функций.
Предположим, что имеется т симптомов Я!, Яп ..., 5 и и заболеваний Ть Т,, ..., Т„. Рассмотрим следующие булевы переменные (! = 1, ..., и; у = 1, ..., л): 1 , если у больного обнаружен 4-й симптом, х;= О, в противном случае; 1 , если у больного обнаружен у-е заболевание, У! = О, в противном случае. Тогда связь между симптомами заболеваний и заболеваниями может быть выражена на языке алгебры логики.
Например, если заболевание Т, всегда сопровождается симптомами Я! и Юз, то булева функция у, -4 (х, х!) тождественно равна 1. Аналогично, может быть известно, что если обнаружены симптомы 5„о4, Яп то обязательно должно быть заболевание Тп и, наоборот, это заболевание всегда проявляется в указанных симптомах. Следовательно, тождественно Равна 1 бУлева фУнкциЯ следУющего вида: х, хз. х! 4-+ Уь Часто один какой-нибудь симптом (например, высокая температура) сопровождает многие заболевания, булева функция в этом слУ 4ае х! ~ (У! м Уз ~ Уз м У4 ~ У5) 1 Таким образом, экспериментально устанавливаются следующие булевы равенства: Я~(х!, хп ..., хщ, У!, Уз, ...1 Уд) = 1; зз( !~ и "' %и У1 Уп " Ул) Ях„хп ..., х, у!, Уп ..., У„) = 1.
119 Булевы функциями,,Я~, ...,,гг называются указаниями. Каждая из них есть, по существу, некоторое составное высказывание относительно причинно-следственной связи между симптомами заболеваний и самими заболеваниями. Из этих равенств следует, что равна 1 и конъюнкция булевых функций Яь Ь ..., ~~.,Т(хь хь ..., х, у~ у~ ".~ уа) =ХА" Л= 1.
Это равенство представляет собой своего рода неявное задание функций (заболеваний) уь уз, ..., у„от аргументов (симптомов) хь хз, ..., х„. Задача диагностики состоит в том, чтобы явно выявить эти зависимости и применить их к конкретному больному. Для этого можно составить таблицу значений функции~ Из общего числа строк 2 ' " нас будут интересовать в ней лишь те, в которых для всех симптомов, выявленных у исследуемого больного, соответствующее значение х равно 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
