Решение задачи: Находим правильный ответ

Хорошо, давайте разберем каждое задание по порядку. Задание 18. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если формула является конъюнкцией (быть может одночленной) переменных и отрицаний переменных, она называется 1) элементарной конъюнкцией 2) простой конъюнкцией 3) упрощенной конъюнкцией 4) минимизированной конъюнкцией Правильный ответ: Формула, представляющая собой конъюнкцию (логическое И) переменных или их отрицаний, называется элементарной конъюнкцией. Например, \(x_1 \land \neg x_2 \land x_3\). 1) элементарной конъюнкцией Задание 19. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если ДНФ булевой функции содержит наименьшее число элементарных конъюнкций по сравнению с другими ДНФ этой же функции она называется 1) кратчайшей ДНФ 2) минимальной ДНФ 3) сокращенной ДНФ 4) наименьшей ДНФ Правильный ответ: ДНФ (дизъюнктивная нормальная форма), которая содержит наименьшее число элементарных конъюнкций для данной булевой функции, называется кратчайшей ДНФ. 1) кратчайшей ДНФ Задание 20. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Число переменных в элементарной конъюнкции называется 1) длиной 2) рангом 3) константой 4) формулой Правильный ответ: Число переменных (или литералов) в элементарной конъюнкции называется её длиной. Например, длина конъюнкции \(x_1 \land \neg x_2 \land x_3\) равна 3. 1) длиной Задание 21. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает 1) сокращенную ДНФ 2) тупиковую ДНФ 3) минимальную ДНФ 4) кратчайшую ДНФ Правильный ответ: Минимальная ДНФ - это тупиковая ДНФ, которая имеет наименьшее число вхождений переменных (литералов). 3) минимальную ДНФ Задание 22. Из предлагаемого перечня вариантов ответа обведите кружком номера ответов. Правильные элементарные конъюнкции 1) \(x_1 x_2 \neg x_1\) 2) \(x_1 x_2 x_3\) 3) \(x_1 x_2 \neg x_3 x_5\) 4) \(x_1 x_2 x_3 x_5\) 5) \(x_1 x_2 x_3 x_5 x_7\) Правильный ответ: Элементарная конъюнкция - это конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза (либо в прямом, либо в инверсном виде). 1) \(x_1 x_2 \neg x_1\). Здесь переменная \(x_1\) встречается и в прямом, и в инверсном виде. Такая конъюнкция всегда ложна (\(x_1 \land \neg x_1 \equiv 0\)) и не является правильной элементарной конъюнкцией в стандартном смысле. 2) \(x_1 x_2 x_3\). Это правильная элементарная конъюнкция. 3) \(x_1 x_2 \neg x_3 x_5\). Это правильная элементарная конъюнкция. 4) \(x_1 x_2 x_3 x_5\). Это правильная элементарная конъюнкция. 5) \(x_1 x_2 x_3 x_5 x_7\). Это правильная элементарная конъюнкция. Таким образом, правильные элементарные конъюнкции: 2) \(x_1 x_2 x_3\) 3) \(x_1 x_2 \neg x_3 x_5\) 4) \(x_1 x_2 x_3 x_5\) 5) \(x_1 x_2 x_3 x_5 x_7\) Задание 23. Из предлагаемого перечня вариантов ответа обведите кружком номера ответов. Представление функции однозначно в виде 1) ДНФ 2) КНФ 3) СКНФ 4) СДНФ 5) сокращенной ДНФ 6) тупиковой ДНФ Правильный ответ: Среди нормальных форм, только совершенные нормальные формы (СДНФ и СКНФ) являются однозначными представлениями булевой функции. Это означает, что для каждой булевой функции существует единственная СДНФ и единственная СКНФ. 4) СДНФ 3) СКНФ Задание 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\) Правильный ответ: Совершенная конъюнктивная нормальная форма (СКНФ) - это конъюнкция элементарных дизъюнкций (ЭД), каждая из которых содержит все переменные функции (либо в прямом, либо в инверсном виде) ровно по одному разу. Такие ЭД называются полными. Таким образом, правильные утверждения: 5) все ЭД полны относительно переменных \(x_1, x_2, \dots, x_n\) 6) все ЭД, полны относительно переменных \(x_1, x_2, \dots, x_n\) (Утверждения 5 и 6 повторяются, но оба верны). Задание 25. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. СКНФ данной функции: \(f = \neg x \rightarrow y\) 1) \((\neg x \lor y) (\neg x \lor y)\) 2) \((\neg x \lor y) (x \lor y)\) 3) \((\neg x \lor y) (x \lor \neg y)\) 4) \((\neg x \lor y)\) 5) \((\neg x \lor y) (x \lor y)\) Правильный ответ: Сначала упростим функцию \(f = \neg x \rightarrow y\). Как мы уже знаем, импликация \(\neg A \rightarrow B\) эквивалентна \(A \lor B\). Значит, \(f = \neg x \rightarrow y \equiv x \lor y\). Теперь нам нужно найти СКНФ для \(f = x \lor y\). СКНФ строится из тех наборов переменных, на которых функция принимает значение 0. Таблица истинности для \(x \lor y\): x | y | \(x \lor y\) --|---|--------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1 Функция \(x \lor y\) принимает значение 0 только при \(x=0, y=0\). Для этого набора \((0,0)\) соответствующая элементарная дизъюнкция в СКНФ будет \((x \lor y)\) (поскольку для 0 берем переменную, для 1 - ее отрицание). Таким образом, СКНФ для \(x \lor y\) является \((x \lor y)\). Теперь посмотрим на варианты: 1) \((\neg x \lor y) (\neg x \lor y)\) - это \(\neg x \lor y\). Неверно. 2) \((\neg x \lor y) (x \lor y)\) - неверно. 3) \((\neg x \lor y) (x \lor \neg y)\) - неверно. 4) \((\neg x \lor y)\) - это исходная функция, но не ее СКНФ. 5) \((\neg x \lor y) (x \lor y)\) - неверно. Похоже, в вариантах ответа есть ошибка или недопонимание. Если \(f = \neg x \rightarrow y\), то \(f \equiv x \lor y\). СКНФ для \(x \lor y\) - это \((x \lor y)\). Ни один из вариантов не соответствует \((x \lor y)\). Вариант 4) \((\neg x \lor y)\) - это просто исходная функция, записанная в виде дизъюнкции. Но это не СКНФ, так как СКНФ должна быть конъюнкцией полных элементарных дизъюнкций. Если \(f = \neg x \rightarrow y\), то это уже элементарная дизъюнкция \(x \lor y\). Если функция уже является элементарной дизъюнкцией, которая содержит все переменные, то она сама и является своей СКНФ. В данном случае \(x \lor y\) является элементарной дизъюнкцией, содержащей все переменные \(x\) и \(y\). Значит, СКНФ для \(f = x \lor y\) является \((x \lor y)\). Среди предложенных вариантов нет \((x \lor y)\). Вариант 4) \((\neg x \lor y)\) - это исходная функция, но не ее СКНФ. Если бы функция была \(f = x \land y\), то СКНФ была бы \((x \lor y) \land (x \lor \neg y) \land (\neg x \lor y)\). Давайте еще раз проверим. \(f = \neg x \rightarrow y\). Таблица истинности: x | y | \(\neg x\) | \(\neg x \rightarrow y\) --|---|-------|----------------- 0 | 0 | 1 | 0 0 | 1 | 1 | 1 1 | 0 | 0 | 1 1 | 1 | 0 | 1 Функция равна 0 только при \(x=0, y=0\). Для СКНФ мы берем дизъюнкцию переменных, соответствующих наборам, где функция равна 0. Для набора \((0,0)\) соответствующая элементарная дизъюнкция: \(x \lor y\). Таким образом, СКНФ для \(f = \neg x \rightarrow y\) является \((x \lor y)\). Среди вариантов нет \((x \lor y)\). Возможно, в вариантах ответа есть опечатка, и один из них должен был быть \((x \lor y)\). Если же мы должны выбрать из того, что есть, и предположить, что \((\neg x \lor y)\) в варианте 4) является СКНФ, то это неверно. Если бы вопрос был про ДНФ, то \(f = \neg x \rightarrow y \equiv x \lor y\). ДНФ была бы \(x \lor y\). Но вопрос про СКНФ. Я не могу выбрать правильный ответ из предложенных вариантов, так как ни один из них не является СКНФ для \(f = \neg x \rightarrow y\). Если бы я был вынужден выбрать, то это была бы ошибка в задании. Задание 26. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Многочлен, являющийся суммой констант и различных правильных элементарных конъюнкций, в которых все переменные входят в первой степени называется 1) правильной элементарной конъюнкцией Правильный ответ: Описание "многочлен, являющийся суммой констант и различных правильных элементарных конъюнкций, в которых все переменные входят в первой степени" очень похоже на определение полинома Жегалкина (или алгебраического нормального вида). Однако, из предложенных вариантов есть только "правильная элементарная конъюнкция", что не соответствует описанию. Если это задание с одним вариантом ответа, то оно некорректно. Если это задание, где нужно выбрать из списка, и список неполный, то я не могу дать ответ. Предположим, что это задание с одним вариантом ответа, и он должен быть правильным. Описание "многочлен, являющийся суммой констант и различных правильных элементарных конъюнкций, в которых все переменные входят в первой степени" - это определение полинома Жегалкина. Поскольку такого варианта нет, я не могу дать ответ. Если бы вопрос был "Что из перечисленного является частью такого многочлена?", то "правильная элементарная конъюнкция" могла бы быть частью ответа. Но вопрос про *название* самого многочлена. Я вынужден констатировать, что при данном единственном варианте ответа, который не соответствует описанию, невозможно выбрать правильный ответ.