Дискретная математика

Томский государственный университет систем управления и радиоэлектроники, 2003, 120с.Часть 1 Теория множеств Булева алгебра.Изложены основные сведения из теории множеств: алгебра множеств, бинарныеотношения, бесконечные множества, теория нечётких множеств. Из булевой алгебрыпредставлены разделы: минимизация булевых функций в дизъюнктивных и конъюнктивныхнормальных формах с учётом неопределенных состояний, булевы уравнения, первые сведения о булевом дифференциальном исчислении. Во второй части освещены темы: теория конечных автоматов — синтез логических (комбинационных) и многотактных схем, теорема Поста о функциональной полноте; комбинаторика — размещения, сочетания и перестановки с повторениями и без повторений, разбиение множеств и др.; теория графов — графы и ориентированные графы, сети, деревья и др., а также приведены контрольные работы по всему курсу дискретной математики. В первой части более 1500 упражнений, во второй — более 2000.Все упражнения закодированы, что обеспечивает возможность работы с пособием в режимеавтоматизированного самоконтроля с применением устройств СИМВОЛ или их компьютерныханалогов (разработки Томского государственного университета систем управления ирадиоэлектроники).Для студентов технических специальностей вузов и техникумов, школьников старшихклассов общеобразовательных школ и для всех желающих самостоятельно пройти вводный курс прикладной дискретной математики.СодержаниеТЕОРИЯ МНОЖЕСТВАлгебра множествМножества ПодмножестваДиаграммы Венна. Универсальное множество Объединение множеств Пересечение множеств Дополнение множеств Законы де МорганаРазность множествСимметрическая разность множествЗакон поглощенияЗакон склеиванияТеоретико-множественные преобразованияБинарные отношенияДекартово произведение множествСтепень множества Понятие бинарного отношенияСимметрия отношенийТранзитивность отношенийРефлексивность отношений Отношения эквивалентностиОтношения строгого порядкаОтношения нестрогого порядкаУпорядоченные множестваОтношения соответствияФункциональные отношения. ОтображенияРеляционная алгебраБесконечные множестваВводные замечанияСравнение бесконечных множествСчетные множестваНесчетные множестваГипотеза континуума Трансцендентные числа.Об эквивалентности множеств точек геометрических объектовТрансфинитные числаПарадоксы теории множествУпражнения на тему «Парадоксы теории множеств» Элементы теории нечетких множествВводные замечанияНечеткие множестваОбъединение нечетких множеств Пересечение нечетких множествДополнение нечеткого множестваРазность и симметрическая разность нечетких множествОсновные свойства операций над нечеткими множествамиБУЛЕВА АЛГЕБРАДвоичные числаПонятие высказывания Аксиомы булевой алгебрыСвойства дизъюнкции и конъюнкции Теоремы одной переменнойДизъюнктивные и конъюнктивные формыТеоремы поглощения, склеивания и де МорганаИнвертирование сложных выражений Дизъюнктивные формы булевых функцийПонятие булевой функцииКак задать булеву функциюМинтермыСовершенная дизъюнктивная нормальная формаТеорема разложения для ДНФКарта ВейчаНанесение функций на карту Вейча Нахождение СДНФ при помощи карт Вейча Алгебраическое упрощение булевых функцийПонятие импликанты Метод КвайнаНахождение простых импликант по карте ВейчаМетод ПетрикаМинимизация булевых функций при помощи карт Вейча Конъюнктивные формы булевых функций Основной способ нахождения КНФМакстермы Совершенная конъюнктивная нормальная формаТеорема разложения для КНФНахождение сокращенных КНФНахождение тупиковых и минимальных КНФПеревод функций из КНФ в ДНФНеполностью определенные булевы функции Понятие неполностью определенной булевой функции СДНФ неполностью определенных функций СКНФ неполностью определенных функцийМинимизация ДНФ неполностью определенных функций Минимизация КНФ неполностью определенных функций Формы высших порядковПонятие порядка булевой функцииГраф-схема булевой функцииАбсолютно минимальные формыПовышение порядка булевых функций Классификация форм булевых функцийО классификации форм высших порядковСимметрические булевы функции Понятие симметрической функцииСпособы представления симметрических функцийОперации над симметрическими функциямиРазложение симметрических функций для ДНФРазложение симметрических функций для КНФОбщий случай симметрии функцийЧисловое представление булевых функцийПонятие изображающего числа булевой функции Операции над изображающими числамиИзображающие числа функций высших порядковВосстановление булевой функции по изображающему числуЧисловое представление систем булевых функцийЗависимость и независимость булевых функцийВиды зависимости между двумя функциямиНахождение явного вида логической зависимости Булевы уравненияУравнения с одной неизвестной переменнойУравнения с несколькими неизвестными переменнымиУравнения конъюнктивного типаУравнения дизъюнктивного типаДругие типы булевых уравнений Булевы уравнения с несколькими неизвестными функциямиЕщё раз о формах высших порядков Неразрешимые уравненияПороговые функцииОсновные понятия Функции, определяемые порогом при неизменных весахТеоремы о пороговых функцияхНахождение пороговых функцийМажоритарные функцииСимметрические мажоритарные функцииБулево дифференциальное исчислениеАксиомы алгебры ЖегалкинаПеревод булевых выражений в алгебру Жегалкина и наоборот Применение карт Вейча в алгебре ЖегалкинаПонятие производной от булевой функцииПроизводная первого порядкаДифференцирование булевых функций с применением карт ВейчаСмешанные производные Теоремы о разложении булевых функцийРазложение булевых функций в ряд Тейлора Нахождение отдельных конъюнкций ряда ТейлораЛитература