Logical equivalence: Which side is better to start to obtain the other?

Question

How to resolve this with steps please:

$$p \to (q \lor r) \equiv (p \to q) \lor (p \to r)$$

I just don't get how with less variable we can have more after or with more we can have less?

Answer 1

$$\begin{align} p \to (q \lor r)& \equiv \lnot p \lor (q \lor r)\\ \\ &\equiv \lnot p \lor q \lor r \\ \\ &\equiv \lnot p \lor \lnot p \lor q \lor r\\ \\ & \equiv \lnot p \lor q \lor \lnot p \lor r \\ \\ &\equiv (\lnot p \lor q) \lor (\lnot p \lor r)\\ \\ &\equiv (p \rightarrow q) \lor (p \rightarrow r)\end{align}$$

We use the fact that $a\rightarrow b \equiv \lnot a \lor b$, and the fact that $a \equiv a\lor a$. We also use associativity of $\lor$, as well as commutativity of $\lor$.

Note that in each form, there are only 3 variables. We simply repeated $\lor \lnot p$ in order to show that both sides of the equivalence are, in fact, equivalent. There are many ways to transform a proposition to a logically equivalent proposition that "looks different".

Answer 2

In general, in my experience it is usually best to start at the most complex side. Why? Well, that turns the problem into a simplification problem. And often there are just a few ways to simplify, but a lot of ways to introduce complexity.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $Therefore I would prove this in essentially the same way as amWhy's first answer does, but in the opposite direction:

$$\calc (p \to q) \lor (p \to r) \calcop={write $\;P \to Q\;$ as $\;\lnot P \lor Q\;$, twice; $\;\lor\;$ is associative, so no parentheses} \lnot p \lor q \lor \lnot p \lor r \calcop={$\;\lor\;$ is symmetric -- bring similar terms together} \lnot p \lor \lnot p \lor q \lor r \calcop{\tag{*}=}{$\;\lor\;$ is idempotent -- to simplify} \lnot p \lor q \lor r \calcop={reintroduce $\;\to\;$} p \to (q \lor r) \endcalc$$

Note how the key step $\ref{*}$ is much easier go find in the simplifying direction than in the 'complicating' direction: there is no need to pull a rabbit out of a hat.

(For a bit more on rabbit extermination, see the introduction of Edsger W. Dijkstra, "The notational conventions I adopted, and why" (EWD1300).)