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.
Preneksowa postać normalna
-
- Administrator
- Posty: 34312
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Preneksowa postać normalna
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
Re: Preneksowa postać normalna
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.
\(\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.
-
- Administrator
- Posty: 34312
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Preneksowa postać normalna
Po pierwsze, nie ma czegoś takiego jak "w domyśle opuścił". Zadanie jest, jakie jest.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 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ć...
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.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.
JK
-
- Użytkownik
- Posty: 609
- Rejestracja: 10 lis 2009, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 135 razy
Re: Preneksowa postać normalna
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: ↑24 wrz 2022, o 12:07Po pierwsze, nie ma czegoś takiego jak "w domyśle opuścił". Zadanie jest, jakie jest.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)}\) .
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.
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.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.
-
- Administrator
- Posty: 34312
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Preneksowa postać normalna
Zgadza się, dziękuję za zwrócenie uwagi (zrobiłem na szybko kopiuj-wklej, powinienem uważniej przeczytać). Powinno byćkrl pisze: ↑24 wrz 2022, o 17:09Jan 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.
\(\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{)} .}\)
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.krl pisze: ↑24 wrz 2022, o 17:09Pozwolę 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.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.
JK