Т. А. Сливина математическая логика и теория алгоритмов

§ 5. Приложения алгебры логики в технике и других областях

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

Использование алгебры логики в конструировании РКС оказалось возможным в связи с тем, что каждой схеме можно поставить в соответствие некоторую формулу алгебры логики, и каждая формула алгебры логики реализуется с помощью некоторой схемы. Это обстоятельство позволяет выявить возможности заданной схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению формулы. С другой стороны, до построения схемы можно заранее описать с помощью формулы те функции, которая схема должна выполнять. Впервые на это указал в 1910 году физик П.С. Эренфест.
Рассмотрим, как устанавливается связь между формулами алгебры логики и переключательными схемами.
Под переключательной схемой будем понимать схематическое изображение некоторого устройства, состоящего из следующих элементов:
1) переключателей, которыми могут быть механические действующие устройства (выключатели, переключающие ключи, кнопочные устройства и т.д.), электромагнитные реле, электронные лампы, полупроводниковые элементы т.п.;
2) соединяющих их проводников;
3) входов в схему и выходов из нее (клемм, на которые подается электрическое напряжение). Они называются полюсами схемы.
Сопротивления, конденсаторы и т. д. на схемах не изображаются.
Переключательной схемой принимаются во внимание только два состояния каждого переключателя, которые называют «замкнутым» и «разомкнутым».
Рассмотрим простейшую схему, содержащую один переключатель Р. Переключателю Р поставим в соответствие высказывание р – «переключатель Р замкнут», а переключателю поставим в соответствие высказывание – «переключатель Р разомкнут». Если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответствие переключательная схема 1.

Схема 1

Формулам, включающим основные логические операции, также могут быть поставлены в соответствие переключательные схемы.
Коньюнкция двух высказываний p и q будет представлена схемой с последовательным соединением двух переключателей P и Q (схема 2).



Схема 2.

Эта схема пропускает ток тогда и только тогда, когда истинны оба высказывания p и q, то есть истинна коньюнкция .

Дизьюнкция двух высказываний p и q будет представлена схемой с параллельным соединением двух переключателей P и Q (схема 3).



Схема 3.
Эта схема пропускает ток тогда и только тогда, когда истинно хотя бы одно из высказываний p или q, то есть истинна дизьюнкция .
Из схем 1, 2 и 3 путем последовательного и параллельного соединения могут быть построены новые переключательные схемы.
Учитывая, что любую формулу алгебры логики с помощью равносильных преобразований можно представить в виде формулы, содержащей только операции дизьюнкция, коньюнкция и отрицание, то любую формулу можно представить в виде схемы, и обратно, любую схему можно записать в виде соответствующей формулы.
Упрощение исходной схемы производится по следующему алгоритму:

1. 
   записать схему в виде формулы
   
2. 
   упростить формулу, используя основные тождества
   
3. 
   по упрощенной формуле начертить схему
   

Пример:
Для заданной схемы

записать формулу и упростив ее, построить более простую схему.

Формула, соответствующая данной схеме:

A& ((( vBvC)& )v((( & )v(B& ))& )v(A& C))

Упростим формулу с помощью основных тождеств:

1. 
   Рассмотрим первую (верхнюю) ветвь схемы:
   ( vBvC) & = ( vBvC) &C=( & )v(B& )v(C& ) = ( & )v (B& )v 0=( & )v(B& )
   
2. 
   Рассмотрим вторую (среднюю) ветвь схемы:
   

( & )v(B& ))& = ( & )v(B& ))& = &

3. 
   Тогда результирующая формула примет вид:
   

A& (( & )v(B& )v ( & )v (A&C)) = A((B& )v( & )v(A&C)) = (B& &A)v ( & &A)v (A&C&A)=((A& )&B)v(A&C) = ((A& )v(A&C)) & ((A&C)vB) = A& ((A&C)vB) = (A&A&C)v(A&B)=(A&C)v(A&B)=A& (BvC)
Таким образом, исходная схема приняла следующий вид:

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

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

( отрицание)
 (конъюнкция)
v (дизъюнкция)
Так же определены следующие логические вентили:

f=( )= И-НЕ

f=( )= ИЛИ-НЕ

f=( )= ИСКЛЮЧАЮЩЕЕ ИЛИ

Упрощение исходной схемы производится по следующему алгоритму:

1. 
   записать схему в виде формулы
   
2. 
   упростить формулу, используя основные тождества
   
3. 
   по упрощенной формуле начертить схему
   

Пример:



Формула, соответствующая данной схеме: F=( )&y&(xvz)
Упростим формулу с помощью основных тождеств:

1. 
   согласно закону поглощения ( )&y=у
   
2. 
   F=y&(xvz).
   

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

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