Die Regeln von DeMorgan



Die Regeln nach DeMorgan beschreiben jeweils logisch äquivalente Ausdrücke.

Durch sie ist es möglich,
  • Junktoren ( logische UND ( ∧ ) , logisches ODER ( ∨ ), logische IMPLIKATION ( → ) ) bzw.
  • Quantoren ( für alle ( ∀ ), es gibt ( ∃ ) )
durch jeweils logische äquivalente Ausdrücke auszudrücken.

Zum Beispiel kann durch Anwendung der DeMorgan-Regeln eine logische Formel derart umgeformt werden, dass sie nur noch aus Junktoren einer Art besteht. Dies durch die Umformung entstehenden Terme sind logisch äquivalent.

Quantoren-Regeln:
  • x ¬ P ≡ ¬ ∃ x P
  • ¬ ∀ x P ≡ ∃ x ¬ P
  • x P ≡ ¬ ∃ x ¬ P
  • ¬ ∀ x ¬ P ≡ ∃ x P

Junktoren:
  • ¬ P ∧ ¬ Q ≡ ¬ ( PQ )
  • ¬ (PQ ) ≡ ( ¬ P ∨ ¬ Q )
  • P ≡ ¬ ¬ P
  • PQ ≡ ¬ ( ¬ P ∨ ¬ Q )
  • PQ ≡ ¬ ( ¬ P ∧ ¬ Q )
  • PQ ≡ ¬ PQ

Oftmals werden unter den DeMorgan-Regeln im Bereich der Elektronik nur die Regeln betrachtet, die die Äquivalenz zwischen den Junktoren UND/ODER beschreiben.

Allgemein


Zusätzlich sei hier noch erwähnt, im Bereich Elektronik finden noch folgende logische Funktionen Verwendung. Sie stellen nur eine Erweiterung der logischen Ausdrücke mit UND/ODER dar und sind eher praktischer Natur. Mehr beschreiben oder ausdrücken kann man damit nicht.

  • Exklusiv Oder : PQ ≡ ( ¬ PQ ) ∨ ( P ∧ ¬ Q )
  • Äquivalenz : PQ ≡ ( PQ ) ∨ ( ¬ P ∧ ¬ Q )