Logika dla informatyków/Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
m Zastępowanie tekstu – „.</math>” na „</math>.” |
||
| (Nie pokazano 1 wersji utworzonej przez jednego użytkownika) | |||
| Linia 4: | Linia 4: | ||
{{cwiczenie|2|| | {{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) | 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>. | ||
}} | }} | ||
| Linia 14: | Linia 14: | ||
{{wskazowka||| | {{wskazowka||| | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none"> | ||
Niech <math>\alpha</math> będzie formułą o randze kwantyfikatorowej <math>q</math>. | 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ą | 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>}} | ||
| Linia 28: | Linia 28: | ||
{{wskazowka||| | {{wskazowka||| | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | <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 | Rozwiązać najpierw zadanie [[#rJ1|3]], a stałe zasymulować jako relacje unarne będące singletonami.</div></div>}} | ||
Aktualna wersja na dzień 09:15, 5 wrz 2023
Ć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}}}
