∃x (P(x) ∨ Q(x)) = ∃x P(x) ∨ ∃x Q(x)

Если придать смысл этим предикатам и будет выполняться равносильность, то можно ли считать это доказательством?

задан 5 Ноя '13 23:02

Еще непонятен один момент в одной из равносильнотей http://savepic.su/3681911.jpg (выделено красным). Объясните пожалуйста.

(5 Ноя '13 23:11) Inna
10|600 символов нужно символов осталось
0

По поводу первого задания. Прежде всего, здесь должен быть не знак равенства, а что-то другое. Либо символ эквиваленции $%\leftrightarrow$% с формулировкой "доказать тавтологию исчисления предикатов", либо просто даны две формулы, и сказано о том, что надо доказать их логическую эквивалентность.

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

Здесь доказательство может выглядеть так. Рассмотрим произвольную интерпретацию, то есть непустое множество $%D$% в качестве предметной области, на котором заданы два одноместных предиката. Их я для простоты буду обозначать как есть, то есть $%P$% и $%Q$%, хотя формально следует различать предикатные символы (просто буквы, не имеющие смысла), и конкретные предикаты, ими задаваемые. Для строгости рассуждения можно использовать дополнительные буквы $%\bar{P}$%, $%\bar{Q}$%, но я думаю, что в данном рассуждении лучше пренебречь подобного рода формальностями.

Итак, сначала предположим, что первая из формул, то есть $%(\exists x)(P(x)\vee Q(x))$%, истинна в некоторой интерпретации. Тогда существует элемент $%x_0\in D$%, для которого высказывание $%P(x_0)\vee Q(x_0)$% истинно. Это мы воспользовались определением истинности формулы в заданной интерпретации -- в той части, которая касается толкования квантора существования. Теперь используем определение дизъюнкции, и тогда окажется, что хотя бы одно из высказываний $%P(x_0)$%, $%Q(x_0)$% истинно. В первом случае формула $%(\exists x)P(x)$% оказывается истинной в рассматриваемой интерпретации, во втором -- формула $%(\exists x)Q(x)$%. В любом из случаев дизъюнкция $%(\exists x)P(x)\vee(\exists x)Q(x)$% окажется в нашей интерпретации истинной.

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

По поводу равносильности, которая рассматривается на картинке по ссылке: там на самом деле присутствует два факта равносильности, относящиеся к выделенной красным цветом формуле. Какую из двух равносильностей надо обосновывать? Далее, какими методами при обосновании разрешено пользоваться? Можно рассуждать "семантически", то есть примерно в том виде, как я это продемонстрировал выше. А можно использовать правила вывода в исчислении предикатов.

Поскольку я не знаю, какой из переходов Вас интересует (а их там аж целых четыре, то есть в "цепочке" вида $%U\equiv V\equiv W$% можно потребовать обоснования того, что $%U$% влечёт $%V$%, что $%V$% влечёт $%U$%, и два случая насчёт связи между $%V$% и $%W$%), я сам выберу для иллюстрации один из случаев -- по принципу "самый сложный". Хотя, в принципе, они все лёгкие.

Прежде всего, надо выделить два часто используемых правила логического рассуждения. Пусть мы доказали формулу $%\Phi(x)$%, где относительно $%x$% никаких предположений не делается. Тогда мы установили справедливость этой формулы для произвольного $%x$%, и этим самым, по смыслу, доказали формулу $%(\forall x)\Phi(x)$%. Это т.н. "правило обобщения". Другое правило таково: если доказана формула $%(\forall x)\Phi(x)$%, то можно взять любое выражение $%t$% (синоним -- "терм" $%t$%), и объявить доказанной формулу $%\Phi(t)$%. В роли $%t$% здесь может выступать любая из переменных: например, $%z$%, или сама переменная $%x$%. Это т.н. "правило перехода к частному случаю". Мы часто его применяем на практике. Скажем, если я знаю, что $%x^2\ge0$% для любого действительного $%x$%, то я могу подставить $%x=a-b$% и заключить, что $%(a-b)^2\ge0$%, сделав далее какие-то преобразования и придя к новым видам неравенств.

Итак, иллюстрирую переход от формулы $%(\forall x)A(x)\vee(\forall y)B(y)$% к $%(\forall x)(A(x)\vee(\forall y)B(y))$% и обратно.

Если дано первое, то я могу воспользоваться правилом разбора случаев. Их здесь имеется два, и в каждом из них я доказываю формулу, обведённую красным. По смыслу выходит так: верно $%(\forall x)A(x)$% или $%(\forall y)B(y)$%. Первый случай: пусть верно первое. Тогда верно $%A(x)$% без квантора, то есть "для произвольного $%x$%". Здесь я перешёл к частному случаю $%A(t)$% при $%t=x$%. Коль скоро $%A(x)$% верно, то верной будет любая дизъюнкция $%A(x)$% с чем угодно. То есть формулу $%A(x)\vee(\forall y)B(y)$% объявляем доказанной. А теперь, поскольку $%x$% "произвольно", применяем правило обобщения и заключаем, что доказано $%(\forall x)(A(x)\vee(\forall y)B(y))$%.

Тут нужна оговорка: в условии подразумевается, что в формуле $%B(y)$% нет свободных вхождений переменной $%x$% (например, формула атомарная). В противном случае само рассуждение не проходит. Теперь второй случай, который пока не разобран: пусть верно $%(\forall y)B(y)$%. Тогда образуем дизъюнкцию $%A(x)\vee(\forall y)B(y)$% -- она считается для этого случая доказанной. И далее обобщаем по $%x$%, добавляя спереди квантор всеобщности.

Обратный переход: пусть нам дано $%(\forall x)(A(x)\vee(\forall y)B(y))$%. Тогда переходим к частному случаю $%A(x)\vee(\forall y)B(y)$%, как это уже делали. Теперь разбор случаев: если $%A(x)$% верно, то обобщаем, приходя к выводу $%(\forall x)A(x)$%. А если верно $%(\forall y)B(y)$%, то так и оставляем. В каждом из этих двух случаев будет верна дизъюнкция $%(\forall x)A(x)\vee(\forall y)B(y)$%, что и требовалось доказать.

ссылка

отвечен 6 Ноя '13 2:06

Спасибо огромное!!!

(24 Ноя '13 0:48) Inna

Можно еще вопрос? Как записать в предваренной нормальной форме предикат ∀x ∃y ∀z P(x,y,z) ∨ ∀x ∃y Q(x,y).

(1 Дек '13 18:37) Inna

$$(\forall x)(\exists y_1)(\exists y_2)(\forall z)(P(x,y_1,z)\vee Q(x,y_2))$$

(1 Дек '13 19:21) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×547

задан
5 Ноя '13 23:02

показан
656 раз

обновлен
1 Дек '13 19:21

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

по почте:

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

по RSS:

Ответы

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

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