Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 10

Этим упорядочением будем пользоваться и в дальнейшем. При любом фиксированном упорядочении наборов логическая функция и переменных полностью определяется вектор-столбцом значений функции, т. е. 2". Поэтому число ~Р,(п) ( различных функций и переменных равно числу различных двоичных векторов длины 2", т. е, 2'". Переменная х; в функции )(х!, ..., х; !, хь х;+!, ..., х ) называется несущественной (или фиктивной), если Т(х!, ..., х! „О, хсь„..., ха) =!(х!, ..., х! !, 1, хсь!, ..., х,) при любых значениях остальных переменных, т.е. если изменение значения х! в любом наборе значений х!, ..., х„не меняет значения функции.

В этом случае функция !(х!, ..., х„) по существу зависит от п — 1 переменной, т. е. представляет 4* б! собой функцию д(х!, „.,х; ьх;+ь ..., х,) от п — 1 переменной. Говорят, что функция д получена из функции 1 удалением фиктивной переменной, а функция 1 получена иа д введением фиктивной переменной, причем эти функции по опре. делению считаются равными. Например, )(хьхз,хз) =а(х!, хе) означает, что пРи любь!х ЗначениЯх к~ и хз 1= и независимо от значения хз. Смысл удаления фиктивных переменных очевиден, поскольку оии не алия!от на значение функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению всякую функцию и переменных можно 'сделать функцией любого большего числа переменных.

