|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Элементы Булевой алгебры и булевы функцииОсновы теории множеств n Основные понятия теории множеств и способы их задания. Парадокс Рассела. Операции над множествами: объединение, пересечение, разность и симметрическая разность, дополнение. Свойства операций и принцип двойственности (правила Моргана). n Сравнение множеств. Диаграммы Эйлера-Венна. Разбиения и покрытия: принцип Гейне-Бореля-Лебега – лемма «о конечном подпокрытии». Алгебра подмножеств: булеан и универсум, счетные множества и их свойства. Несчетные множества и множества «мощности континуума». Теорема Кантора. n Отношения. Упорядоченные пары. Прямое произведение множеств, бинарные отношения (обратное, дополнение, тождественное, универсальное). Композиция и степень отношений, ядро отношения. Свойства отношений. n Функции: определения, инъекция, сюръекция, биекция. Композиция (суперпозиция или сложная функция), индуцированная функция. n Отношения эквивалентности: классы эквивалентности и фактормножества. Ядро функции. n Отношения порядка: минимальные элементы, частичный и линейный порядок. n Замыкание отношений: замыкание отношения относительно свойства, транзитивное и рефлексивное транзитивное замыкания. Алгоритм Уоршалла. Элементы Булевой алгебры и булевы функции n Элементарные булевы функции: существенные и несущественные переменные и переключательные функции (ПФ). ПФ одной переменной (нуль, тождественная, отрицание, единица). ПФ двух переменных (нуль, конъюнкция, сложение по модулю 2, дизъюнкция, стрелка Пирса, эквивалентность, импликация, штрих Шеффера и единица). Их таблицы истинности. n Реализация функций формулами. Равносильные формулы. Закон (теорема) поглощения и принцип двойственности (теорема Моргана). n Нормальные формы: теоремы «о разложении булевой функции по переменным» и «о единственности существования совершенной дизъюнктивной нормальной формы (СДНФ) для любой кроме нуля, булевой функции». Конъюнктивные нормальные формы (КНФ) и теорема «о единственности существования совершенной конъюнктивной нормальной формы (СКНФ) для любой, кроме единицы, булевой функции». n Эквивалентные преобразования в СДНФ: элиминация операций (замена на операции &, V, not), протаскивание отрицаний, раскрытие скобок, правило склеивания/расщепления, сортировка. n Нахождение совершенных, сокращенных и минимальных ДНФ: геометрическая интерпретация ДНФ, методы построения сокращенных ДНФ, метод Блейка. n Нахождение минимальных ДНФ через тупиковые ДНФ. Способы построения тупиковых ДНФ. n Локальные алгоритмы упрощения произвольных ДНФ. Теорема и алгоритм Квайна. n Замкнутые классы. Некоторые замкнутые классы: самодвойственные, линейные, монотонные функции. Функции, сохраняющие 1. Функции, сохраняющие 0. n Полные системы булевых функций. Примеры полных систем и представление БФ полиномом Жегалкина в базисе {0, 1, &,+}. Теорема Поста. n Карты Карно. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |