1
$\begingroup$

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.

2 Answers 2

3

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).

2

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$.