Logika dla informatyków/Ćwiczenia 13

Odniesienia z wykł. 3:

Ćwiczenie 3

Ćwiczenie 5

sbsection*{Ćwiczenia}\begin{small}

Udowodnić, że logiki trójwartościowe Heytinga-Kleene-Łukasiewicza, Bochvara i Sobocińskiego spełniają prawa de Morgana.

Podać przykład zdania logiki pierwszego rzędu, które nie jest tautologią, ale jest prawdziwe we wszystkich strukturach $\mathfrak{𝔄}$ takich, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle A=ad(\mathfrak A\end{eqnarray*}.}

1. Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad

sygnaturą składającą się tylko z równości jest rozstrzygalny.

{\em Wskazówka:\/} Niech $\alpha$ będzie formułą o randze kwantyfikatorowej $q$. Udowodnić, że każde dwie struktury o mocy co najmniej $q$ nad powyższą sygnaturą są $q$-elementarnie równoważne. Wywnioskować stąd, że aby sprawdzić, czy $\alpha$ jest tautologią wystarczyć sprawdzić to w strukturach o mocy co najwyżej $q.$

1. Zbadać złożoność obliczeniową algorytmu zaproponowanego powyżej

iudowodnić, że zbiór tautologii logiki pierwszego rzędu nad sygnaturą składającą się tylko z równości jest {\sc Pspace}-zupełny.

1. Udowodnić, że zbiór tautologii logiki pierwszego

rzędu nad sygnaturą składającą się tylko z równości i skończenie wielu symboli stałych jest rozstrzygalny.

{\em Wskazówka:\/} Rozwiązać najpierw zadanie #rJ1, a stałe zasymulować jako relacjeunarne będące singletonami.

\end{small}