基本情報技術者試験「述語論理」の問題
述語論理で「すべての x について P(x) が成り立つ」という命題の否定として正しいものはどれか。
アすべての x について P(x) が成り立たない
イすべての x について P(x) が成り立つ、と変わらない
ウある x が存在して P(x) が成り立たない
エある x が存在して P(x) が成り立つ
正解
ウ．ある x が存在して P(x) が成り立たない
「すべてのxでP(x)」が偽になるのは、反例が1つでもある場合である。否定は∃x ¬P(x)、すなわち『P(x)が成り立たないxが存在する』となり正しい。
?選択肢ごとの解説
ア ×『すべてのxでP(x)が成り立たない』は∀x ¬P(x)であり、1つの反例どころか全否定を要求するため元命題の否定より強すぎて誤りである。
イ ×否定して元と同じになることはあり得ず、量化子も否定も付けない論理的に誤った主張である。
ウ ○「すべてのxでP(x)」が偽になるのは、反例が1つでもある場合である。否定は∃x ¬P(x)、すなわち『P(x)が成り立たないxが存在する』となり正しい。
エ ×『あるxでP(x)が成り立つ』は∃x P(x)であり、元命題の否定ではなく一部成立を述べる別の命題である。
✎くわしく
量化子の否定では『∀の否定は∃、∃の否定は∀』と量化子が入れ替わり、述語部分が否定される。¬∀x P(x)≡∃x ¬P(x)、¬∃x P(x)≡∀x ¬P(x)。否定が内側に入ると量化子が反転する規則が核心である。
✓本番での押さえどころ
試験のコツ
『全部成り立つ』の否定は『成り立たないものが1つある(反例)』。量化子∀↔∃の反転を必ずセットで行う。
覚え方
全称命題は反例1つで崩れる=否定は『反例が存在する』、と反例の発想で覚える。
よくある誤り
量化子を変えず述語だけ否定して∀x ¬P(x)としてしまう誤りが最頻出。反例が1つあれば全称は崩れる点を意識する。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0087