論理記号.5　論理演算

ホーム
大学数学, 集合と位相
論理記号.5　論理演算

大学数学

2018.06.8

論理演算

前回までで一通りよく使う論理記号については押さえましたが、今回からは論理演算を取り扱います。

$p,q,r$ を命題とします。また、常に真である命題を $1$ 、常に偽である命題を $0$ で表すことにします。

次の計算法則が成り立ちます。（多いですが、一つ一つはそこまで難しくないので慣れていきましょう）

◆Prop.SetTop.1.5.1.　（よく使う計算法則一覧）

○べき等則
$(p \land p) \Leftrightarrow p$
$(p \lor p) \Leftrightarrow p$

○交換則
$(p \land q) \Leftrightarrow (q \land p)$
$(p \lor q) \Leftrightarrow (q \lor p)$

○結合則
$((p \land q) \land r )\Leftrightarrow (p \land (q \land r))$
$((p \lor q) \lor r )\Leftrightarrow (p \lor (q \lor r))$

○分配則
$((p \land q) \lor r )\Leftrightarrow ( (p \lor r) \land (q \lor r))$
$((p \lor q) \land r )\Leftrightarrow ( (p \land r) \lor (q \land r))$
$(p \land (q \lor r) )\Leftrightarrow ( (p \land q) \lor (p \land r))$
$(p \lor (q \land r) )\Leftrightarrow ( (p \lor q) \land (p \lor r))$

○ド・モルガンの法則
$\lnot (p \land q) \Leftrightarrow ( (\lnot p) \lor (\lnot q) )$
$\lnot (p \lor q) \Leftrightarrow ( (\lnot p) \land (\lnot q) )$

○二重否定＝肯定
$\lnot (\lnot p) \Leftrightarrow p$

○ $0$ と $1$ に関わる演算
$(p \land 0) \Leftrightarrow 0$
$(p \lor 0) \Leftrightarrow p$
$(p \land 1) \Leftrightarrow p$
$(p \lor 1) \Leftrightarrow 1$
$(p \land (\lnot p)) \Leftrightarrow 0$
$(p \lor (\lnot p)) \Leftrightarrow 1$

では、順番に解説していきましょう。

べき等則

$(p \land p) \Leftrightarrow p$
$(p \lor p) \Leftrightarrow p$

これは日本語で言ってしまうと極めて単純明快で、「 $p$ または $p$ 」も「 $p$ かつ $p$ 」も結局 $p$ だということです。 $p^2$ （べき）が $p$ に等しいような見た目なので、べき等則と言っています。

交換則

$(p \land q) \Leftrightarrow (q \land p)$
$(p \lor q) \Leftrightarrow (q \lor p)$

これも簡単なことで、かつとまたはで挟んでいるだけなので順序を交換したところで意味は変わらないと言っているだけです。

分配則

$((p \land q) \lor r )\Leftrightarrow ( (p \lor r) \land (q \lor r))$
$((p \lor q) \land r )\Leftrightarrow ( (p \land r) \lor (q \land r))$
$(p \land (q \lor r) )\Leftrightarrow ( (p \land q) \lor (p \land r))$
$(p \lor (q \land r) )\Leftrightarrow ( (p \lor q) \land (p \lor r))$

これについては、実数の分配則

$(p+q) \times r=p \times r+q \times r$
$p \times (q+r) =p \times q+p \times r$

を念頭に置いておくと理解しやすいでしょう。（もちろん実数の分配則では、 $p,q,r$ は実数としています）

ド・モルガンの法則

$\lnot (p \land q) \Leftrightarrow ( (\lnot p) \lor (\lnot q) )$
$\lnot (p \lor q) \Leftrightarrow ( (\lnot p) \land (\lnot q) )$

高校数学の集合の単元で出てきたド・モルガンの法則の論理バージョンです。「かつ」や「または」を否定すると、「かつ」が「または」に、「または」が「かつ」にひっくり返ります。これと同じようにして、一般の命題の否定を作っていくことができます。詳しくは次の記事（否定の作り方）でお話しします。

二重否定＝肯定

$\lnot (\lnot p) \Leftrightarrow p$

これはそのままの意味なので、特に混乱することはないでしょう。こちらも否定の作り方で計算例を出します。

$0$ と $1$ に関わる演算

$(p \land 0) \Leftrightarrow 0$
$(p \lor 0) \Leftrightarrow p$
$(p \land 1) \Leftrightarrow p$
$(p \lor 1) \Leftrightarrow 1$
$(p \land (\lnot p)) \Leftrightarrow 0$
$(p \lor (\lnot p)) \Leftrightarrow 1$

一つずつ意味を解説していきましょう。

$(p \land 0) \Leftrightarrow 0$

常に偽である命題 $0$ と $p$ が同時に成り立つことはないので、左辺は $0$ と同値になります。

$(p \lor 0) \Leftrightarrow p$

