Равносильны ли формулы ∀x∀y∀z(R(y,x)→R(z,y)) и ∀x∀yR(х,у)∨∀x∀y¬R(х,у) ?

задан 14 Янв '18 14:07

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

Да, равносильны. Проверим это. Пусть вторая из формул истинна в некоторой интерпретации. Покажем, что первая в ней тоже истинна. Имеет место один из двух случаев: любые элементы предметной области находятся в отношении R, либо никакие не находятся. В первом случае импликация R(y,x)->R(z,y) имеет вид 1->1. Во втором она же имеет вид 0->0. При этом она в обоих случаях оказывается истинной.

Теперь проверим, что если первая из формул истинна в некоторой интерпретации, то и вторая тоже истинна. Допустим, что отношение R пусто. Тогда доказывать нечего: последний дизъюнктивный член второй формулы даёт истинность. Если же отношение непусто, то существуют элементы предметной области a,b такие, что R(a,b) истинно. Отсюда с учётом истинности первой формулы следует, что R(z,a) истинно при любом z. А из этого уже следует, что R(y,z) истинно при любом y и любом z. Тем самым, отношение R является полным, и даёт истинность первого дизъюнктивного члена второй формулы.

ссылка

отвечен 14 Янв '18 16:01

так, если мы вынесем кванторы во второй формуле, т е ∀x∀yR(х,у)∨∀x∀y¬R(х,у) ~ ∀x∀y¬R(х,у)∨∀x∀yR(х,у)~∀у∀х¬R(у,х)∨∀z∀yR(z,у)~∀x∀z(∀у¬R(у,х)∨∀yR(z,у)). и это не эквивалентно этому ∀x∀y∀z(¬R(у,x)∨R(z,у)). Поэтому ответ кажется нераавносильны

(14 Янв '18 16:23) Jenya

Т е ∀у(¬R(y)∨R(y))не эквив ∀у¬R(y)∨ ∀уR(y)

(14 Янв '18 16:32) Jenya

@Jenya: вынесение кванторов -- операция чисто "механическая". Она не даёт равносильности. Поэтому так делать вообще не надо.

(14 Янв '18 16:39) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,055

задан
14 Янв '18 14:07

показан
417 раз

обновлен
14 Янв '18 16:39

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

по почте:

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

по RSS:

Ответы

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

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