szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 sty 2018, o 19:33 
Użytkownik

Posty: 418
Lokalizacja: Rzeszów
Pragnę się podzielić pewnym wspaniałym dowodem. :lol: Oto zadanie:
Cytuj:
Udowodnij, że w dowolnym ustalonym modelu M prawdziwe są następujące formuły:
...
\ \bigwedge _x r(x, f(x)) \Rightarrow \ \bigwedge _x \ \bigvee _y r(x,y).
Czyli należy pokazać, że ta formuła jest prawdziwa w każdym odpowiednim dla niej modelu, czyli, że jest tautologią rachunku predykatów.

DOWÓD:

Ustalmy dowolny model M, który jest odpowiedni dla rozważanej formuły (czyli, który ustala interpretacje symbolu predykatywnego r, oraz symbolu funkcyjnego f ). Jeśli w modelu M nie jest prawdziwa formuła \bigwedge _x r(x, f(x)) , to cała implikacja jest prawdziwa. Pozostaje więc do rozważenia ten przypadek, gdy prawdziwa jest w modelu M formuła \bigwedge _x r(x, f(x)) . Załóżmy, że tak jest. Pokażemy, że w modelu M prawdziwa jest formuła \bigwedge _x \ \bigvee _y r(x,y) . Weźmy dowolne wartościowanie w zmiennych (i termów). Pokażemy, że prawdziwe jest wtedy (przy tym wartościowaniu) \bigwedge _x \ \bigvee _y r(x,y) . Czyli, że dla dowolnego wartościowania w' , różniącego się od w jedynie na x , należy pokazać, że \bigvee _y r(x,y) . Weźmy dowolne takie wartościowanie w' . Aby pokazać, że \bigvee _y r(x,y) skonstruujemy wartościowanie w'' , różniące się od w' jedynie na y , dla którego prawdą jest r(x,y) . Ponieważ w modelu M prawdziwa jest formuła \bigwedge _x r(x, f(x)) , więc jest prawdziwa również przy wartościowaniu w . Czyli dla dowolnego wartościowania, różniącego się od w jedynie na x , prawdą jest r(x, f(x)) . W szczególności, wartościowanie w' różni się od w jedynie na x , rzeczywiście. Wobec czego dla tego wartościowania w' , prawdą jest r(x, f(x)) . Wobec czego skonstruujmy (dopiero teraz :!: :!: ) wartościowanie w'' , zgodne z w' , poza zmienną y , na której przyjmuje tą samą wartość co term f(x) w wartościowaniu w' . Wtedy r(x,y) ma tą samą wartość logiczną co r(x,f(x)) , a więc jest prawdą, a więc prawdą jest (ze sposobu konstrukcji) \bigvee _y r(x,y) . Porządkując nasz dowód, dostaniemy, że cała rozważana implikacja jest prawdziwa w M. Pokazaliśmy więc, że ta formuła jest prawdziwa w każdym modelu.\square :lol: :D
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2018, o 00:26 
Administrator

Posty: 23709
Lokalizacja: Wrocław
Od strony formalnej ten dowód wygląda słabo.

JK
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2018, o 18:23 
Użytkownik

Posty: 418
Lokalizacja: Rzeszów
A dlaczego? To nie jest dowód formalny. To pokazuje, że taka formuła jest tautologią rachunku predykatów. Ponieważ w myśl twierdzenia Godla, tautologie są tym samym co twierdzenia, więc również jest twierdzeniem rachunku predykatów, czyli istnieje jej dowód formalny, a więc formuła jest prawdziwa.

A jeśli chodzi o sam dowód, to był robiony na podstawie literatury ( dobra- ważniaka, ale go zrozumiałem już wcześniej, wczoraj do niego wróciłem ). Tylko, że na przykład
Cytuj:
Ponieważ w modelu M prawdziwa jest formuła \bigwedge _x r(x, f(x)) , więc jest prawdziwa również przy wartościowaniu w . Czyli dla dowolnego wartościowania, różniącego się od w jedynie na x , prawdą jest r(x, f(x)) . W szczególności, wartościowanie w' różni się od w jedynie na x , rzeczywiście. Wobec czego dla tego wartościowania w' , prawdą jest r(x, f(x)) .
- takiego uzasadnienia tam nie ma. Starałem się przeprowadzić pełne rozumowanie. 8-)

Chyba, że ma Pan jeszcze uwagi. Ale w podobny sposób ( tylko troszkę krótszy) ten dowód przeprowadzono.
Góra
Mężczyzna Offline
PostNapisane: 13 sty 2018, o 10:46 
Użytkownik

Posty: 387
Lokalizacja: Wrocław
OK, przeprowadziłeś poprawny dowód zgodny z "ważniakową" definicją spełniania w modelu. Uczciwie trzeba przyznać, że ta definicja jest powszechnie akceptowana, pochodzi zresztą wprost od Tarskiego.
Ale jest też inna (równoważna) definicja spełniania, która lepiej (prościej) oddaje intuicje związane z formalizacją klasycznej definicji Arystotelesa. Mam na myśli definicję spełniania podaną np. w książce Shoenfielda, Mathematical Logic (zachęcam...).
Właśnie dowody takie, jak ten, który przedstawiłeś powyżej, są najlepszym argumentem na rzecz wyższości definicji z książki Shoenfielda nad definicją "ważniakową". Bo dowód wg tej prostszej definicji jest znacznie krótszy, no i bardziej przejrzysty, naturalny.

Ten krótszy dowód byłby taki:

Załóżmy, że (1) M\models\forall x r(x,f(x)). Pokażemy, że M\models\forall x\exists y r(x,y). Niech więc a\in M. Zgodnie z (1), M\models r(a,f(a)). Zatem f(a) świadczy o tym, że M\models \exists y r(a,y). Skoro a jest dowolne, M\models\forall x\exists y r(x,y).

Jak widać, ten dowód zgodny jest z intuicyjnym rozumieniem kwantyfikatorów. Jest też w pełni zgodny z formalną definicją z książki Shoenfielda. Jest 7 razy krótszy...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznaczanie dopuszczalności modelu  Grisp  0
 Nieliniowa regresja wielokrotna. Znajdowanie modelu.  Infibio  13
 Pole w trójkącie dowolnym, zależność  MAT_AŁ  3
 Prawdopodobieństwo przy podanym modelu kolejki.  kokos22  0
 Równoliczność zbioru R z dowolnym podzbiorem  Algol  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl