Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 48

Что из перечисленного является ИСТИННЫМ в отношении формул в конъюнктивной нормальной форме?
(A) Для любой формулы существует правдивое присваивание, для которого по меньшей мере половина предложений оценивается как истинная.
(B) Для любой формулы есть задание истинности, для которого все пункты оцениваются как истинные
(C) Существует такая формула, что для каждого назначения истинности не более одной четверти пунктов оценивается как истинное.
(D) Ничего из вышеперечисленного

Ответ: (А)
Объяснение: Мы можем легко доказать, что для любой формулы есть присваивание правды, для которого по крайней мере половина предложений оценивается как истинное.

Доказательство:
Рассмотрим произвольное присвоение правды. Для каждого его предложения 'j' введите случайную величину.
X j = 1, если условие «j» выполнено
X j = 0 в противном случае

Тогда X = сумма (j * X j ) — это число удовлетворенных предложений.
Для любого предложения 'c' оно неудовлетворительно, только если все его составляющие литералы 'k' оцениваются как ложные, так как к ним присоединяется оператор OR.
Теперь, поскольку каждый литерал в предложении имеет шанс 1/2 оценить истинность независимо от значения истинности любого из других литералов, вероятность того, что все они ложны, равна (1/2) k .
Таким образом, вероятность того, что «с» выполнено = 1 — (1/2) k
Итак, E (X j ) = 1 * (1/2) k = (1/2) k

Следовательно, E (X j )> = 1/2

Суммирование с обеих сторон, чтобы получить E (X).

Следовательно, E (X) = суммирование (j * X j )> = m / 2, где «m» — количество предложений.
E (X) представляет ожидаемое количество удовлетворенных предложений.

Таким образом, должно существовать присвоение, которое удовлетворяет как минимум половине пунктов.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2007 | Вопрос 48

0.00 (0%) 0 votes