Matematyka.pl

Dzień dobry!

Prosiłbym o sprawdzenie poniższego zadania i wskazania ewentualnego błędu.

Zad. Sprowadzić do postaci preneksowej formułę:
\(\displaystyle{ \bigvee\limits_{x} \ (P(x) \wedge \bigwedge\limits_{y} Q(x,y)) \rightarrow \bigvee\limits_{x} \ (P(x) \wedge Q(x,x) \wedge \bigvee\limits_{y} \ Q(x,y))}\)

Moje rozwiązanie:

\(\displaystyle{ \bigvee\limits_{x} \ (P(x) \wedge \bigwedge\limits_{y} Q(x,y)) \rightarrow \bigvee\limits_{z} \ (P(z) \wedge Q(z,z) \wedge \bigvee\limits_{s} \ Q(z,s)) \\ \bigvee\limits_{x} \ \bigwedge\limits_{y} \ (P(x) \wedge Q(x,y)) \rightarrow \bigvee\limits_{z} \ (P(z) \wedge Q(z,z) \wedge \bigvee\limits_{s} \ Q(z,s)) \\ \bigvee\limits_{x} \ \bigwedge\limits_{y} \ (P(x) \wedge Q(x,y)) \rightarrow \bigvee\limits_{z} \ \bigvee\limits_{s} \ (P(z) \wedge Q(z,z) \wedge Q(z,s)) \\ \bigvee\limits_{x} \ \bigwedge\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \ (P(x) \wedge Q(x,y)) \rightarrow (P(z) \wedge Q(z,z) \wedge Q(z,s))}\)

Początkowo chciałem dwa pierwsze kwantyfikatory dla x oraz y zamienić na przeciwne, ale profesor twierdzi, że dla x zostaje niezmienny. Niestety na temat kwantyfikatora drugiego nie uzyskałem informacji, ale zakładam, że również pozostaje bez zmian.

JanPan pisze: ↑23 wrz 2022, o 22:19Początkowo chciałem dwa pierwsze kwantyfikatory dla x oraz y zamienić na przeciwne, ale profesor twierdzi, że dla x zostaje niezmienny. Niestety na temat kwantyfikatora drugiego nie uzyskałem informacji, ale zakładam, że również pozostaje bez zmian.

Tak się składa, że to Ty masz rację, a profesor jest w błędzie. Poprawna odpowiedź to

\(\displaystyle{ \bigwedge\limits_{x} \ \bigvee\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \ (P(x) \wedge Q(x,y)) \rightarrow (P(z) \wedge Q(z,z) \wedge Q(z,s))}\)

Mam nadzieję, że znasz prawa rachunku kwantyfikatorów, na podstawie których wykonałeś te przekształcenia. Wtedy poprawność powyższej odpowiedzi można udowodnić nawet profesorowi...

JK

A może profesor w domyśle opuścił lub zapomniał o jednym nawiasie i wyjściowa forma to:

