DeMorgans Regeln erklärt

Question

Könnten Sie bitte erklären die DeMorgans Regeln so einfach wie möglich (zB jemand mit nur einem Gymnasium Mathematik Hintergrund)?

Answer 1

Wir haben zwei Werte: T und F

.

Wir diese Werte auf drei Arten kombinieren können. NOT, AND und OR

NOT ist die einfachste:

• NOT T = F
• NOT F = T

Wir können dies schreiben als Wahrheitstabelle :

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

Für Prägnanz

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

Denken Sie an NOT als die Komplement , das heißt, es stellt sich ein Wert in die andere.

AND arbeitet auf zwei Werte:

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

AND ist T nur, wenn seine beiden Argumente (die Werte von x und y in der Wahrheitstabelle) sind T -. Und F sonst

OR ist T, wenn mindestens eines der Argumente T ist:

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

Wir können komplexere Kombinationen definieren. Zum Beispiel können wir eine Wahrheitstabelle für x AND (y OR z) schreiben, und die erste Zeile unten.

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

Sobald wir wissen, wie x AND (y OR z) zu bewerten, die wir in dem Rest der Tabelle füllen.

bewertet die Kombination, bewertet die Stücke und arbeitet von dort oben. Die Klammern zeigen die Teile zuerst zu bewerten. Was wissen Sie aus der gewöhnlichen Arithmetik wird Ihnen helfen, es funktioniert. Sagen Sie bitte 10 - (3 + 5) haben. Zuerst bewerten Sie das Teil in Klammern get

10 - 8

und zu bewerten, dass wie immer die Antwort zu bekommen, 2.

Auswertung dieser Ausdrücke in ähnlicher Weise funktioniert. Wir wissen, wie OR von oben funktioniert, so dass wir unseren Tisch ein wenig erweitern können:

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

Jetzt ist es fast wie wir zurück zum x AND y Tisch sind. Wir ersetzen einfach den Wert von y OR z und zu bewerten. In der ersten Reihe, haben wir

T AND (T OR T)

, das ist die gleiche wie

T AND T

, die einfach T ist.

Wir wiederholen den gleichen Vorgang für alle 8 möglichen Werte von x, y und z (2 möglichen Werten von x mal 2 möglichen Werte von y mal 2 möglichen Werten von z) erhalten

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

können Einige Ausdrücke komplexer sein als sie sein müssen. Zum Beispiel:

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

Mit anderen Worten, NOT (NOT x) ist äquivalent nur x.

DeMorgans Regeln sind handlich Tricks, lassen Sie uns zwischen äquivalente Ausdrücke konvertieren, die bestimmte Muster passen:

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

(Man könnte daran denken, wie man NOT vertreibt durch einfachen AND und OR Ausdrücke.)

Ihr gesunder Menschenverstand wohl versteht schon diese Regeln! Zum Beispiel, man denke an die wenig Volksweisheit, dass „man nicht an zwei Orten zugleich sein kann.“ Wir konnten sie den ersten Teil der ersten Regel fit machen:

NOT (here AND there)

Die Anwendung der Regel, dass eine andere Art zu sagen, ist „du bist nicht hier, oder du bist nicht da.“

Übung:? Wie könnte man die zweite Regel in einfachem Englisch auszudrücken

Für die erste Regel, lassen Sie einen Blick auf die Wahrheitstabelle für den Ausdruck auf der linken Seite des Gleichheitszeichen.

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

Nun ist die rechte Seite:

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

Die Endwerte sind die gleichen in beiden Tabellen. Dies beweist, dass die Ausdrücke sind äquivalent.

. Übung: Zeigen Sie, dass der Ausdrücke NOT (x OR y) und (NOT x) AND (NOT y) ist äquivalent

Answer 2

Mit Blick auf einige der Antworten, ich glaube, ich es besser, indem Sie Bedingungen erklären kann, die miteinander tatsächlich verwandt sind.

