Theoretische Informatik

Nächste Seite: Satz von Cook Aufwärts: NPC Beweise Vorherige Seite: NP-hart, NP-vollständig Inhalt

Aussagelogik

Sprache für eine Formel:

$\begin{displaymath}\alpha::=true\vert x_{i}\vert(\alpha\wedge\beta)\vert(\neg\alpha)\end{displaymath}$

Morgan-Regeln:

$\begin{displaymath}\alpha\vee\beta=\neg((\neg\alpha)\wedge(\neg\beta))\end{displaymath}$

$\begin{displaymath}\alpha\wedge\beta=\neg((\neg\alpha)\vee(\neg\beta))\end{displaymath}$

Zur Wiederholung:

$\wedge$ bedeutet ,,und'',
$\vee$ bedeutet ,,oder''.

Länge einer Formel: Die Länge einer Formel $\alpha$ ist die Anzahl der Opperatoren in $\alpha$ und wird mit $\vert\alpha\vert$ bezeichnet. Operatoren sind $\vee$ , $\wedge$ und $\neg$ .
Notationen:

$\begin{displaymath}\bigwedge_{1\leq i\leq n}a_{i}=a_{1}\wedge a_{2} \wedge \ldots \wedge a_{n}\end{displaymath}$

$\begin{displaymath}\bigvee_{1\leq i\leq n}a_{i}=a_{1} \vee a_{2} \vee \ldots \vee a_{n}\end{displaymath}$

Definitionen:

$\begin{displaymath}\bigwedge_{i=\emptyset}a_{i}=true\end{displaymath}$

$\begin{displaymath}\bigvee_{i=\emptyset}a_{i}=false\end{displaymath}$

Tautologie:
Eine Formel ist dann eine Tautologie, wenn sie für alle Belegungen erfüllt ist.