Что такое ДНФ? Дизъюнктивная нормальная форма (ДНФ) — это ИЛИ (дизъюнкция) наборов И (конъюнкций) переменных или их отрицаний. Пример:

(x1∧¬x2)∨(x2∧x3)(x_1 land lnot x_2) lor (x_2 land x_3)(x1​∧¬x2​)∨(x2​∧x3​)

Цель минимизации Из всех возможных ДНФ для функции найти такую, которая:

имеет наименьшее количество конъюнктов и/или

каждая конъюнкция имеет наименьшее количество литералов (переменных или их отрицаний).

Общий алгоритм минимизации ДНФ: 1. Построение полной ДНФ Полная ДНФ (совершенная ДНФ) — это запись, где каждый элементарный конъюнкт соответствует одному набору переменных, на котором функция равна 1.

Как построить:

Строим таблицу истинности для функции.

Находим все строки, где функция равна 1.

Для каждой строки записываем конъюнкцию:

Переменная входит без отрицания, если её значение в строке — 1;

Переменная входит с отрицанием, если её значение — 0.

Все