Дана формула $$ \forall x P(x) \leftrightarrow \exists x Q(x) $$ Хочу проверить правильность рассуждений $$\forall x P(x) \leftrightarrow \exists x Q(x)\equiv (\neg (\forall x P(x)) \wedge \neg (\exists x Q(x))) \vee (\forall x P(x) \wedge \exists x Q(x))\equiv$$ $$\equiv (\exists x \neg P(x) \wedge \forall x \neg Q(x)) \vee (\forall x P(x) \wedge \exists x Q(x))\equiv$$ $$ \equiv (\exists x \neg P(x) \vee \forall x P(x)) \wedge (\forall x \neg Q(x) \vee \forall x P(x)) \wedge (\exists x \neg P(x) \vee \exists x Q(x)) \wedge (\forall x \neg Q(x) \vee \exists x Q(x))$$ Теперь заменяем связные вхождения одних и тех же переменных и выносим кванторы из скобок $$\equiv \exists x \forall y (\neg P(x) \vee P(y)) \wedge \forall \gamma \forall z (\neg Q(\gamma) \vee P(z)) \wedge \exists k \exists t (\neg P(k) \vee Q(t)) \wedge \forall \beta \exists \xi (\neg Q(\beta) \vee Q(\xi))$$ Далее есть сомнение можно ли просто вытащить все кванторы вперед и сказать что это ответ? $$\forall y \forall \gamma \forall z \forall \beta \exists x \exists k \exists t \exists \xi [(\neg P(x) \vee P(y)) \wedge (\neg Q(\gamma) \vee P(z)) \wedge (\neg P(k) \vee Q(t)) \wedge (\neg Q(\beta) \vee Q(\xi))]$$ Или это бред?

задан 11 Янв 21:28

Проверять такие выкладки -- удовольствие ниже среднего. Тем более, что делать это можно многими способами. Посмотрите описание в книге Верещагина и Шеня. У них там довольно просто описана вся процедура. Думаю, что ответ здесь должен быть проще.

(11 Янв 21:33) falcao

Все кванторы можно вынести на самом первом шаге, а потом уже раскрыть эквиваленцию, если это необходимо

(11 Янв 21:47) haosfortum

Спасибо, об этом я не подумал. Получится тогда $$\forall x \exists y (P(x)\leftrightarrow Q(y))$$

(11 Янв 22:37) RedAlert

@RedAlert: по-моему, Ваша формула логически не эквивалентна оригиналу. Пусть предметная область равна D={a,b}, и Q ложно на любом элементе, а P истинно на a и ложно на b. Формула из условия истинна: 0<->0. Ваша формула ложна: при x=a не существует игрека, так как P(a) истинно, Q(y) ложно.

(11 Янв 22:43) falcao

@falcao: да, вы правы. Тогда так $$\forall y \exists x (P(y)\leftrightarrow Q(x))$$, то есть для каждого y найдется x, такой чтобы формула была истинна?

(11 Янв 23:16) RedAlert

@RedAlert: так ведь это ровно то же самое. Вы переобозначили буквы, это ни на что не влияет.

(12 Янв 1:29) falcao

@falcao: не совсем понимаю тогда как вынести кванторы не раскрывая эквивалентность. Попробую в лоб. $$\forall x P(x) \leftrightarrow \exists x Q(x) \equiv (\exists x \neg P(x) \wedge \forall x \neg Q(x)) \vee (\forall x P(x) \wedge \exists x Q(x))\equiv $$ $$\exists x \forall y (\neg P(x) \wedge \neg Q(y)) \vee \exists x \forall z (P(x) \wedge Q(z)) \equiv $$ $$\exists x \forall y \forall z (\neg P(x) \wedge \neg Q(y)) \vee (P(x) \wedge Q(z))$$

(12 Янв 13:18) RedAlert

@RedAlert: во второй строке формул в конце перепутаны x и z (или P и Q). Там должно быть Q(x) & P(z).

(12 Янв 14:30) falcao
1

@falcao: ой, точно. Очепятка) Должно быть так $$\exists x \forall y \forall z (\neg P(x) \wedge \neg Q(y)) \vee (P(z) \wedge Q(x))$$

(12 Янв 14:34) RedAlert

@RedAlert: да, это должно быть верно. Здесь можно было даже не действовать по процедуре, а подобрать формулу по смыслу. Исходная формула истинна iff 1) P истинна всюду, Q истинна где-то ИЛИ 2) P ложна где-то, Q ложна всюду. Вы это примерно и реализовали.

(12 Янв 14:55) falcao

@falcao: спасибо за помощь.

(12 Янв 15:04) RedAlert
показано 5 из 11 показать еще 6
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,654
×1,047

задан
11 Янв 21:28

показан
62 раза

обновлен
12 Янв 15:04

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

по почте:

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

по RSS:

Ответы

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

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