Yacas Reloaded - Freies Computer Algebra System

Inhalt

Grundlagen der Mathematik

Bezeichnungen

Elementarmathematik

Logik

Aussagenlogik

Aussagen, Formeln und

Tautologien

Aussagenlogische

Formeln

Tautologien

Äquivalenz von Formeln

Disjunktive

Normalformen

Adäquate

Verknüpfungszeichen

Die Theorie L

Prädikatenlogik

Formale Theorien

Modelltheorie

Ableitung

Gödelscher

Unvollständigkeitssatz

Mengenlehre

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Disjunktive Normalformen

Neu: Das Wurzelzieher Mathepedia Forum.

Jetzt registrieren und mit anderen Nutzern über Mathematik diskutieren!

Jede Formel mit k Variablen lässt sich durch eine Wahrheitstafel mit k + 1 Spalten beschreiben: die ersten k Spalten enthalten die möglichen Wahrheitswerte der Variablen, und die letzte Spalte enthält den Wahrheitswert der Formel unter der durch die ersten k Spalten festgelegten Belegung; siehe als Beispiel

A₁	A₂	A₃
f	f	f	f
f	f	w	w	*
f	w	f	w	*
f	w	w	f
w	f	f	w	*
w	f	w	f
w	w	f	w	*
w	w	w	f

Aus der Wahrheitstafel kann man direkt eine Formel ablesen, die zu der Formel, für die die Wahrheitstafel konstruiert wurde, äquivalent ist (die also die gleiche Wahrheitstafel hat). Dazu wählt man alle Zeilen mit dem Wahrheitswert w in der letzten Spalte (Zeilen mit * in der Tabelle) und bildet für jede dieser Zeilen eine Konjunktion der Literale, die genau durch die in der Zeile angegebene Belegung wahr wird.

A₁	A₂	A₃			Konjunktion von Literalen
f	f	w	w	*
f	w	f	w	*
w	f	f	w	*
w	w	f	w	*

Diese Konjunktionen verknüpft man mittels Disjunktion und erhält so eine zur Ausgangsformel äquivalente Formel

Diese spezielle Struktur - Disjunktion von Konjunktionen von Literalen - der neuen Formel bezeichnet man als disjunktive Normalform (DNF).

Lemma 172M (Adäquatheit disjunktiver Normalformen)

Für jede beliebige aussagenlogische Formel gibt es eine äquivalente Formel in disjunktiver Normalform.

Formeln in disjunktiver Normalform enthalten keine Verknüpfungszeichen und . Man braucht demnach nicht alle Verknüpfungszeichen zur Beschreibung von Aussagenverknüpfungen.

Korollar 172N

Für jede aussagenlogische Formel gibt es eine äquivalente Formel mit den Verknüpfungszeichen , und .

Man kann auch noch auf eines der beiden Verknüpfungszeichen und (aber nicht auf beide) verzichten.

Satz 172O

Für jede aussagenlogische Formel gibt es eine äquivalente Formel, die nur die Verknüpfungszeichen und enthält.

Beweis

Sei eine aussagenlogische Formel, die o.B.d.A. (Korollar 172N) nur die Verknüpfungszeichen und enthält. Wir führen eine Induktion über den Formelaufbau.

IA: ist eine Variable A. Dann enthält gar keine Verknüpfungszeichen.

IV: Für beliebige Formeln und gibt es äquivalente Formeln und , die nur und enthalten.

IS: Es ist zu zeigen, dass zu jeder Formel, deren Teilformeln nur und enthalten, eine äquivalente Formel mit nur den Verknüpfungen und existiert.

Fall 1: Wenn die Struktur , dann gilt: und enthält nach Induktionsvoraussetzung nur und .

Fall 2: Habe die Gestalt . Dann gilt: . Nach Induktionsvoraussetzung enthalten und nur und als Verknüpfungszeichen.

Fall 3: Ist von der Gestalt . Dann gilt: Nach Induktionsvoraussetzung enthalten und nur die Verknüpfungszeichen und .

Beispiel

kann unter Nutzung der Doppelnegation () und der de Morgan'schen Regel () umgeformt werden: .

Weiteres Beispiel:

Alles, was lediglich wahrscheinlich ist, ist wahrscheinlich falsch.

Rene Descartes

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: