discrete_math

В таблице перечислены некоторые булевы функции от двух аргументов х1 и х2:

g8 (x1, x2 ) x1 | x2 – штрих Шеффера (антиконъюнкция).

С помощью таблицы можно задать булеву функцию от любого числа аргументов. Таблица для функции от n аргументов содержит 2n строк. В каждой строке записан набор значений аргумента длины n из нулей и единиц, а также значение функции на этом наборе. При заполнении строк таблицы будем придерживаться правила: для каждого i = 1,2,3,…,2n набор значений аргумента в i-й строке представляет собой запись числа (i – 1) в двоичной системе счисления. Таким образом, значения самой функции в таблице будут записаны в виде столбца из нулей и единиц высоты 2n. Если этот столбец записать в виде отдельной строки, то получим так называемый векторный способ задания булевой функции. Например, штрих

из нулей и единиц и каждый из них можно рассматривать как вектор, задающий некоторую булеву функцию от n

Карта Карно – это таблица, которая является ещё одним способом задания булевой функции. Каждому набору значений аргументов во внутренней части этой таблице соответствует одна клетка.

21. Существенные и фиктивные переменные булевых функций, основные тождества, эквивалентные преобразования формул.

К числу основных тождеств относятся следующие:

12

(8)x & x x ,

(9)x & x 0 ,

.

.

.

.

.

.

Преобразования, выполненные на основе данных формул, называются эквивалентными.

22. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом неопределенных коэффициентов.

Определение. Полином, в котором отсутствуют произведения переменных, называется линейным полиномом. Линейный полином Жегалкина от n переменных может иметь самое большее n + 1 слагаемых.

Теорема. Каждая булева функция от n переменных представима полиномом Жегалкина от этих же переменных.

или 1.

23. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом эквивалентных преобразований.

