集合と論理

このページでは、集合の要素数の数え方、命題と逆・裏・対偶、ド・モルガンなどの論理演算の法則、カルノー図を使った論理式の簡略化がわかります。

  • 記号の書き方(このメモのルール):

    • 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
    • 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
  • 一言で言うと:

    • 「ものの集まり(集合)」と「正しいか正しくないか(命題)」を、記号と計算で扱う話。論理回路、SQLの条件、プログラムのif文の土台になる。

集まりを扱う(集合論理)→ 真偽を扱う(命題と論理)→ 計算のルール(論理演算)→ 式を短くする(論理式の簡略化)

覚え方の軸

  • 集合と論理は同じものの言い換え:
    • 積集合∩=論理積AND(・、∧)、和集合∪=論理和OR(+、∨)、補集合=否定NOT(¬)、対称差Δ=排他的論理和XOR(⊕)
  • 数えるときは「足して、重なりを引く」:
    • n(A∪B)=n(A)+n(B)−n(A∩B)
  • 条件文p→qは「真→偽」のときだけ偽:
    • 元の文と対偶は真偽が必ず一致する。逆と裏は一致するとは限らない
  • 式を短くする方法は2つ:
    • 演算則(特にド・モルガン)で変形する、またはカルノー図で「1」のかたまりをまとめる

