Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » NPC Beweise » Aussagelogik
NP-hart, NP-vollständig NPC Beweise Satz von Cook

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.
NP-hart, NP-vollständig NPC Beweise Satz von Cook