Определение. Функция f (x1, x2 ,...,xn ) от n аргументов x1, x2 ,...,xn называется булевой функцией (или функцией алгебры

Определение. Полиномом Жегалкина от переменных x1, x2 ,...,xn называется сумма по модулю 2, в которой каждое

Определение. Полином, в котором отсутствуют произведения переменных, называется линейным полиномом. Линейный полином Жегалкина от n переменных может иметь самое большее n + 1 слагаемых.

Теорема. Каждая булева функция от n переменных представима полиномом Жегалкина от этих же переменных. Разложение методом эквивалентных преобразований. Полином Жегалкина можно построить с помощью эквивалентных преобразований. Для этого необходимо сначала построить ДНФ или КНФ функции, а затем преобразовать получившееся

13

24. Разложение булевых функций в СДНФ и СКНФ.

С помощью СДНФ можно задать любую булеву функцию, кроме тождественного нуля.

С помощью СКНФ можно задать любую булеву функцию, кроме тождественной единицы.

Пример. Функция «голосования» h(x, y, z) (00010111) всегда принимает то значение, которое принимает большинство её

25. Минимизация ДНФ и КНФ методом эквивалентных преобразований.

С помощью СДНФ можно задать любую булеву функцию, кроме тождественного нуля.

С помощью СКНФ можно задать любую булеву функцию, кроме тождественной единицы.

Утверждение. ДНФ и КНФ отличаются от СДНФ и СКНФ тем, что в них не все переменные обязательно входят в каждое слагаемое (множитель).

14

СКНФ функции «голосования» можно привести к более простой конъюнктивной форме, состоящей из трех множителей:

(x y)( x z)( y z) .

26. Минимизация ДНФ и КНФ с помощью карт Карно.

Карта Карно – это таблица, которая является ещё одним способом задания булевой функции. Каждому набору значений аргументов во внутренней части этой таблице соответствует одна клетка.

Карта Карно для функции f(x,y,z) = (00110001) представлена на рисунке.

наборе (010), ему соответствует клетка, содержащая единицу и стоящая на пересечении второго столбца и первой строки карты Карно (на рисунке эта клетка

закрашена). Однако, если две соседние клетки, отвечающие наборам (010) и (011), объединить в прямоугольник, то в СДНФ дизъюнкцию первых двух слагаемых можно будет заменить одним слагаемым xy . В результате получаем более простую

покрывающие фигуры – это квадраты или прямоугольники, каждый из которых стоит из 1, 2, 4 или 8 клеток;

фигуры могут пересекаться, но их количество должно быть минимально возможным (т.е. чем меньше разных фигур используется, тем проще получается ДНФ);

если одна фигура содержится внутри другой, то меньшую фигуру нельзя использовать для покрытия области единиц (т.е. чем крупнее используемые фигуры, тем проще ДНФ).

Чтобы получить минимальную КНФ, надо найти покрытие области нулей функции в карте Карно, используя те же правила для выбора покрывающих фигур.

27. Замкнутые классы булевых функций Т0, Т1, L, лемма о нелинейной функции.

Определение. Функция f (x1, x2 ,...,xn ) от n аргументов x1, x2 ,...,xn называется булевой функцией (или функцией алгебры

Определение. Класс К булевых функций называется замкнутым классом, если любая суперпозиция функций из этого класса сама принадлежит классу К.

28. Замкнутые классы булевых функций S и М, леммы о несамодвойственной и немонотонной функции.

Определение. Функция f (x1, x2 ,...,xn ) от n аргументов x1, x2 ,...,xn называется булевой функцией (или функцией алгебры

Определение. Класс К булевых функций называется замкнутым классом, если любая суперпозиция функций из этого класса сама принадлежит классу К.

самодвойственной функции следует, что на противоположных наборах она принимает противоположные значения. Класс

29. Полная система функций, теорема о двух системах булевых функций.

Определение. Система F булевых функций называется полной системой, если [F] = Р2, т.е. любую булеву функцию можно задать формулой через функции системы F.

Лемма. Пусть имеются две системы функций F и G, причем система F полна, и каждая функция из этой системы выражается в виде формулы через функции системы G. Тогда G – полная система.

16

30. Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.

Определение. Замыканием системы F булевых функций называется множество всех функций, представимых в виде формул через функции множества F. Замыкание F будем обозначать через [F].

Определение. Система F булевых функций называется полной системой, если [F] = Р2, т.е. любую булеву функцию можно задать формулой через функции системы F.

Теорема. Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из пяти классов Т0, Т1, S, M и L.

Пример. Система, состоящая из одной только функции штрих Шеффера f (x, y) x | y , является полной, поскольку она не

принадлежит ни одному из пяти классов Т0, Т1, S, M и L. В то же время система всех булевых функций от одного аргумента {0,1,x, x } неполна, так как все эти функции линейны. Из теоремы о полноте следует, что любой неполный замкнутый класс целиком содержится хотя бы в одном из пяти классов Т0, Т1, S, M и L, так как если бы некоторый неполный замкнутый класс не лежал целиком ни в одном из классов Т0, Т1, S, M и L, то он образовывал бы полную систему. Таким образом, классы Т0, Т1, S, M и L в некотором смысле являются максимальными во множестве Р2 неполными замкнутыми классами.

Определение. Класс булевых функций K называется предполным классом, если сам он не образует полной системы, но для любой булевой функции f K система { f } K полна.

из неё любой функции оставшаяся система будет неполна.

31. Схемы из функциональных элементов, правила построения и функционирования, метод синтеза СФЭ, основанный на СДНФ и СКНФ.

Определение. Функциональный элемент – это математическая модель элементарного дискретного преобразователя, который по определенному закону осуществляет преобразование поступающих ему на вход сигналов в сигнал на выходе преобразователя. Из функциональных элементов с помощью некоторых правил можно строить более сложные по структуре и функционированию модели – схемы из функциональных элементов. В этих моделях входные и выходные сигналы кодируются символами 0 и 1.

Правила построения. Для получения сложных СФЭ из более простых к ним последовательно применяются операции расщепления входа или выхода схемы, присоединения функционального элемента к схеме и подключения функционального элемента ко входу или выходу схемы. Эти операции напоминают правила получения сложной формулы из более простых с помощью суперпозиции.

Синтез СФЭ. Поскольку дизъюнкция, конъюнкция и отрицание образуют полную систему в классе Р2, то любую булеву функцию от n аргументов можно реализовать схемой из функциональных элементов – дизъюнкторов, конъюнкторов и инверторов – с n входами и одним выходом. Для этого можно, например, выразить данную булеву функцию через СДНФ или СКНФ и затем «синтезировать» полученную формулу в виде схемы из функциональных элементов, последовательно применяя перечисленные выше операции расщепления, присоединения и подключения.

32. Метод синтеза СФЭ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.

Определение. Функциональный элемент – это математическая модель элементарного дискретного преобразователя, который по определенному закону осуществляет преобразование поступающих ему на вход сигналов в сигнал на выходе преобразователя. Из функциональных элементов с помощью некоторых правил можно строить более сложные по структуре и функционированию модели – схемы из функциональных элементов. В этих моделях входные и выходные сигналы кодируются символами 0 и 1.

Метод синтеза СФЭ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника. Данный метод также основывается на представлении функции в виде СДНФ, но позволяет строить менее сложные схемы за счет более компактной реализации конъюнкций. Разложение функции в СДНФ может содержать конъюнкции, имеющие общие множители. Если две таких конъюнкции реализовать одной подсхемой в блоке K , то для

этого потребуется конъюнкторов хотя бы на единицу меньше, чем их требовалось прежде, при независимой реализации всех конъюнкций первым методом синтеза. Компактной реализации всех возможных конъюнкций длины n можно добиться с

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

многополюсника n , которые соответствуют конъюнкциям, входящим в СДНФ функций заданной системы. Это позволило бы обойтись меньшим количеством конъюнкторов, чем если бы каждую функцию заданной системы независимо реализовали своей собственной подсхемой.

Если схема из функциональных элементов Σ содержит ровно r функциональных элементов, то говорят, что она имеет сложность r и записывают это в виде равенства L(Σ) = r.

Элементы комбинаторики

33. Основные комбинаторные операции, сочетания и размещения (с возвращением и без возвращения элементов).

Определение. Выборка – это простейшая комбинаторная операция, применяемая к заданному множеству и состоящая в том, что из этого множества выбирается произвольный элемент. Если выбранный элемент удаляют из исходного множества, то такую операцию называют выборкой без возвращения. Если же элемент остается в исходном множестве, то такая выборка называется выборкой с возвращением.

Определение. Повторная выборка k элементов из n-элементного множества без возвращения и без упорядочения называется сочетанием из n по k.

Определение. Повторная выборка k элементов из n-элементного множества без возвращения, но с упорядочением, называется размещением из n по k.

18

34. Комбинаторные принципы сложения, умножения, дополнения, включения-исключения.

Комбинаторный принцип сложения. Суть этого метода в следующем: пусть требуется вычислить количество элементов в некотором множестве В. Если данное множество можно разбить на несколько непересекающихся подмножеств В1, В2, …, Вm и найти их мощности, то число элементов во множестве В можно получить сложением мощностей подмножеств В1, В2, …,

первый элемент взят из множества А, а второй элемент – из множества В.

Комбинаторный принцип включения – исключения является обобщением принципа сложения. Он применяется даже тогда, когда принцип сложения не работает, а именно, если исходное множество является объединением двух и более пересекающихся подмножеств. В самом простом виде принцип включения – исключения основывается на очевидном

соотношении A B AB A B . Также имеет место равенство: A B C ABC A B A CB C A B C

35. Биномиальные коэффициенты, их свойства, бином Ньютона.

Биномиальные коэффициенты обладают многими свойствами, среди которых наиболее важными являются следующие:

36. Треугольник Паскаля, полиномиальная формула.

с биномом Ньютона (x + y)n. Для любого натурального n выполняется равенство:

Треугольник Паскаля.

вершину. Эта симметричность выражается в том, что совпадают элементы, стоящие в одном ряду на одинаковом расстоянии

вариантов упорядоченного разбиения n-элементного множества на k непересекающихся подмножеств мощности n1, n2, n3,…, nk. При k = 2 равенство обращается в формулу для бинома Ньютона.

Пример. Требуется вычислить коэффициент при с17 после раскрытия скобок в выражении (1+2с – с3)10.