Составить СКНФ логической функции на основе таблицы истинности

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

Раздел: Булева алгебра, нормальные формы логических функций

Задача состоит в том, чтобы составить СКНФ (совокупная конъюнктивная нормальная форма) логической функции на основе таблицы истинности. Вот данная таблица истинности:

Алгоритм для построения СКНФ:

1. СКНФ строится как конъюнкция (логическое И) дизъюнкций (логическое ИЛИ).
2. Мы берем только те строки, в которых функция \( f \) равна 0.
3. Для каждой такой строки строится дизъюнкция переменных, причем если переменная равна 1 — мы берем её в исходном виде, а если 0 — то с отрицанием (инверсией).
4. Затем дизъюнкции объединяются в конъюнкцию.

Шаг 1: Найдем строки из таблицы, где значение функции \( f = 0 \).

Это строки:

1. \( a = 0, b = 0, f = 0 \)
2. \( a = 1, b = 0, f = 0 \)

Шаг 2: Построим выражение для каждой строки.

Для строки 1: \( a = 0, b = 0 \) - По правилам построения, переменные \( a \) и \( b \) с инверсией:

\[ \overline{a} \lor \overline{b} \]

Для строки 2: \( a = 1, b = 0 \) - Здесь \( a \) в прямом виде, а \( b \) снова с инверсией:

\[ a \lor \overline{b} \]

Шаг 3: Построим конъюнкцию этих дизъюнкций.

\[ (\overline{a} \lor \overline{b}) \land (a \lor \overline{b}) \]

Окончательное решение: СКНФ функции:

\[ (\overline{a} \lor \overline{b}) \land (a \lor \overline{b}) \]

Пояснение: Мы выбрали строки, где результат функции \( f \) равен 0. Далее для каждой строки составили дизъюнкцию переменных, и инвертировали те, что равны 0. После этого собрали результат в конъюнкцию этих дизъюнкций.