Поэтому любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных (являющегося объединением множеств переменных всех взятых функций),что часто бывает удобно. В частности, только что доказанное равенство (Рз(п) ( = 2' справедливо при условии, что Рз(п) содержит все возможные функции и переменных, в том числе и функции с фиктивными переменными.

Примеры логических функций. Логических функций одной переменной — четыре; они приведены в фе Ч'т грз грз О ' О ! ! О ! О ! ' «Черта сверлу» — традиционное обозначение отрицания, которое из-за его привычности созранеио и в этой главе. Однако оно не очень удобно для формальных определений, а в прилоэкениях — при вводе формул в ЭБМ, где все символы должны располагатьсв в строчку. Поэтому все чаще употребляется символ 1, который будет исгользоваться в гл. б, 52 табл.

3.2, Функции гро и фз — константы О и 1 соответственно; пх значения не зависят от значения переменной, и, следовательно, переменная х для них несущественна. Функция ф! «повторяет» х: ф1(х) =х. Функция фз(х) называется отрицанием х (или функцией НЕ) и обозначается х, ~х,х', х'. Ее значение противоположно значению х. Логических функций двух переменных — 16; они приведены в табл. 3.3. Функции эро и фщ — константы О и 1, т.е. функции с двумя несущественными переменными. Отметим, что формально эти функции отличаются от фо и грз в табл.

3.2; все функции в табл. 3.2 — унарные операции на В, а все функ- Таелича ЗЗ х! х» ~('0 т! '('! тз «4 !(!Б !1!6 чч ч'В $9 !(!!О т!! ч!!2 т!э т!4 т!ь о о о о 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 О 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 ! ! 1 1 0 0 0 0 1 ! 1 1 1 0 0 1 ! 0 0 ! 1 1 0 1 0 1 0 ! 0 1 ции в табл. 3.3 — бинарные операции на В. Однако ранее уже было принято функции, отличающиеся лишь несущественными переменными, считать равными. Функция ф!(х!, х,) называется конъюнкцией х! и хз! ее обозначения: х!е!хм х!Дхь х! х! (во всех случаях знак конъюнкции аналогично умножению часто опускают и пишут х,х,). В этой книге конъюнкция будет обозначаться знаком е!. Она равна 1, только если х! н х, равны 1, поэтому ее называют часто функцией И.

Еще одно ее название — «логическое умножение», поскольку ее таблица действителыю совпадает с таблицей обычного умножения для чисел 0 и 1. Функция !р!(х!, хз) называется дизъюнк!1ией х! и х»! ее обозначения: х!~/хмх!+хм Она равна 1, если х! или хз ра. вен ! («или» здесь понимается в неразделительном смысле — хотя бы один из двух). Поэтому ее называют часто функцией ИЛИ. Функция !р«(х!, х») — это сложение по модулю 2 (см. пример 2.1,6). Ее обозначения: хохм х!Лхь х!чьхм Она равна 1, когда значения ее аргументов различны, и равна О, когда они равны. Поэтому функцию !рз иногда называют неравнозначностью. Функция !рэ(х„х») называется эквивалентностью, или равнозначностью. Ее обозначения: х! х„х!= — хь Она равна 1, когда значения ее аргументов равны, и равна О, когда они различны. Еще трн функции имеют свои названия: !р!з(х!,х!) — импликаиия; обозначения х!-~хмх! «х,; читается «если х!, то хз»; !рв(х!, х») — стрелка Пирса; обозначение хДх,; фм(х!, х») — штрих Шеффера; обозначение х!1хь Остальные функции специальных названий не имеют и, как будет показано позднее, легко выражаются через перечисленные ранее функции.

В функциях зрз и зри переменная х, фиктивна; из табл. 3.3 ВиднО, что фз(хь хз) =кь зр|з(хь хз) =хь В функциях фз и ф,о фиктивна переменная х,: фз(хь х,) =хг, зр1о(хь хз) =хз. Таким образом, из !6 функций двух переменных шесть функций имеют фиктивные переменные. С ростом п (числа переменных) доля функций, имеющих фиктивные переменные, убывает и стремится к нулю. Суперпозиции н формулы. В $ 1.2 было введено понятие суперпознции функций. Напомним, что сунерпозииией ФУнкЦий !'ь ..., !' называетсЯ фУнкциЯ 1, полУченнаЯ с помощью подстановок этих функций друг в друга и переименования переменных, а формулой называется выражение, описывающее эту суперпозицию. Понятие суперпозиции очень важно в алгебре логики, поэтому рассмотрим его более подробно.

Пусть дано множество (конечное или бесконечное) исходных функций Х=()ь ..., т ...). Символы переменных хь ..., х„... будем считать формулами глубины О. Формула г' имеет глубину й+1, если Р имеет вид ),(Гь ..., Р„,), где 1;еиХ, н; — число аРгУментов 1ь а Гь ..., Е„, — фоРмУлы, максимальная из глубин которых равна й. Гь, Р„, называются аодформулами Р; )з называется внешней или главной онвраз1ией формулы г'. Все подформулы формул Еь ..., Р„, также называются подформулами г". Например, !з(хь хз, хз) — это формула глубины 1, а !з(!з(хз х|) гз(хп 1з(хь хз))) — формула глубины 3, содержащая одну подформулу глубины 2 и две подформулы глубины 1. В дальнейшем конкретные формулы, как правило, будут иметь более привычный вид, при котором знаки функций стоят между аргументами (такую запись называют инфиксной).

Например, если тз обозначает дизъюнкцию, тз — конъюнкцию, а тз — сложение по гпоб 2, то приведенная ранее формула примет вид: (3.1) (х, ~/ х,) 8=!(х,й (х,ЯхД) Все формулы, построенные описанным ранее образом, т. е. содержащие только символы переменных, скобки и знаки функций из множества Х, называются формулами над Х, Возможны и другие варианты понятия глубины. Например, часто считается, чтв расстановка отрицаний над переменными не увеличивает глубины; в случае, когда Х содержит ассоциативную операцию 1, можно определить глубину так, что применение) к формулам с той же внешней операцией / не увеличивает глубину формулы. Напри мер, х~(хз'/хзх,) и хзхг(хз'ч/хзхз) имеют одну и ту же глубину 3; ДНФ (см.

далее) всегда имеет глубину 2. Всякая формула, выражагошая функцию / как суперпозицию других функций, задает способ ее вычисления (при славин, что известно, как вычислить исходные функции). тот способ определяется следующим очевидным правилом: формулу можно вычислить, только если уже вычис. лены значения всех ее подформул. Вычислим, например, формулу (3.1) на наборе хг=1, хз — — 1, хз=0. Получим (используя табл, 3.2): хз'г/х1 — — 1; хг(Х~~Я-''хз) =х, 60=0; (хз'г/ 'ч/х Я(хг(х,~~+~хе) ) =1Я0=1, аким образом, формула каждому набору значений аргументов ставит в соответствие значение функции и, следовательно, может служить наряду с таблицей способом задания и вычисления функции. В частности, по формуле, вычисляя ее на всех2" наборах, можно восстановить таблицу функции.

О формуле, задающей функцию, говорят также, что она реализует или представляет эту функцию. В отличие от табличного задания представление данной функции формулой не единственно. Например, если в качестве исходного множества функций зафиксировать множество тфьфг, фз), т. е. функции И, ИЛИ, НЕ, то функцию штрих Шеффера можно представить формулами хз ~/х, их,х,, (3 2) а функцию стрелка Пирса — формулами Х! Хз И Хз~/Хз . (3.3) Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными (см. пример 1.12, б). Эквивалентность формул обозначается знаком равенства; поэтому можно записать фы(хь хз) х,~/хз-—- хгхз. Как для двух данных формул выяснить, эквивалентны они или нет? Существует стандартный метод, всегда приводящий к ответу: по каждой формуле восстанавливаетси таблица' функции, а затем полученные две таблицы ' До сих пор все, что говорилось о формулах и суперпозициях, было справедливо не только для логических, ио и для любых функций вообще (см.

$1.2). Денный же метод проверки эквивалентности годится тельно для функций с конечными областями оиределенихс сравниваются. Иначе говоря, для каждого набора значений переменных проверяется, равны ли на нем значения формул. Этот метод требует 2 2" вычислений (если считать, что обе формулы зависят от п переменных) и на практике оказывается слишком громоздким. Существуют и другие методы установления эквивалентности формул и получения новых формул, эквивалентных исходной. К этим методам, называемым эквивалентными преобразованиями формул, мы еще вернемся. ЗДЬ БУЛЕВА АЛГЕБРА В этом параграфе будут рассмотрены представления логических функций в виде суперпозиций функций И, ИЛИ, НЕ.

Разложение функций по переменным, Совершенная дизь- юнктнвная нормальная форма. Введем обозначение х'=х, х'=х. Пусть а — параметр, равный 0 или 1. Тогда х"=1, если х=а, и х"=О, если хна. Теорема 3.1. Всякая логическая функция Дхв ...,х„) мо- жет быть представлена в следующем виде: Г" (хн ..., х, х +,..., х„) = — ~/ х",С.. х" )(яв ..., а, х +„..., х„), (3.4) аг...,а где т -'и, а дизъюнкция берется по всем 2~ наборам зна- чений переменных хв ..., х . Это равенство называется разлоэхенаем по переменным хь ..., х .