論理包含の表記 のソース

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

%indent
* 概要 [#d267ecf3]
;,論理包含は、歴史的には記号$$ \supset $$で表記されている。
;,他方、集合論でも集合の包含の表記にも記号$$ \supset $$が使われる。
;,ところが、命題$$ p $ \supset $ q $$に対し、$$ p $$と$$ q $$に関連深い集合$$ P $$と$$ Q $$を考えると$$ P $ \subseteq $ Q $$と真逆な向きになり、
;,見た目的に紛らわしいことが起こる。
 
;,以下では、その仕組みを簡単に纏める。
;,なお、混同を避けるため、集合包含は記号$$ \supset $$で表記し、
;,論理包含は今日において良く用いられる$$ \Rightarrow $$で表記する。
 
* 命題と集合の対応付け [#q99ec54e]
;,一般に、集合は命題を使って命題が真となる要素で定義できる。
;,命題$$ p(x) $$による定義は内包表記で集合$$ P $ = $ \{ $ x $ | $ p(x) $ \} $$と書ける。
;,これにより、命題と集合を一対一で対応づけできる。
 
;,例えば、命題$$ p(x) $$が「$$ x $$が偶数」であれば、対応する集合$$ P $ = $ \{ $ x $ | $ x $$が偶数$$ \} $$を必ず唯一に作れる。
 
;,簡潔のため、命題と集合の対応関係を記号$$ \sim $$で表記する。
#ceq(e)
    $$ p(x) $ \sim $ \{ $ x $ | $ p(x) $ \} $$
#ceq(d)
 
;,逆に、集合$$ P $$があると、対応する命題$$ p(x) $$の真偽は、$$ x $$が集合$$ P $$に属すか否かで決まる。
#ceq(e)
    $$ p(x) $ \;\Leftrightarrow\; $ x $ \in $ P $ \;\Leftrightarrow\; $ x $ \in $ \{ $ x $ | $ p(x) $ \} $$
#ceq(d)
 
 
;,特に$$ p(x) $ = $ x $ \in $ P $$のとき、
#ceq(e)
    $$ x $ \in $ P $ \sim $ P $$
#ceq(d)
 
* 真偽値に対応する集合 [#ce745b4e]
** 恒偽 [#b60f0514]
;,$$ p(x) $ = $ F $$、すなわち、$$ p(x) $$が$$ x $$に関わらず恒偽の場合、
;,対応する集合$$ P $ = $ \{ $ x $ | $ F $ \} $$は要素を１つも持たないので、空集合$$ \varnothing $$となる。
;,よって、恒偽は空集合に対応する。
#ceq(e)
    $$ F $ \sim $ \{ $ x $ | $ F $ \} $ = $ \varnothing $$
#ceq(d)
 
** 恒真 [#ac7c3e3b]
;,$$ p(x) $ = $ T $$、すなわち、$$ p(x) $$が$$ x $$に関わらず恒真の場合、
;,対応する集合$$ P $ = $ \{ $ x $ | $ T $ \} $$は全ての$$ x $$を要素として持つので、$$ P $$は全体集合$$ \overline\varnothing $$となる。
;,よって、恒真は全体集合に対応する。
#ceq(e)
    $$ T $ \sim $ \{ $ x $ | $ T $ \} $ = $ \overline\varnothing $$
#ceq(d)
 
;,$$ x $ \in $ X $$で考えている場合、$$ X $$が全体集合になるので、$$ P $ $ = $ \{ $ x $ | $ T $ \} $ = $ X $$が成り立つ。
;,対応式で書くと
#ceq(e)
    $$ T $ \sim $ X $$
#ceq(d)
;,例えば、$$ x $ \in $ X $$で考えている場合、$$ x $ \in $ X $ \Leftrightarrow $ T $$が成り立つ。
;,$$ T $$に代入した$$ x $ \in $ X $ \sim $ X $$も命題と集合の対応関係から自明的に成り立つ。
 
* 基本論理演算に対応する集合演算 [#qf7562c6]
** 論理否定 [#d2c52411]
 
;,命題$$ r(x) $ = $ \lnot $ p(x) $$に対応する集合は$$ R $ = $ \{ $ x $ | $ \lnot $ p(x) $ \} $$と書ける。
;,一方で、内包表記で記述される条件を満たさない集合は補集合であるため、$$ R $ = $ \overline{P} $$と書ける。
;,よって、論理否定は補集合に対応する。
#ceq(e)
    $$ \lnot $ p(x) $ \sim $ \{ $ x $ | $ \lnot $ p(x) $ \} $ = $ \overline{\{\, x \,|\, p(x) \,\}} $$
#ceq(d)
 
;,例えば、真偽値に関して、次の計算が容易に確認できる。
#ceq(e)
    $$ T $ \sim $ \{ $ x $ | $ T $ \} $ = $ \{ $ x $ | $ \lnot $ F $ \} $ = $ \overline{\{\, x \,|\, F \,\}} $ = $ \overline\varnothing $$
#ceq(d)
 
** 論理和 [#q76c10c3]
 
;,命題$$ r(x) $ = $ p(x) $ \lor $ q(x) $$に対応する集合は$$ R $ = $ \{ $ x $ | $ p(x) $ \lor $ q(x) $ \} $$と書ける。
;,一方で、集合としてみた場合、任意の$$ x $$は$$ P $$と$$ Q $$の片方にでも属せば集合$$ R $$の要素となるため、$$ R $ = $ P $ \cup $ Q $$と書ける。
;,よって、論理和は和集合に対応する。
#ceq(e)
    $$ p(x) $ \lor $ q(x) $ \sim $ \{ $ x $ | $ p(x) $ \lor $ q(x) $ \} $ = $ P $ \cup $ Q $$
#ceq(d)
 
** 論理積 [#q76c10c3]
 
;,命題$$ r(x) $ = $ p(x) $ \land $ q(x) $$に対応する集合は$$ R $ = $ \{ $ x $ | $ p(x) $ \land $ q(x) $ \} $$と書ける。
;,一方で、集合としてみた場合、任意の$$ x $$は$$ P $$と$$ Q $$の両方に属して初めて集合$$ R $$の要素となるため、$$ R $ = $ P $ \cap $ Q $$と書ける。
;,よって、論理積は積集合に対応する。
#ceq(e)
    $$ p(x) $ \land $ q(x) $ \sim $ \{ $ x $ | $ p(x) $ \land $ q(x) $ \} $ = $ P $ \cap $ Q $$
#ceq(d)
 
* 論理包含と部分集合 [#e8d0c1ab]
 
;,命題$$ r(x) $ = $ [ $ p(x) $ \Rightarrow $ q(x) $ ] $$の集合表記を考える。
;,論理包含は論理否定と論理和を使って、$$ p(x) $ \Rightarrow $ q(x) $ = $ \lnot $ p(x) $ \lor $ q(x) $$と書ける
;,そのため、$$ r(x) $$に対応する集合$$ R $$は以下に計算できる。
#ceq(e)
    $$ r(x) $ \sim $ R $$
#ceq(c)
    $$ = $ \{ $ x $ | $ p(x) $ \Rightarrow $ q(x) $ \} $$
    $$ = $ \{ $ x $ | $ \lnot $ p(x) $ \lor $ q(x) $ \} $$
#ceq(e)
#ceq(c)
    $$ = $ \{ $ x $ | $ \lnot $ p(x) $ \} $ \cup $ \{ $ x $ | $ q(x) $ \} $$
    $$ = $ \overline{\{\, x \,|\, p(x) \,\}} $ \cup $ \{ $ x $ | $ q(x) $ \} $$
#ceq(e)
#ceq(c)
    $$ = $ \overline{P} $ \cup $ Q $$
#ceq(d)
;,これに端的に表す専用の集合演算記号は、一般的には用意されてない。
 
;,そこで、$$ r(x) $$が恒真のとき、$$ P $$と$$ Q $$の関係について考える。
;,$$ r(x) $ = $ T $ \sim $ \overline\varnothing $$より、$$ R $ = $ \overline{P} $ \cup $ Q $ = $ \overline\varnothing $$となる。
;,両辺の補集合を取ると、$$ P $ \cap $ \overline{Q} $ = $ \varnothing $$が言える。
;,これは、$$ Q $$の外側に$$ P $$の要素が存在しない意味であるため、$$ P $$が$$ Q $$に集合的に包含される関係になる。
 
#ceq(e)
    $$ p(x) $ \Rightarrow $ q(x) $ \quad $ \Leftrightarrow $ \quad $ P $ \subseteq $ Q $$
#ceq(d)
 
;,もし、論理包含の記号を$$ \Rightarrow $$の代わりに$$ \supset $$を用いた場合、
;,論理式と集合式で$$ \supset $$と$$ \subset $$の両方が出て、紛らわしい見た目になってしまう。
#ceq(e)
    $$ p(x) $ \supset $ q(x) $ \quad$ \Leftrightarrow $ \quad$ P $ \subseteq $ Q $$
#ceq(d)