Formuły rownowazne.

[vizard]

Witam .Mam takie pytanie jak pokazać że formuły \(\displaystyle{ \forall x (\phi \Rightarrow \psi)}\) i \(\displaystyle{ (\exists x\psi)
\Rightarrow \phi}\) są równo ważne. Czy mogę je połączyć spójnikiem równoważności i pokazać ze tak formuła jest tautologią \(\displaystyle{ }\)

[Qń]

formuły \(\displaystyle{ \forall x (\phi \Rightarrow \psi)}\) i \(\displaystyle{ (\exists x\psi)
\Rightarrow \phi}\) są równoważne.

Zarówno w tej formie (gdy \(\displaystyle{ \phi, \psi}\) nie zależą od \(\displaystyle{ x}\)), jak i po poprawieniu ich na \(\displaystyle{ \phi (x), \psi (x)}\) - te formuły nie są równoważne.

Q.

[Jan Kraszewski]

Chyba, że chodziło o formuły \(\displaystyle{ \forall x(\psi(x) \Rightarrow \phi)}\) i \(\displaystyle{ (\exists x\psi(x)) \Rightarrow \phi}\).

JK

[chozz]

O to chodzilo. Zmienna x może mieć wolne wystąpienia w \(\displaystyle{ \psi}\), ale nie w \(\displaystyle{ \phi}\). Ale jak to pokazać? Mogę próbować jakoś przekształcić poprzednik implikacji? Tzn.


\(\displaystyle{ \forall x(\psi(x) \Rightarrow \phi) \equiv \neg\neg (\forall x(\psi(x) \Rightarrow \phi) \equiv \neg (\exists x(\psi(x) \wedge \neg \phi)) \equiv \neg (\exists x(\psi(x)) \wedge \neg \phi) \equiv \neg\neg (\exists x(\psi(x)) \Rightarrow \phi) \equiv (\exists x(\psi(x))\Rightarrow\phi)}\)

Teraz poprzednik implikacji jest taki sam jak następnik więc są równoważne? W przejściu tam jednym korzystam, z tego że zmienna wolna x nie ma wystąpienia w \(\displaystyle{ \phi}\). Kolejna sprawa, czy jeśli miałbym sprawdzić czy niżej podane formuły są równoważne:

\(\displaystyle{ \forall x(\psi(x) \Rightarrow \phi)}\) i \(\displaystyle{ (\forall x\psi(x)) \Rightarrow \phi}\)

To wystarczy argument, że z tego że istnieje, nie wynika że dla każdego?

[Jan Kraszewski]

O to chodzilo. Zmienna x może mieć wolne wystąpienia w \(\displaystyle{ \psi}\), ale nie w \(\displaystyle{ \phi}\). Ale jak to pokazać? Mogę próbować jakoś przekształcić poprzednik implikacji? Tzn.

\(\displaystyle{ \forall x(\psi(x) \Rightarrow \phi) \equiv \neg\neg (\forall x(\psi(x) \Rightarrow \phi) \equiv \neg (\exists x(\psi(x) \wedge \neg \phi)) \equiv \neg (\exists x(\psi(x)) \wedge \neg \phi) \equiv \neg\neg (\exists x(\psi(x)) \Rightarrow \phi) \equiv (\exists x(\psi(x))\Rightarrow\phi)}\)

Teraz poprzednik implikacji jest taki sam jak następnik więc są równoważne?

Jaki poprzednik i następnik jakiej implikacji? Masz dwie formuły i wykonując powyższe przekształcenia pokazałeś, że są one równoważne. Czego chcieć więcej?

Kolejna sprawa, czy jeśli miałbym sprawdzić czy niżej podane formuły są równoważne:

\(\displaystyle{ \forall x(\psi(x) \Rightarrow \phi)}\) i \(\displaystyle{ (\forall x\psi(x)) \Rightarrow \phi}\)

To wystarczy argument, że z tego że istnieje, nie wynika że dla każdego?

Nie wystarczy. Jeżeli chcesz uzasadnić, że formuły nie są równoważne, to musisz wskazać konkretne \(\displaystyle{ \psi}\) i \(\displaystyle{ \phi}\), dla których tej równoważności nie ma.

JK

[chozz]

No fakt, nie wiem czemu myślałem cały czas o tej równoważności jak o implikacji. No dobra, w takim razie nie wiem jak szukać takiego kontrprzykładu? Jakieś sugestie, idee?