集合論理:ものの集まりを記号で扱う

  • 集合:
    • ある条件を満たし、他のものとはっきり区別できるものの集まり
  • 要素:
    • 集合に属するもの。元(げん)ともいう
  • 空集合:
    • 要素数が0の集合。記号は ∅
  • 有限集合:
    • 要素が有限個の集合
  • 無限集合:
    • 要素が無限個の集合
  • 部分集合:
    • 1つの集合の中に考える、いくつかの要素の集まり
    • 要素数がN個の集合の部分集合は、空集合と自分自身を含めて全部で 2ᴺ個
    • 例:
      • U={1,2,3}の部分集合は 2³=8個
  • 真部分集合:
    • AがBの部分集合で、AとBが一致しないとき、AをBの真部分集合という
  • べき集合:
    • 部分集合を全部集めて、それを要素にした集合
    • 例:
      • U={1,2,3}のべき集合={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
  • 差集合 A−B:
    • Aの要素で、Bの要素ではないものの集合(AからBを取り除いた残り)
    • A−B=A∩Bᶜ とも書ける(★過去問で問われた)
  • 対称差 A△B:
    • 「Aにあって Bにない」か「Bにあって Aにない」ものの集合(どちらか一方にだけあるもの)
    • A△B=(A−B)∪(B−A)=(A∩Bᶜ)∪(Aᶜ∩B)
    • 論理演算の排他的論理和にあたる
  • 補集合の書き方:
    • 集合Aの補集合は、上に線を引いて表すのが一般的だが、Aᶜ と書くこともある
  • 集合の要素数 n(A):
    • 集合Aの要素の数
  • 和集合の要素数の公式(★)
    • 2つの場合:
      • n(A∪B)=n(A)+n(B)−n(A∩B)
    • 3つの場合:
      • n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(C∩A)+n(A∩B∩C)
    • イメージ:
      • 全部足すと重なりを二重に数えてしまうので、その分を引く
  • 例:
    • 50人のクラスで、犬を飼っている人が20人、猫を飼っている人が15人、どちらも飼っていない人が22人のとき、両方飼っている人は?
    • n(A∪B)=50−22=28
    • 28=20+15−n(A∩B) なので、n(A∩B)=7人
    • 「どちらも飼っていない」=n(Aᶜ∩Bᶜ)=n((A∪B)ᶜ)。これはド・モルガンの法則

命題と論理:正しいか正しくないかを記号で扱う

  • 命題:
    • 1つの判断や主張を記号や文章で表したもので、真(True)か偽(False)かがはっきり決まるもの
    • 例:
      • 「今日は暑い」は人によって感じ方が違うので命題ではない。「7は奇数である」は真の命題、「9は素数である」は偽の命題
    • ふつう p、q などの記号で表す
  • 条件命題(命題関数):
    • 変数xを含み、xの値によって真偽が決まる命題。p(x)、q(x)と書く(変数が2つならp(x,y))
    • 例:
      • 「xは偶数である」は、x=4なら真、x=3なら偽
  • 複合命題(合成命題):
    • 複数の命題を「かつ」「又は」などで結んだ命題
種類 意味 記号 真になるとき
連言命題(合接命題) pかつq p∧q 両方とも真のときだけ真
選言命題(隣接命題) p又はq p∨q 少なくとも一方が真なら真(両方偽のときだけ偽)
否定命題 pでない ¬p pが偽なら真
条件文(含意命題) pならばq p→q pが真でqが偽のときだけ偽、それ以外は真
双条件文 pならばq、かつ、qならばp p↔q(p≡q) pとqの真偽が同じなら真
  • 真理値表:
    • 命題の真偽の組合せと、その結果を一覧にした表。真を1(T)、偽を0(F)で書く
  • 真理集合:
    • 命題が真になる範囲を、集合の図(ベン図)で表したもの
  • 例:
    • p:雨が降る、q:風が強い、とすると、「雨が降らず、風も強くない」は ¬p∧¬q(pもqも偽のときだけ真)
  • 含意:
    • 「真→偽」のときだけ結果が偽になる演算(→のこと)
  • p→qの読みかえ:
    • 「pであってqでない、ということはない」と考える
    • p→q = ¬(p∧¬q)= ¬p∨q(ド・モルガンで展開)
  • 前件と後件:
    • 条件文p→qのpを前件、qを後件という
  • 原子論理式:
    • 論理式を組み立てている p や q のような、いちばん小さい論理式
  • トートロジー:
    • 原子論理式の真偽にかかわらず、常に真になる論理式(例:p∨¬p)
  • 矛盾式:
    • 常に偽になる論理式(例:p∧¬p)
  • 逆・裏・対偶(★)
名前 形 元の文(p→q)と真偽が一致するか
元の文 p→q −
逆 q→p 一致するとは限らない
裏 ¬p→¬q 一致するとは限らない
対偶 ¬q→¬p 必ず一致する
  • 覚え方:
    • 逆は入れかえ、裏は否定、対偶は入れかえて否定。逆と裏は、互いに対偶の関係なので、逆と裏どうしは真偽が一致する
  • 例(推論問題):
    • 前提:
      • 毎日、電車かバスのどちらか一方で通勤する。電車のときは必ず本を読み、バスのときは必ず音楽を聴く
    • 「電車→本を読む」の対偶は「本を読まない→電車ではない」。電車でなければバスなので、「本を読まない日はバスに乗っている」は正しい
    • 「本を読む日は電車に乗っている」は逆なので、正しいとはいえない(バスで音楽を聴きながら本も読む日もありうる)

論理演算:計算のルール

  • 基本論理演算:
    • 論理積演算(AND)、論理和演算(OR)、否定演算(NOT)の3つ。この3つの基本論理回路を組み合わせれば、いろいろな論理回路を作れる
  • 演算記号の対応(どちらの記号で出ても計算できるようにする)
演算 論理演算の記号 集合演算の記号
論理積 ・ 又は ∧ ∩
論理和 + 又は ∨ ∪
否定 上線 又は ¬ 上線 又は ᶜ
排他的論理和 ⊕ Δ(A△B=(A∩Bᶜ)∪(Aᶜ∩B))
  • 排他的論理和(XOR)の真理値表:
A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
  • XORの使いみち:
    • ビットの反転。反転したいビットだけ1にしたデータとXORをとる
    • 例:
      • 8ビットデータの下位4ビットを反転するには、0F(16進)=0000 1111 とXORをとる
      • 0101 1100 ⊕ 0000 1111 = 0101 0011
  • 演算則(論理演算と集合演算で同じ形になる)
    • べき等則:
      • A・A=A、A+A=A(集合:A∩A=A、A∪A=A)
      • べき等:
        • 同じ操作を何度繰り返しても同じ結果になること(例:A・A・A=A・A=A)
    • 交換の法則:
      • A・B=B・A、A+B=B+A
    • 結合の法則:
      • (A・B)・C=A・(B・C)、(A+B)+C=A+(B+C)
    • 分配の法則:
      • A・(B+C)=(A・B)+(A・C)
      • A+(B・C)=(A+B)・(A+C)(ふつうの数の計算では成り立たない形なので注意)
    • 吸収の法則:
      • A+(A・B)=A、A・(A+B)=A
    • ド・モルガンの法則(★):
      • ¬(A・B)=¬A+¬B、¬(A+B)=¬A・¬B
      • 集合:(A∩B)ᶜ=Aᶜ∪Bᶜ、(A∪B)ᶜ=Aᶜ∩Bᶜ
      • 覚え方:
        • 否定を中に入れると、ANDとORが入れかわる
    • その他:
      • A+0=A、A・0=0、A+1=1、A・1=A、A+¬A=1、A・¬A=0
      • 集合:A∪∅=A、A∩∅=∅、A∪U=U、A∩U=A、A∪Aᶜ=U、A∩Aᶜ=∅(∅:空集合、U:全体集合)

論理式の簡略化:同じ意味のまま式を短くする

  • 簡略化:
    • 与えられた論理式と等価な(同じ結果になる)、より短い論理式を求めること
  • 演算則を使う方法(例):
    • A・B+A・¬B+¬A・B を簡略化する
    • 手順:
      • ①べき等則で A・B をもう1つ足す(足しても値は変わらない)
      • ②A・B+A・¬B+¬A・B+A・B
      • ③第1・2項をAでくくり、第3・4項をBでくくる:A・(B+¬B)+B・(¬A+A)
      • ④B+¬B=1、¬A+A=1 なので:A+B
  • カルノー図:
    • 論理式を図(マス目)で表したもの
    • 手順:
      • ①論理式の各項にあたるマスに「1」、あたらないマスに「0」を入れる
      • ②「1」が縦か横に連続しているマスをまとめる
      • ③まとめた範囲で、真偽に関係なくなった変数を消す
    • 上の例:
      • A=1の行はBに関係なく1なので A、B=1の列はAに関係なく1なので B。合わせて A+B
  • 変数が4つのカルノー図:
    • 変数A,Bと変数C,Dに分けて、4行×4列の図で考える。行と列の並びは 00→01→11→10(隣どうしで1ビットだけ変わる順)
    • 図の端どうし(例えば左端の列と右端の列)もつながっているとみなしてまとめられる

混同しやすいペア

  • 差集合 A−B(Aだけにあるもの)/対称差 A△B(どちらか一方だけにあるもの)
  • 部分集合(自分自身も含む)/真部分集合(自分自身とは一致しない)
  • 部分集合(集まりの一部)/べき集合(部分集合を全部集めた集合。要素数は2ᴺ)
  • 逆(q→p)/裏(¬p→¬q)/対偶(¬q→¬p。これだけ元と必ず同じ真偽)
  • 連言(かつ、∧)/選言(又は、∨)
  • 条件文 p→q(真→偽のときだけ偽)/双条件文 p↔q(真偽が同じときだけ真)
  • トートロジー(常に真)/矛盾式(常に偽)
  • 論理和 OR(両方1でも1)/排他的論理和 XOR(両方1なら0)

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました