Logika dla informatyków/Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 23: | Linia 23: | ||
Wywnioskować stąd, że aby sprawdzić, czy <math>\alpha</math> jest tautologią wystarczyć sprawdzić to w strukturach o mocy co najwyżej <math>q.</math> | Wywnioskować stąd, że aby sprawdzić, czy <math>\alpha</math> jest tautologią wystarczyć sprawdzić to w strukturach o mocy co najwyżej <math>q.</math> | ||
</div></div>}} | </div></div>}} | ||
{{ | |||
{{cwiczenie|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. }} | 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. }} | ||
<span id="rJ2"></span> | |||
rzędu nad sygnaturą składającą się tylko z równości i skończenie | {{cwiczenie|4|| | ||
wielu symboli stałych jest rozstrzygalny. | 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. | ||
}} | |||
{ | {{wskazowka||| | ||
zasymulować jako relacjeunarne będące singletonami. | <div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Rozwiązać najpierw zadanie [[#rJ1|3]], a stałe zasymulować jako relacjeunarne będące singletonami.</div></div>}} | |||
Wersja z 12:00, 26 wrz 2006
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.
Ćwiczenie 2
Podać przykład zdania logiki pierwszego rzędu, które nie jest tautologią, ale jest prawdziwe we wszystkich strukturach takich, że
Ć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}}}
