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

Это свойство, очевидно, является инвариантным относительно операций введения и удаления несущественных переменных. Такой класс может рассматриваться. 3 а м е ч а н и е. Если дана конечная система функций пз Р,: (Л, ..., ),), гл-1, то можно считать, что все зти функции зависят от одних н тех же переменных х„...

..., х„, т. е. имеют вид ~,(хо ..., х„),..., 7',(хь ..., х„), С другой стороны, если дана функция, отличная от константы, то путем отождествления переменных из нее «южно получить равную ей функцию, все переменные которой являются существенными. В заключение етого параграфа рассмотрим примеры функций алгебры логики. Данные функции часто употребляются в математической логике и кибернетике и вграют такую н«е роль, как, например, х" или з1пх в аналиае, поэтому их можно считать «элекентарнымиг: 1) /,(х) Π— константа О; 2) Ь(х) 1 — константа 1; 8) тг(х) = х — тождественная функция; 4) ~,(х) х — отрицание х (х читается «не хг); 5) й(х;, х,) (х,дгх,) — конъюнкция х, и х, (читается «х, и х,г).

Вместо анака й употребляется знак или вообще знак опускается, т. е. пишут (х,х,). Эту функцию часто называют логическим умножением; 6) ~«(хо х,) (х, ч'х«) — дигъюнкция х, и х, (читается «х, или х,г). Эту функцвю часто называют логическим сложением; 7) Д(хо х,) (х, - х,) — импликация х, и х, (читается «из х, следует х,э). Эту функцию часто называют логическим следованием; 8) /„(хо х,)=(х, +х,) — сложение х, и х, по шод2; 9) ~,(х„х,) =(х,lх,) — функция Шеффера. т4 ч.

1. ФункциОБАльные системы с ОпегАциями Таблаца 2 Таблааа 3 В таблицах 2, 3 даются аначения этих функций. Заметим, что (х, б1 х,) пйп(х„х«) (х, х,), (х, Чх,) шах(хо х,). $2. Формулы. Реализация функций формулами Как и в элементарной алгебре, исходя иа «элементарныхз функций, можно строить формулы. Ниже приводится индуктивное определение формул. Определение. Пусть $ — некоторое .(не обязательно конечное) подмножество функций из Р. а) Бааис индукции.

Каждая функция 1(хо ... ..., х„) из $ нааывается формулой иод $. б) Индуктивный переход. Пусть 1,(хо ..., х ) — функция из $ и А„..., А — выражения, являющиеся либо формулами над $, либо символами переменных из У. Тогда выражение ЯАИ ..., А ) называется формулой яад Ч1. Пример 1. Пусть «1 — мно1кество «элементарныхэ функций. Следующне выражения являются формулами над $: 1) (((х,х,) + х,~ + х,); 2) з) ГЛ. !. АЛГЕБРА ЛОГПКН В дальнейшем будем обозначать формулы заглавными готическими буквами с квадратными скобками, в которых перечисляются функции, необходимые для их построения. Так означает, что формула И построена из ~„..., Г,. В тех случаях, когда нужно обратить внимание на множество тех переменных, которые участвуют в построении формулы, пишут И(х„..., х„). Пусть И вЂ” произвольная формула над $, тогда формулы, которые использовались для ее построения, будем называть иодформулами формулы И.

Пусть формула И является формулой над множеством 6 Ц,(хо ..., х„), ..., ~,(х„..., х„)), т. е. И И[~о ... ..., 1,]. Возьмем множество функций 0 = (л,(х„..., х.), ..., л. (х„..., х )), где ла имеет те же переменные, что и 1а (1 1, ..., э). Определение. Рассмотрим формулу 6 6(б„... /~1 ° 1а ~ ..., б,], которая получается из И путем аамены~ ). З1 ° ° ° Ка Говорят, что формула 6 имеет то же строение, что и формула И.

Пример 2. 1) Ф (ха, (ха саха)), И=(ха 4(хатха)Ъ 2) О (У„(х,- х,)),6=(ха- (х,- х,)]. Очевидно, что И и 6 имеют одинаковое строение. В дальнейшем строение формулы обозначается через С (с индексами или без них), и формула И одноаначно определяется строением С и упорядоченной совокупностью (~„~а, ..., г.). Поэтому можно писать И - С[1а 6, ", 1.]. Сопоставим теперь каждой формуле И(х„..., х„)' над $ функцию ~(х„..., х„) из Р„опираясь на индуктивное определение формул.

а) Ваэи с индукции. Если И(х„..., х„) Ях„... ..., х„), где гав 6, то формуле И(х„..., х„) сопоставим функцию 1(х„..., х„). 16 Ч 1 ФУНКШ10НАЛЬНЫК СПСТЕМЫ С ОПЕРАЦПЯЫП б) Индуктивный переход. Пусть 6(х„ ..., х,) го(Ао ..., А ), где А (1 1, ..., т) является либо формулой вад $, либо символом переменной хко. Тогда по предположению индукции А, сопоставлена либо функция 1, из Р„либо тождественная функция г', хач. Сопоставим формуле 6(х„..., х„) функцию Дхо ...

..., х.)=1о(1о, 1-) Если функция ) соответствует формуле 6, то говорят также, что формула 6 реализует Яункцию ). Поскольку функции рассматриваются с точностью до фиктивных переменных, мы счптасм, что формула 6 реализует п любую функцию, равную 1. Замечание 1. Если функция 1(х„..., х„), реализуеьгая формулой 6(х„..., х„), имеет несущественную переменную х„то пря и > 1 переменную х< можно удалить, заменив функцию ) равной ей функцией 1', а формулу 6 — формулой И', получающейся из И в результате отождествления переменной х, с любой пз оставшихся переменных. Очевидно, что 6' является формулой над $ и реализует функцпю 1'. Функцпю 1, соответствующую формуле 6, будем нааывать суперпозицией функций из $, а процесс получения функции ) из $ будем называть операцией срперпозиции.

