Лекция Логические переменные в двузначной логике Определение Логической переменной в двузначной логике называется перемен ная величина x, принимающая значения из некоторого двухэлементного множества
 Скачать 283.73 Kb.
|
1 2 Лекция 1. Логические переменные в двузначной логике Определение 1. Логической переменной в двузначной логике называется перемен- ная величина x, принимающая значения из некоторого двухэлементного множества. Пример 1. Логические переменные могут принимать значения из следующих двух- элементных множеств: 1) E 2 = {0, 1} ; 2) E ? = { истина, ложь} (при доказательстве теорем); 3) E ?? = { да, нет} (в так называемых экспертных системах, используемых для ав- томатического анализа информации с целью решения проблем); 4) E ??? = { наличие потенциала в +5 вольт в определенной точке схемы, отсутствие потенциала в +5 вольт в той же точке} (в электронике). Упражнение 1 (д/з). Привести другие примеры логических переменных, прини- мающих значения из некоторых двухэлементных множеств. Замечание 1. В дальнейшем, кроме специально оговоренных случаев, будем рас- сматривать логические переменные, принимающие значения из множества E 2 = {0, 1} Определение 2. Пусть n натуральное число. Далее будем рассматривать n ло- гических переменных x 1 , x 2 , . . . , x n , причем x i принимает значения из E 2 = {0, 1} (i = 1, . . . , n) . Составим для этих логических переменных упорядоченные наборы их значе- ний (a 1 , a 2 , . . . , a n ) , где a i ? {0, 1} (i = 1, . . . , n) . Каждый набор значений (a 1 , a 2 , . . . , a n ) называется также двоичным вектором. Пример 2. Составить всевозможные наборы значений логических переменных и найти их количество при следующих значениях n: a) n = 1: для 1 логической переменной x 1 имеется N 1 = 2 различных набора значе- ний, каждый из которых состоит из 1 значения: (0) и (1). б) n = 2: для 2 логических переменных x 1 и x 2 имеется N 2 = 4 различных набора значений, каждый из которых состоит из 2 значений: (0, 0), (0, 1), (1, 0), (1, 1). в) n = 3: Упражнение 2 (д/з). n = 3. N 3 ? Утверждение. Количество всех возможных наборов значений n логических пе- ременных равно N n = 2 n Доказательство (методом математической индукции). 1. Очевидно, что для одной переменной (n = 1) имеется N 1 = 2 1 = 2 различных набора значений: (0) и (1) (см. пример 2а). 2. Предположим, что для n = k переменных имеется 2 k возможных наборов значе- ний: N k = 2 k 3. Докажем, что N k+1 = 2 k+1 . Для этого добавим к набору k переменных (x 1 , x 2 , . . . , x k ) (k+1) ю переменную x k+1 . Тогда каждому набору значений k переменных (a ? 1 , a ? 2 , . . . , a ? k ) будут соответствовать 2 набора значений k + 1 переменной: (a ? 1 , a ? 2 , . . . , a ? k , 0) и (a ? 1 , a ? 2 , . . . , a ? k , 1) Следовательно, количество наборов значений k + 1 переменной равно N k+1 = 2 · N k = 2 · 2 k = 2 k+1 , ч.т.д. 1 Множества наборов значений логических переменных часто для определенности выстраивают в некотором порядке, что обозначается (c 1 , . . . , c n ) · · · (a 1 , . . . , a n ) (b 1 , . . . , b n ) · · · (d 1 , . . . , d n ). Знак читается как предшествует. В частности, нередко используется так называемый лексикографический порядок. Определение 3. Лексикографическим порядком наборов значений логических пе- ременных называется порядок, при котором для любых двух наборов (a 1 , . . . , a n ) и (b 1 , . . . , b n ) таких, что (a 1 , . . . , a n ) (b 1 , . . . , b n ) , выполняется одно из следующих со- отношений: ? ? ? ? ? ? a 1 < b 1 , (1) ?m : 1 ? m ? n ? 1, ? ? ? ? ? ? ? a 1 = b 1 , a m = b m , a m+1 < b m+1 (2) Определение 3'. Нелексикографическим порядком наборов значений логических переменных называется порядок, при котором существуют такие наборы (a ? 1 , . . . , a ? n ) и (b ? 1 , . . . , b ? n ) , что (a ? 1 , . . . , a ? n ) (b ? 1 , . . . , b ? n ) , для которых не выполняется ни одно из соотношений (1) и (2). Пример 3. а) n = 1: (0) (1) лексикографический порядок в силу определения 3 (выполня- ется соотношение (1)), (1) (0) нелексикографический порядок в силу определения 3' (не выполняется ни одно из соотношений (1) и (2)). б) n = 2: 1 ? . (0, 0) (0, 1) (1, 0) (1, 1) лексикографический порядок: (a 1 , a 2 ) = (0, 0) (0, 1) = (b 1 , b 2 ) , так как в этих наборах a 1 = 0; b 1 = 0 и a 2 = 0 < 1 = b 2 (выпол- няется соотношение (2)), и аналогично (0, 1) (1, 0) (выполняется (1)), (1, 0) (1, 1) (выполняется (2)). 2 ? . (0, 0) (0, 1) (1, 1) (1, 0) нелексикографический порядок: (a 1 , a 2 ) = (1, 1) (1, 0) = (b 1 , b 2 ) , хотя a 1 = 1, b 1 = 1 (не выполняется (1)) и a 2 = 1 > 0 = b 2 (не выполня- ется (2)). Упражнение 3 (д/з). Привести другие примеры нелексикографического порядка наборов значений 2 логических переменных. в) n = 3: Упражнение 4 (д/з). Привести примеры лексикографического и нелексикогра- фического порядка наборов значений 3 логических переменных. Замечание 3. Отметим, что лексикографический порядок совпадает с порядком возрастания наборов (a 1 , . . . , a n ) , рассматриваемых как числа, записанные в двоичной системе счисления, например: (0, 0) ? 0 · 2 1 + 0 · 2 0 < 0 · 2 1 + 1 · 2 0 ? (0, 1) Упражнение 5 (д/з). Проиллюстрировать с помощью записи в двоичной системе счисления соотношения (0, 1) (1, 0) , (1, 0) (1, 1) 2 Лекция 2. Логические функции Напомним, что в математическом анализе под числовой функцией нескольких пере- менных понимается правило (закон соответствия), сопоставляющее числам (x 1 , x 2 , . . . , x n ) ? D ? R n , называемым аргументами, некоторое вполне определенное число y ? E ? R, где множество D область определения функции, множество E область значений функции, что обозначается y = f(x 1 , . . . , x n ) . При этом функция может быть задана различными способами: 1) аналитическим (явно в виде формулы y = f(x 1 , . . . , x n ) , неявно в виде фор- мулы F (x 1 , . . . , x n , y) = 0 или параметрически); 2) графическим (график функции - кривая для n = 1, поверхность для произволь- ного n); 3) если множество D конечно табличным (в этом случае функции называются дискретными). Пример 1. Пусть n = 2 и y = f(x 1 , x 2 ) , причем (x 1 , x 2 ) ? D ? R 2 , где D = {(1, 1), (1, 2), (2, 1), (2, 2)} . Тогда табличным способом можно задать следующую функ- цию f : D f ? E , где E = {1, 2, 3}: x 1 x 2 f (x 1 , x 2 ) 1 1 1 1 2 2 2 1 3 2 2 1 Упражнение 1 (д/з). Задать табличным способом другие функции f : D f ? E , где D и E множества из примера 1. Замечание 1. В отличие от математического анализа, в дискретной математи- ке рассматриваются только дискретные функции. В частности, в разделе дискретной математики, называемом двузначной логикой, рассматриваются функции логических переменных, принимающих только два значения (см. определение 1 из лекции 1): 0 и 1, или истина и ложь и т.д. (см. пример 1 из лекции 1), при этом те же два значения принимают и сами функции. Таким образом, можно сформулировать Определение 1. Логической функцией n переменных на двухэлементном множе- стве D называется правило f, сопоставляющее n логическим переменным (аргументам) x 1 , . . . , x n со значениями из D некоторый вполне определенный элемент подмножества E f того же множества D. В этом случае (D, . . . , D) ? D n область определения функ- ции f, а множество E f ? D область значений f: (D, . . . , D) f ? E f ? D ? D n f ? E f ? D. В частности, для E 2 = {0, 1} ({0, 1}, . . . , {0, 1}) f ? E f ? {0, 1} ? {0, 1} n f ? E f ? {0, 1}. 3 f логическая функция n переменных Замечание 2. Построить логическую функцию значит задать какое-либо правило, которое позволяет найти значения функции f для всех возможных наборов значений аргументов, например, в виде таблицы, в левой части которой перечислены все возмож- ные наборы значений аргументов для определенности в лексикографическом порядке, а в правой части значения функции, соответствующие этим наборам (см. примеры ниже). Пример 2. n = 1, {0, 1} f 1,i ? E f 1,i ? {0, 1} : f 1,i логические функции одной перемен- ной (здесь и далее первый индекс обозначает число переменных, а второй индекс i номер рассматриваемой функции среди функций данного числа переменных). f 1,i ? (i ?) i = 0 . f 1,0 : Таблица 1 x f 1,0 (x) 0 0 1 0 Упражнение 2 (д/з). Построить другие логические функции одной переменной. Сколько их всего существует? Ответ: 4 функции, представленные в табл. 2. Таблица 2 x f 1,0 (x) f 1,1 (x) f 1,2 (x) f 1,3 (x) 0 0 0 1 1 1 0 1 0 1 Замечание 3. Эти функции называются и обозначаются следующим образом: f 1,0 (x) ? 0 константа ноль, f 1,1 (x) ? x тождественная функция, f 1,2 (x) ? Ї x отрицание x (читается не x), f 1,3 (x) ? 1 константа единица. Замечание 4 (расширенная интерпретация отрицания). Если 0 ложь и 1 истина, то: а) отрицание истины (1) есть ложь (0), б) отрицание лжи (0) есть истина (1). Далее рассмотрим логические функции f 2,i двух переменных (n = 2). В этом случае количество различных наборов переменных будет равно N 2 = 2 2 = 4 (см. утверждение из лекции 1). Упражнение 3 (д/з). Построить в лексикографическом порядке все логические функции f 2,i двух переменных. Чему равно их количество P 2 (2) ? (Здесь нижний индекс означает количество возможных значений каждой переменной, а число в скобках количество переменных.) 4 Ответ: P 2 (2) = 16 . Функции представлены в табл. 2 в лексикографическом поряд- ке, соответствующем возрастанию чисел от 0 до 15, записанных в двоичной системе счисления. Вторые индексы у функций соответствуют этим числам. Таблица 2 x 1 x 2 f 2,0 (x 1 , x 2 ) f 2,1 (x 1 , x 2 ) f 2,2 (x 1 , x 2 ) f 2,3 (x 1 , x 2 ) 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 x 1 x 2 f 2,4 (x 1 , x 2 ) f 2,5 (x 1 , x 2 ) f 2,6 (x 1 , x 2 ) f 2,7 (x 1 , x 2 ) 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 x 1 x 2 f 2,8 (x 1 , x 2 ) f 2,9 (x 1 , x 2 ) f 2,10 (x 1 , x 2 ) f 2,11 (x 1 , x 2 ) 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 x 1 x 2 f 2,12 (x 1 , x 2 ) f 2,13 (x 1 , x 2 ) f 2,14 (x 1 , x 2 ) f 2,15 (x 1 , x 2 ) 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 5 Лекция 3. Логические функции двух переменных. Композиции логических функций. Эквивалентные логические функции Некоторые из логических функций двух переменных (см. таблицу 2 лекции 2) имеют специальные названия и обозначения: a) f 2,0 (x 1 , x 2 ) ? 0 константа ноль. Таблица 1 x 1 x 2 f 2,0 (x 1 , x 2 ) 0 0 0 0 1 0 1 0 0 1 1 0 b) f 2,1 (x 1 , x 2 ) = x 1 ? x 2 конъюнкция x 1 и x 2 (читается x 1 и x 2 ). Отметим, что x 1 ? x 2 = min(x 1 , x 2 ) . Конъюнкцию часто называют логическим умножением и обозначают также x 1 · x 2 или x 1 x 2 Замечание 1 (расширенная интерпретация конъюнкции). Если 0 ложь и 1 истина, то конъюнкцию можно интерпретировать так: а) ложь и ложь ложь, б) ложь и истина ложь, в) истина и ложь ложь, г) истина и истина истина. Таблица 2 x 1 x 2 f 2,1 (x 1 , x 2 ) 0 0 0 0 1 0 1 0 0 1 1 1 c) f 2,6 (x 1 , x 2 ) = x 1 ? x 2 сложение по mod 2: x 1 ? x 2 = x 1 + x 2 (x 1 + x 2 < 2), 0 (x 1 + x 2 = 2). Замечание 2. Здесь и далее второй индекс функции (ее номер среди функций двух переменных) соответствует двоичному числу, образованному значениями этой функции на наборах значений аргументов, расположенных в лексикографическом порядке. Так, 6 = 0 · 2 3 + 1 · 2 2 + 1 · 2 1 + 0 · 2 0 Таблица 3 x 1 x 2 f 2,6 (x 1 , x 2 ) 0 0 0 0 1 1 1 0 1 1 1 0 6 d) f 2,7 (x 1 , x 2 ) = x 1 ?x 2 дизъюнкция x 1 и x 2 (читается: x 1 или x 2 ). Отметим, что x 1 ? x 2 = max(x 1 , x 2 ) . Дизъюнкцию часто называют логическим сложением и обозначают также x 1 + x 2 Замечание 3 (расширенная интерпретация дизъюнкции). Если 0 ложь и 1 истина, то дизъюнкцию можно интерпретировать так: а) ложь или ложь ложь, б) ложь или истина истина, в) истина или ложь истина, г) истина или истина истина. Таблица 4 x 1 x 2 f 2,7 (x 1 , x 2 ) 0 0 0 0 1 1 1 0 1 1 1 1 e) i = 9 : f 2,9 (x 1 , x 2 ) = x 1 ? x 2 эквиваленция (равная 1, если x 1 и x 2 равны между собой, и 0 в противном случае). Таблица 7 x 1 x 2 f 2,9 (x 1 , x 2 ) 0 0 1 0 1 0 1 0 0 1 1 1 Замечание 4 (расширенная интерпретация эквиваленции). Если 0 ложь и 1 истина, то эквиваленцию можно интерпретировать так: а) ложь равносильна лжи истина, б) ложь равносильна истине истина, в) истина равносильна лжи ложь, г) истина равносильна истине истина. f) i = 13 : f 2,13 (x 1 , x 2 ) = x 1 ? x 2 импликация x 1 и x 2 (читается: из x 1 следует x 2 ). Эту функцию часто называют логическим следованием. Таблица 8 x 1 x 2 f 2,13 (x 1 , x 2 ) 0 0 1 0 1 1 1 0 0 1 1 1 Замечание 5 (расширенная интерпретация импликации). Если 0 ложь и 1 истина, то импликацию мпожно интерпретировать так: 7 а) из лжи может следовать ложь истина, б) из лжи может следовать истина истина, в) из истины может следовать ложь ложь, г) из истины может следовать истина истина. g) f 2,15 (x 1 , x 2 ) = 1 константа единица. Таблица 5 x 1 x 2 f 2,15 (x 1 , x 2 ) 0 0 1 0 1 1 1 0 1 1 1 1 В общем случае число различных логических функций n переменных обозначает- ся P 2 (n) (индекс 2, как и выше, означает количество возможных значений каждого аргумента). Упражнение 1 (д/з). Доказать методом математической индукции, что P 2 (n) = 2 2 n число различных двоичных векторов длины 2 n Определение 1. Функция, полученная путем применения логической функции f 0 (x 1 , . . . , x n ) к значениям логических функций f 1 (x 1 , . . . , x m ), . . . , f n (x 1 , . . . , x m ) , назы- вается композицией логических функций: f (x 1 , . . . , x m ) = f 0 (f 1 (x 1 , . . . , x m ), . . . , f n (x 1 , . . . , x m )). Иcпользуя композиции логических функций, можно получать другие логические функции. Пример 1. Из f 2,7 (x 1 , x 2 ) с помощью функции отрицания f 1,2 (x) получить f 1,2 (f 2,7 (x 1 , x 2 )) ? Ї f 2,7 (x 1 , x 2 ) Решение: Таблица 1 x 1 x 2 f 2,7 (x 1 , x 2 ) f 1,2 (f 2,7 (x 1 , x 2 )) 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 , где используется функция отрицания f 1,2 (x) : Таблица 2 x f 1,2 (x) 0 1 1 0 Пример 2. Из f 2,2 (x 1 , x 2 ) и f 2,3 (x 1 , x 2 ) с помощью функции конъюнкции f 2,1 (x 1 , x 2 ) получить f 2,1 (f 2,2 (x 1 , x 2 ), f 2,3 (x 1 , x 2 )) ? f 2,2 (x 1 , x 2 ) ? f 2,3 (x 1 , x 2 ) 8 Решение: Таблица 3 x 1 x 2 f 2,2 (x 1 , x 2 ) f 2,3 (x 1 , x 2 ) f 2,2 (x 1 , x 2 ) ? f 2,3 (x 1 , x 2 ) 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 , где используется функ- ция конъюнкции f 2,1 (x 1 , x 2 ) : Таблица 4 x 1 x 2 f 2,1 (x 1 , x 2 ) 0 0 0 0 1 0 1 0 0 1 1 1 Упражнение 1 (д/з). Из f 2,1 (x 1 , x 2 ) и f 2,3 (x 1 , x 2 ) с помощью функции дизъюнкции f 2,7 (x 1 , x 2 ) получить f 2,7 (f 2,1 (x 1 , x 2 ), f 2,3 (x 1 , x 2 )) ? f 2,1 (x 1 , x 2 ) ? f 2,3 (x 1 , x 2 ) Определение 2. Эквивалентными логическими функциями называются функ- ции, имеющие одинаковые таблицы задания функции. Будем обозначать эквивалентные функции так: f 1 (x 1 , . . . , x n ) ? f 2 (x 1 , . . . , x n ) Пример 3. Ї f 2,11 (x 1 , x 2 ) ? f 2,4 (x 1 , x 2 ) , как видно из следующей таблицы: Таблица 5 x 1 x 2 f 2,11 (x 1 , x 2 ) Ї f 2,11 (x 1 , x 2 ) f 2,4 (x 1 , x 2 ) 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0 Упражнение 2 (д/з). Доказать: Ї f 2,2 (x 1 , x 2 ) ? f 2,13 (x 1 , x 2 ) , f 2,4 (x 1 , x 2 ) ? f 2,5 (x 1 , x 2 )? f 2,6 (x 1 , x 2 ) 9 Лекция 4. Несущественные и существенные переменные Определение 1. Переменная x i для функции n переменных f(x 1 , . . . , x i?1 , x i , x i+1 , . . . , x n ) называется несущественной, если для любых наборов значений переменных, отличаю- щихся только значениями переменной x i , будет выполняться равенство f (a 1 , . . . , a i?1 , 0, a i+1 , . . . , a n ) = f (a 1 , . . . , a i?1 , 1, a i+1 , . . . , a n ), (?) т.е. изменение x i при любом одинаковом наборе остальных переменных не изменяет значения функции. Замечание 1. Если выполнено (*), функция f(x 1 , . . . , x i?1 , x i , x i+1 , . . . , x n ) по суще- ству зависит от n?1 переменной, т.е. представляет собой функцию g(x 1 , . . . , x i?1 , x i+1 , . . . , x n ) : f (x 1 , . . . , x i?1 , x i , x i+1 , . . . , x n ) ? g(x 1 , . . . , x i?1 , x i+1 , . . . , x n ). Данную функцию можно получить из функции f(x 1 , . . . , x n ) путем удаления несуще- ственной переменной x i . И наоборот, иногда полезно вводить несущественную пере- менную, т.е. можно любую функцию сделать функцией сколь угодно большого числа переменных, что часто бывает удобно. Пример 1. Доказать, что для функций одной переменной f 1,0 (x) и f 1,3 (x) един- ственная переменная x является несущественной. Решение. 1) Функция f 1,0 (x) задается таблицей 1. Таблица 1 x f 1,0 (x) 0 0 1 0 Из этой таблицы видно, что f 1,0 (0) = 0, f 1,0 (1) = 0; т.е. изменение значения переменной x не приводит к изменению значения функции. Следовательно, x несущественная переменная. 2) Функция f 1,3 (x) задается таблицей 2. Таблица 2 x f 1,3 (x) 0 1 1 1 Из этой таблицы видно, что f 1,3 (0) = 1, f 1,3 (1) = 1, т.е. изменение значения переменной x не приводит к изменению значения функции. Следовательно, x несущественная переменная. 10 Упражнение 1 (д/з). Доказать, что для функций двух переменных f 2,0 (x 1 , x 2 ) и f 2,15 (x 1 , x 2 ) обе переменные x 1 и x 2 являются несущественными. Пример 2. Доказать, что функция f 2,3 (x 1 , x 2 ) имеет одну несущественную пере- менную: а) найти ее, б) обосновать. Решение. 1) Функция f 2,3 (x 1 , x 2 ) задается таблицей 3. Таблица 3 x 1 x 2 f 2,3 (x 1 , x 2 ) 0 0 0 0 1 0 1 0 1 1 1 1 Из этой таблицы видно, что ? ? ? ? ? ? ? f 2,3 (0, 0) = 0, f 2,3 (0, 1) = 0, f 2,3 (1, 0) = 1, f 2,3 (1, 1) = 1, т.е. изменение значения переменной x 2 при одинаковых значениях x 1 не приводит к изменению значения функции. Следовательно, x 2 несущественная переменная. 2) Из доказанного следует, что функции f 2,3 (x 1 , x 2 ) соответствует функция только одной переменной g 2,3 (x 1 ) . Исключая x 2 из табл. 3, получим табл. 4 таблицу задания функции g 2,3 (x 1 ) , причем g 2,3 (x 1 ) ? x 1 , т.е. функция g 2,3 (x 1 ) эквивалентна тождествен- ной функции f 1,1 (x 1 ) ? x 1 Таблица 4 x 1 g 2,3 (x 1 ) 0 0 1 1 Упражнение 2 (д/з). Доказать, что каждая из функций f 2,5 (x 1 , x 2 ), f 2,10 (x 1 , x 2 ) и f 2,12 (x 1 , x 2 ) имеет одну несущественную переменную: а) найти ее, б) обосновать. Замечание 2. Из примера 1 следует, что из 4 функций одной переменной 2 функ- ции f 1,0 (x) и f 1,3 (x) , т.е. 50 процентов, имеют несущественные переменные. Из при- мера 2 и упражнений 1-2 следует, что из 16 функций двух переменных 6 функций f 2,0 (x 1 , x 2 ), f 2,3 (x 1 , x 2 ), f 2,5 (x 1 , x 2 ), f 2,10 (x 1 , x 2 ), f 2,12 (x 1 , x 2 ) и f 2,15 (x 1 , x 2 ) , т.е. 37,5 процен- тов, имеют несущественные переменные. Замечание 3. Можно показать, что с ростом числа переменных доля функций с несущественными переменными убывает и стремится к нулю. Замечание 4. Если переменная не является несущественной, то она является существенной, т.е. имеет место Определение 2. Переменная x i называется существенной для функции n перемен- ных f(x 1 , . . . , x n ) , если существует хотя бы один набор значений (a ? 1 , . . . , a ? i?1 , 0, a ? i+1 , . . . , a ? n ) 11 всех ее переменных, кроме x i , для которого выполняется условие f (a ? 1 , . . . , a ? i?1 , 0, a ? i+1 , . . . , a ? n ) = f (a ? 1 , . . . , a ? i?1 , 1, a ? i+1 , . . . , a ? n ). Пример 3. Зададим произвольным образом логическую функцию трех перемен- ных в виде табл. 5. Определим существенные и несущественные переменные для этой функции. Таблица 5 x 1 x 2 x 3 f (x 1 , x 2 , x 3 ) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 Решение. Проверим несущественность переменной x 3 . Для этого мы должны срав- нить значения функции при одинаковых значениях x 1 и x 2 . Запишем их: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f (0, 0, 0) = 0, f (0, 0, 1) = 0, f (0, 1, 0) = 1, f (0, 1, 1) = 1, f (1, 0, 0) = 1, f (1, 0, 1) = 1, f (1, 1, 0) = 0, f (1, 1, 1) = 0. Из этих соотношений следует, что изменение значения переменной x 3 при одинаковых значениях x 1 и x 2 не приводит к изменению значения функции. Следовательно, x 3 явля- ется несущественной переменной. Исключая из табл. 5 переменную x 3 , т.е. вычеркивая третий столбец и по одной из каждых двух одинаковых строк, получим табл. 6, задаю- щую функцию двух переменных g(x 1 , x 2 ) , эквивалентную функции f 2,6 (x 1 , x 2 ) Таблица 6 x 1 x 2 g(x 1 , x 2 ) 0 0 0 0 1 1 1 0 1 1 1 0 Упражнение 3 (д/з). Доказать, что для функции g(x 1 , x 2 ) переменные x 1 и x 2 являются существенными. 12 Лекция 5. Полиномы Жегалкина Произвольная логическая функция может быть представлена в виде некоторой эк- вивалентной ей композиции конъюнкции и сложения по модулю 2, называемой полино- мом Жегалкина. Пример 1. Рассмотрим, например, логические функции 1 ? x 1 ? (x 1 ? x 2 ), x 2 ? (x 1 ? x 3 ) ? (x 1 ? x 2 ? x 3 ), которые напоминают по структуре алгебраические полиномы (многочлены) нескольких переменных, только вместо умножения в них используется конъюнкция (логическое умножение), а вместо обычного сложения сложение mod 2. Эти функции относятся к так называемым полиномам Жегалкина. Однако, логические функции x 1 ? (x 2 ? x 2 ), x 1 ? x 1 ? (x 1 ? x 2 ) не входят в класс полиномов Жегалкина. Чтобы дать формальное определение полиномов Жегалкина, введем несколько вспо- могательных обозначений. Обозначения. n i=1 ?x i def = x 1 ? · · · ? x n (1) Аналогично j max j=1 ?f ? j (x i 1 , . . . , x i k ) def = f ? 1 (x i 1 , . . . , x i k ) ? · · · ? f ? j max (x i 1 , . . . , x i k ) j (k ? IN). (2) Далее будем рассматривать функции f ? j определенного вида, что обозначается f ? j = f j (x i 1 , . . . , x i k ) = (x i 1 ? · · · ? x i k ) j (k ? 1), (3) для которых полагаем, что: а) каждая из переменных x i 1 , . . . , x i k входит в каждую из функций f j (x i 1 , . . . , x i k ) не более чем по одному разу: i l = i m (1 ? l ? k, 1 ? m ? k, l = m) (4) (например, функция f 1 (x 1 ) = x 1 ? x 1 недопустима, так как здесь l = 1 = 2 = m, но i l = i 1 = 1 = i 2 = i m ); б) все функции f j различны между собой: f p (x i 1 , . . . , x i k ) = f s (x i 1 , . . . , x i k ) (1 ? p ? j max , 1 ? s ? j max , p = s) (5) 13 (например, недопустима ситуация, когда f 1 (x 1 , x 2 ) = f 2 (x 1 , x 2 ) = x 1 ? x 2 , так как здесь p = 1 = 2 = s , но f p (x 1 , x 2 ) = f 1 (x 1 , x 2 ) = x 1 ? x 2 = f 2 (x 1 , x 2 ) = f s (x 1 , x 2 ) ). Замечание 1. При k = 1 в (3) имеем f ?? j (x i mj ) = x i mj Определение 1. Полиномом Жегалкина от n логических переменных называется полином, являющийся суммой по mod 2 некоторой константы a ? {0, 1} и некоторых функций f j (x i 1 , . . . , x i k ) вида (3), удовлетворяющих условиям (4) и (5): a ? j max j=1 ?f j (x i 1 , . . . , x i k 1 2 |