命題

命題とは

一般に式や文章で表された事柄で,正しいか否かが明確に決まるものを命題と言います.例えば,「8+8=16である」は真(true)の命題,「8+8=0である」は偽(false)の命題です.一方,「この小説は面白い」は命題ではありません.人によって意見が分かれてしまうからです.なお,真と偽を合わせて真理値と言います.

「pならばqである」という書き方,例えば「n=8ならばn+8=16である」というものも命題です.ここで,pはn=8であること,qはn+8=16であることに相当します.このとき,pを命題の仮定,qを結論と言います.この命題を記号で表すと, $n=8\Rightarrow n+8=16$ となります.

なお,この命題の「n+8=16ならばn=8」も成立します.よって,この命題は $n=8\Leftrightarrow n+8=16$ と表せます.

命題の文章が長い場合は,命題Pや命題Qというように,記号を割り振ることがあります.ここでPやQを命題変数と言います.また,真を1,偽を0と表します.

論理演算

コンピュータで処理を行うときの条件を与える場合,条件の真偽がはっきりしている命題を使います.実際には,命題を組み合わせたり命題を否定して条件を与えることがあり,これを論理演算と言います.具体例を次に示します.

論理演算の結果を表にしたものを真理値表と言います.上記に掲げた論理演算の真理値表を示します.

P 0101
Q 0011
P OR Q 0111
P AND Q 0001
NOT P 1010
P XOR Q 0110
P NOR Q 1000
P NAND Q 1110
$P\subset Q 1011

Column

論理演算には複数の記号があります.例えば,A OR Bは $A\vee B$ や $A\cup B$ とも表します.

文献によって異なりますが,公的試験ではどの記号を使うか,設問文に記載があるはずです.

Point

論理演算を用いて特定のビットを取りだしたり,ビットを反転させることができます.具体的として,ビット列011110を考えます.

下2桁を取りだしたい場合,上4桁が全て0になるようにすれば良いので,000011とAND演算をします.ビットを反転させる場合は,111111とXOR演算すると,100001になります.

論理代数(ブール代数)

論理代数は,論理式を用いて論理関係を代数的に求めることです.論理式は命題変数と論理記号で表現され,論理式自体は以下のように定義します.

それぞれの命題論理に0か1を対応させた関数を付加関数と言います.また,ある論理式において,全ての付加関数に対して1が成立するものを恒真式(トートロジー),0が成立するものを恒偽式と言います.

全ての論理式において成立する関係を論理式の基本公理と言います.

Point

上に示したド・モルガンの法則は2つの論理変数についてですが,これはn個の変数にも対応します.つまり, $\overline{A\cdot B\cdot\cdots\cdot Z}=\overline{A}+\overline{B}+\cdots +\overline{Z} \quad \overline{A+B+\cdots +Z}=\overline{A}\cdot\overline{B}\cdot\cdots\cdot\overline{Z}$ が成り立ちます。

また,上記の公式で $\cdot$ と $+$ を入れ替えたものが多いと気づいた方もいらっしゃると思います.この関係を双対の関係と言います.

これらの公理を暗記することも大事ですが,複雑な式で表された論理式を簡単な式で表すこと(簡略化)はもっと大事です.

集合

集合の定義

1桁の整数の集まりのように,含まれる「もの」がはっきりしているの集まりを集合と言います.また,集合に含まれる1つ1つの「もの」を要素(元)と言います.

aが集合Aの要素であるときaは集合Aに属すると言い,記号で表すと $a\in A$ となります.逆に,aが集合Aの要素でないときは,aは集合Aに属さないと言い,記号で表すと $a\notin A$ となります.

集合の表し方には2つの方法があります.1つは集合に含まれる要素を1つずつ列挙していく方法で,要素の数が多すぎる場合は「…」を使って省略します.もう1つは,式を使う方法です.例として,正の整数かつ8の倍数である集合Aを表します.

  1. A={8,16,24,32,…}
  2. A={8n|nは正の整数}

2つの集合A,Bについて,Aのどの要素もBの要素であるとき,集合Aは集合Bの部分集合であると言い,記号で表すと $A\subset B$ となります.なお,任意の集合Aについて, $A\subset A$ です.つまり,A自身がAの部分集合と考えます.

また, $A\subset B$ かつ $B\subset A$ であるとき,集合Aと集合Bは等しいと言い,記号で表すと $A=B$ となります.なお, $A\subset B$ かつ $A\neq B のとき,集合Aは集合Bの真部分集合であると言います.

1つも要素をもたない集合を空集合と言い,記号では $\phi$ と表します.任意の集合Aに対して $\phi\subset A$ です.

集合Aと集合Bのどちらにも共通する要素全体の集合を,AとBの共通集合(積集合)と言い,記号では $A\capB$ と表します. $A\capB=\phi$ のとき,AとBは互いに素であると言います.また,少なくともどちらか一方に属する要素全体の集合をAとBの和集合と言い,記号では $A\cupB$ と表します.

1つの集合Uを指定して,Uの要素や部分集合だけを考えるとき,Uを全体集合(普遍集合)と言います.全体集合Uの部分集合Aに対して,集合Aに属さないUの要素全体の集合を,Uに関するAの補集合と言います.記号では $\overline{A}$ と表します

その他に差集合があります.例えば,全体集合Uから集合Aを抜いた部分はAの補集合ですが,これはAの差集合でもあります.記号で表すと $U-A$ となります.

集合の要素の個数が有限のものを有限集合,無限のものを無限集合と言います.集合Aが有限集合のとき,要素の個数をn(A)と表します。

集合の代表的な法則

集合の代表的な法則を示します.

集合と命題の関連

一般に,命題 $p\Rightarrow q$ において,全体集合をU,仮定pと結論qを満たすUの要素全体の集合をそれぞれP,Qとすると,次のことが成立します.

ベン図

今まで集合について説明してきましたが,記号や式だけでは分かりにくいことが多いと思います.そこで,ベン図を使って説明します.全体集合Sに対して,集合Aと集合Bがあるとします.塗りつぶされた部分が該当する集合です.

集合が3つの場合は3つの円を重ね合わせることで全ての集合を表せますが,4つ以上になるとベン図で表すことは難しくなります.