Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Замечание 3. Если $ содержит тождественную функцию, то формулировка пункта б) в определении формул и функций, реализуемых формулами, упрощается: нужно предполагать, что все А{ являются формулами над
Введенный нами язык формул удобен для записи функций алгебры логики, описывающих различные условия или высказывания. Для иллюстрации рассмотрим два примера. В них используются высказывания вида «имеет место х» или просто «лэ>, а это в свою очередь означает, что при данных условиях х истинно или равно 1.
Пример 4. Сложение п-разрядных двоичных чисел, Мы исходим из обычного алгоритма сложения «столбиком»
хп...х2хг
+
Уп--У& 1
2П+1 гп' ' * 22г1 ’
Требуется выразить значения разрядов суммы через значения разрядов слагаемых. Для решения этого вопроса рассматривают вспомогательные величины шп, ___________
..ю!, где ич обозначает результат переноса из кто разряда в (? + 1)-й разряд. Эти параметры появляются в упомянутом алгоритме.
ГЛ. і. АЛГЕБРА ЛОГИКИ
Ясно, что тогда
2? =((?, + 1/0+
(и?о = 0, хп+{ — уп+1 — 0, 1= 1, ..гс + 1).
Величина и\ определяется условием переноса из г-го разряда в (г+1)-й разряд: «перенос в (г+1)-й разряд имеет место тогда и только тогда, когда по крайней мере две из трех величин уи равны 1». Это высказывание более подробно можно сформулировать так: «Ж| и уо> или «дч и ^-1» или «г/1 и
Если теперь заменить союзы «и» и «или» символами & И V, ТО получим следующую формулу ДЛЯ 10и
Ц?( — {[ & г/0 V (ас, & щ<_1) ] V (у, & н??_,)},
(г = 1, гг).
Пример 5. Задача о вызове свободного лифта. Пусть в подъезде имеется три лифта, обслуживающих п этажей. На каждом этаже имеется устройство, которое позволяет при нажатии кнопки вызывать ближайший свободный лифт. Спрашивается, как можно на логическом языке записать условие вызова г-го лифта (г = 1, 2,
3)? Мы рассмотрим эту задачу для случая вызова лифта на первом этаже.
Для описания исходной информации введем 3п аргументов
хи Уи 2и Хг, у2,
Хп, Уп, 2П,
где XI *= 1 тогда и только тогда, когда 1-й лифт находится на г'-м этаже и свободен; у1 — 1 тогда и только тогда, когда 2-й лифт находится на г-м этаже и свободен; 2( = 1 тогда и только тогда, когда 3-й лифт находится на 1-м этаже и свободен.
Обозначим через
Д (*^17 ^1* ^1» • * *7 Х-П1 Уп 1 , . . ., Дц (#1, У±, 2
!) • * *7 ХП) Уп, гп)
функции, равные 1 тогда и только тогда, когда вызывается лифт с номером соответственно 1, 2, 3. Условие вызова 1-го лифта, или функция Д, характеризуется тем, что «1-й лифт свободен и нет свободных лифтов, расположенных на более низком этаже, чем 1-й лифт». Это высказывание можно выразить подробнее следующим образом: «1-й лифт вызывается тогда и только тогда, когда 1-й лифт находится па 1-м этаже и свободен или на 1-м этаже нет свободных лифтов с номерами 2 и 3, и в этом случае 1-й лифт находится на 2-м этаже 2*
20 Ч. I, ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
и свободен, или на 2-м этаже нет свободных лифтов
с номерами 2 и 3 и здесь, в свою очередь...» Запишем
это высказывание через высказывания zu ...
•.я*, у„, zn\ «1-й лифт вызывается тогда и только
тогда, когда хи или когда «не г/, и не z^, и в этом
случае Х2 ИЛИ «не 1/2 и не 2г» и здесь, в свою очередь...». Теперь нетрудно получить формулу ДЛЯ /i, если заменить союзы «и» и «или» на & и V, частицу «не» на ~ и расставить скобки в соответствии с соединительными словами:
fi (*^t> Е/11 ^1» • • ?» Уп» *п)
= {х± V {(^i [х2 V [{уг & Zi)&(. ..)]]}}.
Аналогичные формулы получаются для функций fu и /ш:
/il (^ii Vl-t Zit . . Хп, Упг zn) =
= (г/i V {Xi & Zi)& {уг V [(#2& Zz)&{.. .)]]>},
fill (*^1» У it • ? ч Vnt Zn)
= {Zi V {xt &yt)& [я, V [(*,& y2)&(...)]]}}.
Таким образом, язык формул представляет известный интерес.
§ 3. Эквивалентность формул.
Свойства элементарных функций.
Принцип двойственности
Мы видели, что каждой формуле над $ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции (см., в частности, пример 6).
Определение. Формулы SI и 0 над $ называются эквивалентными, если соответствующие им функции fu и /э равны, т. е. /§[ = /а- Запись St = S3 будет означать, что формулы St и S3 эквивалентны.
Пример 6.
1) 0 = (:г & .г),_____________________________
2) {х^ХгЛ- а:3))= {Xi V [(?s -? г3) {х3 -* :с2)]},
3) (ж-* у) = {у -*ж).
Приведем список эквивалентностей (тождеств), характеризующих свойства некоторого множества элементарных функций (главным образом множества {’0, 1, ж, (Xi&ar2)t (ZjVza)}),
ГЛ. і. АЛГЕБРА ЛОГИКИ
21
Обозначим через {х1 * Хг) любую ИЗ функций (т^&Хг), (г! V х2), (х1 + х2). Существенно только, чтобы символ ° в тождестве всюду имел один и тот же смысл.
1) Функция обладает свойством ассоциатив-
ности:
( (Ж| °х2)^3) = (х, • (ха » X*) )'.
2. Функция (х! ° хг) обладает свойством коммутативности:
(ж, 0Хг)^{хг^Хх).
3. Для конъюнкции ц. дизъюнкции выполняются дистрибутивные законы:
((ж, V х2)&х3) = ((х, & х8) V (х2 &*,)),
( (X! & Хг) V Хя) = ( (х* V Хл) & (хА V Ж5) ) .
4. Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:
