Logika dla informatyków/Ćwiczenia 13: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Tprybick (dyskusja | edycje)
718 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu – „.</math>” na „</math>.”
 
(Nie pokazano 7 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
Odniesienia z wykł. 3:
{{cwiczenie|1||
Udowodnić, że logiki trójwartościowe Heytinga-Kleene-Łukasiewicza, Bochvara i Sobocińskiego spełniają prawa de Morgana.  
}}


<span id="rJ1"> Ćwiczenie 3</span>
{{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>.
}}


<span id="rJ1"></span>
{{cwiczenie|3||
Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad
sygnaturą składającą się tylko z równości jest rozstrzygalny.}}


{{wskazowka|||
<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>. 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>.
</div></div>}}




<span id="rJ2"> Ćwiczenie 5 </span>
{{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&nbsp;równości jest PSPACE-zupełny. }}
 
<span id="rJ2"></span>
{{cwiczenie|4||
Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad sygnaturą składającą się tylko z&nbsp;równości i skończenie wielu symboli stałych jest rozstrzygalny.
}}
{{wskazowka|||
<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 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 A=ad(𝔄).

Ć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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_dla_informatyków/Ćwiczenia_13&oldid=80329”