Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.