- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
§ 5. Полнота. Примеры полных систем
Выше было показано, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , x1x2, x1x2. Оказывается, что таким свойством обладают и некоторые другие системы элементарных функций.
Система функций {f1, f2,..., fk} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.
Примеры. Системы P2 множество всех булевых функций и 2={, x1x2, x1x2}.
Теорема 1.3. Пусть даны две системы функций из P2: F={f1, f2,...} и G={g1,g2,...}, относительно которых известно, что система F полна и каждая ее функция выражается в виде формулы через функции системы G. Тогда система G также является полной.
Пусть h произвольная функция из P2. Т.к. система F полная, можно выразить h формулой над F, то есть h=c(f1, f2,...). По условию f1=c1(g1,g2,...), f2=c2(g1,g2,...), ... Поэтому в формуле c(f1, f2,...) можно исключить вхождения функций f1, f2,..., заменив их функциями из G:
h=c(f1, f2,...)=c(c1(g1,g2,...), c2(g1,g2,...), ...)= c’(g1,g2,...).
Таким образом, произвольную формулу h удалось выразить через функции системы G, что доказывает полноту этой системы.
Опираясь на теорему 1.3, можно установить полноту еще ряда систем.
3. Система 3={,x1x2} является полной. В качестве полной системы выберем 2={,x1x2,x1x2} (см. п. 2). В соответствии с законом де Моргана, x1x2=.
4. Система 4={,x1x2} является полной. Аналогично п. 3 с помощью закона де Моргана выражаем конъюнкцию через дизъюнкцию и отрицание: x1x2=.
5. Система 5={x1x2}, состоящая из одной функции стрелки Пирса, является полной. В качестве полной выберем систему 3={,x1x2}. Затем, =xx и x1x2=(x1x1)(x2x2).
6. Система 6={x1|x2}, состоящая только из одной функции штриха Шеффера, является полной. За полную возьмем систему 4={,x1x2}. Затем, =x|x и x1x2=(x1|x1)|(x2|x2).
7. Система 7={1,x1x2,x1x2} является полной. За полную возьмем систему 3={,x1x2}. Отрицание выразим через константу 1 и сложение по модулю 2: =x1.
Формула, построенная из констант 0 и 1 и функций x1x2 и x1x2 после раскрытия скобок и несложных алгебраических преобразований переходит в полином по модулю 2, который называют полиномом И.И.Жегалкина.
Пример. Общий вид полинома Жегалкина для функции трех переменных следующий:
f(x1,x2, x3)=a123x1x2x3 a12x1x2 a13x1x3 a23x2x3 a1x1 a2x2 a3x3 a0 ,
где a123, a12, ..., a0 коэффициенты полинома, каждый из которых может принимать одно из двух значений 0 или 1.
Теорема 1.4 (Жегалкина). Каждая функция из P2 может быть выражена при помощи полинома по модулю 2.
Подсчитаем общее число различных полиномов Жегалкина от n переменных. Число m различных конъюнкций равно количеству подмножеств (i1,i2,...,ik) множества {1,2...,n}, то есть m=2n ( соответствует a0). Каждая конъюнкция имеет коэффициент a..., который можно выбрать двумя способами (0 либо 1). В соответствии с правилом произведения число различных полиномов от n переменных, которые можно образовать из этих конъюнкций, равно 2m=(пустому подмножеству конъюнкций соответствует полином 0).
Таким образом, число всех полиномов Жегалкина от n переменных равно числу всех булевых функций от тех же переменных. Отсюда, как следствие, получаем единственность представления функций посредством полиномов Жегалкина.
Пример. Выразить x1|x2 в виде полинома Жегалкина. Ответ. x1|x2 = x1x21.