論理学の色々 #論理学クイズ？

ビュー数3726平均正答率40.1%全問正解率1.3%

正答率などの反映は少し遅れることがあります。

1. 1-3は直観主義論理上で答えてください。以下のうち非妥当なのは？

• ￢∃x.P(x)->∀x.￢P(x)
• P->￢￢P
• ￢￢P->P

二重否定除去は必ずしも成り立ちませんが導入はいつでも妥当です。

2. 以下のうち非妥当なのは？

• P∨￢P
• ∀x.￢P(x)->￢∃x.P(x)
• (￢P∨Q)->P->Q

排中律は必ずしも成り立ちません。

3. LLPOを仮定した場合示せるのは？

• 実数の等号についての排中律
• WLPO
• 全ての実関数の連続性

LLPOは実数の等号についての排中律を導きます。

4. (ここからは古典的に答えてよいです。)再帰的述語の階層はなにと一致する？

• Π^0_1
• Σ^0_1
• Δ^0_1

ポストの定理のbase caseです。

5. では計算可枚挙述語は？

• Δ^0_1
• Π^0_1
• Σ^0_1

正解は「Σ^0_1」です！

6. 以下のうち選択公理が必要ないのは？(A,Bは集合でAは空でないとします。)

• A->Bに単射が飛ぶならB->Aに全射が飛ぶ。
• 可算集合の可算和は可算集合である。
• A->Bに全射が飛ぶならB->Aに単射が飛ぶ。

選択公理がない文脈で、濃度の議論が面倒くさい理由がわかるでしょう。

7. ツェルメロの集合論で存在が出ないのは？

• ω+ω
• 最小の非可算順序数
• ツェルメロの集合論でもZFで存在が証明できる全ての順序数の存在が言える。

置換公理図式がないと極限がとれません。

8. 以下のうちTuring completeでないのは？

• コンビネータ論理
• プッシュダウンオートマトン
• 型無しラムダ計算

正解は「プッシュダウンオートマトン」です！

9. 以下のうちTuring completeでないのは？

• Dual Stack Automata
• 単純型つきラムダ計算
• Queue Automata

単純型つきラムダ計算は無限ループの表現を失うためTuring completeになれません。

10. RCA_0で証明できないのは？

• 実数のArchimedian Property
• 全ての可算な体に対する代数閉包の存在
• Konigの補題(oはウムラウト)

正解は「Konigの補題(oはウムラウト)」です！

論理学の色々 #論理学クイズ？

0 / 10点

あなたの正答率は86.4%で、平均の40.1%よりも上です！

コピペテキスト

テキストをコピー

クイズをやり直す

都道府県のご当地クイズ

人気急上昇中

お絵描き診断

ハートを描いてモテ度を診断

お絵描き診断

「あ」と書いて分かるぶりっ子度診断

お絵描き診断

丸を書いて女子力診断

お絵描き診断

撃つ場所で診断

お絵描き診断

天才度診断

もっとクイズを見る