Logika dla informatyków/Ćwiczenia 13

Odniesienia z wykł. 3:

Ćwiczenie 5

Ćwiczenie 1

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

((cwiczenie|2|| Podać przykład zdania logiki pierwszego rzędu, które nie jest tautologią, ale jest prawdziwe we wszystkich strukturach $\mathfrak{𝔄}$ takich, że $A=ad(\mathfrak{𝔄}).$ }}

Ćwiczenie 3

{{{3}}}

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}