FAQ

AlecSoft design © 1996Введение в дискретную математикуВМК МГУ 2-й семестр 19961 поток, лектор - О.Б. Лупанов (Мехмат МГУ)Другие источники:С.В. Яблонский. Введение в дискретную математику.В.Г. Болтянский, В.А. Ефремович. Наглядная топология.Frequently Asked Questions1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.Фиксируем исходный алфавит переменных U = {u1, ... , un,...}Будем рассматривать функции f(u1, ... , un), аргументы которых определены на множестве E2 ={0,1} и такие, что f(a1, ...

, an)  E2, когда ai  E2 .Эти функции будем называть функциями алгебрылогики или булевыми функциями.Каждая f определяет отображение f: E2 x E2 x ... x E2  E2.Обозначим систему булевых функций через P2.Каждая функция однозначно определяется таблицей истинности. Число строк в таблице истинности для функции n аргументов равно m = 2n. Число функций из P2, зависящих от n аргументовравно p2 (n) = 2m.Функция f существенно зависит от переменной xi, если существуют два набора ее аргументов A= (a1,...,ai 0 ai+1,...,an) и A’ = (a1,...,ai 1 ai+1,...,an), отличающиеся только в значении xi, такие, что значения функции на этих наборах различны: fA  fA’.

Если хi не является существенной, то она называется несущественной или фиктивной.Пусть хi несущественна для f. Тогда обозначим через g функцию n-1 аргументов (a1,...,aiai+1,...,an), такую, что g(a1,...,ai ai+1,...,an) = f(a1,...,ai 0 ai+1,...,an) = f(a1,...,ai 1 ai+1,...,an). Будем говорить,что g получена из f путем удаления фиктивной хi и что f получена из g путем введения фиктивнойхi.f и g называются равными: f  g если f получается из g введением и удалением фиктивных переменных.Элементарные функции: (а) константы 0, 1(б) унарные связки: x, отрицание x(в) бинарные связки: конъюнкция xy  x & y  x  y  min(x,y), дизъюнкция x  y  max(x,y),импликация x  y  (xy) , сложение по модулю 2 (исключающее или) x  y = x + y (mod 2),‘штрих’ Шеффера x / y  (x & y).Простейшие тождествадвойное отрицание (x) = x(x & y) = (x)  (y), (x  y) = (x) & (y)коммутативность x & y = y & x, x  y = y  xx & (x) = 0, x  (x) = x  (x) = 11 & x = 0  x = x, 0 & x = 0, 1  x = x0  x = 1, 1  x = xассоциативность (x & y) & z = x & (y & z)  x & y & z - аналогично для связок , .дистрибутивность (x & y)  z = (x  z) & (y  z), (x  y) & z = (x & z)  (y & z), x  (y & z) = (x  y)& (x  z)(x  y) = y  (x)AlecSoft design © 19962.

Теорема о разложении булевой функции по аргументам. Теорема осовершенной дизъюнктивной нормальной форме.Любую булеву функцию f можно представить в видеf(x1, x2,...,xn) = x1g1(x2,...,xn)  x1g2(x2,...,xn) = x1f(0, x2,...,xn)  x1f(1, x2,...,xn) - разложением по первой переменной. Указанные функции g1 и g2 определены единственным образом.Обозначение x  {x , если  = 1, x, если  = 0}Аналогично, f раскладывается по m  n переменным x1,...,xm - единственным образом в дизъюнкцию 2m формул видаx11...xmm f(1,..,m,xm+1,..., xn).Разложение по всем n переменным называется СДНФ для функции f. СДНФ строится с помощью таблицы истинности.С помощью понятия СДНФ становится очевидно, что любая булева функция представима в видеформулы над множеством из трех элементарных связок { &, ,  }3.

Полные системы. Примеры полных систем (с доказательством).Система булевых функций {f1, f2, ... , fn} называется полной (в P2), если любая булева функцияможет быть записана в виде формулы через функции этой системы.Множество из трех элементарных связок {&, , } является полной системой. При этом оноостается полным, если убрать одну из двух бинарных связок &,  выразив эту связку через другую иотрицание.Теорема. Если система F полна и все ее функции выражаются через функции системы G, то Gтакже полна.Система из одной функции Шеффера {x/y} является полной.

В самом деле , (x/x) = x и (x/y) =x&y4. Теорема Жегалкина о представимости булевой функции полиномом.Система G = {0, 1, x&y, x  y} полна. Таким образом, любая f, представленная в виде формулынад G, после раскрытия скобок выражается в виде полинома по mod 2 (полинома Жегалкина)f ( x1 ,..., xn )   a(i1 ,.., is ) x1...xs, где суммирование производится повсем наборам переменных и по mod 2. Единственность такого представления доказывается подсчетом числа различных полиномов, которое оказывается равным мощности P2.5.