П р и и е р 3. Пусть ),(хо х,), (,(х„х„х,) и г;(хо хм х,) — функции, соответствующие формулам из примера 1. 1) Формула (((х,х,)+ х,)+ х,) строится за три шага. Мы имеем следующие подформулы: (х,х,), ((х,х,)+ х,), (((х,х,)+ х,)+ х,). В табл. 4 приводятся соответствующие им функции, которые вычисляются с испольаованием табл. 3 и правила б). Последний столбец определяет функцию ~,(хо х,); очевидно, что ~, (х„х,) шах (х„х,).

Таблаца 4 ГЛ. Ь АЛГЕБРА ЛОГИКИ 2) Функцию Ь(хо х„хз) мы будем строить несколько иным путем (также вытекающим иэ определения). Для каждого набора (о„о„о,), испольауя табл. 2 и 3, найдем )з (оо о„оз) (о, (о, + о,) ) (см. табл. 5). Таблица б 3) Для нахождения функции гз(х„хз, хз) будем, опираясь иа табл. 2 и 3, искать те наборы, иа которых формула (хз Ч [(хз -~ хз) (хз - хз)Р обращается в 1. Очевидяо, что вто раввосильио иахождеиию случаев, при которых формула (хз Ч [(хз - х,) (х, - х,)1) равна О. Последнее имеет место при х, * 0 и в тех случаял, когда [(х,- х,) (х,- хз)) обращается в О. Накокец, формула [(х,- х,) (х,- хз)) обращается в О, когда по крайней мере одна ив формул (х,- х,), (х,- х,) обращается в О, что имеет место при х, 1, х, О или при хз О, х, 1.

Таким образом, (з(х„хз, х,) равна 1 ка наборах (0,0,1) и (0,1,0) (см. табл. 5). Замечание 2. Пункт б) в определении формул можно еамекить иа пункт, вспольэующий две более простые операции. 1) Операция подстаноеки переменных. Пусть 1В ч, ь фтнкционлльнык спствмы с опвглцпямн — подстановка переменных (к», не обязана отличаться от я»„при т ть р). Зта подстановка позволяет произвести подстановку переменных у функции 1(к„..., к.) и получить в результате функцию т(к»„...» к»„).

Очевидно, подстановка переменных включает в себя переименование переменных, перестановку переменных и отождествление переменных. 2) Операция бвсиовторной подстановки функций. Она позволяет строить выражения ~(Ао ..., А ), где А,— либо формула, либо переменная из У, причем хотя бы одно из А, отлично от переменной, а множества переменных, входящих в А» и Аь не пересекаются. Очевидно, что всякая формула над 3 может быть получена из функций, принадлежащих $, путем применения сначала операции бесповторной подстановки функций (многократной), а аатем операции подстановки переменных (причем однократной). Замечание 3. Если ч» содержит тождественную функцию, то формулировка пункта б) в определении формул и функций, реализуемых формулами, упрощается: нужно предполагать, что все А, являются формулами над $.

Введенный нами язык формул удобен для записи функций алгебры логики, описывающих различные условия или высказывания. Для иллюстрации рассмотрим два примера. В них испольауются высказывания вида «имеет место к» или просто «я», а это в свою очередь означает, что при данных условиях я истинно или равно 1. Пример 4. Сложение п-разрядных двоичных чисел. Мы исходим из обычного алгоритма слон»ения «столбикомэ в„...

в в + в ° .. в«в, «в+»«в " вз«г ' Требуется выразить значения разрядов суммы через значения разрядов слагаемых. Для решения этого вопроса рассматривают вспомогательные величины к»„, и»„„... ..., и»„ где »о» обоаначает результат переноса из $-го разряда в (3 + 1)-й разряд. Эти параметры появляются в упомянутом алгоритме. Гл. <.

АлГеБРА логики >9 Ясно, что тогда г, =((х, + у;)+ к>,,) (а>< О, х„+,— — у„+, О, 1 1, ..., и+1). Величина <о< определяется условием переноса из 1-го разряда в (1+ 1)-й разряд: «перенос в (<+ 1)-й разряд имеет место тогда и только тогда, когда по крайней мере две из трех величин х„уь и>« равны 1». Это высказывание более подробно можно сформулировать так: «х< и у,» или «х< п и><,» илн «у, и и>« ».

Если теперь заменить союзы «и» и «или» символами д< и ч<, то получим следующую формулу для и><> и« (1(х, д< у) <т(х,б< п><,)1'ч<(у,д< и><,)), (1= 1, ..., и). П р п м е р 5. Задача о вызове свободного лифта. Пусть в подъезде имеется три лифта, обслуживающих п этажей. На каждом этаже имеется устройство, которое позволяет при нажатии кнопки вызывать ближайший свободный лифт.

Спрашивается, как можно на логическом языке записать условие вызова 1-го лифта (1 1, 2, З)2 Мы рассмотрим зту задачу для случая вызова лифта на первом этаже. Для оппсанпя исходной информации введем Зн аргументов х„у„г„х„у„г„..., х„, у„, г„, где х, 1 тогда и только тогда, когда 1-й лифт находится на 1-и этаже и свободен; у, 1 тогда и только тогда, когда 2-й лифт находится на 1-и этаже и свободен; г, = 1 тогда и только тогда, когда 3-й лпфг находится на >-и этаже и свободен.