Proofs in propositional logic I'm preparing for a class of mine in the next semester named mathematical logic and I'm working on old class materials. As I have no solutions I'd like to ask you if you could tell me if my solutions are correct.
(1) Show whether tautology, satisfiable or not satisfiable.
(a) $(X \to 1) \to (0 \to Y)$


*

*$(X \to 1) \to (0 \to Y) \equiv (X \to 1) \to 1 \equiv 1 \to 1 \equiv 1$


Clearly a tautology.
(b) $(1 \to (X \lor Y)) \land (0 \to (\lnot X \land \lnot Y))$


*

*$(1 \to (X \lor Y)) \land (0 \to (\lnot X \land \lnot Y)) \equiv (0 \lor (\lnot X \land \lnot Y)) \land (1 \lor X \lor Y)) \equiv (0 \lor (\lnot X \land \lnot Y)) \land 1$


Satisfiable, but not a tautology. Satisfiable with interpretation I with $I(X) = I(Y) = 0$.
(c) $\lnot (Y \to X) \land (\lnot X \to (X \land Y))$


*

*$\lnot (Y \to X) \land (\lnot X \to (X \land Y)) \equiv (Y \land \lnot  X) \land \lnot (\lnot X \land \lnot (X \land Y)) \equiv (Y \land \lnot  X) \land (X \lor (X \land Y)) \equiv (Y \land \lnot  X) \land (X \lor X) \land (X \lor Y)) \equiv Y \land \lnot  X \land X \land (X \lor Y)) \equiv Y \land 0 \land (X \lor Y)) \equiv 0$


Not satisfiable.
(2) Show that the following formulas are equivalent.
(a) $(Y \to X)\land((X \lor Z)\to Y) \equiv (X \lor Y \lor Z) \to (X \land Y)$


*

*$(Y \to X)\land((X \lor Z)\to Y) \equiv (\lnot Y \lor X) \land (\lnot (X \lor Z) \lor Y) \equiv (\lnot Y \lor X) \land ((X \land Z) \lor Y) \equiv ?$ what next?


(b) $(X \land Z) \lor ((X \land Z) \land ((Y \lor \lnot Z) \to U)) \equiv ((\lnot Y \land Z) \lor U \lor (X \land Z)) \land X \land Z$
I don't know how to solve these ones. Could you please help me out with these or give me a hint?
 A: For 2a:
$(Y \to X)\land((X \lor Z)\to Y) \equiv$ (Implication)
$\neg(Y \land \neg X) \land (\neg ((X \lor Z) \land \neg Y)) \equiv$ (DeMorgan)
$(\neg Y \lor \neg \neg X) \land (\neg (X \lor Z) \lor \neg \neg Y) \equiv$ (Double Negation)
$(\neg Y \lor X) \land (\neg (X \lor Z) \lor Y) \equiv$ (DeMorgan)
$(\neg Y \lor X) \land ((\neg X \land \neg Z) \lor Y) \equiv$ (Distribution)
$(\neg Y \lor X) \land (\neg X \lor Y) \land (\neg Z \lor Y) \equiv$ (Identity)
$(\neg Y \lor X) \land (\neg X \lor Y) \land (\neg Z \lor Y) \land 1 \equiv$ (Complement)
$(\neg Y \lor X) \land (\neg X \lor Y) \land (\neg Z \lor Y) \land (\neg Y \lor Y) \equiv$ (Distribution)
$((\neg Y \lor X) \land (\neg X \lor Y) \land (\neg Z \lor Y) \land \neg Y) \lor ((\neg Y \lor X) \land (\neg X \lor Y) \land (\neg Z \lor Y) \land Y) \equiv$ (Reduction)
$ ((\neg Y \lor X) \land (\neg X \land \neg Z \land \neg Y)\lor (X \land (\neg X \lor Y) \land (\neg Z \lor Y) \land Y) \equiv$ (Absorption)
$ (\neg X \land \neg Z \land \neg Y) \lor (X \land Y) \equiv$ (DeMorgan)
$ \neg (X \lor Z \lor Y) \lor (X \land Y) \equiv$ (Double Negation)
$ \neg (X \lor Z \lor Y) \lor \neg \neg (X \land Y) \equiv$ (DeMorgan)
$\neg((X \lor Y \lor Z) \land \neg (X \land Y)) \equiv$ (Implication)
$(X \lor Y \lor Z) \to (X \land Y)$
Phew!  Note that a good number of steps could have been done at once with the following equivalence:
Implication
$P \rightarrow Q \equiv \neg P \lor Q$
Akso, two very useful principles I used here are:
Absorption
$P \land (P \lor Q) \equiv P$
Reduction
$P \land (\neg P \lor Q) \equiv P \land Q$
But even with that, this boolean algebra solution was probably a lot more work than an 8-row truth-table would have been! :)
... I'll leave you to 2b ...
A: Notice that $$A\to B\equiv\neg(A\wedge\neg B)\equiv(\neg A)\vee B.$$
(1)
(b) \begin{align}
(1\to(X\vee Y))\wedge(0\to(\neg X\wedge\neg Y))&\equiv (0\vee X\vee Y)\wedge(1\vee(\neg X\wedge\neg Y))\\&\equiv(0\vee X\vee Y)\wedge(1\vee\neg X)\wedge(1\vee\neg Y)\\&\equiv(0\vee X\vee Y)\wedge1\wedge1\\&\equiv0\vee X\vee Y
\end{align} Satisfiable iff $X,Y\neq0.$
(2)
(a) \begin{align}
(Y\to X)\wedge((X\vee Z)\to Y)&\equiv(\neg Y\vee X)\wedge(\neg(X\vee Z)\vee Y)\\&\equiv(\neg Y\vee X)\wedge((\neg X\wedge\neg Z)\vee Y)\\&\equiv(\neg Y\vee X)\wedge(\neg X\vee Y)\wedge(\neg Z\vee Y)
\end{align} And \begin{align}
(X\vee Y\vee Z)\to(X\wedge Y)&\equiv\neg(X\vee Y\vee Z)\vee(X\wedge Y)\\&\equiv(\neg X\wedge\neg Y\wedge\neg Z)\vee(X\wedge Y)
\end{align} Both are satisfiable iff $X,Y,Z=0\vee X,Y=1.$
(b) \begin{align}
((\neg Y\wedge Z)\vee U\vee(X\wedge Z))\wedge X\wedge Z&\equiv(X\wedge Z\wedge X\wedge Z)\vee(((\neg Y\wedge Z)\vee U)\wedge X\wedge Z)\\&\equiv(X\wedge Z)\vee(X\wedge Z\wedge(\neg(Y\vee\neg Z)\vee U))\\&\equiv(X\wedge Z)\vee((X\wedge Z)\wedge((Y\vee\neg Z)\to U))
\end{align}
