ド・モルガンの法則とは、論理と真理値表で否定を書き直す

論理の演算とド・モルガンの法則はどう決まっているのか

論理の演算は、真 (True) と偽 (False) の 2 つの値だけを扱い、全部の組み合わせの答えを並べた真理値表で意味が決まります。ド・モルガンの法則も、その表の上で確かめられる決まりです。

AND、OR、NOT、XOR の真理値表

基本の演算は AND、OR、NOT の 3 つです。2 つが違うときだけ真になる XOR (排他的論理和) もよく使います。

OR は「どちらか一方だけ」ではありません。両方が真でも真です。日本語の「または」は、どちらか一方だけの意味で使うこともあるので、取り違えやすい所です。

否定を配るときは AND と OR を入れ替える

ド・モルガンの法則は、かっこの外の否定を中へ配るとき、AND と OR を入れ替えるという決まりです。式は次の 2 本です。

not (A and B)
  は (not A) or (not B)
not (A or B)
  は (not A) and (not B)

1 本目は「A かつ B、ではない」が「A でないか、B でないか」と同じという意味です。2 本目は「A または B、ではない」が「A でもなく、B でもない」と同じという意味です。

仕事のコードでは、冒頭の条件を次のように書き直すのに使います。

if not (logged_in and has_perm):
    deny()

if (not logged_in
        or not has_perm):
    deny()

どちらも「ログインしていない」か「権限が無い」なら断ります。

集合で書くと、補集合と共通部分と和集合

ド・モルガンの法則は、集合 (ものの集まり) でも同じ形で成り立ちます。補集合 (ほしゅうごう) は、全体のうち、その集合に入っていない物の集まりです。「A の補集合」は「A でない物」の集まりなので、論理の NOT にあたります。

この対応で読み替えると、「A と B の共通部分の補集合は、A の補集合と B の補集合の和集合」、「A と B の和集合の補集合は、A の補集合と B の補集合の共通部分」です。2 つの円を重ねたベン図で塗ってみると同じ所が塗られます。この頁では、図を塗る代わりに、全部の場合をコードで比べます。

3 つ以上でも、全部を入れ替えるだけ

条件が 3 つ以上でも、否定を配るときは、全部の AND を OR に (または全部の OR を AND に) 入れ替えます。

not (A and B and C)
  は not A or not B or not C
not (A or B or C)
  は not A and not B and not C

「3 つの集合のド・モルガンの法則」と呼ばれるのはこの形です。2 つの場合をくり返し使うと、いくつになっても同じ形になります。

「すべて」と「ある」の否定

「すべての〜が真、ではない」は「ある〜が偽」と同じで、「ある〜が真、ではない」は「すべての〜が偽」と同じです。ド・モルガンの法則を、条件がいくつあっても使える形にした物です。

Python では、すべてが真かを all、1 つでも真があるかを any で調べます。次の 2 つの式は、同じ答えになります。

not all(xs)
any(not x for x in xs)

日本語の「全部は来なかった」と「全部来なかった」の違いも、この形です。「全部は来なかった」は「来なかった人がいる」(部分否定)、「全部来なかった」は「誰も来なかった」(全否定) です。

not は and より先に効く

Python では、not が and より先に、and が or より先に効きます。公式文書の演算子の優先順位の表で、Boolean NOT、Boolean AND、Boolean OR の順に並んでいます。

ですから not a and not b は (not a) and (not b) で、not (a and b) とは違う式です。かっこを省くと意味が変わる所なので、否定を配った式にはかっこを付けて読み直すと安全です。