faecher:informatik:oberstufe:techinf:formale_logik:grundlagen:start

Grundlagen der Aussagenlogik

Eine Aussage bezeichnet ein sprachliches Gebilde, dem in sinnvoller Weise genau eine der beiden Eigenschaften wahr oder falsch zugeordnet werden kann. Man kürzt ab: wahr=1, falsch=0.

In der Aussagenlogik oder Schaltalgebra verwenden wir

  • Variablen, die meist mit x0,x1,x2... bezeichnet werden. Bei diesen Variablen handelt es sich um boolsche Werte, sie können also nur zwei Zuständen (0 - Falsch, 1 - Wahr) annehmen.
  • Logische Funktionen ordnen einer oder mehreren boolschen Variablen einen Funktionswert zu, sie werden oft mit y bezeichnet. Der Funktionswert kann ebenfalls nur 1 (wahr) oder 0 (falsch) sein. Logische Funktionen lassen sich sehr gut als Wahrheits- oder Wertetabellen darstellen, da durch die beschränkte, diskrete Anzahl der Variablenkombinationen häufig eine Auflistung aller Funktionswerte möglich ist.
  • "Gerechnet" wird mit den logischen Verknüpfungen
    • AND: ∧
    • OR: ∨
    • NOT: ¬
  • Beim Rechnen gelten - ähnlich wie die Punkt vor Strich Regeln: "Klammer vor NOT vor AND vor OR"
Die Verknüpfung mit UND ∧ nennt man Konjunktion
Die Verknüpfung mit ODER ∨ nennt man Disjunktion

Kommutativgesetz (Vertauschung erlaubt)

  • x0x1=x1x0
  • x0x1=x1x0

Distributivgesetz (Gießkannenregel)

  • x0(x1x2)=(x0x1)(x0x2)
  • x0(x1x2)=(x0x1)(x0x2)

Neutralelement

  • x00=x0
  • x01=x0

Komplement

  • x0¬x0=0
  • x0¬x0=1

Assoziativgesetze (Klammern dürfen bei gleichen Operatoren weggelassen/umgesetzt werden)

  • (x0x1)x2=x0x1x2=x0(x1x2)
  • (x0x1)x2=x0x1x2=x0(x1x2)

Idempotenzgesetze

  • x0x0=x0
  • x0x0=x0

Absorptionsgesetze

  • x0(x0x1)=x0
  • x0(x0x1)=x0

De Morgan’sche Regel ("ausmultiplizieren des NICHT")

  • ¬(x0x1)=¬x0¬x1
  • ¬(x0x1)=¬x0¬x1

Gegeben ist die logische Funktion f durch

f=(¬x0¬x1x2)(¬x0x1¬x2)(¬x0x1x2)(x0¬x1x2)

(A1)

  • Wieviele Zeilen hat die Wahrheitstabelle dieser Funktion?
  • Schreibe die Wahrheitstabelle der Funktion auf1).

Lösung


Nun stellt sich die Frage, ob man den doch sehr langen Funktionsterm vielleicht unter Verwendung der Rechengesetze so vereinfachen kann, dass man einen kürzeren Term als Ergebnis erhält, der dieselbe Wahrheitstabelle hat, also dieselbe logische Funktion beschreibt.

Wenn man die Wertetabelle der Beispielfunktion betrachtet, fällt auf:

(1) Wenn x0=0 und x1=1 ist der Funktionswert 1, gleichgültig, was für einen Wert x2 annimmt.

Das entspricht den beiden eingerahmten Termen:

Rechnerisch kann man hier den Teilterm (¬x0x1) ausklammern, so dass der eingerahmte Term zu (¬x0x1)(¬x2x2)

wird.


(A2)

Vereinfache die folgenden logischen Terme:

  • f=x1(¬x2)x1x2
  • g=x1(¬x2)x3x1(¬x2)(¬x3)(¬x1)(¬x2)(¬x3)
  • h=(¬x1)(¬x2)(¬x3)(¬x1)(¬x2)x3(¬x1)x2x3x1(¬x2)(¬x3)x1x2x3x1x2(¬x3)

1)
Das geht auch mit einem Tabellenverarbeitungsprogramm….
  • faecher/informatik/oberstufe/techinf/formale_logik/grundlagen/start.txt
  • Zuletzt geändert: 24.09.2024 18:33
  • von Frank Schiebel