Formale Grunden der Informatik - Tautologien

05.05.2008, 11:31	Anita23	Auf diesen Beitrag antworten »
Formale Grunden der Informatik - Tautologien Hallo Leute Ich bekommen bei einer Aufgabe im Informatikstudium Kopfzerbrechen, die Aufgabenstellung ist eingentlich sehr schlüssig, dennoch bereitet mir der Beweis schwierigkeiten. --------- Seinen M = {A1, A2, ....An} eine endliche Formelmenge und A und B Formeln. Beweisen Sie: 1.) Gilt M \|= A und ist B eine Tautologie, so folgt M\{B} \|= A 2.) M \|= A gilt genau dann, wenn \|=(A1^A2^....^An) => A ------------- Lg, Anita
05.05.2008, 11:38	Dual Space	Auf diesen Beitrag antworten »
RE: Formale Grunden der Informatik - Tautologien Wie ist denn die Realtion "\|=" definiert?
05.05.2008, 12:15	Mazze	Auf diesen Beitrag antworten »
Ist $\begin{eqnarray} \Phi \end{eqnarray}$ eine Belegung und F eine Formel und $\begin{eqnarray} \Phi(F) = 1 \end{eqnarray}$ dann schreibt man $\begin{eqnarray} \Phi \models F \end{eqnarray}$ . Entsprechend gilt für eine Menge von Formeln M: $\begin{eqnarray} \Phi \end{eqnarray}$ ist ein Model von M wenn $\begin{eqnarray} \Phi(x) = 1 ~ \forall x \in M \end{eqnarray}$ man schreibt dann $\begin{eqnarray} \Phi \models M \end{eqnarray}$ Weiterhin gilt : $\begin{eqnarray} M \models A \Leftrightarrow \forall \Phi : \Phi \models M \Rightarrow \Phi \models A \end{eqnarray}$ so und nun zu Deinem Problem: Wenn $\begin{eqnarray} M \models A \end{eqnarray}$ gilt, dann gilt nach definition oben $\begin{eqnarray} \forall \Phi : \Phi \models M \Rightarrow \Phi \models A \end{eqnarray}$ Da B eine Tautologie ist gilt, das $\begin{eqnarray} \forall \Phi \models M\setminus{B} \Rightarrow \Phi \models B \end{eqnarray}$ . Das musst Du nur noch zusammen pappen. Zweitens ist schon interessanter. Die Rückrichtung ist klar, wenn die Konjunktion aller Formeln eine Tautologie ist, und die Folgerung gilt, so muss auch $\begin{eqnarray} M \models A \end{eqnarray}$ gelten. Das muss man nur aufschreiben. Die Hinrichtung zeigt man mittels Kontraposition. Nimm an es gilt $\begin{eqnarray} M \models A \end{eqnarray}$ aber es gibt eine Belegung $\begin{eqnarray} \Phi \end{eqnarray}$ so das gilt $\begin{eqnarray} \Phi(A) = 0 \end{eqnarray}$ . Zeige das dann $\begin{eqnarray} \Phi \models M \end{eqnarray}$ aber nicht $\begin{eqnarray} M \models A \end{eqnarray}$ gilt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »