Dany jest język pierwszego rzędu oraz formuła \(\displaystyle{ B}\) tego języka, w której nie występują żadne kwantyfikatory oraz \(\displaystyle{ B}\) jest prawdziwa w każdym modelu \(\displaystyle{ M}\) tzn. \(\displaystyle{ \vDash_{M} B}\). Udowodnić, że formuła \(\displaystyle{ B}\) powstała przez podstawienie w pewnej tautologii \(\displaystyle{ A}\) rachunku zdań za zmienne zdaniowe pewnych formuł (ta sama formuła dla każdego wystąpienia danej zmiennej).
Jest to zadanie 2.25 z książki Eliotta Mendelsona "Introduction to Mathematical Logic". Nie mam na nie pomysłu.
Formuła bez kwantyfikatorów w logice pierwszego rzędu
-
- Użytkownik
- Posty: 609
- Rejestracja: 10 lis 2009, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 135 razy
Re: Formuła bez kwantyfikatorów w logice pierwszego rzędu
Nie wprost. Załóżmy, że \(\displaystyle{ B}\) jest tautologią logiczną, ale nie jest podstawieniem tautologii rachunku zdań. Identyfikujemy najpierw formułę \(\displaystyle{ A}\) rachunku zdań, której podstawieniem jest formuła \(\displaystyle{ B}\). Skoro \(\displaystyle{ A}\) nie jest tautologią, istnieje wartościowanie jej zmiennych zdaniowych przy którym \(\displaystyle{ A}\) jest fałszywa. Używając tego wartościowania budujemy model \(\displaystyle{ M}\), w którym formuła \(\displaystyle{ B}\) nie jest prawdziwa. (Można nawet zbudować model \(\displaystyle{ M}\) skończony).
(Oczywiście rozważana tu "logika pierwszego rzędu" nie ma wbudowanego standardowego rozumienia równości, gdyż wtedy zadanie jest błędne. Aksjomaty równości nie są podstawieniami tautologii rachunku zdań. W logice tej w języku mogą być jednak nie tylko symbole predykatów, lecz również symbole funkcyjne. Zadanie pozostaje poprawne.)
(Oczywiście rozważana tu "logika pierwszego rzędu" nie ma wbudowanego standardowego rozumienia równości, gdyż wtedy zadanie jest błędne. Aksjomaty równości nie są podstawieniami tautologii rachunku zdań. W logice tej w języku mogą być jednak nie tylko symbole predykatów, lecz również symbole funkcyjne. Zadanie pozostaje poprawne.)
-
- Użytkownik
- Posty: 2283
- Rejestracja: 14 cze 2011, o 11:34
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 88 razy
- Pomógł: 351 razy
Re: Formuła bez kwantyfikatorów w logice pierwszego rzędu
Zatrzymajmy się na chwilę przy tym. Zrobiłbym to tak:
Najpierw udowodniłbym, że zbiór formuł atomowych jest przeliczalny (myślę, że dowód nie jest trudny, więc go pominę). Niech \(\displaystyle{ (D_n)}\) będzie równowartościowym ciągiem wszystkich formuł atomowych, a \(\displaystyle{ (p_n)}\) równowartościowym ciągiem wszystkich zmiennych zdaniowych. Określam przez rekursję strukturalną funkcję \(\displaystyle{ A}\) na zbiorze wszystkich formuł bez kwantyfikatorów danego języka pierwszego rzędu - wartościami są formuły rachunku zdań.
\(\displaystyle{ A(D_n)=p_n}\)
\(\displaystyle{ A(\neg D)=\neg A(D)}\)
\(\displaystyle{ A(D\Rightarrow E)=A(D)\Rightarrow A(E)}\)
Wówczas \(\displaystyle{ A(B)}\) jest formułą rachunku zdań, której podstawieniem jest formuła \(\displaystyle{ B}\).
Czy jest to dobre podejście?
Niestety nie wiem w tej chwili, jak zbudować ten model. Mogę prosić o więcej szczegółów?Skoro \(\displaystyle{ A}\) nie jest tautologią, istnieje wartościowanie jej zmiennych zdaniowych przy którym \(\displaystyle{ A}\) jest fałszywa. Używając tego wartościowania budujemy model \(\displaystyle{ M}\), w którym formuła \(\displaystyle{ B}\) nie jest prawdziwa. (Można nawet zbudować model \(\displaystyle{ M}\) skończony).
-
- Użytkownik
- Posty: 609
- Rejestracja: 10 lis 2009, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 135 razy
Re: Formuła bez kwantyfikatorów w logice pierwszego rzędu
Tak.
Przykład: załóżmy, że \(\displaystyle{ B=P(x,y,z)\land Q(z,x)}\), zaś \(\displaystyle{ A(B) = p\land q}\). \(\displaystyle{ p\land q}\) nie jest tautologią, o czym świadczy wartościowanie \(\displaystyle{ p=q=0}\). Tworzymy model \(\displaystyle{ M}\) o uniwersum złożonym z \(\displaystyle{ a,b,c}\) i określamy w nim interpretację predykatów \(\displaystyle{ P,Q}\) tak, że \(\displaystyle{ P^M(a,b,c)}\) i \(\displaystyle{ Q^M(c,a)}\) mają wartość logiczną zero (tę samą, co zmienne \(\displaystyle{ p,q}\) przy wartościowaniu, dla którego formuła \(\displaystyle{ A(B)}\) ma wartość zero). Wtedy oczywiście formuła \(\displaystyle{ B}\) nie jest prawdziwa w modelu \(\displaystyle{ M}\), gdyż trójka \(\displaystyle{ a,b,c}\) jej nie spełnia.matmatmm pisze: ↑31 gru 2020, o 13:23Niestety nie wiem w tej chwili, jak zbudować ten model. Mogę prosić o więcej szczegółów?Skoro \(\displaystyle{ A}\) nie jest tautologią, istnieje wartościowanie jej zmiennych zdaniowych przy którym \(\displaystyle{ A}\) jest fałszywa. Używając tego wartościowania budujemy model \(\displaystyle{ M}\), w którym formuła \(\displaystyle{ B}\) nie jest prawdziwa. (Można nawet zbudować model \(\displaystyle{ M}\) skończony).
-
- Użytkownik
- Posty: 2283
- Rejestracja: 14 cze 2011, o 11:34
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 88 razy
- Pomógł: 351 razy
Re: Formuła bez kwantyfikatorów w logice pierwszego rzędu
Zdecydowałem się zdefiniować ten model jako przeliczalny tzn. uniwersum \(\displaystyle{ U}\) jako zbiór liczb naturalnych.
Dla każdego symbolu relacyjnego \(\displaystyle{ n}\) zmiennych \(\displaystyle{ P_k^n}\) oraz \(\displaystyle{ i_1,\ldots,i_n\in U=\NN}\) określam
\(\displaystyle{ (P^n_k)^M(i_1,\ldots,i_n) :\iff \nu(A(P^n_k(x_{i_1},\ldots,x_{i_n})))=1,}\)
gdzie \(\displaystyle{ \nu}\) jest wcześniej znalezionym wartościowaniem. Udowodniłem, że gdy język nie zawiera stałych ani symboli funkcyjnych, to ciąg \(\displaystyle{ s=(1,2,3,\ldots)}\) spełnia formułę \(\displaystyle{ B}\) w tym modelu wtedy i tylko wtedy, gdy \(\displaystyle{ \nu(A(B))=1}\).
To wystarcza dla tezy zadania, ale pod tym dodatkowym założeniem, że nie ma stałych ani symboli funkcyjnych. Pytanie czy wtedy, gdy stałe lub symbole funkcyjne są, to moja definicja relacji nie wymaga modyfikacji i jak zdefiniować stałe i funkcje?
Dla każdego symbolu relacyjnego \(\displaystyle{ n}\) zmiennych \(\displaystyle{ P_k^n}\) oraz \(\displaystyle{ i_1,\ldots,i_n\in U=\NN}\) określam
\(\displaystyle{ (P^n_k)^M(i_1,\ldots,i_n) :\iff \nu(A(P^n_k(x_{i_1},\ldots,x_{i_n})))=1,}\)
gdzie \(\displaystyle{ \nu}\) jest wcześniej znalezionym wartościowaniem. Udowodniłem, że gdy język nie zawiera stałych ani symboli funkcyjnych, to ciąg \(\displaystyle{ s=(1,2,3,\ldots)}\) spełnia formułę \(\displaystyle{ B}\) w tym modelu wtedy i tylko wtedy, gdy \(\displaystyle{ \nu(A(B))=1}\).
To wystarcza dla tezy zadania, ale pod tym dodatkowym założeniem, że nie ma stałych ani symboli funkcyjnych. Pytanie czy wtedy, gdy stałe lub symbole funkcyjne są, to moja definicja relacji nie wymaga modyfikacji i jak zdefiniować stałe i funkcje?
Ostatnio zmieniony 2 sty 2021, o 21:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 609
- Rejestracja: 10 lis 2009, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 135 razy
Re: Formuła bez kwantyfikatorów w logice pierwszego rzędu
Wartość logiczna formuły zdaniowej dla danego wartościowania zmiennych zależy tylko od wartości zmiennych zdaniowych w tej formule. Dlatego można zbudować model skończony jak wyżej. Jeśli są symbole funkcyjne, pokombinuj z algebrą termów w danym języku i na niej określ odpowiednio predykaty, zgodnie z zadanym wartościowaniem zmiennych zdaniowych. Również w tym przypadku można zbudować model skończony.