С.В. Яблонский - Введение в дискретную математику, страница 4

Обоаначив> через ~<(х„ у„ г„ .. ч х„, у„, г„),..., ~«<(х„ у„ г„ .. „ х„, у„, г„) функции, равные 1 тогда и только тогда, когда вызывается лифт с номером соответственно 1, 2, 3. Условие вызова 1-го лифта, или функция ><, характеризуется тем, что «1-й лифт свободен и нет свободных лифтов, расположенных на более низком этаже, чем 1-й лифт». Это высказывание можно выразить подробнее следующим образом: «1-й лифт вызывается тогда и только тогда, когда 1-й лифт находятся на 1-и этаже и свободен или на 1-и этаже нет свободных лифтов с номерами 2 и 3, и в этом случае 1-й лифт находится на 2-м этаже ЯО ч.

1. Функц!!онлльные спсте»аы с опеглш!яыи и свободен, или на 2-м этаже нет свободных лифтов с номерами 2 и 3 и здесь, в свою очередь...» Запишем это высказывание через высказывания х» у» г» ... ..., х„, у„, г„: «а-й лифт вызывается тогда и только тогда, когда х» или когда «не у, и не г,», и в этом случае х, или «не у, и не г,» и здесь, в свою очередь...». Теперь нетрудно получить формулу для К если заменить союзы «и» и «илн» на й и М, частицу «не» на и расставить скобки в соответствии с соединительными словами: Уа(Х» Уаа г» * ° х У г») (х, Ч ((у, й а,) й [х, Ч [(у, й га) й (...) ДН. Аналогичные формулы получаются для функций ааа и аааа. ~аа(х„у„г„..., х„, у„, г„) (уа Ч (Ха й га)й [уа ~/ [(ха й га) й ( ° )ПНа 1ааа(ха У» га х" У.

г.) (г, 'у' (х, йу,)й [га Ч [(х,й уа)й(...)ДН. Таким образом, язык формул представляет известный интерес. $ 3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности Мы видели, что каждой формуле над $ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функцпи (см., в частности, пример 6). Определение. Фор»аулы а( и 6 над $ называют- ся эквивалентными, если соответствующие им функции /н и ~и равны, т. е. ~и = /е.

Запись 6-6 будет означать, что формулы Й и 6 эквивалентны. Пример 6. т) О (хйх), 2) (х,(х, + х,)) = (ха ~/ [(х, - х,) (х, - х,) ), 3) (х - у) = (у х). Приведем список эквивалентностей (тождеств), характеризующих свойства некоторого множества элементарных функций (главным образом множества (О, т, х, (Ха й ха)а (ха Чха))), ГЛ. 1. АЛГЕБРА ЛОГ11КИ 21 Обозначим через (х, ° х,) любую из функций (х, 81 х,), (хз ~ хз), (ха+ха). Существенно только, чтобы символ ° в тождестве всюду имел один и тот же смысл. 1) Функция (х, ° х,) обладает свойством ассоциативности: ((Х Х ) Х ) = (Х з(х зх )) 2.

Функция (х, ° х,) обладает свойством коммутатпвности: (х, ° х,) = (х, ° х,). 3. Для конъюнкции и дизъюпкции выполняются дистрибутивные законы: ( (Ха ~ Хз) 8а Хз) = ( (Хз 8а Хз) ~l (Ха 8а Ха) ) з ( (х, 81 ха) ~ хз) ( (хз Ъ' хз) 8а (хз ~ хз) ) . 4. Имеют взесто следующие соотношения между отрицанием, конъюнкцией и дизъюнкцпей: х х, (х, 81 хз) = (ха 'а' ха), (х, Ч ха) = (ха 8а ха). 5. Выполняются следующие свойства конъюнкции и дизъюнкцип: (Х8ах)=х, (ХЧх)=х, (х 8а х) = О, (х ~/ х) = 1, (хайО)=0, (ХЧО)=х, (Х811)=х, (хЧ1) 1. Тождества легко могут быть проверены путем соцоставления функций, соответствующих правой и левой частям тождеств. Замечания. 1.

С целью упрощения записи формул мы условимся, что операция 8а сильнее операции ~/, т. е. если нет скобок, то сначала выполняется операция 81, а потом К Например, запись (х, & х, Ч х,) означает ((х, 8а х,) Ч х,). 2. В силу закона ассоциативности для (х, ° х,) можно вместо формул ((х, ° х,) х,), (х, ° (х, ° х,)) пользоваться выражением (х, ° х, ° х,), которое не является формулой, но может быть превращено в нее путем расстановки скобок, причем функциональные свойства не меняются, как бы мы пи расставляли скобки. 3.

В формулах, у которых впезппяя фупкция является либо конъюнкцией, либо дизъюнкциеи, либо сложе- ч. ь фтнкциональныв систкмы с опкгьциями нием по шой 2, либо импликацией, либо функцией Шевфера, внешние скобки опускаются, например, пишем х, — х, вместо (х, — х,); опускаются также скобки у выражения, над которым стоит злак, например, пишем х, — х, вместо (х, — х,). В дальнейшем будем употреблять следующие обозначения: 4 д, х,-х,д,хгд,...д,х„ $1 а 1/ хг хг~/хг)/ ... ~/х,. ь т Эти записи имеют смысл также и при з = 1. Удобно сформулировать ряд правил, вытекающих из пунктов 2 и 5 списка тождеств злементарных функций.

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

В дальнейшем, используя замечания 1, 2 и 3, мы будем употреблять не формулы, а выражения, отличающиеся от формул тем, что в нпх кое-где опущены скобки. Эти выражения мы также иногда будем называть формулами. Очевидно, что если 6' — подформула формулы ч1 и если заменить любое из ее вхождений на эквивалентную формулу 6', то формула 6 перейдет в формулу 6, которая будет зквивалентна И. Этот принцип вместе с тождествами для элементарных функций, к которым присоединяются все тождества, получаемые подстановкой вместо переменных х,х„х„х, любых формул, позволяет осуществлять вквивалентные преобрааования и, тем самым, получать новые тождества.

П ример 7. х, Ч х,х, х, 1 ~/ х,х, =х,(х; 1/ х,) Ч х,х, = х х, ~/ х уг ~/ х х, = х х, ~/ х хг ~/ х х . .= х~хг ~/ х~хг = х~ (хг '/ хг) = х~ ' 1 = хь 23 ГЛ. 1. АЛГЕБРА ЛОГПКН Таким образом, х, Ч х,х, х„т. е. получаем правило поглои1ения проиаеедения х,х, множителем х,. Существует еще один способ для получения тождеств. Оя основан на использовании так называемого принципа двойственности. Определение. Функция 11(х„..., х„)1», равная у (хь ..., х„), называется двойственной фрнкг1ией н футиии )(х„..., х„).

Очевидно, что таблица для двойственной функции (при выбранном порядке наборов) получается из таблицы для функции /(хо ..., х„) инвертированием (т. е. заменой 0 на 1 и т на 0) столбца функции и его переворачнванием (см. табл. 6). Таблица В 1Лх„х„,ха) 1* ях„ х„ Л х~ х~ О О О О О 1 О 1 О О 1 1 1 О О 1 О 1 1 1 О 1 1 1 ПОСКОЛЬКУ (~(Х»,, ..., ХЬ,))» 1(Хй...,, Хгх), тО функпив (1(х1ы ! хгх)1» опРеДелнет то же ото- бражение, что и [~(хь .. х х„))».

Обозначим это отобра- жение череа 1». Тогда (~(хо ..., т„))» = 1»(хо ..., х„). Легко видеть, что среди функций О, 1, х, х, х,дгхм х,Чх, функция О двойственна т, функция $ двойственна О, функция х двойственна х, функция х двойственна у, функция х, де х, двойственна х, Чх„ функция х, Ч х, двойственна х,й х,. Из определения двойственности вытекает, что 24 ч. 1, Функцнонлльные системы с ОпеРАциями т. е.

функция 1 является двойственной к ~* (свойство взаимности) . Пусть 1(х„..., х„) выражена формулой 6. Спрашивается, какой внд пмеет формула 6, реализующая 1*(х„..., х„)у Обозначпм через х„..., х все различные символы переменных, встречающиеся в множествах (Х11~, ~ Х1Р1)~, 1 (ХР111, 1 ХР1РР1) Теорема 2.

Если Ф(х„..., х„) 1(Л(х„, ..., х„,), ..., 1 (х „..., Х,РР~)), то 1 (11(Х11~ ° ° ° ~ Х1Р )1 ° ° ° 1 lщ (Х1Р11 ° ° ° 1 х )) Из теоремы вытекает Принцип двойственности. Если формула 6 С[1„..., 1,1 реализует функцию ~(хи ..., Х„), то 1 Ч Р1 формула С)1„..., 1,1, т. е. формула, полученная ив 6 заменой функций 1„..., 1, соответственно на реализует функцию (в(х„..., х„). Эту формулу мы будем называть формулой, двойственной к 6, п обозначать через 6в. Таким образом, 6* — С ~~'„..., 1,'1.

Для формул над множеством 9 (О, 1, х, х,81Х„ х, Чх,) принцип двойственности может быть сформулирован так: для получения формулы 6*, двойственной к формуле 6, нужно в формуле 6 всюду заменить О на 1, 1 на О, д1 на 'ч1, Ч на д1. Доказательство. Ф'( „...,. „) Ф(Х1... -/((1(Х11 ",Х1Р,). -~0 ( .", „). -~0,(х " хр,) - 1*(1; (хи, ., х„) '1 УР1 (~3~1~ ' ° ' з ХЯРР1)) ° ° ° ~ 1Р1 (Хн11 ° ° ° 1 Хирн)) ..., )н (Х„„...1 Х„Р„)) Х,,) ° ° ° ~" (Х 1 ° Х Р )). 25 ГЛ, !. АЛГЕБРА ЛОГИКИ ХХли, если И = С[О, 1, х, х, йх„х, ~lхь), то И» С[1, О, х, х,Чх„хьдьх>1. Пример 8. в 1) И, (х„х,) = х, дь х„И! (хь, х,) = х, »' х„ 2) И»(х„х«) =х,х,)/х,хь, И,(х,,х«) =(х, Ч'х,)(х, ь/хь).

Из принципа двойственности вытекает, что если И(х„..., х„) = 6(х„..., х„), то Иа(х„.. а х„)= 6«(х„..., х„). Пример 9. Из тождества хьдьх, х,Ъ'хь вытекает тождество х, Чх, х, дь хь. Принцип двойственности позволяет почти в два раза сокращать усилия на вывод тождеств прн рассмотрении свойств элементарных функций. Другие применения принципа двойственности будут даны ниже. з 4. Разложение булевых функций по переменным. Совершенная дььзъюнктивная нормальная форма Говоря о языке формул, мы сознательно не касались весьма важного вопроса.

Если в качестве $ допустить некоторый запас элементарных функций, то всякая лп функция алгебры логики может быть выражена в виде формулы3 Влияьайшпе рассмотрения направлены на решение этого вопроса. Введем обозначение х' хорха, где о — параметр, равный либо О, либо 1. Очевидно, что )х прп о= О, х'- ьх прн о 1. Легко видеть, что х' 1 тогда и только тогда, когда х о, т.