Найти двойственную функцию по принципу двойственности

Предмет: Математическая логика и дискретная математика

Раздел: Логические функции и преобразования

Дано:

Логическая функция записана в виде: \[ f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee x_1 \cdot x_2 \vee \overline{x_1} \cdot x_2 \cdot x_3 \]

Задача:

1. Найти двойственную функцию по принципу двойственности.
2. Найти ДНФ (дизъюнктивную нормальную форму) для двойственной функции.

1. Нахождение двойственной функции

Принцип двойственности заключается в том, чтобы заменить операции и константы следующим образом:

1. Конъюнкцию (логическое умножение, ∧, "·") заменить на дизъюнкцию (логическое сложение, ∨).
2. Дизъюнкцию (логическое сложение, ∨) заменить на конъюнкцию (логическое умножение, ∧).
3. Константу 0 заменить на 1 и наоборот.
4. Все переменные остаются без изменений.

Применим двойственность к данной функции: \[ f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee x_1 \cdot x_2 \vee \overline{x_1} \cdot x_2 \cdot x_3 \]

Заменим каждую операцию по принципу двойственности:

• Конъюнкции (·) превращаются в дизъюнкции (∨), и наоборот.
• Дизъюнкции (∨) превращаются в конъюнкции (·).

Получаем новую функцию: \[ f^*(x_1, x_2, x_3) = (x_2 \vee \overline{x_3}) \cdot (x_1 \vee x_2) \cdot (\overline{x_1} \vee x_2 \vee x_3) \]

Это и есть двойственная функция.

2. Нахождение ДНФ двойственной функции

Теперь найдём дизъюнктивную нормальную форму (ДНФ) для двойственной функции.

Изначально двойственная функция представлена в виде конъюнкции трёх термов: \[ f^*(x_1, x_2, x_3) = (x_2 \vee \overline{x_3}) \cdot (x_1 \vee x_2) \cdot (\overline{x_1} \vee x_2 \vee x_3) \]

Чтобы получить ДНФ, необходимо раскрыть скобки в этой функции, применяя дистрибутивность дизъюнкций относительно конъюнкций.

1. Раскрываем сначала первые две скобки: \[ (x_2 \vee \overline{x_3}) \cdot (x_1 \vee x_2) = (x_2 \cdot x_1 \vee x_2 \cdot x_2 \vee \overline{x_3} \cdot x_1 \vee \overline{x_3} \cdot x_2) \]

   Здесь учтём, что \( x_2 \cdot x_2 = x_2 \), и упрощаем:

   \[ = x_2 \cdot x_1 \vee x_2 \vee \overline{x_3} \cdot x_1 \vee \overline{x_3} \cdot x_2 \]

2. Теперь умножаем эту часть на оставшуюся скобку: \[ (x_2 \cdot x_1 \vee x_2 \vee \overline{x_3} \cdot x_1 \vee \overline{x_3} \cdot x_2) \cdot (\overline{x_1} \vee x_2 \vee x_3) \]

   Распределим каждый член первой части по каждому члену второй части:

   \[ = (x_2 \cdot x_1 \cdot (\overline{x_1} \vee x_2 \vee x_3)) \vee (x_2 \cdot (\overline{x_1} \vee x_2 \vee x_3)) \vee (\overline{x_3} \cdot x_1 \cdot (\overline{x_1} \vee x_2 \vee x_3)) \vee (\overline{x_3} \cdot x_2 \cdot (\overline{x_1} \vee x_2 \vee x_3)) \]

Далее можно раскрыть все скобки и упростить получившиеся выражения, устраняя дубликаты. Но даже в этом виде итоговое выражение уже можно считать ДНФ двойственной функции, так как оно представляет собой дизъюнкцию конъюнкций.