TU Wien:Formale Modellierung VU (Salzer)/Kapitel Aussagenlogik

1. Aussagenlogik
2. Endliche Automaten
3. Formale Sprachen und Grammatiken
4. Prädikatenlogik
5. Petri-Netze

Diese Seite ist noch nicht fertig!

Siehe auch Zusammenfassung Aussagenlogik.pdf.

Beispiel für eine Inferenzregel:

${\begin{array}{ll}\left.{\begin{aligned}&{\text{Alle x sind y.}}\\&{\text{z ist ein x.}}\end{aligned}}\right\}&{\text{Prämissen}}\\\hline {\text{z ist y.}}&{\text{Konklusion}}\end{array}}$

Kriterium für die Gültigkeit von Inferenzregeln

Immer wenn alle Prämissen wahr sind, ist auch die Konklusion wahr.

Funktionen

and	$\land$	nand	$\uparrow$
or	$\lor$	nor	$\downarrow$
iff	$\equiv$	xor	$\not \equiv$
implies	$\supset$		$\not \supset$
if	$\subset$		$\not \subset$

{not, and, or} ist vollständig für die aussagenlogische Funktionen (es können alle mit ihnen ausgedrückt werden). Ebenfalls vollständig sind {not, and}, {nand}, {not, or}, {nor}, {not, implies} und {implies, false}.

De Morgansche Gesetze

De Morgansche Gesetze

${\begin{aligned}\neg (a\land b)&=\neg a\lor \neg b\\\neg (a\lor b)&=\neg a\land \neg b\end{aligned}}$

Sonstiges

• Syntax und Semantik
• Normalformen (z.B. disjunktive und konjunktive Normalform)
• Erfüllbarkeitsproblem (Satisfiability, SAT)
• Dualität von Funktionen, Operatoren und Formeln