Logika dla informatyków/Ćwiczenia 4: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 8: | Linia 8: | ||
kwantyfikatorowej <math>q</math> definiujące porządek liniowy o mocy <math>2^q.</math> | kwantyfikatorowej <math>q</math> definiujące porządek liniowy o mocy <math>2^q.</math> | ||
}} | }} | ||
{{cwiczenie|2|| | |||
Adaptując dowód Faktu [[#qq]]udowodnić, że struktury | Adaptując dowód Faktu [[#qq]]udowodnić, że struktury | ||
<math>\<\{1-1/n | n=1,2,\dots\},\leq\></math> oraz | <math>\<\{1-1/n | n=1,2,\dots\},\leq\></math> oraz | ||
<math>\<\bigcup_{n=1}^\infty\{1-1/n,1+1/n,3-1/n\},\leq\></math>, gdzie <math>\leq</math> jest | <math>\<\bigcup_{n=1}^\infty\{1-1/n,1+1/n,3-1/n\},\leq\></math>, gdzie <math>\leq</math> jest w obu wypadkach standardowym porządkiem liczb wymiernych, są elementarnie równoważne. | ||
w obu wypadkach standardowym porządkiem liczb wymiernych, są | |||
elementarnie równoważne. | |||
Wywnioskować stąd, że pojęcie dobrego porządku nie jest wyrażalne w logice | Wywnioskować stąd, że pojęcie dobrego porządku nie jest wyrażalne w logice | ||
pierwszego rzędu. (Zupełnie inny dowód tego faktu poznamy | pierwszego rzędu. (Zupełnie inny dowód tego faktu poznamy | ||
w Rozdziale [[#zwarciig\leftrightarrowwi]]. | w Rozdziale [[#zwarciig\leftrightarrowwi]].}} | ||
{{cwiczenie|3|| | |||
Niech <math>R</math> będzie jednoargumentowym symbolem relacyjnym. | |||
Udowodnić, że klasa wszystkich takich struktur </math>\mathfrak A=\langle | Udowodnić, że klasa wszystkich takich struktur </math>\mathfrak A=\langle | ||
A,R\rangle</math>, że <math>|R|=|A- R|</math>, nie jest aksjomatyzowalna żadnym zbiorem | A,R\rangle</math>, że <math>|R|=|A- R|</math>, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.}} | ||
zdań pierwszego rzędu. | |||
{{cwiczenie|4|| | |||
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów | |||
<math>\mathfrak A=\langle A,E\rangle,</math> w których istnieją dwa | <math>\mathfrak A=\langle A,E\rangle,</math> w których istnieją dwa | ||
wierzchołki o równych sobie, skończonych stopniach, nie jest | wierzchołki o równych sobie, skończonych stopniach, nie jest | ||
aksjomatyzowalna żadnym zdaniem pierwszego rzędu. | aksjomatyzowalna żadnym zdaniem pierwszego rzędu.}} | ||
{{cwiczenie|5|| | |||
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów | |||
<math>\mathfrak A=\langle A,E\rangle,</math> których każdy skończony podgraf jest planarny, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu. }} | |||
{{cwiczenie|6|| | |||
wszystkie skończone klasy abstrakcji mają parzystą moc, nie jest | Pokazać, że klasa wszystkich relacji równoważności, których wszystkie skończone klasy abstrakcji mają parzystą moc, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu. }} | ||
aksjomatyzowalna żadnym zdaniem pierwszego rzędu. | |||
{{cwiczenie|7|| | |||
Dane są dwie struktury relacyjne </math>\mathfrak A=\langle | Dane są dwie struktury relacyjne </math>\mathfrak A=\langle | ||
U,R^\mathfrak A\rangle</math> i <math>\mathfrak B=\langle U,R^\mathfrak B\rangle</math> | U,R^\mathfrak A\rangle</math> i <math>\mathfrak B=\langle U,R^\mathfrak B\rangle</math> nad sygnaturą złożoną z jednego dwuargumentowego symbolu | ||
nad sygnaturą złożoną z jednego dwuargumentowego symbolu | relacyjnego. Ich nośnikiem jest <math>U=\{1,2,\dots,15\}</math>, relacja <math>R^\mathfrak A(x,y )</math> zachodzi \wtw, gdy <math>x|y</math>, a relacja <math>R^\mathfrak B(x,y )</math> \wtw, gdy <math>x\equiv y\pmod 2.</math> | ||
relacyjnego. Ich nośnikiem jest | |||
<math>U=\{1,2,\dots,15\}</math>, relacja <math>R^\mathfrak A(x,y )</math> zachodzi \wtw, gdy | |||
<math>x|y</math>, a relacja <math>R^\mathfrak B(x,y )</math> \wtw, gdy <math>x\equiv y\pmod 2.</math> | |||
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie | Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie <math>\var\varphi</math> takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math> }} | ||
<math>\var\varphi</math> takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math> | |||
{{cwiczenie|8|| | |||
struktury relacyjne <math>\mathfrak A</math> i <math>\mathfrak B</math> | Dane są dwie sześcioelementowe struktury relacyjne <math>\mathfrak A</math> i <math>\mathfrak B</math> nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane: | ||
nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. | |||
Struktury są narysowane poniżej jako grafy skierowane: | |||
<span id=""/> <math> \begi\prooftree array \justifies c|c \using \textrm{(W )}\endprooftree | <span id=""/> <math> \begi\prooftree array \justifies c|c \using \textrm{(W )}\endprooftree | ||
| Linia 102: | Linia 95: | ||
</math> | </math> | ||
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie | Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie math>\var\varphi</math> | ||
takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math> | takie, że <math>\mathfrak A\models\var\varphi</math> i <math>\mathfrak B\not\models\var\varphi.</math>}} | ||
\end{small} | \end{small} | ||
Wersja z 14:47, 25 wrz 2006
Linek z wykładu 8 do cwiczenia 4. Nazwa linku: "c"
Ćwiczenie 1
Wykazać, że dla dostatecznie dużych istnieje zdanie o randze kwantyfikatorowej definiujące porządek liniowy o mocy
Ćwiczenie 2
Adaptując dowód Faktu #qqudowodnić, że struktury Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{1-1/n | n=1,2,\dots\},\leq\>} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\bigcup_{n=1}^\infty\{1-1/n,1+1/n,3-1/n\},\leq\>} , gdzie jest w obu wypadkach standardowym porządkiem liczb wymiernych, są elementarnie równoważne.
Wywnioskować stąd, że pojęcie dobrego porządku nie jest wyrażalne w logice pierwszego rzędu. (Zupełnie inny dowód tego faktu poznamy
w Rozdziale #zwarciig\leftrightarrowwi.Ćwiczenie 3
{{{3}}}
Ćwiczenie 4
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest
aksjomatyzowalna żadnym zdaniem pierwszego rzędu.Ćwiczenie 5
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów
których każdy skończony podgraf jest planarny, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.Ćwiczenie 6
Pokazać, że klasa wszystkich relacji równoważności, których wszystkie skończone klasy abstrakcji mają parzystą moc, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.
Ćwiczenie 7
{{{3}}}
Ćwiczenie 8
{{{3}}}
\end{small}
