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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Aneczka (dyskusja | edycje)
700 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „.</math>” na „</math>.”
 
(Nie pokazano 6 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||
sbsection*{Ćwiczenia}\begin{small}
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.  
#
}}
Udowodnić, że logiki trójwartościowe Heytinga-Kleene-Łukasiewicza,
{{wskazowka|||
Bochvara i Sobocińskiego spełniają prawa de Morgana.
<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>}}
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\end{eqnarray*}.</math> 
#<span id="rJ1" \> Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad
sygnaturą składającą się tylko z&nbsp;równości jest rozstrzygalny. 
 
{\em Wskazówka:\/} 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>
 
 
#Zbadać złożoność obliczeniową algorytmu zaproponowanego powyżej
iudowodnić, że zbiór tautologii logiki pierwszego rzędu nad
sygnaturą składającą się tylko z&nbsp;równości jest {\sc Pspace}-zupełny.
 
#<span id="rJ2" \>  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.  
 
{\em Wskazówka:\/} Rozwiązać najpierw zadanie [[#rJ1]], a stałe  
zasymulować jako relacjeunarne będące singletonami.  
 
 
 
\end{small}

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”