Udowodnij prawo rozkładu kwantyfikatora

[macjekkk]

Dzień dobry,

Chciałbym zapytać o poprawność mojego rozwiązania zadania. Polecenie brzmi "Udowodnij poniższe prawa rozkładu kwantyfikatora", a jednym z przykładów jest: \(\displaystyle{ ∀x (ϕ(x) ⇔ ψ(x)) ⇒ (∀x ϕ(x) ⇔ ∀xψ(x))}\). Mój dowód nie wprost wygląda tak:

0) \(\displaystyle{ Z = 0 ⇒ [∀x (ϕ(x) ⇔ ψ(x))] = 1 ∧ [(∀x ϕ(x) ⇔ ∀xψ(x))] = 0}\)

1) (wynika z 0) \(\displaystyle{ [∀x(ϕ(x) = 1) ∧ ∀x(ψ(x)) = 0)] ∨[∀x(ϕ(x) = 0) ∧ ∀x(ψ(x)) = 1)]}\)

2) (wynika z 1) \(\displaystyle{ [∀x(ϕ(x) = 1) ∧ ∃x(ψ(x)) = 0)] ∨ [∃x(ϕ(x) = 0) ∧ ∀x(ψ(x)) = 1)]}\)

3) (wynika z 2) \(\displaystyle{ ∃x[(ϕ(x) ⇔ ψ(x)) = 0]}\)

4) (wynika z 3) \(\displaystyle{ \neg ∀x(ϕ(x) ⇔ ψ(x))}\) - sprzeczność z 0;

Na studiach używamy zapisu w punktach, nie wiem, czy moje rozumowanie i zapis jest poprawny, stąd proszę o pomoc w rozwiązaniu, pozdrawiam.

[Jan Kraszewski]

Taki zapis jest dość paskudny, bo nie ma żadnych uzasadnień, ale skoro tak zapisujesz na studiach, to nie masz wyjścia.

Niestety dość niefrasobliwie używasz nawiasów. Ponadto sam zapis rozumowania jest dla mnie niejasny (ponieważ wiem, jak powinien wyglądać argument, więc jestem się w stanie domyślić, że próbujesz zapisać to samo, ale nie przekonuje mnie to) i formalnie niepoprawny (przez te nawiasy). Trudno mi jednak ocenić, jakiej wersji wymagają u Ciebie na studiach.

JK

[iksinski]

Ja bym to zrobił tak:

1 \(\displaystyle{ ∀x (ϕ(x) ⇔ ψ(x)) ⇒ (∀x ϕ(x) ⇔ ∀xψ(x))}\).

2 \(\displaystyle{ ∀x (ϕ(x) ⇔ ψ(x))}\). przesłanka

3.1 \(\displaystyle{ ∀x ϕ(x) }\). założenie
3.2 \(\displaystyle{ ϕ(x) }\).
3.3 \(\displaystyle{ (ϕ(x) ⇔ ψ(x)) }\).
3.4 \(\displaystyle{ ψ(x) }\).
3.5 \(\displaystyle{ ∀xψ(x) }\).

4 \(\displaystyle{ ∀x ϕ(x) ⇒ ∀xψ(x) }\).

5.1 \(\displaystyle{ ∀x ψ(x) }\). założenie
5.2 \(\displaystyle{ ψ(x) }\).
5.3 \(\displaystyle{ (ϕ(x) ⇔ ψ(x)) }\).
5.4 \(\displaystyle{ ϕ(x) }\).
5.5 \(\displaystyle{ ∀xϕ(x) }\).

6 \(\displaystyle{ ∀xψ(x) ⇒ ∀x ϕ(x) }\).

7 \(\displaystyle{ ∀x ϕ(x) ⇔ ∀xψ(x) }\).

Bardzo długie ale wszystko widać.

[Jan Kraszewski]

Widać ścianę znaczków bez żadnego wytłumaczenia bądź uzasadnienia.

JK

[iksinski]

Wystarczy tylko znać reguły systemu dedukcji naturalnej. Za mało miejsca żeby je podawać. Tutaj właściwie to tylko reguła opuszczania kwantyfikatora ogólnego i dołączania kwantyfikatora ogólnego. To system Słupeckiego i Borkowskiego.

[Jan Kraszewski]

Po pierwsze, nie wydaje się, by w tym wypadku chodziło o system dedukcji naturalnej. Wystarczy zobaczyć próby założyciela wątku by wiedzieć, o jaki zapewne rodzaj uzasadnienia chodzi.

Po drugie, to formułujący rozwiązanie ma zadbać o to, by było ono czytelne. Ja sobie oczywiście odtworzę Twój tok rozumowania, co nie znaczy, że jest to dobrze sformułowane rozwiązanie.

JK

[iksinski]

Po pierwsze, nie wydaje się, by w tym wypadku chodziło o system dedukcji naturalnej. Wystarczy zobaczyć próby założyciela wątku by wiedzieć, o jaki zapewne rodzaj uzasadnienia chodzi.

Ale pisze "Udowodnij poniższe prawa rozkładu kwantyfikatora". Jak już się czegoś dowodzi to w jakimś systemie Gentzena, Słupeckiego, Hilberta itp. Nie zostało to podane.

[Jan Kraszewski]

Jak już się czegoś dowodzi to w jakimś systemie Gentzena, Słupeckiego, Hilberta itp.

Niekoniecznie. To nie musi być dowód syntaktyczny.

JK

[iksinski]

Po drugie, to formułujący rozwiązanie ma zadbać o to, by było ono czytelne. Ja sobie oczywiście odtworzę Twój tok rozumowania, co nie znaczy, że jest to dobrze sformułowane rozwiązanie.

Brakuje tylko reguł po prawej stronie każdej linijki.

Dodano po 2 godzinach 52 minutach 25 sekundach:
Ja bym to zrobił tak:

1 \(\displaystyle{ ∀x (ϕ(x) ⇔ ψ(x)) ⇒ (∀x ϕ(x) ⇔ ∀xψ(x))}\).

2 \(\displaystyle{ ∀x (ϕ(x) ⇔ ψ(x))}\). przesłanka
3 \(\displaystyle{ (ϕ(x) ⇔ ψ(x)) }\) 2, O\(\displaystyle{ ∀}\)

4.1 \(\displaystyle{ ∀x ϕ(x) }\). założenie
4.2 \(\displaystyle{ ϕ(x) }\). 4.1, O\(\displaystyle{ ∀}\)
4.3 \(\displaystyle{ ψ(x) }\). 3, 4.2 MP
4.4 \(\displaystyle{ ∀xψ(x) }\). 4.3, D\(\displaystyle{ ∀}\)

5 \(\displaystyle{ ∀x ϕ(x) ⇒ ∀xψ(x) }\). 4.1-4.4 D\(\displaystyle{ ⇒}\)

6.1 \(\displaystyle{ ∀x ψ(x) }\). założenie
6.2 \(\displaystyle{ ψ(x) }\). 6.1, O\(\displaystyle{ ∀}\)
6.3 \(\displaystyle{ ϕ(x) }\). 3, 6.2 MP
6.4 \(\displaystyle{ ∀xϕ(x) }\). 6.3, D\(\displaystyle{ ∀}\)

7 \(\displaystyle{ ∀xψ(x) ⇒ ∀x ϕ(x) }\). 6.1-6.4 D\(\displaystyle{ ⇒}\)

8 \(\displaystyle{ ∀x ϕ(x) ⇔ ∀xψ(x) }\). 5, 7 D \(\displaystyle{ \wedge }\)

Legenda:

\(\displaystyle{ ∀x ϕ(x)/ ϕ(x/t)}\) O\(\displaystyle{ ∀}\) - opuszczanie kwantyfikatora ogólnego ( bez ograniczeń )
\(\displaystyle{ ϕ(x/t)/∀x ϕ(x)}\) D\(\displaystyle{ ∀}\) - dołączanie kwantyfikatora ogólnego( warunek: zmienna x nie może być wolna w
założeniach)
\(\displaystyle{ ϕ(x),(ϕ(x) ⇔ ψ(x)/ψ(x)}\) MP - reguła podobna do modus ponenes
\(\displaystyle{ zal x.1,x.n/x.1 \Rightarrow x.n}\) D\(\displaystyle{ ⇒}\)- reguła dołączania implikacji
\(\displaystyle{ ϕ,ψ/ϕ \wedge ψ }\) D \(\displaystyle{ \wedge }\) reguła dołączania koniunkcji

Oczywiście to rozumowanie jest banalnie proste, ale komuś może się przydać znajomość dedukcji. Teraz chyba wszystko w porządku.

[Jan Kraszewski]

W porządku, ale jak pisałem wcześniej - myślę, że nie o to chodziło.

JK

[foundofmath]

Jak już się czegoś dowodzi to w jakimś systemie Gentzena, Słupeckiego, Hilberta itp.

Niekoniecznie. To nie musi być dowód syntaktyczny.

Jak wobec tego określa Pan kryterium na bycie twierdzeniem?

[Jan Kraszewski]

Jak wobec tego określa Pan kryterium na bycie twierdzeniem?

Semantycznie.

W pierwszym poście macjekkk w gruncie rzeczy przeprowadził taki dowód, tylko mu się trochę nawiasy pomieszały i no forma była nie najlepsza.

JK

[iksinski]

A jest jakaś definicja prawdy? Bo chyba o to pytał foundofmath?

Dodano po 13 godzinach 13 minutach 51 sekundach:

W pierwszym poście macjekkk w gruncie rzeczy przeprowadził taki dowód, tylko mu się trochę nawiasy pomieszały i no forma była nie najlepsza.

Moim zdaniem to rozwiązanie jest niestety błędne. Przejście z 2 do 3 jest dla mnie niezrozumiałe. \(\displaystyle{ 0 \Leftrightarrow 0 }\) daje przecież 1 a nie 0.

Dodano po 1 godzinie 9 minutach 19 sekundach:
Odwołuję, co napisałem. Jednak dowód jest poprawny. Nawiasy też w porządku. Zrozumiałem przejście z 2 do 3.

[foundofmath]

Jak wobec tego określa Pan kryterium na bycie twierdzeniem?

Semantycznie.

Ale to nie jest jednoznaczne jeśli abstrahujemy od konkretnego systemu. Chodzi mi o to, czy w tym ujęciu zabiega Pan o to, by ten schemat był prawdziwy we wszystkich dziedzinach (po odpowiednim podstawieniu) i nie zważa Pan na nic więcej, czy to ujęcie ma odzwierciedlać jakiś konkretny system z wnioskowaniem syntaktycznym (innymi słowy domyślnie zakłada Pan jednoznaczność swojego podejścia).

[Jan Kraszewski]

To pierwsze.

JK