Are the following logical statements equal? Solution verification

Question

We were requested to rewrite the following statement: \begin{equation*} ((\phi \rightarrow(\psi \lor \lnot X)) \land (\phi \rightarrow (\psi \land X))) \end{equation*} using $\exists, \land, \lnot $ only. My result: \begin{equation*} ((\lnot(\phi \land (\lnot \psi \land X))\land (\lnot \phi \land \lnot (\psi \land X))) . \end{equation*} Is this correct? Is there a quick way of verifying this solution?

Thank you.

Answer 1

Your left-hand side conjunctor is ok, but not the right-hand side one, as Mauro commented.

$$ (ϕ→(ψ∨¬X))∧(ϕ→(ψ∧X)) \iff ((¬(ϕ∧(¬ψ∧X))∧\underbrace{\color{}{(¬ϕ∧¬(ψ∧X))}}_{¬(ϕ∧¬(ψ∧X))})$$

Recall the equivalences we need:

1. $ \alpha \rightarrow \beta \equiv \neg (\alpha \land \neg \beta)$
2. $ \alpha \lor \beta \equiv \neg (\neg \alpha \land \neg \beta)$

To avoid mistakes, I suggest you to proceed by steps.

Also, you don't need really to care about the existential quantifier $\exists$, since your given formula

$$(ϕ→(ψ∨¬X))∧(ϕ→(ψ∧X))$$

is a propositional formula, so that it doesn't really makes sense to require it in a equivalence.