FAQ (793784)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 ...

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы