Найти СКНФ функции f, заданной столбцом своих значений (0,1,0,0,1,1,0,1)

Решение:

Найдём совершенную конъюнктивную нормальную форму (СКНФ) для функции \( f \), заданной вектором значений \( (0,1,0,0,1,1,0,1) \). Вектор имеет длину 8, что соответствует 3 переменным (\( 2^3 = 8 \)). Переменные будем обозначать \( x_1, x_2, x_3 \).

Соответствие индексов вектора и значений переменных:

• Индекс 0: \( x_1=0, x_2=0, x_3=0 \)
• Индекс 1: \( x_1=0, x_2=0, x_3=1 \)
• Индекс 2: \( x_1=0, x_2=1, x_3=0 \)
• Индекс 3: \( x_1=0, x_2=1, x_3=1 \)
• Индекс 4: \( x_1=1, x_2=0, x_3=0 \)
• Индекс 5: \( x_1=1, x_2=0, x_3=1 \)
• Индекс 6: \( x_1=1, x_2=1, x_3=0 \)
• Индекс 7: \( x_1=1, x_2=1, x_3=1 \)

Функция равна 1 для тех наборов входных переменных, которым соответствуют единицы в векторе значений. Ищем строки, где значение равно 1:

• Индекс 1: \( x_1=0, x_2=0, x_3=1 \) → \( \bar{x}_1 \land \bar{x}_2 \land x_3 \)
• Индекс 3: \( x_1=0, x_2=1, x_3=1 \) → \( \bar{x}_1 \land x_2 \land x_3 \)
• Индекс 5: \( x_1=1, x_2=0, x_3=1 \) → \( x_1 \land \bar{x}_2 \land x_3 \)
• Индекс 7: \( x_1=1, x_2=1, x_3=1 \) → \( x_1 \land x_2 \land x_3 \)

СКНФ — это дизъюнкция (логическое ИЛИ) найденных конъюнкций (логическое И):

\( f(x_1, x_2, x_3) = (\bar{x}_1 \land \bar{x}_2 \land x_3) \lor (\bar{x}_1 \land x_2 \land x_3) \lor (x_1 \land \bar{x}_2 \land x_3) \lor (x_1 \land x_2 \land x_3) \)

Выберите один ответ:

(Предполагается, что варианты ответов были бы представлены ниже)

Ответ: \( (\bar{x}_1 \land \bar{x}_2 \land x_3) \lor (\bar{x}_1 \land x_2 \land x_3) \lor (x_1 \land \bar{x}_2 \land x_3) \lor (x_1 \land x_2 \land x_3) \)