Wskaż kontrprzykład lub udowodnij

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
patrykoz
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 paź 2017, o 11:33
Płeć: Mężczyzna
Lokalizacja: Tajemnica

Wskaż kontrprzykład lub udowodnij

Post autor: patrykoz » 2 lis 2017, o 09:28

Witam. Mam takie zdanie:
(\(\displaystyle{ \forall x\ p(x)\wedge\ \exists x\ q(x)) \implies \exists x\ ((p(x) \wedge\ q(x))}\)

Czy istnieje kontrprzykład?
Czy mogę sobie to przełożyć na(trochę dziecinne zobrazowanie ) (każde jabłko jest czerwone i istnieje smaczne jabłko) to istnieje jabłko(które jest czerwone i jest smaczne)?

Pozdrawiam.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15209
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5046 razy

Re: Wskaż kontrprzykład lub udowodnij

Post autor: Premislav » 2 lis 2017, o 10:34

To zobrazowanie pokaże Ci, czy masz iść w stronę dowodu, czy w stronę szukania kontrprzykładu, więc się nawet przyda.
Podpowiem, że kontrprzykład nie istnieje.
Negacja implikacji:
\(\displaystyle{ \neg\left( r \Rightarrow s\right) \Leftrightarrow r \wedge \neg s}\)
czyli w naszym przypadku:
\(\displaystyle{ \neg\left( \forall x\ (p(x))\wedge\ \exists x ( q(x) ))\implies \exists x\ (p(x) \wedge\ q(x))\right) \Leftrightarrow\left( \forall x\ (p(x))\wedge\ \exists x\ (q(x))) \wedge \forall x\left( \neg(p(x))\vee \neg (q(x))\right)}\)
i chyba dalej sobie poradzisz (dążymy do pokazania, że takie zdanie, jak to ostatnie, nigdy nie jest prawdziwe).


Można też w innym stylu:
jeżeli zdanie \(\displaystyle{ \forall x\ (p(x))\wedge\ \exists x\ (q(x))}\) jest fałszywe, to całe zdanie
\(\displaystyle{ \forall x\ (p(x))\wedge\ \exists x\ (q(x)) \implies \exists x\ ((p(x) \wedge\ q(x))}\) jest prawdziwe (patrz eliminacja implikacji). W przeciwnym razie weźmy takie \(\displaystyle{ x_1}\), że
zachodzi \(\displaystyle{ q(x_1)}\) (możemy takie ustalić z uwagi na \(\displaystyle{ \exists x(q(x))}\)), wiemy też o nim, że zachodzi dlań \(\displaystyle{ p(x_1)}\) (bo \(\displaystyle{ \forall x(p(x)}\)), śtąd dla tegoż \(\displaystyle{ x_1}\) mamy prawdziwość zdania \(\displaystyle{ p(x_1)\wedge q(x_1)}\).

Awatar użytkownika
Takahashi
Użytkownik
Użytkownik
Posty: 186
Rejestracja: 12 maja 2017, o 19:04
Płeć: Mężczyzna
Lokalizacja: brak
Podziękował: 1 raz
Pomógł: 22 razy

Re: Wskaż kontrprzykład lub udowodnij

Post autor: Takahashi » 2 lis 2017, o 17:58

Ale znaczkologia

Weź \(\displaystyle{ x_0}\), świadka zdania \(\displaystyle{ \exists x q(x)}\) i... < to jest zdecydowanie lepsze podejście (czyli nr 2 u Przemka).

patrykoz
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 paź 2017, o 11:33
Płeć: Mężczyzna
Lokalizacja: Tajemnica

Re: Wskaż kontrprzykład lub udowodnij

Post autor: patrykoz » 2 lis 2017, o 19:09

A mógłbym prosić jeszcze o wytłumaczenie dlaczego w \(\displaystyle{ f(x)}\) wartość nie zależy od zmiennej \(\displaystyle{ x}\) ? I w takim razie od czego zależy?
Dlaczego możemy postawić znak równoważności \(\displaystyle{ \forall x f(x) \iff \forall x p(x)}\) ?
Ostatnio zmieniony 2 lis 2017, o 19:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Jan Kraszewski
Administrator
Administrator
Posty: 27296
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4594 razy

Re: Wskaż kontrprzykład lub udowodnij

Post autor: Jan Kraszewski » 2 lis 2017, o 19:31

patrykoz pisze:A mógłbym prosić jeszcze o wytłumaczenie dlaczego w \(\displaystyle{ f(x)}\) wartość nie zależy od zmiennej \(\displaystyle{ x}\) ? I w takim razie od czego zależy?

A co to jest \(\displaystyle{ f(x)}\) ?
patrykoz pisze:Dlaczego możemy postawić znak równoważności \(\displaystyle{ \forall x f(x) \iff \forall x p(x)}\) ?
W ogólności nie możemy.

JK

patrykoz
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 31 paź 2017, o 11:33
Płeć: Mężczyzna
Lokalizacja: Tajemnica

Re: Wskaż kontrprzykład lub udowodnij

Post autor: patrykoz » 2 lis 2017, o 19:46

Jan Kraszewski pisze: A co to jest \(\displaystyle{ f(x)}\) ?
To jest forma zdaniowa. Chodziło o \(\displaystyle{ \varphi(x)}\)

Może napiszę całe zdanie:

\(\displaystyle{ \exists x \varphi (x) \vee \forall \psi (x) \iff \exists x \forall y (\varphi(x) \vee \psi (x))}\)

Na ćwiczeniach powiedziane było że \(\displaystyle{ \exists x \varphi (x) \vee \forall \psi (x)}\) nie zależy od zmiennej x. Ale dlaczego?

Ponadto postawiliśmy \(\displaystyle{ \forall \varphi(x) \iff \forall \varphi(y)}\)

Jan Kraszewski
Administrator
Administrator
Posty: 27296
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4594 razy

Re: Wskaż kontrprzykład lub udowodnij

Post autor: Jan Kraszewski » 2 lis 2017, o 19:53

patrykoz pisze:\(\displaystyle{ \exists x \varphi (x) \vee \forall \psi (x) \iff \exists x \forall y (\varphi(x) \vee \psi (x))}\)
Powinno być

\(\displaystyle{ \exists x \varphi (x) \vee \forall\red x\black \psi (x) \iff \exists x \forall y (\varphi(x) \vee \psi (\red y\black))}\)
patrykoz pisze:Na ćwiczeniach powiedziane było że \(\displaystyle{ \exists x \varphi (x) \vee \forall \psi (x)}\) nie zależy od zmiennej x. Ale dlaczego?
W formule \(\displaystyle{ \exists x \varphi (x) \vee \forall\red x\black \psi (x)}\) zmienna \(\displaystyle{ x}\) jest związana.
patrykoz pisze:Ponadto postawiliśmy \(\displaystyle{ \forall \varphi(x) \iff \forall \varphi(y)}\)
I znów

\(\displaystyle{ \forall\red x\black \varphi(x) \iff \forall\red y\black \varphi(y)}\).

Pomyśl o tym w ten sposób: zdanie \(\displaystyle{ \forall x \varphi(x)}\), że formuła \(\displaystyle{ \varphi(x)}\) jest spełniona dla wszystkich \(\displaystyle{ x}\)-ów. Zauważ, że zdanie \(\displaystyle{ \forall y\varphi(y)}\) niesie dokładnie tę samą treść - literka, której użyjesz jest nieistotna.

JK

ODPOWIEDZ