Глава 4 Алгебра логики (стр. 1 )

Глава 4 Алгебра логики

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

Процесс проектирования д. у. можно разделить на 2 части:

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

2.  Техническое проектирование, т. е. построение устройства из физических элементов.

Дискретные устройства делятся на 2 класса:

1.  Комбинационные схемы – устройства, в которых каждому входному сигналу соответствует выходной сигнал.

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

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

4.1  Формулы и функции алгебры логики

4.1.1  Высказывания и операции над ними

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

В качестве примеров высказываний можно назвать «Сейчас идет снег» и «Первокурсники СибГУТИ изучают математику».

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

В дальнейшем нас будет интересовать не то, о чем идет речь в данном высказывании (его содержательная часть), а лишь какое значение истинности оно имеет. В алгебре логики все высказывания, имеющие одинаковые значения истинности, взаимозаменяемы, т. е. имеется два класса: класс истинных высказываний и класс ложных высказываний – (И, Л), (T, F), (1,0).

Высказывания a и b являются равносильными (a º b), если совпадают их значения истинности.

Высказыванию Р поставим в соответствие логическую переменную x, которая принимает значение 1, если Р истинно и 0, если оно ложно.

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

Логические операции, или связки: унарная операция – инверсия, бинарные – конъюнкция, дизъюнкция, импликация, равносильность (эквивалентность), штрих Шеффера, стрелка Пирса, кольцевая сумма.

Инверсия (логическое отрицание): NOT, НЕ, , черта над переменной. Меняет значение переменной на противоположное.

Конъюнкция (логическое умножение): AND, И, Ù, ×, &. Имеет значение ложь, если значение хотя бы одного операнда ложно.

Дизъюнкция (логическое сложение): OR, ИЛИ, Ú. Имеет значение истина, если значение хотя бы одного операнда истинно.

Импликация (логическое следование): ЕСЛИ…ТО…, ®. В выражении ЕСЛИ a ТО b переменная a является посылкой (основанием), переменная b – заключением (следствием, выводом). Имеет значение ложь тогда и только тогда, когда из истинной посылки делается ложное заключение.

Равносильность (эквивалентность): …ТОГДА И ТОЛЬКО ТОГДА, КОГДА…, «, ~, º. Имеет значение истина, когда переменные совпадают.

Штрих Шеффера (антиконъюнкция): по определению (a|b) º (a&b).

Стрелка Пирса (антидизъюнкция): (a¯b), по определению (a¯b) º (aÚb).

Кольцевая сумма (сложение по модулю 2, исключающее ИЛИ): по определению (aÅb)º(a«b). Имеет значение истина, когда оба аргумента различны (для большего числа аргументов – когда количество единиц нечетно).

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

A	B	A	A & B	A Ú B	A ® B	A º B	A | B	A ¯ B	A Å B
0	0	1	0	0	1	1	1	1	0
0	1	1	0	1	1	0	1	0	1
1	0	0	0	1	0	0	1	0	1
1	1	0	1	1	1	1	0	0	0

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

Теорема 4.1   

1.  A ® B º ØA Ú B.

2.  A « B º (A ® B)&( B ® A) º (A & B) Ú (ØA & ØB) º (ØA Ú B) & (A Ú ØB).

Доказательство: с помощью таблиц истинности.

4.1.2  Построение формул

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

Пусть {xi | iÎI} – некоторое множество логических переменных. Формулой алгебры логики является любая логическая переменная (атомарной формулой) или выражение, построенное из формул с помощью логических операций.

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

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

Любая формула, кроме элементарной, должна быть заключена в наружные круглые скобки. Однако обилие скобок затрудняет чтение формул, поэтому в алгебре логики приняты некоторые соглашения относительно расстановки скобок: 1) внешние скобки не пишутся; 2) знак конъюнкции можно обозначать точкой или не писать; 3) на множестве {, &, Ú, ®, «, |, ¯, Å } вводится приоритет операций, который определяется посредством транзитивного отношения > «быть сильнее» и отношения эквивалентности ~«быть равносильным». Если все равносильные операции объединить в классы эквивалентности {}, то можно записать: {} > {&, |, ¯} > {Ú} > {®} > {«, Å}.

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

  Пример 4.1  ((((a&b)&c)Úd)®((aÚb)&a)) º abc Ú d ® (aÚb)&a, в итоге в формуле осталась только одна пара скобок, которая нужна для того, чтобы дизъюнкция выполнилась прежде конъюнкции. И наоборот, расставим скобки в формуле в соответствии с последовательностью выполнения операций: xÅy«z®uÚv&w¯x|y º ((xÅy)«(z®(uÚ(((v&w)¯x)|y)))).

4.1.3  Булевы функции и формулы

Функцией алгебры логики (ФАЛ) от n переменных x1, x2, …, xn называется функция f:{0,1}n®{0,1}, т. е. функция, которая произвольному набору
(s1, …, sn) нулей и единиц ставит в соответствие значение f(s1, …, sn)Î{0,1}.

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

Утверждение Для булевой функции от n аргументов существует 2n различных наборов аргументов.

Булева функция f(x1, x2, …, xn) называется полностью определенной, если ее значения определены на всех 2n наборах переменных. В противном случае функция частично определенная.

Функция существенно зависит от переменной xi, (или переменная xi – существенная), если $ такой набор значений x1, x2, …, xn , что . В противном случае переменная xi – несущественная (фиктивная).

x1	x2	f1	f2
0	0	0	1
0	1	0	1
1	0	1	0
1	1	1	0

  Пример 4.2  Пусть две булевы функции заданы таблицей истинности. Для них переменная x1 существенная, а x2 – несущественная.