Решение задач: Элементарная конъюнкция и кратчайшая ДНФ

Хорошо, я внимательно изучил предоставленные изображения и готов дать ответы на все задания. --- 18. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если формула является конъюнкцией (быть может одночленной) переменных и отрицаний переменных, она называется 1) элементарной конъюнкцией 2) простой конъюнкцией 3) упрощенной конъюнкцией 4) укороченной конъюнкцией Правильный ответ: **1) элементарной конъюнкцией** --- 19. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если ДНФ булевой функции содержит наименьшее число элементарных конъюнкций по сравнению с другими ДНФ этой же функции она называется 1) кратчайшей ДНФ 2) минимальной ДНФ 3) сокращенной ДНФ 4) наименьшей ДНФ Правильный ответ: **1) кратчайшей ДНФ** --- 20. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Число переменных в элементарной конъюнкции называется 1) длиной 2) рангом 3) константой 4) формулой Правильный ответ: **1) длиной** --- 21. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает 1) сокращенную ДНФ 2) тупиковую ДНФ 3) минимальную ДНФ 4) кратчайшую ДНФ Правильный ответ: **3) минимальную ДНФ** --- 22. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов. Правильные элементарные конъюнкции 1) \(x_1 x_2 \overline{x_3} x_4\) 2) \(x_1 x_2 \overline{x_3} x_5\) 3) \(x_1 x_2 x_3 x_4\) 4) \(x_1 x_2 x_3 x_5\) 5) \(x_1 x_2 x_3 x_4 x_5\) Правильный ответ: **Все варианты 1, 2, 3, 4, 5 являются правильными элементарными конъюнкциями.** (Элементарная конъюнкция - это конъюнкция переменных или их отрицаний. Все представленные варианты соответствуют этому определению.) --- 23. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов. Представление функции одночленной в виде 1) ДНФ 2) КНФ 3) СКНФ 4) СДНФ 5) сокращенной ДНФ 6) тупиковой ДНФ Правильный ответ: **1) ДНФ, 5) сокращенной ДНФ, 6) тупиковой ДНФ.** (Одночленную функцию можно представить в виде ДНФ, которая также является сокращенной и тупиковой ДНФ.) --- 24. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов. Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных \(x_1, x_2, \dots, x_n\) называется 1) ДНФ в которой нет одинаковых ЭК 2) ДНФ в которой нет одинаковых ЭД 3) все ЭК правильны относительно переменных \(x_1, x_2, \dots, x_n\) 4) все ЭД правильны относительно переменных \(x_1, x_2, \dots, x_n\) 5) все ЭД полны относительно переменных \(x_1, x_2, \dots, x_n\) 6) все ЭД, полны относительно переменных \(x_1, x_2, \dots, x_n\), входят в каждой элементарной конъюнкции Правильный ответ: **4) все ЭД правильны относительно переменных \(x_1, x_2, \dots, x_n\)** и **5) все ЭД полны относительно переменных \(x_1, x_2, \dots, x_n\)**. (СКНФ состоит из элементарных дизъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде, и каждая такая дизъюнкция является правильной и полной.) --- 25. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. СКНФ данной функции: \(f = x \rightarrow y\) 1) \((\overline{x} \lor y) (\overline{x} \lor \overline{y})\) 2) \((\overline{x} \lor y) (x \lor y)\) 3) \((\overline{x} \lor y)\) 4) \((\overline{x} \lor y) (x \lor \overline{y})\) Для функции \(f = x \rightarrow y\) (импликация) таблица истинности выглядит так: \(x\) | \(y\) | \(x \rightarrow y\) --- | --- | --- 0 | 0 | 1 0 | 1 | 1 1 | 0 | 0 1 | 1 | 1 СКНФ строится по тем строкам, где функция равна 0. В данном случае это строка \(x=1, y=0\). Для этой строки элементарная дизъюнкция будет \(\overline{x} \lor y\). Таким образом, СКНФ функции \(f = x \rightarrow y\) это \(\overline{x} \lor y\). Правильный ответ: **3) \((\overline{x} \lor y)\)** --- 26. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Многочлен, являющийся суммой констант и различных правильных элементарных конъюнкций, в которых все переменные входят в первой степени называется 1) правильной элементарной конъюнкцией Правильный ответ: **В данном вопросе не хватает вариантов ответа, кроме первого. Однако, исходя из определения, такой многочлен называется полиномом Жегалкина (или полиномом по модулю 2). Если же речь идет о сумме конъюнкций, то это ДНФ. Но формулировка "все переменные входят в первой степени" указывает на полином Жегалкина.** Если бы были другие варианты, возможно, был бы более подходящий. Но из предложенного (только 1) правильной элементарной конъюнкцией) это неверно, так как многочлен - это сумма, а конъюнкция - это произведение. **Предполагая, что вопрос относится к стандартным формам, и если бы был вариант "ДНФ" или "полином Жегалкина", то ответ был бы одним из них. В текущем виде, с единственным вариантом "правильной элементарной конъюнкцией", этот вариант не подходит.** **Если нужно выбрать из того, что есть, и если это вопрос с подвохом или неполный, то я не могу дать однозначно правильный ответ, который бы соответствовал единственному предложенному варианту.** **Однако, если вопрос подразумевает, что многочлен состоит из таких конъюнкций, то сам многочлен не является конъюнкцией. Поэтому вариант 1) не подходит.** ---