1
$\begingroup$

I have to show the following

  1. Is Pr $[\varphi \leftrightarrow \psi]=1,$ so is $\operatorname{Pr}[\varphi]=\operatorname{Pr}[\psi]$

  2. Is $\operatorname{Pr}[\varphi \rightarrow \psi]=1,$ so is $\operatorname{Pr}[\varphi] \leq \operatorname{Pr}[\psi] $

  3. For all $\varepsilon>0$ $\operatorname{Pr}[\varphi \rightarrow \psi] \geq 1-\varepsilon,$ implies that $\operatorname{Pr}[\varphi] \leq \operatorname{Pr}[\psi]+\varepsilon .$

  4. In none of the cases holds the reversal . (For the third case Fall this means, that there is a distribution, formulas and an $\varepsilon>0$ exists with $\operatorname{Pr}[\varphi] \leqq \operatorname{Pr}[\psi]+\varepsilon$ but $\operatorname{Pr}[\varphi \rightarrow \psi]<1-\varepsilon $

Could someone please help me through that?

Edit1:

For the second one i did the following

$P[\varphi \rightarrow \psi]=1 \equiv P[\neg \varphi \vee \psi] = 1$

$ \equiv P[\neg \varphi] + P[\psi] - P[\neg \varphi \wedge \psi]=1$

$\equiv 1-P[\varphi] + P[\psi] - P[\neg \varphi \wedge \psi] = 1$

$\equiv P[\psi] - P[\neg \varphi \wedge \psi] = P[\varphi]$

$\implies P[\varphi] \leq P[\psi]$

Now i am stuck with the first case wherer i have $$P[\varphi \rightarrow \psi] \geq 1- \epsilon \equiv P[\neg \varphi \vee \psi] \geq 1 - \epsilon$$ $$\equiv P[\neg \varphi]+P[\psi]-P[\neg \varphi \wedge \psi] \geq 1- \epsilon $$ $$\equiv 1-P[\varphi]+P[\psi]-P[\neg \varphi \wedge \psi] \geq 1 - \epsilon $$ $$\equiv P[\psi]-P[\neg \varphi \wedge \psi] \geq - \epsilon + P[\varphi]$$ $$\equiv P[\psi] + \epsilon \geq P[\varphi] + P[\neg \varphi \wedge \psi]$$

$\endgroup$
1
  • $\begingroup$ Anyone some advice on 4. ? $\endgroup$ – Rapiz Jan 4 '20 at 19:06
1
$\begingroup$

Notice: If $p\geq q+r$ and $r\geq 0$, then $p\geq q$.

You have reached $\Pr[\psi]+\epsilon\geq\Pr[\varphi]+\Pr[\neg\varphi\wedge\psi]$, and so ...

$\endgroup$
2
  • $\begingroup$ Well yeah that simply states that Pr[ψ]+ϵ≥Pr[φ] thanks any ideas for the 4 ? $\endgroup$ – Rapiz Jan 1 '20 at 18:21
  • $\begingroup$ i have now done 1 to 3 i know that for the fourth i have to show that these do not hold backwards for each $\endgroup$ – Rapiz Jan 2 '20 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.