Podstawienie pewnego termu na zmienną

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Podstawienie pewnego termu na zmienną

Post autor: matinf » 22 paź 2016, o 12:37

Czy jeśli \(\displaystyle{ A\models \exists_x \phi}\), to także \(\displaystyle{ A\models\phi[t/x]}\), dla pewnego termu \(\displaystyle{ t}\)?

\(\displaystyle{ A}\) jest strukturą. \(\displaystyle{ A\models \exists_x \phi}\) oznacza, że \(\displaystyle{ A}\) modeluje formułę po prawej stronie, czyli dla każdego wartościowania formuła jest zawsze spełniona. Żeby to rozwiązać muszę zrozumieć o co chodzi. Czym jest term ? Co tak na prawdę mam pokzać ?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jan Kraszewski
Administrator
Administrator
Posty: 25985
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Podstawienie pewnego termu na zmienną

Post autor: Jan Kraszewski » 22 paź 2016, o 13:05

Term

Intuicyjnie: termy to wszystkie poprawne składniowo napisy, które możesz stworzyć używając symboli zmiennych, symboli stałych i symboli funkcyjnych.

JK

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Podstawienie pewnego termu na zmienną

Post autor: matinf » 22 paź 2016, o 15:09

W takim razie to wydaje się być prawdziwe. Bo przecież możemy wziąć:
\(\displaystyle{ t=x}\) (term może być zmienną).
To tylko złudzenie pewnie, bo tam stoi jeszcze istnieje. Możesz wytłumaczyć o co w tym chodzi ?


PS Termny nie mogą zawierać relacji albo spójników logicznych ?-- 23 paź 2016, o 14:50 --Czy jeśli \(\displaystyle{ A\models \exists_x \phi}\), to także \(\displaystyle{ A\models\phi[t/x]}\), dla pewnego termu\(\displaystyle{ t}\)?

Jeszcze raz spróbuję to przemyśleć.
W jednej z formuł mamy \(\displaystyle{ \exists}\) w drugiej nie. Przede wszystkim - czym jest tutaj \(\displaystyle{ A}\) ? Jest strukturą. A jaką ? To po prostu jakiś zbiór dziedzina. Dlaczego ? Ha, pomyliłem się. Jest strukturą, ale nic na jej temat nie mogę powiedzieć, bo nie wiem jakie jest dokładnie \(\displaystyle{ \phi}\). Wszystko zależy od tego co siedzi w \(\displaystyle{ \phi}\) - czy jakies symbole funkcyjne, relacyjne.
Co mówi to: \(\displaystyle{ A\models \exists_x \phi}\) ?
To mówi po prostu, że struktra \(\displaystyle{ A}\) modeluje formułę po prawej stronie. Co znaczy, że modeluje. Tzn, że jakbyśmy nie powartościowali to i tak mamy prawdziwą formułę. Co wartościowali ? No to co jest w \(\displaystyle{ \phi}\) czyli jakieś symbole relacyjne/funkcyjne/dziedzinę zamienić na coś "prawdziwego", np \(\displaystyle{ \le/\lambda x.x/\NN}\).

Co zatem mówi to: \(\displaystyle{ A\models \exists_x \phi}\) ?
Że w tej strukturze \(\displaystyle{ A}\) ta formuła jest po prawej, innymi słowy, ze znajdziemy \(\displaystyle{ x}\) taki, że zajdzie \(\displaystyle{ \phi}\).

No to teraz:
\(\displaystyle{ A\models\phi[t/x]}\)
Tu nie ma kwantyfikatora po prawej stronie. Ale czym jest ten \(\displaystyle{ x}\) ? Bo on pewnie występuje w \(\displaystyle{ \phi}\) skoro podstawiamy na niego term \(\displaystyle{ t}\). Czy on jest zmienną wolną ? Ale co taka zmienna wolna oznacza ?

Bo nie wiem jak mam o tym myśleć. Na razie tylko wiem co znaczy założenie. Struktra \(\displaystyle{ A}\) zapewnia, że \(\displaystyle{ \exists_x \phi}\) niezależnie od wartościowania w \(\displaystyle{ \phi}\) mamy prawdę.

krl
Użytkownik
Użytkownik
Posty: 474
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 98 razy

Podstawienie pewnego termu na zmienną

Post autor: krl » 23 paź 2016, o 15:54

matinf pisze:W takim razie to wydaje się być prawdziwe. Bo przecież możemy wziąć:
\(\displaystyle{ t=x}\) (term może być zmienną).
To tylko złudzenie pewnie, bo tam stoi jeszcze istnieje. Możesz wytłumaczyć o co w tym chodzi ?


PS Termny nie mogą zawierać relacji albo spójników logicznych ?
1. No to weźmy \(\displaystyle{ t=x}\). Czym wtedy jest formuła \(\displaystyle{ \phi(t/x)}\)? Co to znaczy, że jest ona spełniona w \(\displaystyle{ A}\)?
2. "O co w tym chodzi?" Niejasne pytanie.
3. Ad PS: patrz link dany przez Jana Kraszewskiego.
Określenie "struktura modeluje formułę/zdanie" jest bardzo rażące.

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Podstawienie pewnego termu na zmienną

Post autor: matinf » 23 paź 2016, o 16:24

Cytat dotyczy postu przed edycją, ale i tak się odniosę:
1. No to weźmy \(\displaystyle{ t=x}\). Czym wtedy jest formuła \(\displaystyle{ \phi(t/x)}\)?
To jest po prostu formuła \(\displaystyle{ \phi(x)}\)
Co to znaczy, że jest ona spełniona w \(\displaystyle{ A}\)?
\(\displaystyle{ A}\) to pewna struktura, która narzuca coś - jakieś symbole relacyjne, funkcyjne, dziedzinę. Narzuca je w ten sposób, że formuła jest prawdziwa - chodzi o to, że formuła wygląda jakoś tak:
\(\displaystyle{ \forall_{x,y,z} r(x,y)\wedge r(y,z) \to r(x,z)}\). I ta formuła nie jest konkretna ani trochę. Teraz jak weźmiemy strukturę: \(\displaystyle{ (\NN, \le_{\NN})}\) to jest to struktura, w której formuła jest spełniona (=prawdziwa). Natomiast czym tutaj jest wartościowanie ? Nie wiem. Co mam na myśli mówiąc wartościowanie ? Struktura jest modelem dla formuły o ile dla każdego wartościowania formuła jest prawdziwa. Być może modelem jest tutaj każda relacja przechodnia, a wartościowaniem - no no moje \(\displaystyle{ \le_{\NN}}\). Hmm ?

Ale trzeba pamiętać, że strukturą jest tu ( w moim przykładzie relacji przechodniej) dowolna relacja binarna na zbiorem \(\displaystyle{ X}\) (który też jest dowolny).
Czyli model jest strukturą, ale struktura modelem nie zawsze. Modelm jest każda relacja przechodnia - i jeszcze raz - a czym wartościowanie ?

krl
Użytkownik
Użytkownik
Posty: 474
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 98 razy

Podstawienie pewnego termu na zmienną

Post autor: krl » 23 paź 2016, o 18:48

Na jedno z pytań odpowiedziałeś dobrze: gdy \(\displaystyle{ t=x}\), to \(\displaystyle{ \phi(t/x)=\phi}\).
Załóżmy, że \(\displaystyle{ x}\) jest jedyną zmienną wolną w \(\displaystyle{ \phi}\). Wtedy formuła \(\displaystyle{ \phi=\phi(x)}\) nie jest zdaniem. Co to znaczy wtedy, że formuła \(\displaystyle{ \phi(x)}\) jest prawdziwa w strukturze \(\displaystyle{ A}\)? (wsk: już o tym była mowa w innym poście).

I teraz rozstrzygnij sam: czy jeśli \(\displaystyle{ A\models \exists x\phi}\), to formuła \(\displaystyle{ \phi(x)}\) jest prawdziwa w \(\displaystyle{ A}\) ? (bo tak przypuszczasz powyżej)

A w ogóle to co rozumiesz przez formułę \(\displaystyle{ \phi(t/x)}\), gdy \(\displaystyle{ t}\) jest dowolnym termem?

W ostatnim Twoim poście piszesz pewne formuły w taki sposób, że nie jestem pewien, czy rozumiesz, co to jest zasięg kwantyfikatora w formule. Chodzi o nawiasy... (to bardzo częsty błąd u informatyków)

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Podstawienie pewnego termu na zmienną

Post autor: matinf » 23 paź 2016, o 21:28

Załóżmy, że \(\displaystyle{ x}\) jest jedyną zmienną wolną w \(\displaystyle{ \phi}\). Wtedy formuła \(\displaystyle{ \phi=\phi(x)}\) nie jest zdaniem. Co to znaczy wtedy, że formuła \(\displaystyle{ \phi(x)}\) jest prawdziwa w strukturze A? (wsk: już o tym była mowa w innym poście).
Zmienna wolna, to niekwantyfikowana. \(\displaystyle{ \phi(x)}\) - co to jest ? Przecież w naszym zadaniu to nigdzie nie występuje.
A w ogóle to co rozumiesz przez formułę \(\displaystyle{ \phi(t/x)}\), gdy \(\displaystyle{ t}\) jest dowolnym termem?
Po prostu syntaktycznie to rozumiem - w miejsce iksa wszędzie wpisuję term \(\displaystyle{ t}\).

Na resztę pytań nie mogę spróbować odpowiedzieć, bo nie wiem czym jest dla Ciebie \(\displaystyle{ \phi(x)}\).

Jan Kraszewski
Administrator
Administrator
Posty: 25985
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Podstawienie pewnego termu na zmienną

Post autor: Jan Kraszewski » 23 paź 2016, o 22:22

matinf pisze:\(\displaystyle{ \phi(x)}\) - co to jest ? Przecież w naszym zadaniu to nigdzie nie występuje.
Występuje. Skoro chcesz robić podstawienie termu \(\displaystyle{ t}\) za zmienną \(\displaystyle{ x}\), to ta zmienna powinna w \(\displaystyle{ \phi}\) występować jako zmienna wolna, bo inaczej to podstawienie będzie puste (nic nie podstawiasz, bo nie ma gdzie podstawiać) i zadanie strywializuje się. Zapis \(\displaystyle{ \phi=\phi(x)}\) podkreśla, że jedyną zmienną wolną formuły \(\displaystyle{ \phi}\) jest właśnie \(\displaystyle{ x}\) (co założył dla uproszczenie sytuacji krl).

JK

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Podstawienie pewnego termu na zmienną

Post autor: matinf » 23 paź 2016, o 23:17

Ok, w takim razie jutro wieczorem spróbuję się nad tym raz jeszcze zastanowić.

-- 24 paź 2016, o 22:06 --

Dziś nie dałem rady, jutro wieczorem powinienem zdołać to przemyśleć.

-- 25 paź 2016, o 22:12 --

Dziś znowu nie dałem rady
Praca mi nie daje żyć
Jutro siądę do tego.-- 26 paź 2016, o 22:48 --
Czy jeśli \(\displaystyle{ A\models \exists_x \phi}\), to także \(\displaystyle{ A\models\phi[t/x]}\), dla pewnego termu \(\displaystyle{ t}\)?
No cóż mogę powiedzieć.
Popatrzmy \(\displaystyle{ A\models\exists_x\phi}\). Rozważmy może takie zdanie: \(\displaystyle{ \phi: x \ge 0}\)
Weźmy strukturę \(\displaystyle{ \langle \NN\rangle}\). Wówczas mogę powiedzieć, że \(\displaystyle{ A\models \exists_x\phi}\).
Czy natomiast \(\displaystyle{ A\models\phi[t/x]}\) ?
To się wydaje dziwne trochę, bo pytanie jest o pewien term. No więc ja wezmę term \(\displaystyle{ x}\). Czyli to przyjmie postać \(\displaystyle{ \phi[x/x]=x > 0}\) co jest prawdą w strukturze liczb naturalnych.

Czy się mylę?

ODPOWIEDZ