Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
/ (о: 1, .. >, С?;— 1, 0, ос,.).!, ..о^г;)
^ / (oil, . . i, 1, • . ., Ctn) •
В этом случае переменная х{ называется существенной. Если Xi не является существенной переменной, то она называется несущественной или (фиктивной.
Пусть для функции f(xu ..хф) переменяя Xi является фиктивной. Возьмем таблицу для функции f{xu ... ..., хп) и по ней построим новую таблицу путем вы-
12 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
черкивания всех строк вида {аи ..а<-1, 1, а?+1, ..ап) и вычеркивания столбца для аргумента х?. Полученная таблица будет определять некоторую функцию g(xl> ... ..., х<+и ..хГ1). Будем говорить, что функция g{xu Х1-1, х{+1, ..хп) получена из {(хи ..а:„) путем удаления фиктивной переменной х^ а также, что
ФУНКЦИЯ ](хи . . ., ?„) ПОЛучаеТСЯ ИЗ р(х1) . .., Х1-и
#<+1, ..х„) путем введения фиктивной переменной Хь
Определение. Функции и /2 называются равными, если функцию /2 МОЖНО получить ИЗ /1 путем добавления и изъятия фиктивных аргументов.
В дальнейшем всюду функции рассматриваются с точностью до фиктивных переменных, т. е. мы считаем, что если задана функция fl, то задана и любая равная ей функция /2. Это накладывает некоторые естественные ограничения на классы функций, которые будут здесь рассматриваться. В частности, класс функций, обладающих определенными свойствами, будет рассматриваться только в том случае, если эти свойства инвариантны относительно операций введения и удаления фиктивных переменных.
Существуют два типа функций, которые не имеют существенных переменных: функции первого типа тождественно равпы 0, а второго — X. Ввиду этого целесообразно включить в наши рассмотрения константы 0 и 1 (рассматривая их как функции от пустого множества переменных).
Для иллюстрации сказанного рассмотрим два класса симметрических функций.
Определение. Булева функция 1(хи ..., хп) называется симметрической относительно переменных хи ..., хк (2<&^л.), если для любой подстановки
Аналогично вводится понятие функции, симметрической относительно произвольных переменных .. ., х{^ Очевидно, что функции, тождественно равные константам 0 и 1, являются симметрическими относительно любой совокупности своих перемеппых.
п ример 1. а) Класс функций, симметрических относительно всех своих переменных. Это свойство не яв-
I имеет место- равенство
ГЛ. і. АЛГЕБРА ЛОГИКИ
13
ляется инвариантным относительно операции введения несущественной переменной, так как любая функция, отличная от константы и обладающая этим свойством, существенно зависит от всех своих переменных (зависимость хотя бы от одной переменной следует из того, что функция принимает оба значения 0 и 1, а зависимость от всех переменных — из симметрии). Такие классы дальше рассматриваться не будут.
б) Класс функций, симметрических относительно всех своих существенных переменных. Это свойство, очевидно, является инвариантным относительно операций введения и удаления несущественных переменных. Такой класс может рассматриваться.
Замечание. Если дана конечпая система функций из Р2: (А, /Л, $>1, то можно считать, что все эти
функции зависят от одних и тех же переменных #!, ... ..., хп, т. е. имеют вид
/1 (^1, • * ?) 2-п) »??•»/* (*^1> • • Ч Хп) ?
С другой стороны, если дана функция, отличная от константы, то путем отождествления переменных из нее можно получить равную ей функцию, все переменные которой являются существенными.
В заключение этого параграфа рассмотрим- примеры функций алгебры логики. Данные функции часто употребляются в математической логике и кибернетике и играют такую же роль, как, например, хп или атд; в анализе, поэтому их можно считать «элементарными»:
1) 1ЛХ) = 0 — константа 0;
2) /2(ж)= 1 —• константа 1;
3) /,(*) = х — тождественная функция;
4) }ь(х) = х — отрицание х (.т читается «не я»);
5) /5(^1, хг) = {х1&хг)—конъюнкция Х1 и хъ (чита-
ется их1 и .т-»). Вместо знака & употребляется знак -или вообще знак опускается, т. е. пишут (х^х2). Эту функцию часто называют логическим умножением',
6) fe(xu хг) = (^ V л:г) — дизъюнкция Х\ и х2 (читается «х, или хг»). Эту функцию часто называют логическим, сложением;
7) /7(^1, xг) = (x^ хг) —импликация .т, и х2 (чита-
ется «из х1 следует д:2»). Эту функцию часто называют
логическим следованием;
8) /е(^1, жг) = (а*,+ж2)—сложение хх и хг по той 2;
9) и (^11 хг)= (хФхг) — функция Шеффера.
14 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Таблица 2
X 0 1 X X
0 0 1 0 1
1 0 1 1 0
Таблица 3
*1 х2 (?З7! V х2> О,-*-*,,) (хг/х2)
0 0 0 0 1 0 \
0 1 0 1 1 1
1 0 0 1 0 1 1
1 1 1 1 1 0 0
В таблицах 2, 3 даются значения этих функций. Заметим, что
(.г± & #2) = т1п (а?!, х^={х1-хг)1 (#! Угс2)= тах^,, х2).
§ 2. Формулы. Реализация функций формулами
Как и в элементарной алгебре, исходя из «элементарных» функций, можно строить формулы. Ниже приводится индуктивное определение формул.
Определение. Пусть ^ — некоторое (пе обязательно конечное) подмножество функций из Рг.
а) Базис индукции. Каждая функция {(хи ... .... хт) из $ называется формулой над
б) Индуктивный переход. Пусть /о(хи ... ..., Хт) — функция из $ и Аи ..Лт — выражения, являющиеся либо формулами над либо символами неременных из и. Тогда выражение и(Аи ..Лт) называется формулой над &