Понятие замкнутого класса. Замкнутость классов.Пусть R  P2. Замыканием [R] класса R называется множество всех функций из P2, представимых в виде формул над R.Очевидно, что R  [R], [[R]] = [R], если R1  R2 , то [R1]  [R2]Замыканием {1, } является класс L линейных функций.R - полный класс  [R] = P2.Класс R называется замкнутым, если [R] = R.Любой класс вида R = [A] замкнут.Класс линейных функций L = [{1, }] замкнут.Через Т0 и Т1 обозначаются классы функций, сохраняющих соответственно константы 0 и 1, т.е. f Т0  f(0,0,...,0)=0 и g  Т1  f(1,1,...,1)=1.

Классы Т0 и Т1 замкнуты.AlecSoft design © 1996Класс S самодвойственных функций (See also п.6) замкнут.Класс M монотонных функций (See also п.7) замкнут.6. Двойственность. Класс самодвойственных функций, его замкнутость.Функция f* = f(x1,..., xn) называется двойственной к f(x1,...,xn). Таблица истинности для f*получается из таблицы истинности для f инвертированием и переворачиванием столбца значений.Очевидно, что двойственными для функций 0, 1 являются соответственно 1, 0; двойственнымидля x, x являются соответственно x, x; двойственными для x & y, x  y являются соответственноx  y, x & y.Принцип двойственности: пусть f(x1,...,xn) представлена в виде формулы С [f1,..,fn] над мн-вомфункций {f1,..,fn}. Тогда формула С* = С [f1*,..,fn*], полученная заменой всех вхождений fi соответственно на fi* представляет функцию f*(x1,...,xn), двойственную к f.Обозначим через S класс всех самодвойственных функций, т.е.

всех булевых функций f = f*. Такие f на противоположных наборах аргументов принимают противоположные значения.Мощность S =2 2n Card ( P2 )Покажем, что класс S замкнут (See also п.5). Поскольку E(x) = x самодвойственна, то достаточнопоказать, что F = f(f1, f2,...,fn) самодвойственна, если только {f ,f1, f2,...,fn}  S. В самом деле, согласно принципу двойственности, заменяя в формуле для F функцию f и каждую из функций fi соответственно на f* = f и fi* = fi, т.е. не изменяя формулу, получаем формулу для функции, двойственной кF.

Таким образом, любая F - композиция самодвойственных - является самодвойственной.7. Класс монотонных функций, его замкнутость.Частичный порядок на множестве двоичных наборов. Пусть =(a1,...,an) и =(b1,...,bn) - наборыиз n битов. Будем писать   , если а1b1 , ... , аnbn.Булева функция f называется монотонной, если для любых наборов    выполняется f() f().

Примеры: x, x & y,x  y.Обозначим через M класс всех монотонных булевых функций.Класс M замкнут (See also п.5). Поскольку E(x) = x монотонна, то достаточно показать, что F =f(f1, f2,...,fn) монотонна, если только {f, f1, f2,...,fn}  M. В самом деле, если   , то в силу монотонности fi имеем f1()  f1(), ... , fn()  fn(). Тогда F()= F(f1(), ... , fn())  F(f1(), ... , fn()) в силумонотонности f. Таким образом, любая F - композиция монотонных - является монотонной.8.

Лемма о несамодвойственной функции.Лемма. Если f = f(x1, ...,xn)  S, то путем подстановки вместо xi либо x, либо x, из нее можнополучить константную (несамодвойственную) функцию g() одной переменной x.В самом деле, поскольку f несамодвойственна, то существует набор  такой, что f() = f().Положим xi = x, если i = 1 , xi = x , если i = 0. Тогда g(0) = f(1,..., n) = f(1,..., n) = g(1).

Таким образом, g - константа.9. Лемма о немонотонной функции.Лемма. Если f = f(x1, ...,xn)  M, то путем подстановки вместо xi либо x, либо константы 0,1, изнее можно получить отрицание (немонотонную функцию) g(x) = x одной переменной x.Будем называть наборы  и  соседними (по i-й координате), если они отличаются только в i-йкоординате.AlecSoft design © 1996В силу немонотонности f найдется пара соседних наборов    таких, что 1 = f() > f() = 0.  =(a1, ...

ai-1, 0, ai+1, ..., an) и  = (a1, ... ai-1, 1, ai+1, ..., an). Рассмотрим функцию g(x) = (a1, ... ai-1, x, ai+1, ...,an). Очевидно , g(0) = f() = 1 и g(1) = f() = 0. Таким образом, g(x) = x.10. Лемма о нелинейной функции.Лемма. Если f = f(x1, ...,xn)  L , то путем подстановки вместо xi либо x(y) либо x(y) либоконстант 0,1, а также, возможно, навешивания отрицания на f, из нее можно получить конъюнкцию(нелинейную функцию) g(x,y) = x&y двух переменных x и y. Рассмотрим полином Жегалкина для f. f ( x1 ,..., xn )   a( i1 ,..,i s )x1 ...