\(\displaystyle{ \bigvee\limits_{x} \ \left((P(x) \wedge \bigwedge\limits_{y} Q(x,y)) \rightarrow \bigvee\limits_{x} \ ((P(x) \wedge \bigwedge\limits_{y} Q(x,x) \wedge \bigvee\limits_{y} Q(x,y))\right)}\) .

Czy wtedy końcowa postać wygląda tak:
\(\displaystyle{ \bigvee\limits_{x} \bigvee\limits_{y} \bigvee\limits_{z} \bigvee\limits_{s} \ \left((P(x) \wedge Q(x,y)) \rightarrow ((P(z) \wedge Q(z,z) \wedge Q(z,s))\right)}\) ?


I jeszcze jedno pytanie. Kiedy możemy zastosować ewentualne przejście z formy \(\displaystyle{ \rightarrow }\) na \(\displaystyle{ \vee }\) (czyli z '\(\displaystyle{ p \rightarrow q}\)' na '\(\displaystyle{ \neg p \vee q}\)')? Jako krok pierwszy, zaraz po zmianie kolidujących zmiennych? Po wyciągnięciu kwantyfikatorów wydaję mi się niewłaściwe.

JanPan pisze: ↑24 wrz 2022, o 11:24 A może profesor w domyśle opuścił lub zapomniał o jednym nawiasie i wyjściowa forma to:

\(\displaystyle{ \bigvee\limits_{x} \ \left((P(x) \wedge \bigwedge\limits_{y} Q(x,y)) \rightarrow \bigvee\limits_{x} \ ((P(x) \wedge \bigwedge\limits_{y} Q(x,x) \wedge \bigvee\limits_{y} Q(x,y))\right)}\) .

Po pierwsze, nie ma czegoś takiego jak "w domyśle opuścił". Zadanie jest, jakie jest.
Po drugie, powyższa forma jest niedobra, bo masz zagnieżdżone kwantyfikatory kwantyfikujące po \(\displaystyle{ x}\) - tak się nie robi. No i dodałeś tam jeszcze jakiś kwantyfikator, więc to nie ma wiele wspólnego z wyjściowym zadaniem.

Profesor też może się pomylić (jak każdy). Pytanie brzmi, czy potrafi się do tego przyznać...

JanPan pisze: ↑24 wrz 2022, o 11:24 I jeszcze jedno pytanie. Kiedy możemy zastosować ewentualne przejście z formy \(\displaystyle{ \rightarrow }\) na \(\displaystyle{ \vee }\) (czyli z '\(\displaystyle{ p \rightarrow q}\)' na '\(\displaystyle{ \neg p \vee q}\)')? Jako krok pierwszy, zaraz po zmianie kolidujących zmiennych? Po wyciągnięciu kwantyfikatorów wydaję mi się niewłaściwe.

W Twoich przekształceniach z pierwszego postu najwygodniej zrobić to po trzeciej linijce (pierwsze trzy linijki masz tam dobrze, dopiero ostatnia jest zła). Można to zrobić wcześniej, to bez znaczenia, ale wydaje mi się, że wtedy przekształcenia będą mniej wygodne.

JK

Tak, pomyliłem się i dodałem kwantyfikator.

Dziękuję za pomoc.

Jan Kraszewski pisze: ↑24 wrz 2022, o 12:07

JanPan pisze: ↑24 wrz 2022, o 11:24 A może profesor w domyśle opuścił lub zapomniał o jednym nawiasie i wyjściowa forma to:

\(\displaystyle{ \bigvee\limits_{x} \ \left((P(x) \wedge \bigwedge\limits_{y} Q(x,y)) \rightarrow \bigvee\limits_{x} \ ((P(x) \wedge \bigwedge\limits_{y} Q(x,x) \wedge \bigvee\limits_{y} Q(x,y))\right)}\) .

Po pierwsze, nie ma czegoś takiego jak "w domyśle opuścił". Zadanie jest, jakie jest.

Jan Kraszewski trafnie wskazuje, że nie ma czegoś takiego jak "w domyśle opuścił" i "zadanie jest jakie jest". Zgodnie z tymi zasadami odpowiedź

Jan Kraszewski pisze: ↑23 wrz 2022, o 22:52 Poprawna odpowiedź to
\(\displaystyle{ \bigwedge\limits_{x} \ \bigvee\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \ (P(x) \wedge Q(x,y)) \rightarrow (P(z) \wedge Q(z,z) \wedge Q(z,s))}\)

też jest błędna, bo brakuje w niej nawiasów określajacych zasięg kwantyfikatorów.
Ten sam błąd powtarza też autor pytania w końcowym wyniku w pierwszym poście. Opuszczanie nawiasów wskazujących na zasięg kwantyfikatorów to częsty błąd.

Jan Kraszewski pisze: ↑24 wrz 2022, o 12:07
Po drugie, powyższa forma jest niedobra, bo masz zagnieżdżone kwantyfikatory kwantyfikujące po \(\displaystyle{ x}\) - tak się nie robi. No i dodałeś tam jeszcze jakiś kwantyfikator, więc to nie ma wiele wspólnego z wyjściowym zadaniem.

Pozwolę sobie nie zgodzić się tu z Janem Kraszewskim. Tak się czasami robi i nie jest to błąd, choć istotnie zapis staje się wtedy mniej przejrzysty. Przypomnienie: kwantyfikator \(\displaystyle{ Qx}\) wiąże wszystkie wolne wystąpienia zmiennej \(\displaystyle{ x}\) w swoim zasięgu. Ta reguła jednoznacznie okresla znaczenie formuły z zagnieżdżonymi kwantyfikatorami.

krl pisze: ↑24 wrz 2022, o 17:09

Jan Kraszewski pisze: ↑23 wrz 2022, o 22:52 Poprawna odpowiedź to
\(\displaystyle{ \bigwedge\limits_{x} \ \bigvee\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \ (P(x) \wedge Q(x,y)) \rightarrow (P(z) \wedge Q(z,z) \wedge Q(z,s))}\)

też jest błędna, bo brakuje w niej nawiasów określajacych zasięg kwantyfikatorów.

Zgadza się, dziękuję za zwrócenie uwagi (zrobiłem na szybko kopiuj-wklej, powinienem uważniej przeczytać). Powinno być

\(\displaystyle{ \bigwedge\limits_{x} \ \bigvee\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \red{(}\, (P(x) \wedge Q(x,y)) \rightarrow (P(z) \wedge Q(z,z) \wedge Q(z,s))\red{)} }\)

albo nawet

\(\displaystyle{ \bigwedge\limits_{x} \ \bigvee\limits_{y} \ \bigvee\limits_{z} \ \bigvee\limits_{s} \red{(}\, P(x) \wedge Q(x,y) \rightarrow P(z) \wedge Q(z,z) \wedge Q(z,s)\red{)} .}\)

krl pisze: ↑24 wrz 2022, o 17:09

Jan Kraszewski pisze: ↑24 wrz 2022, o 12:07
Po drugie, powyższa forma jest niedobra, bo masz zagnieżdżone kwantyfikatory kwantyfikujące po \(\displaystyle{ x}\) - tak się nie robi. No i dodałeś tam jeszcze jakiś kwantyfikator, więc to nie ma wiele wspólnego z wyjściowym zadaniem.

Pozwolę sobie nie zgodzić się tu z Janem Kraszewskim. Tak się czasami robi i nie jest to błąd, choć istotnie zapis staje się wtedy mniej przejrzysty.

Wiem, ale nie napisałem, że to błąd (bo formalnie to poprawny zapis), tylko że tak się "nie robi", czyli że nie spodziewam się, że w zadaniu dla studentów tego typu pojawi się taki zapis.

JK