Logika dla informatyków/Ćwiczenia 4: 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 15 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
Linek z wykładu 8 do cwiczenia 4. Nazwa linku: "c"
Link z wykładu 8 do cwiczenia 4. Nazwa linku: "c"




Linia 6: Linia 6:
{{cwiczenie|1|c|
{{cwiczenie|1|c|
Wykazać, że dla dostatecznie dużych <math>q</math> istnieje zdanie o randze  
Wykazać, że dla dostatecznie dużych <math>q</math> istnieje zdanie o randze  
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>.
}}
}}
Adaptując dowód Faktu&nbsp;[[#qq]]udowodnić, że struktury
<math>\<\{1-1/n&nbsp;|&nbsp;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
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&nbsp;logice 
{{cwiczenie|2||
pierwszego rzędu.  (Zupełnie inny dowód tego faktu poznamy 
Adaptując dowód Faktu [[#qq]]udowodnić, że struktury <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 w obu wypadkach standardowym porządkiem liczb wymiernych, są elementarnie równoważne.  
w&nbsp;Rozdziale&nbsp;[[#zwarciig\leftrightarrowwi]]. )


#Niech <math>R</math> będzie jednoargumentowym symbolem relacyjnym.
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|8]].}}
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
zdań pierwszego rzędu.  


#Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów 
{{cwiczenie|3||
<math>\mathfrak A=\langle A,E\rangle,</math> w których istnieją dwa
Niech <math>R</math> będzie jednoargumentowym symbolem relacyjnym. 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 zdań pierwszego rzędu.}}
wierzchołki o równych sobie, skończonych stopniach, nie jest  
aksjomatyzowalna żadnym zdaniem pierwszego rzędu.  


#Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów  
{{cwiczenie|4|f|
<math>\mathfrak A=\langle A,E\rangle,</math> których każdy skończony podgraf jest planarny,  
Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów <math>\mathfrak A=\langle A,E\rangle</math>, w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.}}
nie jest 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. }}


#Pokazać, że klasa wszystkich relacji równoważności, których  
{{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&nbsp;jednego dwuargumentowego symbolu  
nad sygnaturą złożoną z&nbsp;jednego dwuargumentowego symbolu  
relacyjnego. Ich nośnikiem jest <math>U=\{1,2,\dots,15\}</math>, relacja <math>R^\mathfrak A(x,y )</math> zachodzi wtedy i tylko wtedy, 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&nbsp;<math>\mathfrak B\not\models\var\varphi.</math>  


#Dane są dwie sześcioelementowe  
{{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:  
[[Grafika:ldi_cw8.gif]]


<span id=""/> <math> \begi\prooftree array \justifies c|c \using \textrm{(W )}\endprooftree
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>.}}
 
\xymatrix
{
*{\ast}
\ar@{<->}[r]
\ar@{<->}[d]
\ar@{<->}[dr]
&
*{\ast}
\ar@{<->}[d]
\ar@{<->}[l]
\ar@{<->}[dl]
&
*{\ast}
&
\\
*{\ast}
\ar@{<->}[r]
&
*{\ast}
&
*{\ast}
&
*{\relax}
}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
\xymatrix
{
*{\ast}
\ar@{<->}[d]
\ar@{<->}[dr]
&
*{\ast}
&
*{\ast}
&
\\
*{\ast}
\ar@{<->}[r]
&
*{\ast}
&
*{\ast}
&
*{\relax}
}
\end{array}
</math>
 
Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie <math>\var\varphi</math>  
takie, że <math>\mathfrak A\models\var\varphi</math> i&nbsp;<math>\mathfrak B\not\models\var\varphi.</math>  
 
 
\end{small}

Aktualna wersja na dzień 09:35, 5 wrz 2023

Link z wykładu 8 do cwiczenia 4. Nazwa linku: "c"



Ćwiczenie 1

Wykazać, że dla dostatecznie dużych q istnieje zdanie o randze kwantyfikatorowej q, definiujące porządek liniowy o mocy 2q.

Ć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 8.

Ćwiczenie 3

Niech R będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur 𝔄=⟨A,R⟩, że |R|=|A−R|, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Ćwiczenie 4

Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów 𝔄=⟨A,E⟩, 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 𝔄=⟨A,E⟩, 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

Dane są dwie struktury relacyjne 𝔄=⟨U,R𝔄⟩ i 𝔅=⟨U,R𝔅⟩ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Ich nośnikiem jest U={1,2,…,15}, relacja R𝔄(x,y) zachodzi wtedy i tylko wtedy, gdy x|y, a relacja R𝔅(x,y) \wtw, gdy x≡y(mod2).

Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi} .

Ćwiczenie 8

Dane są dwie sześcioelementowe struktury relacyjne 𝔄 i 𝔅 nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:

Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi} .
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_dla_informatyków/Ćwiczenia_4&oldid=80723”