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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Aneczka (dyskusja | edycje)
700 edycji
Nie podano opisu zmian
Aneczka (dyskusja | edycje)
700 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
Odniesienia z wykł. 3:
Odniesienia z wykł. 3:


<span id="rJ1"> Ćwiczenie 3</span>
<span id="rJ2"> Ćwiczenie 5 </span>






{{cwiczenie|1||
Udowodnić, że logiki trójwartościowe Heytinga-Kleene-Łukasiewicza, Bochvara i Sobocińskiego spełniają prawa de Morgana.
}}


<span id="rJ2"> Ćwiczenie 5 </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>
 
}}
 
sbsection*{Ćwiczenia}\begin{small}
#
Udowodnić, że logiki trójwartościowe Heytinga-Kleene-Łukasiewicza,
Bochvara i Sobocińskiego spełniają prawa de Morgana.
#
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
{{cwiczenie|3|| 
kwantyfikatorowej <math>q</math>. Udowodnić, że każde dwie struktury o mocy co
<span id="rJ1" \>  Udowodnić, że zbiór tautologii logiki pierwszego rzędu nad
najmniej <math>q</math> nad powyższą sygnaturą są <math>q</math>-elementarnie równoważne.
sygnaturą składającą się tylko z równości jest rozstrzygalny.
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>


{{wskazowka|||
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  
#Zbadać złożoność obliczeniową algorytmu zaproponowanego powyżej  

Wersja z 11:53, 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.

((cwiczenie|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

{{{3}}}
  1. 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 równości jest {\sc Pspace}-zupełny.

  1. 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}

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_dla_informatyków/Ćwiczenia_13&oldid=56555”