language-agnostic - ド・モルガンの法則の説明

Question

ド・モルガンの法則をできるだけ簡単に説明していただけますか?

Answer 1

ブール代数の概要

と の 2 つの値がTありFます。

NOTこれらの値を、AND、の 3 つの方法で組み合わせることができますOR。

いいえ

NOT最も簡単です：

• NOT T = F
• NOT F = T

これを真理値表として書くことができます:

when given.. | results in...
============================
           T | F
           F | T

簡潔にするために

x | NOT x
=========
T | F
F | T

つまりNOT、 1 つの値を別の値に変換します。

と

AND次の 2 つの値で動作します。

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

ANDはT、両方の引数(真理値表のxとの値) が— であり、そうでない場合のみです。yTF

また

ORはT、その引数の少なくとも 1 つが次の場合ですT。

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

組み合わせる

より複雑な組み合わせを定義できます。たとえば、 の真理値表を作成できx AND (y OR z)ます。最初の行は以下のとおりです。

x y z | x AND (y OR z)
======================
T T T | ?

を評価する方法がわかったらx AND (y OR z)、表の残りの部分を埋めることができます。

組み合わせを評価するには、ピースを評価し、そこから作業を進めます。括弧は、最初に評価する部分を示しています。普通の算数から知っていることは、それを解決するのに役立ちます。あなたが持っているとしましょう10 - (3 + 5)。まず、括弧内の部分を評価して取得します

10 - 8

そしてそれをいつものように評価して答えを得る2.

これらの式の評価は同様に機能します。上からどのように機能するかを知っているORので、テーブルを少し拡張できます。

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

x AND yこれで、テーブルに戻ったようです。の値を代入してy OR z評価するだけです。最初の行には、

T AND (T OR T)

これはと同じです

T AND T

これは単にTです。

x、y、およびz( の 2 つの可能な値x時間の 2 つの可能な値 の2 つのy可能な値)のすべての 8 つの可能な値に対して同じプロセスを繰り返し、z取得します。

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

一部の式は、必要以上に複雑になる場合があります。例えば、

x | NOT (NOT x)
===============
T | T
F | F

つまり、NOT (NOT x)はjustと同等xです。

デモガンの法則

DeMorgan のルールは、特定のパターンに適合する同等の式を変換できる便利なトリックです。

• NOT (x AND y) = (NOT x) OR (NOT y)
• NOT (x OR y) = (NOT x) AND (NOT y)

NOT(これは、 がsimpleANDおよび式を介してどのように分配されるかと考えることができますOR。)

あなたの常識は、おそらくこれらのルールをすでに理解しているでしょう! たとえば、「同時に 2 つの場所にいることはできない」という民俗の知恵について考えてみてください。最初のルールの最初の部分に適合させることができます。

NOT (here AND there)

ルールを適用すると、「あなたはここにいない、またはそこにいない」という別の言い方になります。

演習: 2 番目の規則を平易な英語でどのように表現しますか?

最初のルールとして、等号の左側の式の真理値表を見てみましょう。

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

右側は次のとおりです。

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

最終的な値は、両方のテーブルで同じです。これにより、式が等しいことが証明されます。

演習:NOT (x OR y)式と(NOT x) AND (NOT y)が等しいことを証明します。

Answer 2

いくつかの回答を見てみると、実際に相互に関連する条件を使用することで、よりよく説明できると思います。

ANDDeMorgan の法則は、2 つの条件の任意の組み合わせ、具体的には、組み合わせ (両方の条件が真でなければならない) と組み合わせ (どちらか一方が真であり得る)を記述するには、2 つの同一の方法があるという事実に言及していますOR。例は次のとおりです。

デモガンの法則の第 1 部

口述:アリスには兄弟がいます。
条件:アリスには兄弟ORがいます アリスには姉妹がいます。
反対:アリスは一人っ子です (NOT兄弟がいます)。
条件:アリスにはNOT兄弟がANDいて、彼女にはNOT姉妹がいます。

言い換えると： NOT [A OR B] = [NOT A] AND [NOT B]

デモガンの法則のパート 2

説明:ボブは車の運転手です。
条件:ボブは車ANDを持っています ボブは免許を持っています。
反対側:ボブはNOT車の運転手です。
条件:ボブはNOT車を持ってORいます。ボブはNOT免許を持っています。

