Formuła bez kwantyfikatorów w logice pierwszego rzędu

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
matmatmm
Użytkownik
Użytkownik
Posty: 2280
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Formuła bez kwantyfikatorów w logice pierwszego rzędu

Post autor: matmatmm »

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.
krl
Użytkownik
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

Post autor: krl »

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.)
matmatmm
Użytkownik
Użytkownik
Posty: 2280
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

Post autor: matmatmm »

krl pisze: 31 gru 2020, o 10:01 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}\).
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?
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).
Niestety nie wiem w tej chwili, jak zbudować ten model. Mogę prosić o więcej szczegółów?
krl
Użytkownik
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

Post autor: krl »

matmatmm pisze: 31 gru 2020, o 13:23 Czy jest to dobre podejście?
Tak.
matmatmm pisze: 31 gru 2020, o 13:23
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).
Niestety nie wiem w tej chwili, jak zbudować ten model. Mogę prosić o więcej szczegółów?
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
Użytkownik
Użytkownik
Posty: 2280
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

Post autor: matmatmm »

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?
Ostatnio zmieniony 2 sty 2021, o 21:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
krl
Użytkownik
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

Post autor: krl »

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