Matematyka.pl

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.

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

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ć.

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

JK

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.

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

Jan Kraszewski pisze: 1 mar 2020, o 12:52 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.

iksinski pisze: 1 mar 2020, o 13:03Jak już się czegoś dowodzi to w jakimś systemie Gentzena, Słupeckiego, Hilberta itp.

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

JK

Jan Kraszewski pisze: 1 mar 2020, o 12:52 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.

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

JK

Jan Kraszewski pisze: 1 mar 2020, o 13:19

iksinski pisze: 1 mar 2020, o 13:03Jak 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?

foundofmath pisze: 1 mar 2020, o 21:11Jak 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

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

Dodano po 13 godzinach 13 minutach 51 sekundach:

Jan Kraszewski pisze: 1 mar 2020, o 22:22 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.

Jan Kraszewski pisze: 1 mar 2020, o 22:22

foundofmath pisze: 1 mar 2020, o 21:11Jak 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).

To pierwsze.

JK