Сокращенные днф.

Алгоритм построения сокращенных ДНФ.

1)Находим произвольную КНФ, реализующую ф-ю f(можно взять СКНФ)

2)Перемножаем элементы дизъюнкции и переходим в ДНФ

3)упрощаем полученую ДНФ, используя

x*x=x

xVx=x

x*x=0

xVx=1

xVxy=x

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

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