Logika dla informatyków/Ćwiczenia 13

Ćwiczenie 1

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

Ćwiczenie 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

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

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

Wskazówka

{{{3}}}

Ćwiczenie 4

Zbadać złożoność obliczeniową algorytmu zaproponowanego powyżej i udowodnić, że zbiór tautologii logiki pierwszego rzędu nad sygnaturą składającą się tylko z równości jest PSPACE-zupełny.

Ćwiczenie 4

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.

Wskazówka

{{{3}}}