Дискретная математика. Часть 2

Лекция 3 по дискретной математики 02.03.2021 Этот файл следует смотреть в текстовом редакторе с моноширинным шрифтом, таким как Consolas. Это нужно для выравнивания колонок, чтобы схемы и таблицы отображались правильно. На лекции 3 рассматривались разделы 8.2, 8.3, 8.4 и 5.1 из учебника Алексеева. Напоминание Сложность L(S) схемы S — это число функциональных элементов в S. L(f) = min по схемам, которые реализуют f от сложности каждой схемы. L(n) = max по всевозможным функциям от n аргументов. Для каждой функции f(x1, ..., xn) определяется L(f), и от этих чисел берется максимум. Пусть L1(f) есть сложность схемы, построенной по СДНФ для функции f. Такая схема есть лишь одна из схем, реализующих f, поэтому L(f) <= L1(f). L1(n) определяется аналогично L(n), то есть это максимум L1(f) по всем функциям f от n аргументов. Таким образом, L1(n) функциональных элементов достаточно для реализации любой функции от n аргументов по ее СДНФ. На с. 121. находится верхняя оценка для L1(n). Было показано, что L1(n) <= n(s + 1) - 1, где s есть количество элементарных конъюнкций в СДНФ, то есть количество 1 в кортеже значений функции от n аргументов. Таким образом, s <= 2^n, но на самом деле достаточно положить s <= 2^n - 1, потому что функцию с 2^n единицами, то есть функцию, тождественно равную 1, можно реализовать всего двумя функциональными элементами. Подставляя s <= 2^n - 1 в L1(n) <= n(s + 1) - 1, получаем L1(n) <= n*2^n - 1. Пусть L2(f) есть сложность схемы, построенной для функции f с помощью теоремы о разложении. Этот метод описан на прошлой лекции. Это тоже лишь одна из схем, реализующих f, поэтому L(f) <= L2(f). L2(n) определяется аналогично L(n), то есть это максимум L2(f) по всем функциям f от n аргументов. Таким образом, L2(n) функциональных элементов достаточно для реализации любой функции от n аргументов с помощью теоремы о разложении. На с. 123 показано, что L2(n) удовлетворяет рекуррентному уравнению L2(n) = 2*L2(n-1) + 4 с начальным условием L2(1) = 2. В разделе 4.2 показано, что неоднородное рекуррентное уравнение первого порядка x(n) = a*x(n-1) + b с начальным условием x(0) = x0 имеет решение x(n) = a^n(x0 - b/(1-a)) + b/(1-a). Если вместо x0 известно x(1) = x1, то из решения уравнения следует, что x(n) = a^(n-1)(x1 - b/(1-a)) + b/(1-a). В случае L2 имеем a = 2, b = 4, x1 = 2. Поэтому L2(n) = 2^(n-1)(2 - 4/(-1)) + 4/(-1) = 2^(n-1)*6 - 4 = 3*2^n - 4. **************************************** С. 124 m(x, y, z) = xy \/ xz \/ yz. Это функция большинства: она принимает значение большинства из своих аргументов. Упражнения 1. Показать, что m(x, y, z) = xy ⨁ xz ⨁ yz. 2. Показать, что функция m самодвойственна. 1011 = 11 +0101 = 5 ----10000 16 x ⨁ y = x(~y) \/ (~x)y = (x \/ y)(~x \/ ~y) = (x \/ y)(~(xy))