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 9: | Linia 9: | ||
}} | }} | ||
{{cwiczenie|2|| | |||
Podać przykład zdania logiki pierwszego rzędu, które nie jest tautologią, ale jest prawdziwe we wszystkich strukturach <math>\mathfrak A</math> takich, że <math>A=ad(\mathfrak A).</math> | Podać przykład zdania logiki pierwszego rzędu, które nie jest tautologią, ale jest prawdziwe we wszystkich strukturach <math>\mathfrak A</math> takich, że <math>A=ad(\mathfrak A).</math> | ||
}} | }} | ||
{{cwiczenie|3|| | <span id="rJ1"></span> | ||
{{cwiczenie|3|| | |||
sygnaturą składającą się tylko z równości jest rozstrzygalny. | Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad | ||
sygnaturą składającą się tylko z równości jest rozstrzygalny.}} | |||
{{wskazowka||| | {{wskazowka||| | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">__HIDDER__<div class="mw-collapsible-content" style="display:none"> | |||
Niech <math>\alpha</math> będzie formułą o randze kwantyfikatorowej <math>q</math>. Udowodnić, że każde dwie struktury o mocy co najmniej <math>q</math> nad powyższą sygnaturą są <math>q</math>-elementarnie równoważne. | Niech <math>\alpha</math> będzie formułą o randze kwantyfikatorowej <math>q</math>. Udowodnić, że każde dwie struktury o mocy co najmniej <math>q</math> nad powyższą sygnaturą są <math>q</math>-elementarnie równoważne. | ||
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>}} | |||
}} | }} | ||
{{cwiczenia|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. }} | |||
sygnaturą składającą się tylko z równości jest | |||
#<span id="rJ2" \> Udowodnić, że zbiór tautologii logiki pierwszego | #<span id="rJ2" \> Udowodnić, że zbiór tautologii logiki pierwszego | ||
Wersja z 11:57, 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}}}
}}
- 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}
