Amazon.de Widgets

Imperative Programmierung und PyNassi 1

Was mir in der OOP die UML leistet, bringt mir in der imperativen Programmierung das Struktogramm. Natürlich gibt es in der imperativen Programmierung auch einen Datenflußplan und einen Programmablaufplan und besonders für Assembler sind auch Speicherbelegungspläne noch immer in Verwendung, aber ich finde, dass das Struktogramm nach Nassi-Shneiderman (Wikipedia) am wichtigsten ist.
PyNassi führe ich in diesem Zusammenhang nicht nur an, weil mir das Projekt gefällt und weil man damit aus einem Struktogramm gleich einen Code generieren kann, sondern weil es auch aufzeigt, dass man auch in typischen OOP-Programmier- oder Skriptsprachen prozedural programmieren kann. Sehr sinnlos ist das in Java oder gar in Ruby, denn Ruby halte ich für die Programmiersprache in der das Konzept der OOP am konsequentesten umgesetzt wurde. Umgekehrt kann man theoretisch auch in C, Cobol oder gar in Assembler objektorientiert programmieren, obwohl das hoffentlich nie jemand von mir verlangt. Programmiersprachen sind nach vielen Kriterien einteilbar und auch bei den Paradigmen findet man unterschiedliche Einteilungen. Eine Betrachtung der historischen Entwicklung ist also unbedingt empfehlenswert. Eines haben aber alle Programmiersprachen gemeinsam, am Ende wird daraus auf verschieden Wegen direkt oder indirekt Maschinencode erzeugt, was erklärt, dass man sie auch leicht zweckentfremdet verwenden kann und zum Beispiel in Python, einer typischen OOP-Skriptsprache (also mit Interpreter statt Compiler) strukturierte Programme entwerfen und programmieren kann. Im Fall von PyNassi macht dies sogar Sinn, meistens sind imperative Programmfragmente in OOP-Sprachen aber völlig unangebracht und kontraindiziert.
In den nächsten Artikeln möchte ich auf folgende Punkte etwas näher eingehen:

  • Problemanalyse
  • Formularentwurfsblatt
  • Speierbelegungsplan
  • Datenflußplan
  • Programmablaufplan
  • Struktogramm
  • PyNassi

Eines möchte ich vorweg nehmen, denn es ist jedenfalls klar und nicht diskutierbar, dass die Eva die Chefin aller Anwendungsprogrammierer ist. Mit Eva meine ich natürlich die Eingabe, Verarbeitung und Ausgabe. ;-) (170)

Normalformen

Zuerst Beispiele für ein Literal, Minterm und Maxterm
Literal = eine negierte oder nicht negierte Aussagenvariable.
Minterm = eine Konjunktion von (nicht unbedingt verschiedenen) Literalen.
Maxterm = eine Disjumnktion von Literalen.

Disjunktive Normalform (DNF)

Eine DNF ist eine Disjunktion von Mintermen, wie z. B. (p∧¬q∧w)∨(r∧s∧¬t)∨(s∧s∧f)

Konjunktive Normalform (KNF)

Eine KNF ist eine Konjunktion von Maxtermen, wie z. B. (p∨¬q∨p∨f)∧(r∨s)∧t

Eine Basiskonjunktion ist ein Minterm, der alle gegebenen Aussagevariablen genau einmal als Literal (aber weder “w” noch “f”) enthält.

Eine Basisdisjunktion ist ein Maxterm, der alle gegebenen Aussagevariablen genau einmal als Literal (ohne “w” und “f”) enthält.

Für die Variablen p, q, r wäre also p∧¬q∧r eine Basiskonjunktion und p∨q∨¬r eine Basisdisjunktion.

Eine kanonisch (ausgezeichnete) DNF (KDNF) ist eine disjunktive Verknüpfung von Basiskonjunktionen, bei der jede Basiskonjunktion höchstens einmal auftritt.

Eine kanonisch (ausgezeichnete) KNF (KKNF) ist eine konjunktive Verknüpfung von Basisdisjunktionen, bei der jede Basisdisjunktion höchstens einmal auftritt.

Die Konstante f alleine ist auch eine DNF bzw. w eine KNF.

Zu jeder aussagelogischen Formel gibt es eine KDNF (KKNF), die zu dieser äquivalent ist.

Beispiel:

Gesucht ist eine KDNF, die äquivalent ist zu: ¬(¬p→q)∨r

1) Wahrheitstafel erstellen

rot ist die Negation von p; türkis die Implikation, welche nur bei w →f falsch ist, sonst immer wahr; amber ist die Negation des Klammerinhalts, die mit r verknüpft wird.

p q r ¬(¬p→q) ∨r
w w w f (w) f w 1
w w f f (w) f f
w f w f (w) f w 2
w f f f (w) f f
f w w w (w) f w 3
f w f w (w) f f
f f w w (f) w w 4
f f f w (f) w w 5

