集合・命題・述語論理

集合と命題は、データベース設計や仕様記述、SQL の WHERE 条件まで、多くの分野を支える基礎です。IPAの応用情報技術者試験シラバスでも、集合、命題、述語論理、量化子などが基礎理論の学習項目として示されています。

鳴海 理央

集合?
は和・積・差・補集合の4つの演算を覚えるところからです。
ベン図?
で書けば一発。

砂原 ニコ

ベン図、中学でやったやつ!
2つの円が重なるあれ?

緒方 ナオミ 先生

そう。
AP では3つの集合のベン図 (3円) で『どこに該当する要素は何個か』を求める問題がよく出るわ。

藤咲 まりあ

命題?
ってなんですかぁ?

鳴海 理央

真か偽かが定まる文のことです。
「3+5=8」は真の命題、「3+5=9」は偽の命題です。
一方、「xは3より大きい」はxが未指定のままでは真偽が定まらない述語です。
述語論理?
では変数を量化子（∀『すべての』、∃『ある』）で束縛して命題にします。

緒方 ナオミ 先生

AP では『すべての X について P(X) が成り立つ』『ある X が存在して Q(X) が成り立つ』の否定パターンが頻出。
¬∀x P(x) ⇔ ∃x ¬P(x) ね。

砂原 ニコ

うーん…とりあえず『すべて』の否定は『少なくとも一つは違う』ってこと?

鳴海 理央

そうそう。
日常の例えで覚えるのが一番。

集合と論理式を手順で解く

集合Aを「模試を受けた人」、集合Bを「復習をした人」とします。受験者40人のうち、Aが24人、Bが18人、両方に属する人が10人なら、少なくとも一方を行った人数は |A∪B|=24+18-10=32人 です。10人を引くのは、AとBの両方で二重に数えたからです。どちらも行っていない人数は、全体集合Uから補集合を取り、40-32=8人と求めます。

含意P→Qは、Pが真なのにQが偽のときだけ偽です。そのため、否定はP∧¬Qになります。「登録済みなら利用できる」の反例を探すなら、「登録済みなのに利用できない」ケースを探せばよい、という対応です。逆Q→Pや対偶¬Q→¬Pを混同しないでください。元の命題と常に同値なのは対偶で、逆は同値とは限りません。

試験での見分け方

• 「または」「少なくとも一方」は和集合、「かつ」「両方」は積集合と読む。
• 補集合は必ず全体集合Uを確認する。同じAでも、何を全体とするかでAの補集合は変わる。
• 量化子を否定するときは、∀と∃を入れ替えて中身も否定する。
• P→Qの否定を、誤って¬P→¬Qとしない。真理値表で「真→偽」の一行を確認する。

出題範囲の確認先: IPA「試験要綱・シラバス」