ドモルガンルールの説明

StackOverflow https://stackoverflow.com/questions/2168603

  •  24-09-2019
  •  | 
  •  

質問

説明していただけますか ドモルガンルール できるだけ簡単に（例：中等教育の数学の知識しかない人に）？

役に立ちましたか？

解決

2 つの値があります。 T そして F.

これらの値は次の 3 つの方法で組み合わせることができます。 NOT, AND, 、 そして OR.

NOT 最も単純です:

  • NOT T = F
  • NOT F = T

これは次のように書くことができます 真理値表:

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

簡潔にするために

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

のことを考える NOT として 補体, つまり、一方の値をもう一方の値に変換します。

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

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

AND は T 両方の場合のみ 引数 (の値 x そして y 真理値表では) T - そして F さもないと。

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.

8 つの可能な値すべてに対して同じプロセスを繰り返します。 x, y, 、 そして z (2 つの可能な値 x の 2 つの可能な値を乗算したもの y の 2 つの可能な値を乗算したもの 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) は 同等 ただに x.

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

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

（これは次のように考えるかもしれません NOT シンプルな方法で配布します AND そして 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) は同等です。

他のヒント

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

ドモルガンの法則は、2 つの条件の任意の組み合わせを記述するための 2 つの同一の方法が存在するという事実を指します。 AND 組み合わせ (両方の条件が true である必要があります)、および OR の組み合わせ (どちらか一方が true になる可能性があります)。例は次のとおりです。

ドモルガンの法則のパート 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歳の子供でも少しは混乱しないと思います。確かに、真理値表に関するこのようなナンセンスな話よりも混乱は少ないです (これらすべてを見ていると私でさえ混乱してしまいます)。

これは、同じことを行うために条件文を書くのに簡単な方法を提供することができ言い換える真実文、とだけの方法である。

平易な英語で

の の
何かがあれやこれやでない場合には、それはまた、これとないものではありません。
何かがこのそれではない場合には、それはまた、このかないことではありません。

注：単語「や」Iは、非排他的または前述の例でを意味するためにそれを使用しています。

上の英語の不正確さを考えます。

のたとえば、以下の擬似コードは等価である：の
もしNOT（A OR B）...
IF（NOT A）AND（NOT B）...

IF NOT（A AND B）...
IF NOT（A）OR NOT（B）...

あなたが未成年の飲酒を探している警察官であれば、あなたは次のいずれかを行うことができ、そしてド・モルガンの法則は、彼らが同じことに達すると言います：

処方物1（A AND B）

  

もし彼らしているの下にの年齢   制限や飲酒のアルコールの   飲料は、それらを逮捕ます。

製剤2（NOT（NOT A OR NOT B））

  

もし彼らしているのオーバーの   年齢制限OR飲みA   のノンアルコールの飲料、それらを手放すます。

これは、方法によって、私の例ではありません。私の知る限りでは、それらを理解する人々の能力で作られたどのくらいの差を見つけるために、同じルールが異なる方法で表現された科学実験の一部であった。

「彼は車もバスも持っていません。」 「彼は車を持っていないし、バスを持っていない」と同じことを意味します。

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

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

正式には:

  • not (車またはバス) = (車ではない) かつ (バスではない)
  • not (車とバス) = (車ではない) または (バスではない)

英語では、「または」は、両方を持たないという選択を意味する傾向があります。論理では、「または」は常に英語の「および/または」と同じ意味です。

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

最初のケース:not (cor またはバス) = (車ではない) および (バスではない)

 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
---+---++---------+---------------++---------+---------+--------------------

単純なベン図、2つの交差する円を描きます。右に左とBにAを入れてください。今（A及びB）は、明らかに交差するビットです。だから、NOT（AとB）が交差するビットにないすべてのもの、両方の円の残りの部分です。色という点でます。

交差する前に、AとBのように別の二つの円を描きます。それは明らかにAだだけでなく、B.色のため、今NOT（A）は、これは中、右円（B）にだすべてのものではなく、交差点である。同様にNOT（B）は、左の円内のすべてではなく、交差点で、 Bと同様A.色として、この中にためています。

二つの図面は同じように見えます。あなたはNOT（AおよびB）= NOT（A）またはNOT（B）ことを証明しました。 T'other場合は、学生のための演習として残しておきます。

ドモルガンの法則を使用すると、さまざまな方法で論理演算の文字列を述べることができます。それはあなたがまたはのために、のための交差点とし、組合ないために補数を使用する集合論のロジックと集合論に適用されます。

ドモルガンの法則は、乗算の分配則にかなり類似している操作を実行する、あなたは論理式を簡素化することができます。

だから、あなたはCに似た言語で、次のしている場合は、

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

これは、論理的に等価です 

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

はまた、そのように動作します 

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

に変わります。

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

そして、あなたは、もちろん、逆に行くことができます。

これらの文の等価性は、真理値表と呼ばれるものを使用して見ることは容易です。真理値表では、単にあなたの変数（x、y、z）と、これらの変数のための入力のリストすべての組み合わせをレイアウト。その後、各述語、または論理式の列を持っている、とあなたは、与えられた入力に対して式の値を決定します。コンピュータサイエンス、コンピュータ工学、または電気工学のための任意の大学のカリキュラムは、おそらくあなたが構築しなければならない真理値表の数と大きさと狂気を駆動します。

なぜそれらを学びますか？私は、コンピューティングの最大の理由は、それが大きな論理式の可読性を向上させることができることだと思います。一部の人々は、彼らがそれを逃す場合は、それが誰かを混同することができると思うと、式の前に!ない論理使って好きではありません。特定のゲートタイプは、より速く安価である、またはあなたがのために必要なチップパッケージの数を減らすことができますので、あなたはすでに彼らのために全体の集積回路を使用しているので、チップのゲートレベルにドモルガンの法則を使用しての影響は、しかし、便利です成果ます。

わからない私はこれらすべての年、これを保持してきたが、それは機会の数に有用であることが判明している理由。ミスター・ベイリー、私の学年10数学の先生に感謝します。彼はドモルガンの定理と呼んでます。

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

あなたは括弧の中や外に否定を移動すると、論理演算子（AND、OR）の変更。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top