Здравствуйте! Помогите доказать тождество (мат. логика)

[Mary_strong]

Здравствуйте! Помогите доказать тождество:
$x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.
Вот если бы здесь не было квантора $\forall$, то было бы легко:
$(A\wedge (A\Rightarrow B))\Longrightarrow (A \wedge (\neg A\vee B))\Longrightarrow\\ \Longrightarrow (A \wedge \neg A \vee A\wedge B)\Longrightarrow (A\wedge B)\Longrightarrow B.$
А вот, что делать с квантором? Спасибо!

[Null]

Есть аксиома $\forall y P(y) \Rightarrow P(z)$

[Mary_strong]

Null, а где можно найти подобные аксиомы?

[paha]

ну... если $\forall y$ $(y+1)^2=y^2+2y+1$, то $(z+1)^2=z^2+2z+1$... что не исключает $(z+1)^2=z^2+1$... просто $z$ такое, что $2z=0$ и $0+1=1$

[Null]

Чему это противоречит?

$\forall y P\rightarrow P[z/y]$ - формальная запись аксиомы. Последнее обозначение означает формулу P где все свободные $y$ заменены на $z$.

[paha]

Null в сообщении #386119 писал(а):

Чему это противоречит?

я только проиллюстрировал смысль аксиомы))

[Виктор Викторов]

Mary_strong в сообщении #386103 писал(а):

Здравствуйте! Помогите доказать тождество:
$x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.
Вот если бы здесь не было квантора $\forall$, то было бы легко:
$(A\wedge (A\Rightarrow B))\Longrightarrow (A \wedge (\neg A\vee B))\Longrightarrow\\ \Longrightarrow (A \wedge \neg A \vee A\wedge B)\Longrightarrow (A\wedge B)\Longrightarrow B.$
А вот, что делать с квантором? Спасибо!

Что делать с квантором я не знаю.

Mary_strong в сообщении #386103 писал(а):

Помогите доказать тождество:
$x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.

А теперь попробуем доказать, что это высказывательная форма истинна при всех значениях переменной $x$. Во-первых мы должны предположить, что высказывательная форма определена на некотором множестве $T$. Во вторых, что $A\subseteq T$. Поскольку ничего специфического про $P(x)$ не сказано, то могут существовать такие $x$, что $P(x)$ истинно, но могут существовать и такие $x$, что $P(x)$ ложно. При этих допущениях воспользуемся формулой $D\Rightarrow F\equiv \neg D \vee F$. Получаем: $\neg(x\in A \wedge \forall x(x\in A\Rightarrow P(x)))\vee P(x)$.
Преобразуем эту форму так: $\neg(x\in A) \vee \exists x(x\in A\Rightarrow P(x)) \vee P(x)$. Получили дизъюнкцию. Разберите случаи.

[Joker_vD]

Mary_strong в сообщении #386116 писал(а):

а где можно найти подобные аксиомы?

В начале вашего курса. Разные авторы и лекторы по-разному вводят понятия, обозначения, определения и аксиомы. В читавшемся мне курсе дискретной математики аксиом, кажется, не было совсем.

[Виктор Викторов]

Виктор Викторов в сообщении #386160 писал(а):

Mary_strong в сообщении #386103 писал(а):

Помогите доказать тождество:
$x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.

А теперь попробуем доказать, что это высказывательная форма истинна при всех значениях переменной $x$. Во-первых мы должны предположить, что высказывательная форма определена на некотором множестве $T$. Во вторых, что $A\subseteq T$. Поскольку ничего специфического про $P(x)$ не сказано, то могут существовать такие $x$, что $P(x)$ истинно, но могут существовать и такие $x$, что $P(x)$ ложно. При этих допущениях воспользуемся формулой $D\Rightarrow F\equiv \neg D \vee F$. Получаем: $\neg(x\in A \wedge \forall x(x\in A\Rightarrow P(x)))\vee P(x)$.
Преобразуем эту форму так: $\neg(x\in A) \vee \exists x(x\in A\Rightarrow P(x)) \vee P(x)$. Получили дизъюнкцию. Разберите случаи.

Я наврал и никто не заметил. Действительно, $\neg(x\in A \wedge \forall x(x\in A\Rightarrow P(x)))\vee P(x)$.
А вот это $\neg(x\in A) \vee \exists x(x\in A\Rightarrow P(x)) \vee P(x)$ враньё. Правильно: $\neg(x\in A) \vee \exists x\neg (x\in A\Rightarrow P(x)) \vee P(x)$. И воспользуюсь случаем сделать ещё одно преобразование: $x\notin A \vee \exists x\neg (x\in A\Rightarrow P(x)) \vee P(x)$.

[mkot]

Виктор Викторов в сообщении #386160 писал(а):

Преобразуем эту форму так: $\neg(x\in A) \vee \exists x(x\in A\Rightarrow P(x)) \vee P(x)$. Получили дизъюнкцию. Разберите случаи.

Если необходимо доказать, что импликация всегда верна, в подобных задачах выгодно действовать кверхногами: показать, что она не может быть, ложной, то есть положить противное. Почему? Потому что случай когда импликация ложна один: посылка истинна, заключение ложно.

[Виктор Викторов]

Вот то, что нас просят доказать:

Mary_strong в сообщении #386103 писал(а):

Помогите доказать тождество: $x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.

Вот это моё враньё:

mkot в сообщении #387033 писал(а):

Виктор Викторов в сообщении #386160 писал(а):

Преобразуем эту форму так: $\neg(x\in A) \vee \exists x(x\in A\Rightarrow P(x)) \vee P(x)$. Получили дизъюнкцию. Разберите случаи.

Если необходимо доказать, что импликация всегда верна, в подобных задачах выгодно действовать кверхногами: показать, что она не может быть, ложной, то есть положить противное. Почему? Потому что случай когда импликация ложна один: посылка истинна, заключение ложно.

В задачке спрашивается: Почему враньё надо доказывать? А вот то, что действительно нужно доказать: $x\notin A \vee \exists x\neg (x\in A\Rightarrow P(x)) \vee P(x)$. А уж если ещё и преобразовать вот так: $x\notin A \vee \exists x (x\in A \wedge \neg P(x)) \vee P(x)$, то всё становится ясным.

[Виктор Викторов]

Mary_strong в сообщении #386103 писал(а):

Помогите доказать тождество:
$x\in A \wedge \forall x(x\in A\Rightarrow P(x))\Longrightarrow P(x)$.

Подробно про эту формулу $\forall x(x\in A\Rightarrow P(x))$ в книге Юрия Шихановича "Введение в современную математику" страница 157.