Es gibt 5 Ergebnisse mit “w” aus diesen Zeilen können die Literale übernommen werden, wenn die Voraussetzung “w” war, sonst wird die Negation übernommen, weil eine Basiskonjunktion nur dann wahr ist, wenn alle Literale wahr sind. Mit einer Konjugation ergeben sich die Basiskonjunktionen und wenn disjunktiv verknüpft werden, erhält man eine KDNF. Eine Disjunktion von Basiskonjunktionen ist genau dann wahr, wenn mindestens eine Basiskonjunktion wahr ist.

Zeile p q r Literale Basiskonjunktion
1 w w w p q r p∧q∧r
2 w f w p ¬q r p∧¬q∧r
3 f w w ¬p q r ¬p∧q∧r
4 f f w ¬p ¬q r ¬p∧¬q∧r
5 f f f ¬p ¬q ¬r ¬ p∧¬q∧¬r

 

KDNF: (p∧q∧r)∨(p∧¬q∧r)∨(¬p∧q∧r)∨( ¬p∧¬q∧r)∨(¬ p∧¬q∧¬r)

Die KDNF hat genau die gleichen Wahrheitswerte wie die gegebene Formel und ist damit äquivalent zu ihr. Wenn in der Resultatsspalte nur “f” vorkommen, dann ist “f” die KDNF.

Bei den Verfahren zur Bildung der KKNF bzw. KDNF werden “und” mit “oder” und “f” mit “w” bzw. umgekehrt vertauchst, wie bei den Gesetzten von De Morgan, den Distributiv- und Verschmelzungsgesetzen, weil wegen des Dualitätsprinzips gilt:

Sind zwei Ausdrücke a und b, in denen nur die Junktoren ¬, ∧, und ∨ vorkommen äquivalent, dann sind auch die Formeln, die aus a und b dadurch entstehen, dass alle ∧ durch ∨, ∨ durch ∧, w durch f und f durch w erstetzt werden.

Z. B.: a ∧w↔a es gilt daher auch a∨ f↔a

  (177)

Ein- und Ersetzung, wichtige Äquivalenzen und Tautologien

Bei aussagenlogischen Formel sind aussagenlogisch indeterminiert, oder es handelt sich um Tautologien oder Kontradiktionen.
.) Tautologie – (immer wahr) wenn die Aussage unabhängig von ihren Variablen wahr ist. Z. B. (p→p)↔(¬q∨q)
.) Kontradiktion – (immer falsch) ist unabhängig von ihren Variablen falsch. Z. B. (p↔¬p)∨(r∧¬r)
.) Aussagenlogisch Indeterminiert – wenn die Aussage für mindestens eine Belegung der Variablen wahr und für mindestens eine Belegung falsch ist. Z. B. p→q∨r
Tautologien und aussagenlogisch indeterminierte Aussagen werden auch als erfüllbare Aussagen bezeichnet.
In der Aussagenlogik ist man u.a. an der Charakterisierung und Erzeugung von Tautologien interessiert.

Die Einsetzung

a[p/b] ist die Formel die aus a entsteht, wenn für jedes Vorkommen der Variable p in der Aussage a durch die Formel b eingesetzt wird.
Z. B.: a: p→q→p
b: (r∨s)
a[p/b]: (r∨s)→q→(r∨s)
Einsetzungstheorem – Ist a eine Tautologie bzw. eine Kontradiktion, dann ist es auch a[p/b].
Durch Einsetzen wird aus einer Tautologie wieder eine Tautologie, bzw. aus einer Kontradiktion eine Kontradiktion.

Ersetzung

I) Jede Formel a ist Teilformel von sich selbst.
II) Ist a eine zusammengesetzte Formel, z. B. ¬b, b∨c, b→c, usw. dann sind auch b und c Teilformeln von a.
III) Jede Teilformel einer Teilformel von a ist ebenfalls eine Teilformel von a.

Z. B.: a: p→((¬q∨r)→s)

Teilformeln:
lt I) p→((¬q∨r)→s)
lt II) p, (¬q∨r)→s
lt III) ¬q∨r, s
lt III) ¬q∨r, s
lt III) ¬q, r
lt III) q
Ersetzungen sind mehrdeutig. 2 Formeln a und b sind äquivalent oder logisch gleich, wenn die Formel a↔b eine Tautologie ist.
Es gilt das Ersetzungstheorem:
Wenn b↔c ist, dann ist a↔a[[b/c]]
Weiterlesen (193)

Nachhaltige Notizen zu Taijiquan, Linux, Informatik, Mathematik, Dadaichmuss, Umfragen, Satire, außergewöhnlichen Begebenheiten, Weltgeschehen, Lifestyle, …