つまり: NOT [A AND B] = [NOT A] OR [NOT B] .

これで 12 歳の子供の混乱は少し減ると思います。確かに、真理値表についてのこのナンセンスよりも混乱が少ないです (私でさえ、それらすべてを見て混乱しています)。

Answer 3

これは、真実のステートメントを言い換える方法に過ぎず、同じことを行うための条件文を簡単に記述する方法を提供できます。

平易な英語で:
何かがこれでもあれでもないとき、それはこれでもあれでもありません。
これでもあれでもないものは、これでもあれでもない。

注:「または」という言葉の英語の不正確さを考えると、前の例では非排他的なまたはを意味するために使用しています。

たとえば、次の疑似コードは等価です:
If NOT(A OR B)...
IF (NOT A) AND (NOT B)....

ない場合 (A と B)...
ない場合 (A) またはない場合 (B)...

Answer 4

「彼は車もバスも持っていません。」は「彼は車を持っておらず、バスも持っていません」と同じ意味です。

「彼は車もバスも持っていません。」は、「彼は車を持っていないか、バスを持っていません。どちらかわかりません。どちらも持っていないかもしれません」と同じ意味です。

もちろん、平易な英語で「彼は車もバスも持っていません」。彼がこれら2つのことの少なくとも1つを持っているという強い意味を持っています. しかし、厳密に言えば、論理的な観点から言えば、どちらも持っていない場合でも、このステートメントは真です。

正式には：

• not (車またはバス) = (車ではない) and (バスではない)
• not (車とバス) = (車ではない) or (バスではない)

英語では、'or' は選択を意味する傾向があり、両方を持っていないことを意味します。論理的には、'or' は常に英語の 'and/or' と同じ意味です。

これがどのように機能するかを示す真理値表は次のとおりです。

最初のケース: not (cor or bus) = (not car) and (not bus)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

2 番目のケース: not (車とバス) = (車ではない) または (バスではない)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

Answer 5

あなたが未成年者の飲酒者を探している警察官なら、次のいずれかを行うことができます。ド・モルガンの法則によれば、どちらも同じことになります。

製剤 1 (A および B)

年齢制限未満でアルコール飲料を飲んでいる場合は 、逮捕してください。

式 2 (NOT(NOT A OR NOT B))

年齢制限 を超えているか、ノンアルコール飲料を飲んでいる場合は、手放してください。

ちなみに、これは私の例ではありません。私の知る限り、これは科学実験の一部であり、同じ規則をさまざまな方法で表現して、人々の理解能力にどの程度の違いがあるかを調べた.

Answer 6

DeMorgan の法則により、一連の論理演算をさまざまな方法で記述することができます。これは論理と集合論に適用されます。集合論では、not の補数、and の交点、or の和集合を使用します。

DeMorgan の法則を使用すると、乗算の分配特性にかなり似た演算を実行して、論理式を単純化できます。

したがって、C ライクな言語で次のような場合

if !(x || y || z) { /* do something */ }

論理的には次のものと同等です。

if (!x && !y && !z)

次のようにも機能します。

if !(x && !y && z)

になる

if (!x || y || !z)

もちろん、逆に行くこともできます。

これらのステートメントの同等性は、真理値表と呼ばれるものを使用して簡単に確認できます。真理値表では、単純に変数 (x、y、z) を配置し、これらの変数の入力のすべての組み合わせをリストします。次に、述語または論理式ごとに列を作成し、指定された入力に対して式の値を決定します。コンピューター サイエンス、コンピューター エンジニアリング、または電気工学の大学のカリキュラムでは、作成しなければならない真理値表の数とサイズに頭が悩まされることでしょう。

では、なぜそれらを学ぶのでしょうか。コンピューティングにおける最大の理由は、より大きな論理式の読みやすさを改善できることだと思います。式の前にlogical not を使用するのを好まない人もい!ます。これを見逃すと混乱する可能性があるからです。チップのゲート レベルでのドモルガンの法則の使用の影響は有用ですが、特定のゲート タイプはより高速で安価であるか、または既に集積回路全体を使用しているため、ゲートに必要なチップ パッケージの数を減らすことができます。結果。