Спирина, М.С. Дискретная математика

Функция / 15 = (1110), равная 0, только если оба аргумента рав­ ны 1, называется ш трихом Ш еф ф е р а . Обозначается как Д х , у) = х \ у. Штрих Шеффера является отрицанием конъюнкции. Все перечисленные функции двух булевых переменных заме­ чательны не только тем, что являются логическими операция­ ми, сходными с операциями над множествами, но и тем, что они симметричны по своим аргументам. Запись соответствую­ щей операции между символами переменных позволяет рассмат­ ривать ее как бинарное отношение, причем симметричное. П о ­ этому в табл. 4.3 указан только разделяющий знак, а порядок сле­ дования аргументов несуществен. О бщ е е правил о . Поскольку подстановка 0 —> 1, 1 —>0 в строке значений (т.е. инверсия значений функции) отображает двоичное число в дополнительное до 11 . .. 1 , то любые две функции, распо­ ложенные симметрично относительно центральной вертикальной оси таблицы значений, будут взаимно инвертированными. Поэто­ му fk ~ f 2 2\\ _*• Эта формула является простым переводом чисел из двоичной в десятичную систему записи. Например, штрих Шеф­ фера f l5(x, у) = х | у = ху = / 2 (х, у). 2. И м плик ации . Функция / 4 = (1101), значение которой равно 0 , только если первый аргумент равен 1 , а второй 0 , называется импликацией , или сл ед у ем о с т ью (от лат. implico —тесно связывать). Обозначается как Д х , у) = х -> у. Очевидно, что подобная опера­ ция несимметрична. Тогда функция / 12 = (1011) будет также имп­ ликацией, но уже Д х , у) = у -> х. Функции Уз = (0010) ИУ 5 = (0100) являются отрицаниями имп­ ликаций / 14 и / 12 соответственно. 3. Ф унк ц ии , явно за в и сящ и е о т о д н о й п ер ем ен н о й . Функция f A= = (ООП), все значения которой совпадают со значениями первой переменной, обозначается Д х , у) =х. Аналогично/ 6 (х, у) = (0101) = у. Функции / , з = (1100) и / п = (1010) являются отрицаниями f 4 и f b соответственно. В последнем примере уже из формулы было очевидно, что от переменной у функция не зависит, так как она явно не входит в формулу. Однако возможен случай, когда переменная явным образом входит, но значение функции от нее все равно не за­ висит. Докажем два тождества с помощью таблицы истинности (см. табл. 4.3). 1. x- 1= х. 2 . у v у = 1 . Рассмотрим таблицу значений (таблицу истинности) функции g(x, у) = х(у v у). Из тождеств видно, что g(x, у) = х(у v у) = х ■1 = х. Обе переменные в формулу входят явно, а фактически получаем ту же функцию f 4, зависящую только от х. Итак, булева функция 138