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

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

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

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

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

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

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

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

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

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%よりも上です！

コピペテキスト

テキストをコピー

クイズをやり直す

都道府県のご当地クイズ

人気急上昇中

診断

海賊の賽HO診断

診断

修羅場ポイントHO診断

お絵描き診断

星を描いてわかる精神年齢

お絵描き診断

「x」の書き方で分かるあなたの偏差値

診断

きょうあなHO診断

もっとクイズを見る