|
Дана формула $$ \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 
RedAlert
показано 5 из 11
показать еще 6
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
11 Янв 21:28
показан
62 раза
обновлен
12 Янв 15:04
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Проверять такие выкладки -- удовольствие ниже среднего. Тем более, что делать это можно многими способами. Посмотрите описание в книге Верещагина и Шеня. У них там довольно просто описана вся процедура. Думаю, что ответ здесь должен быть проще.
Все кванторы можно вынести на самом первом шаге, а потом уже раскрыть эквиваленцию, если это необходимо
Спасибо, об этом я не подумал. Получится тогда $$\forall x \exists y (P(x)\leftrightarrow Q(y))$$
@RedAlert: по-моему, Ваша формула логически не эквивалентна оригиналу. Пусть предметная область равна D={a,b}, и Q ложно на любом элементе, а P истинно на a и ложно на b. Формула из условия истинна: 0<->0. Ваша формула ложна: при x=a не существует игрека, так как P(a) истинно, Q(y) ложно.
@falcao: да, вы правы. Тогда так $$\forall y \exists x (P(y)\leftrightarrow Q(x))$$, то есть для каждого y найдется x, такой чтобы формула была истинна?
@RedAlert: так ведь это ровно то же самое. Вы переобозначили буквы, это ни на что не влияет.
@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))$$
@RedAlert: во второй строке формул в конце перепутаны x и z (или P и Q). Там должно быть Q(x) & P(z).
@falcao: ой, точно. Очепятка) Должно быть так $$\exists x \forall y \forall z (\neg P(x) \wedge \neg Q(y)) \vee (P(z) \wedge Q(x))$$
@RedAlert: да, это должно быть верно. Здесь можно было даже не действовать по процедуре, а подобрать формулу по смыслу. Исходная формула истинна iff 1) P истинна всюду, Q истинна где-то ИЛИ 2) P ложна где-то, Q ложна всюду. Вы это примерно и реализовали.
@falcao: спасибо за помощь.