Эквивалентны ли следующие формулы: $$\forall x \forall y \exists z \exists t (A(t, y) \rightarrow B(x, z)) $$ и $$ \forall x \forall t \exists y \exists z (A(y, t) \rightarrow B(x, z))?$$

задан 7 Дек '19 17:07

Связанные переменные можно переименовывать. Сделаем так, чтобы бескванторная часть формулы приняла тот же вид в обоих случаях. Для первой формулы положим t:=u, y:=v. Для второй y:=u, t:=v. Кванторные приставки примут вид (Ax)(Av)(Ez)(Eu) и (Ax)(Av)(Eu)(Ez). Осталось сослаться на то, что одноимённые кванторы можно переставлять. Формулы логически эквивалентны.

(7 Дек '19 19:14) falcao

а можно как-то доказывать эквивалентность, не пользуясь перестановками кванторов? например (Eu)(Ax)(Ev)(Ay)(A(x,y) -> B(u,v)) и (Ev)(Ax)(Ay)(Eu)(A(x,y) -> B(u,v))?

(10 Дек '19 19:16) bloodyblueducky

@bloodyblueducky: по-моему, в новом примере эквивалентности не будет. Там, вроде, нет даже односторонних импликаций ни в какую из сторон. То есть надо контрпримеры строить. В комментариях для этого маловато места -- надо завести новый отдельный вопрос.

(10 Дек '19 20:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×824
×30

задан
7 Дек '19 17:07

показан
32 раза

обновлен
10 Дек '19 20:10

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

по почте:

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

по RSS:

Ответы

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

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