DeMorgans Gesetz bezieht sich auf die Tatsache, dass es zwei identische Weise eine beliebige Kombination von zwei Bedingungen zu schreiben - insbesondere die AND Kombination (beide Bedingungen müssen erfüllt sein) und die OR Kombination (entweder kann man wahr sein). Beispiele hierfür sind:

Teil 1 von DeMorgans Gesetz

Statement:. Alice hat ein Geschwister
Bedingungen:. Alice hat einen Bruder OR Alice eine Schwester hat
Gegenüber: Alice ist ein einziges Kind (nicht NOT ein Geschwister hat)
. Bedingungen:. Alice hat NOT einen Bruder, AND sie hat NOT eine Schwester

Mit anderen Worten: NOT [A OR B] = [NOT A] AND [NOT B]

Teil 2 von DeMorgans Gesetz

Statement: Bob ist ein Autofahrer
. Bedingungen:. Bob hat ein Auto AND Bob hat eine Lizenz
Gegenüber: Bob ist NOT ein Autofahrer
. Bedingungen:. Bob hat NOT ein Auto haben, OR Bob tut NOT eine Lizenz

Mit anderen Worten:. NOT [A AND B] = [NOT A] OR [NOT B]

ich denke, das auf eine 12-jährige etwas weniger verwirrend wäre. Es ist sicherlich weniger verwirrend als all diesen Unsinn über Wahrheitstabellen (auch bei allen jenen verwechselt ich auf der Suche bin immer).

Answer 3

Es ist nur eine Art und Weise neu zu formulieren Wahrheit Aussagen, die einfacheren Wege der conditionals Schreibens zur Verfügung stellen kann, das Gleiche zu tun.

Im Klartext:
Wenn etwas nicht dies oder das ist es auch nicht und das nicht.
Wenn etwas nicht dies und das, es ist auch dies oder nicht nicht.

. Hinweis: die Ungenauigkeit der englischen Sprache auf dem Wort gegeben ‚oder‘ Ich benutze es ein nicht ausschließliche oder im vorangegangenen Beispiel bedeutet

Zum Beispiel das folgende Pseudo-Code entspricht:
Wenn nicht (A oder B) ...
IF (NOT A) und (NICHT B) ....

IF NOT (A und B) ...
IF NOT (A) oder nicht (B) ...

Answer 4

Wenn Sie ein Polizist sind für minderjährigen Trinker suchen, können Sie eine der folgenden Aktionen tun, und De Morgan Gesetz sagt, dass sie auf dasselbe hinaus:

FORMULIERUNG 1 (A und B)

  

Wenn sie unter das Alter   begrenzen und Trinken ein alkoholische   Getränk, verhaften sie.

FORMULIERUNG 2 (NOT (NOT A ODER NICHT B))

  

Wenn sie über   die Altersgrenze oder Trinken eines    nicht-alkoholische Getränke, sie gehen lassen.

Das, nebenbei bemerkt, ist nicht mein Beispiel. Soweit ich weiß, es war Teil eines wissenschaftlichen Experiments, in dem die gleiche Regel auf unterschiedliche Weise zum Ausdruck gebracht wurde, um herauszufinden, wie viel Unterschied es in den Menschen Fähigkeit gemacht, sie zu verstehen.

Answer 5

„Er hat nicht entweder ein Auto oder einen Bus.“ das Gleiche bedeutet wie „Er hat kein Auto hat, und er hat keinen Bus.“

„Er hat kein Auto und einen Bus.“ bedeutet dasselbe wie „Er entweder kein Auto hat, oder nicht über einen Bus, ich bin nicht sicher, welche, vielleicht hat er keine hat.“

Natürlich in einfachem Englisch „Er hat kein Auto und einen Bus.“ hat eine starke Implikation, dass er zumindest eine dieser beiden Dinge hat. Aber streng genommen von einem logischen Standpunkt der Aussage gilt auch, wenn er nicht einer von ihnen hat.

Formal:

• nicht (Auto oder Bus) = (nicht Auto) und (nicht Bus)
• nicht (Auto und Bus) = (nicht Auto) oder (nicht Bus)

In Englisch ‚oder‘ neigt dazu, eine Wahl zu bedeuten, dass Sie nicht beides haben. In der Logik bedeutet ‚oder‘ immer gleich ‚und / oder‘ in englischer Sprache.

Hier ist eine Wahrheitstabelle, die zeigt, wie das funktioniert:

Erster Fall: nicht (cor oder Bus) = (nicht Auto) und (nicht 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
---+---++--------+--------------++---------+---------+--------------------

Zweiter Fall: nicht (Auto und Bus) = (nicht Auto) oder (nicht Bus)

 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 6

Zeichnen Sie ein einfaches Venn-Diagramm, zwei sich schneidende Kreise. Setzen Sie A in der linken und B in der rechten Seite. Jetzt (A und B) ist offensichtlich der Schnitt Bit. So NOT (A und B) ist alles, was nicht in dem Schnitt Bit ist, der Rest beiden Kreise. Farbe, die in.

Zeichnen Sie zwei weitere Kreise wie vor, A und B, schneidet. Nun NICHT (A) ist alles, dass die im rechten Kreis (B), aber nicht die Kreuzung, denn das ist offensichtlich A als auch B. Farbe ist das in. Ähnlich NICHT (B) alles im linken Kreis ist aber nicht die Kreuzung, denn das ist B sowie A. Farbe dies.

Zwei Zeichnungen gleich aussehen. Sie haben NICHT (A und B) = NICHT (A) oder nicht (B) bewiesen. T'other Fall ist für den Schüler als Übung.

Answer 7

DeMorgans Gesetz ermöglicht es Ihnen, eine Reihe von logischen Operationen auf unterschiedliche Weise zu äußern. Es gilt für Logik und Mengenlehre, wo in der Mengenlehre Sie Ergänzung verwenden für nicht, Kreuzung und, und Vereinigung für oder.

DeMorgans Gesetz ermöglicht es Ihnen, einen logischen Ausdruck zu vereinfachen, eine Operation durchzuführen, die auf die distributive Eigenschaft der Multiplikation ziemlich ähnlich ist.

Also, wenn Sie die folgenden in einer C-ähnlichen Sprache

haben

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

Es ist logisch äquivalent zu:

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

Es funktioniert auch in etwa so:

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

verwandelt sich in

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

Und Sie können natürlich in umgekehrter gehen.

Die Gleichwertigkeit dieser Aussagen ist einfach eine Wahrheitstabelle mit etwas genannt zu sehen. In einer Wahrheitstabelle, legen Sie einfach aus Ihren Variablen (x, y, z) und Liste, die alle Kombinationen von Eingaben für diese Variablen. Sie haben dann Spalten für jedes Prädikat, oder logischen Ausdruck, und legen Sie fest, für die gegebenen Eingaben, um den Wert des Ausdrucks. Jede Universität Lehrplan für Informatik, Computertechnik oder Elektrotechnik werden Sie wahrscheinlich bonkers fahren mit der Anzahl und Größe der Wahrheitstabellen müssen Sie konstruieren.

Also, warum sie lernen? Ich denke, der Hauptgrund, warum in Computing ist, dass es die Lesbarkeit von größeren logischen Ausdrücken zu verbessern. Manche Leute mögen keine logische Verwendung nicht vor Ausdrücke !, wie sie denken, dass es jemand verwirren können, wenn sie es versäumen. Die Auswirkungen der DeMorgans Gesetz auf der Gate-Ebene der Chips ist jedoch von Nutzen, weil bestimmte Gate-Typen schneller, billiger, oder Sie sind bereits eine ganze integrierte Schaltung für sie verwenden, so dass Sie die Anzahl der Chip-Pakete reduzieren kann für die erforderliche Ergebnis.

Answer 8

Nicht sicher, warum ich das all die Jahre beibehalten haben, aber es hat sich auf eine Reihe von Gelegenheiten als nützlich erwiesen. Vielen Dank an Herrn Bailey, meine 10. Klasse Mathelehrer. Er nannte es DeMorgans Theorem.

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

Wenn Sie die Negation in die oder aus den Klammern zu bewegen, dem logischen Operator (AND, OR) ändert.