左辺は常に偽である命題 $0$ または $p$ が成り立つと言っているのですが、 $0$ が成り立つことはないので、 $p$ と同値になります。

$(p \land 1) \Leftrightarrow p$

常に真である命題 $1$ と $p$ が同時に成り立つとき、 $p$ さえ成り立てばいつでも $1$ は成り立つので、左辺は $p$ と同値になります。

$(p \lor 1) \Leftrightarrow 1$

常に真である命題 $1$ または $p$ が成り立つとき、 $1$ は常に成り立つので、左辺は $1$ と同値になります。

$(p \land (\lnot p)) \Leftrightarrow 0$

$p$ と $p$ でないが同時に成り立つことはあり得ないので、左辺は常に偽です。したがって $0$ と同値です。

$(p \lor (\lnot p)) \Leftrightarrow 1$

すべての命題は真偽が決定できるものであることが、命題の定義です。定義から、 $p$ であるか $p$ でないかのいずれかは必ず成り立っているので、左辺は常に真です。したがって $1$ と同値です。

計算例

では、いくつか計算例を示していきましょう。新しい概念に出会ったときは使って慣れることが大切です。

◇Ex.SetTop.1.5.2.

論理記号.2の記事で、

$p \Rightarrow q$ は $( \lnot p) \lor q$ と同値であることを定理として述べましたが、改めてこれを示しましょう。

$p \Rightarrow q$ がいつ真になるかを考えると、「 $p$ が成りたっていてかつ $q$ が成り立つ」ときか、「そもそも $p$ が成り立っていない」とき、またそのときに限り真となります。

言い換えると、 $p \Rightarrow q$ は「 $p$ かつ $q$ 」または「 $p$ でない」と同値です。このことを論理記号で書くと、

$(p \Rightarrow q) \Leftrightarrow ( (p \land q ) \lor ( \lnot p))$

となります。ここから式変形していきましょう。

まず、分配則を用いて、

$( (p \land q ) \lor ( \lnot p)) \Leftrightarrow ((p \lor ( \lnot p )) \land ( q \lor ( \lnot p )))$

次に、 $(p \lor (\lnot p)) \Leftrightarrow 1$ と交換則を $q \lor ( \lnot p )$ に適用して、

$((p \lor ( \lnot p )) \land ( q \lor ( \lnot p ))) \Leftrightarrow (1 \land ( ( \lnot p ) \lor q))$

それから、再び交換則を用いて、

$(1 \land ( ( \lnot p ) \lor q) ) \Leftrightarrow (( ( \lnot p ) \lor q) \land 1)$

さらに、 $(p \land 1) \Leftrightarrow p$ を、 $p$ を $( \lnot p ) \lor q$ として適用すると、

$(( ( \lnot p ) \lor q) \land 1) \Leftrightarrow ( ( \lnot p ) \lor q)$

以上から、

$(p \Rightarrow q) \Leftrightarrow (( \lnot p) \lor q)$

よって示されました。

◇Ex.SetTop.1.5.3.

$p \Rightarrow q$ と $q \Rightarrow r$ が同時に成り立つとき、 $p \Rightarrow r$ が成り立ちます。これを仮言三段論法と言います。

全体を論理式で表すと、

$((p \Rightarrow q) \land (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)$

が成り立ちます。この命題が真であることを示してみましょう。

示すためには、上の式全体が $1$ と同値であることを示せばよいです。（ $1$ は常に真であることを表すので、 $1$ と同値であるというのは、命題が真であるということです）

まず、Ex.SetTop.1.5.2.の結果を使って式の全体を書き換えます。

$((p \Rightarrow q) \land (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)$
$\Leftrightarrow$
$(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \Rightarrow ((\lnot p) \lor r )$
$\Leftrightarrow$
$\lnot(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \lor ((\lnot p) \lor r )$

以下、次のように変形していきます。（どの計算法則を使っているのか自分で考えてみて下さい）

$\lnot(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \lor ((\lnot p) \lor r )$
$\Leftrightarrow$
$(\lnot((\lnot p) \lor q )) \lor (\lnot((\lnot q) \lor r )) \lor ((\lnot p) \lor r )$
$\Leftrightarrow$
$(p \land (\lnot q) ) \lor (q \land (\lnot r) ) \lor (\lnot p) \lor r$
$\Leftrightarrow$
$((p \land (\lnot q) ) \lor (\lnot p)) \lor ((q \land (\lnot r) ) \lor r)$
$\Leftrightarrow$
$((p \lor (\lnot p) ) \land ((\lnot q) \lor (\lnot p))) \lor ((q \lor r ) \land ( (\lnot r) \lor r))$
$\Leftrightarrow$
$((\lnot q) \lor (\lnot p)) \lor (q \lor r )$
$\Leftrightarrow$
$((\lnot q) \lor q) \lor ((\lnot p) \lor r )$
$\Leftrightarrow$
$1 \lor (\lnot p) \lor r$
$\Leftrightarrow$
$1$