In der Informatik werden logische Formeln häufig genutzt, um zu spezifizieren, welche Situationen (=Welten) erlaubt sind und welche nicht. Natürlich sollten Systeme so gestaltet sein, dass verbotene Situationen nicht auftreten - oder dies zumindest möglichst unwahrscheinlich wird. In dieser Aufgabe soll es um solche Wahrscheinlichkeiten gehen. Wir ordnen Welten Wahrscheinlichkeiten zu: Sei dazu
$$B=\left\{\beta | \beta:\left\{x_{1}, \ldots, x_{n}\right\} \rightarrow\{0,1\}\right\}$$
die Menge aller möglichen Welten (für feste n Variablen). Eine Wahrscheinlichkeitsverteilung p ordnet jeder Welt
$$\beta \in B $$ eine Wahrscheinlichkeit
$$p(\beta)$$ zwischen 0 und 1 dafür zu, dass diese Situation (=Welt) eintritt. Wenn zum Beispiel die Variable b für es brennt:
steht und die Variable m für (Brand-)Melder piepst: dann bedeutet $$p(\beta)=0.9$$
mit $$ \beta(b)=0, \beta(m)=0 $$ und $$ p\left(\beta^{\prime}\right)=0.05$$ mit $$ \beta^{\prime}(b)=0, \beta^{\prime}(m)=1$$, dass mit 90 % Wahrscheinlichkeit es nicht brennt und der Melder gleichzeitig nicht piepst und es mit 5 % Wahrscheinlichkeit nicht brennt, aber der Melder trotzdem piepst. Die fehlenden 5 % (es gilt immer p(b)=1)
müssen sich dann auf die Fälle es brennt und es piepste und es brennt und es piepst nicht verteilen. Wir können nun Formeln $$ \varphi $$ text{ in natürlicher Weise eine Wahrscheinlichkeit zuordnen: $$ P[\varphi]=\sum_{\beta \in B, \beta \models \varphi} p(\beta),$$ die Wahrscheinlichkeit einer Formel ist also die Summe der Wahrscheinlichkeiten aller Situationen (=Welten), in denen sie eintritt (=wahr ist).
Zeigen Sie
1. Ist Pr[ ϕ↔ψ ] = 1,so gilt Pr[ ϕ ] = Pr[ ψ ].(»Sind Formeln sicher äquivalent,so sind sie gleichwahrscheinlich.«)
2. Ist Pr[ ϕ→ψ ] = 1,sogiltPr[ ϕ ]≤Pr[ ψ ].(»Folgt ψ sicher aus ϕ ,ist ψ
mindestens so wahrscheinlich wie ϕ .«)
3. Für alleε> 0 folgt aus Pr[ ϕ→ψ ] ≥1−ε , dass Pr[ ϕ ] ≤ Pr[ ψ ] +ε . (»Folgt ψ fast sicher aus ϕ , ist ψ fast so wahrscheinlich wie ϕ .«)
4. In keinem der Fällen gilt die Umkehrung. (Für den dritten Fall bedeutet dies, dass es eine Verteilung, Formeln und ein ε > 0 gibt mit Pr[ ϕ ] ≤ Pr[ ψ ] + ε aber Pr[ ϕ → ψ ] < 1− ε .)
Ansatz:
1.
P[ϕ ↔ ψ] = 1 ≡ P[(ϕ∧ψ)∨(¬ϕ∧¬ψ)] = 1 ≡ P[ϕ∧ψ] + P[¬ϕ∧¬ψ] = 1 ≡ P[ϕ∧ψ] = 1−P[¬ϕ∧¬ψ] ≡ P[ϕ∧ψ] = P[ϕ∨ψ] ≡ P[ϕ∧ψ] = P[ϕ/ψ] + P[ψ/ϕ] + P[ϕ∧ψ] ≡ 0 = P[ϕ/ψ] + P[ψ/ϕ] ≡ 0 = P[ϕ∧¬ψ] + P[ψ∧¬ϕ] ≡−P[ϕ∧¬ψ] = P[ψ∧¬ϕ] =⇒ P[ϕ∧¬ψ] = 0 und P[ψ∧¬ϕ] = 0 P[ϕ] = P[ϕ/ψ] + P[ϕ∧ψ] =⇒ P[ϕ] = 0 + P[ϕ∧ψ] =⇒ P[ϕ] = P[ϕ∧ψ] =⇒ P[ϕ] + P[¬ϕ∧¬ψ] = 1 =⇒ P[ϕ] = 1−P[¬ϕ∧¬ψ] =⇒ P[ϕ] = P[ϕ∨ψ] =⇒ P[ϕ] = P[ϕ] + P[ψ]−P[ϕ∧ψ] =⇒ P[ϕ] = P[ϕ] + P[ψ]−P[ϕ] =⇒ P[ϕ] = P[ψ]
2.
P[ϕ → ψ] = 1 ≡ P[¬ϕ∨ψ] = 1 ≡ P[¬ϕ] + P[ψ]−P[¬ϕ∧ψ] = 1 ≡ 1−P[ϕ] + P[ψ]−P[¬ϕ∧ψ] = 1 ≡ P[ψ]−P[¬ϕ∧ψ] = P[ϕ] =⇒ P[ϕ] ≤ P[ψ]
1
3.
P[ϕ → ψ] ≥ 1−e ≡ P[¬ϕ∨ψ] ≥ 1−e ≡ P[¬ϕ] + P[ψ]−P[¬ϕ∧ψ] ≥ 1−e ≡ 1−P[ϕ] + P[ψ]−P[¬ϕ∧ψ] ≥ 1−e ≡ P[ψ]−P[¬ϕ∧ψ] ≥−e + P[ϕ] ≡ P[ψ] + e ≥ P[ϕ] + P[¬ϕ∧ψ] =⇒ P[ψ] + e ≥ P[ϕ]
Zu 4 habe ich jetzt keinen Ansatz, da ich dort nicht weiß wie ich das vernünftig unformen kann um auf die Behauptung zurückzukommen.
1. Pr[ ϕ ] = Pr[ ψ ] Weiß da nicht wie ich auf Pr[ ϕ↔ψ ] != 1 komme.
Gleiches für 2 und 3.
Kann mir da bitte jemand weiterhelfen? Finde auch nichts vernünftiges dazu.
