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

Любая булева функция однозначно определяется множеством наборов, на которых она принимает единичное значение. Множество таких наборов обозначим Nf. Это множество можно интерпретировать как множество вершин n-мерного куба, где n-количество переменных данной функции.

25. Содержание

    • Множества. Основные понятия.
    • Операции над множествами и их свойства.
    • Декартово произведение. Разбиение множеств.
    • Алгебра множеств
    • Отношение. Бинарное отношение
    • Алгебра бинарных отношений
    • Отображение. Виды отображений
    • Отношение порядка. Изоморфизм упорядоченных множеств.
    • Алгебраические системы. Изоморфизм алгебраических систем.
    • Функции алгебры логики.
    • Формулы. Реализация функций формулами.
    • Эквивалентность формул. Свойства элементарных булевых функций.
    • Двойственные функции. Принцип двойственности
    • Разложение булевых функций по переменным. Сднф.
    • Полнота и замкнутость.
    • Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
    • Классы т0, т1.
    • Класс s.
    • Класс м.
    • Класс l
    • Теорема о функциональной полноте. Проверка системы функций на полноту.
    • Задача минимизации булевых функций.
    • Задача минимизации булевых функций в геометрической постановке.
    • Сокращенные днф.
    • Тупиковые днф и решение задачи минимизации.
    • Графы. Основные понятия.
    • Орграфы. Основные понятия.
    • Маршруты. Цепи. Циклы. Связность.
    • Операции над графами