How to find an equivalent formula? I have a formula: $p \wedge \neg q \implies q \vee \neg p $, and i have calculated a truth table as follows:
$$\begin{array}{c}
p&q&\text{Formula}\\ \hline
0&0&1\\
0&1&1\\
1&0&0\\
1&1&1
\end{array}$$
Somehow, they found an equivalent formula to be $ \neg p \vee q$. But I am not sure how they achieved this. Thanks for the help.
 A: In this particular case, if you scan down the right side of the truth table, you get almost all $1$'s. The sentence is false only if $p$ holds and $q$ fails. So the negation of our sentence is equivalent $p\land \lnot q$. It follows that our sentence is equivalent to $\lnot(p\land \lnot q)$, and therefore to $\lnot p\lor q$.
This kind of procedure is also useful when there are more proposition letters, but the sentence is "seldom" false (or seldom true).  
A: It may have been done algebraically, rather than by means of a truth table.
Since $r\to s$ is logically equivalent to $\lnot r\lor s$, $p \wedge \neg q \to q \vee \neg p$ is logically equivalent to $\lnot(p\land\lnot q)\lor(q\lor\lnot p)$. Applying de Morgan’s law to the first term, we see that this in turn is logically equivalent to $\lnot p\lor q\lor q\lor\lnot p$. And of course $q\lor q$ and $\lnot p\lor\lnot p$ are logically equivalent to $q$ and to $\lnot p$, respectively, so $\lnot p\lor q\lor q\lor\lnot p$ reduces to $\lnot p\lor q$.
