Доказать или опровергнуть общезначимость формулы. Помогите, пожалуйста. [(y→p)(¬x→y)(x→z)]→(z∨p)

задан 10 Сен '14 22:25

изменен 11 Сен '14 16:07

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
0

Исследовать формулу на общезначимость можно многими способами, и мне лично кажется, что метод резолюций является не самым подходящим. Но, раз уж так поставлена задача, то рассмотрим её решение при помощи этого метода. А в конце я укажу дополнительно два других способа.

Схема такая: нам дана импликация, и мы принимаем то, что написано в её посылке, и отрицаем то, что написано в заключении. Получается некий набор формул, который надо исследовать на выполнимость. Если таковая имеет место, то это даёт нам набор значений высказывательных переменных, для которых посылка становится истинной, а заключение -- ложным (так как мы рассматривали его отрицание). И это значит, что формула не является общезначимой. И наоборот: если мы из нашего набора формул имеем противоречие, то выполнимости нет, и тогда наша исходная формула общезначима.

В посылке импликации мы имеем конъюнкцию формул. Каждую из формул, составляющих конъюнкцию, мы принимаем, и перечисляем их через запятую, превращая все импликации в дизъюнкции по правилу $%(a\to b)=(\neg{a}\lor b)$%, с учётом закона двойного отрицания. Это даёт нам список $%\neg{y}\lor p$%, $%x\lor y$%, $%\neg{x}\lor z$%.

Теперь надо принять отрицание заключение импликации, то есть $%\neg{(z\lor p)}$%. По закону де Моргана, это будет конъюнкция отрицаний: $%(\neg{z})(\neg{p})$%. Как и выше, все конъюнктивные члены добавляем в список, и теперь у нас имеется следующее: $$\neg{y}\lor p, x\lor y, \neg{x}\lor z, \neg{z}, \neg{p}.$$ Все формулы данного списка представляют собой элементарные дизъюнкции (состоящие, возможно, из одного члена). Теперь нам надо проверить, можем ли мы из каждого такого дизъюнкта (их всего 5) извлечь по одному члену так, чтобы не возникало противоречия (никакая переменная не шла вместе со своим отрицанием).

Ясно, что из двух последних дизъюнктов мы можем взять только $%\neg z$% и $%\neg{p}$% за неимением выбора. Тогда из третьего дизъюнкта мы берём $%\neg{x}$%, избегая противоречия, а из первого берём $%\neg{y}$%. Тогда оказывается, что из второго дизъюнкта ничего уже более не подходит: получается противоречие. Вывод: наша формула логически общезначима.

Теперь то же самое более просто. Допустим, что формула не общезначима, то есть на на каких-то наборах бывает ложной. В этом случае посылка истинна, заключение ложно. Из $%|z\lor p|=0$% следует $%|z|=|p|=0$%. Подставляем эти значения в условия истинности импликаций из посылки: $%|y\to0|=1$%, $%|x\to0|=1$%. Из определения импликации следует ложность обеих посылок: $%|y|=0$%, $%|x|=0$%. Но тогда $%|\neg{x}\to y|=|1\to0|=0$%, и вторая по счёту импликация из условия ложна. Противоречие.

Наконец, способ "естественного вывода". Нам дано, что $%y\to p$%, $%\neg{x}\to y$%, $%x\to z$%. Требуется логически вывести $%z\lor p$%, что представимо импликацией $%\neg{z}\to p$%. Можно принять её посылку, то есть $%\neg{z}$%, и попытаться доказать $%p$%. Это легко: из $%x\to z$% мы по контрапозиции получаем $%\neg{z}\to\neg{x}$%. Поскольку $%\neg{z}$% нам дано, то по правилу отсечения (modus ponens) выводим $%\neg{x}$%. По тому же правилу, с учётом $%\neg{x}\to y$% выводим $%y$%. Применяя правило ещё раз, из $%y\to p$% приходим к выводу $%p$%, что и требовалось.

ссылка

отвечен 11 Сен '14 17:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×22

задан
10 Сен '14 22:25

показан
506 раз

обновлен
11 Сен '14 17:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru