Matematyka.pl

Dowód wprost dla tezy : \(\displaystyle{ \exists x \left[ P(x) \rightarrow \neg Q(x)\right] \rightarrow \left[ \forall x P(x) \rightarrow \exists x \neg Q(x)\right] }\)

Dowód nie wprost dla tezy
\(\displaystyle{ \forall x\left[ Q(x) \rightarrow \neg P(x)\right] \rightarrow \left[ \forall x P(x) \rightarrow \neg \exists x Q(x) \right] }\)


Nie rozumiem tych przejść w tych dowodach i od czego się zaczyna

Dwa najważniejsze narzędzia których potrzebujesz to zamiana implikacji na alternatywę:
\(\displaystyle{
p \rightarrow q \Leftrightarrow \neg p \vee q
}\)

i prawa de Morgana dla kwantyfikatorów:
\(\displaystyle{
\neg \exists x P(x) \Leftrightarrow \forall x \neg P(x)\\
\neg \forall x P(x) \Leftrightarrow \exists x \neg P(x)
}\)

do tego może się przydać jeszcze
\(\displaystyle{
\neg (p \wedge q) \Leftrightarrow \neg p \vee \neg q\\
\neg (p \vee q) \Leftrightarrow \neg p \wedge \neg q
}\)

i rozbrajasz to po kolei, jak masz implikację zamieniasz na alternatywę, jak masz negację wewnątrz kwantyfikatora wyciągasz na zewnątrz, jak masz negację przy dwóch elementach alternatywy albo koniunkcji wyciągasz ją przed nawias i kombinujesz

Dodano po 25 minutach 3 sekundach:
weźmy ten pierwszy przykład
\(\displaystyle{ \exists x \left[ P(x) \rightarrow \neg Q(x)\right] \rightarrow \left[ \forall x P(x) \rightarrow \exists x \neg Q(x)\right] }\)
najpierw tę dużą implikację po środku zmieniam na alternatywę, czyli nie prawda że pierwszy duży nawias lub prawda że drugi:

\(\displaystyle{ \neg \left( \exists x \left[ P(x) \rightarrow \neg Q(x)\right]\right) \vee \left( \left[ \forall x P(x) \rightarrow \exists x \neg Q(x)\right] \right) }\)
teraz w lewym nawiasie stosuję to samo

\(\displaystyle{ \neg \left( \exists x \left[ \neg P(x) \vee \neg Q(x)\right]\right) \vee \left( \left[ \forall x P(x) \rightarrow \exists x \neg Q(x)\right] \right) }\)
zwróć uwagę, że neguję tylko lewą stronę implikacji, negacja Q jest bo już tam była
teraz po prawej najpierw wyciągam negację przed kwantyfikator

\(\displaystyle{ \neg \left( \exists x \left[ \neg P(x) \vee \neg Q(x)\right]\right) \vee \left( \left[ \forall x P(x) \rightarrow \neg \forall x Q(x)\right] \right) }\)

i likwiduję ostatnią implikację po prawej

\(\displaystyle{ \neg \left( \exists x \left[ \neg P(x) \vee \neg Q(x)\right]\right) \vee \left( \left[
\neg \forall x P(x) \vee \neg \forall x Q(x)\right] \right) }\)

teraz w obu kwadratowych nawiasach masz alternatywę negacji, można je obie zamienić na negacje koniunkcji

\(\displaystyle{ \neg \left( \exists x \left[ \neg ( P(x) \wedge Q(x) ) \right]\right) \vee \left( \left[
\neg ( \forall x P(x) \wedge \forall x Q(x) ) \right] \right) }\)

teraz po lewej mogę wyciągnąć negację przed kwantyfikator

\(\displaystyle{ \neg \left( \neg \forall x \left[ P(x) \wedge Q(x) \right]\right) \vee \left( \left[
\neg ( \forall x P(x) \wedge \forall x Q(x) ) \right] \right) }\)

i mamy negację negacji, która się kasuje

\(\displaystyle{ \forall x \left[ P(x) \wedge Q(x) \right] \vee \left( \left[
\neg ( \forall x P(x) \wedge \forall x Q(x) ) \right] \right) }\)

po prawej możemy oba predykaty wrzucić w jeden kwantyfikator

\(\displaystyle{ \forall x \left[ P(x) \wedge Q(x) \right] \vee
\neg ( \forall x ( P(x) \wedge Q(x) )) }\)

i tym sposobem mamy zdanie, które dosłownie mówi "dla każdego x prawdą jest P i Q LUB nieprawda, że dla każdego x prawdą jest P i Q", innymi słowy jeżeli zastąpimy lewą stronę tak:

\(\displaystyle{ \forall x \left[ P(x) \wedge Q(x) \right] \Leftrightarrow R(x) }\)
to otrzymaliśmy
\(\displaystyle{
R(x) \vee \neg R(x)
}\)
co jest zawsze prawdą i do takiej formy należy dążyć