Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I don't know how to prove that $p\Rightarrow q$ is equivalent to $\neg p\lor q$ ,here is the link p=>q . And I don't know how wolframalpha generate "Minimal forms" .

Can you prove $p\Rightarrow q \equiv \neg p\lor q$, and explain how to get "Minimal forms" ?


share|cite|improve this question
Okay, => means implication, $\Rightarrow$. I take it that $||$ means "or", $\lor$? – Arturo Magidin Aug 18 '11 at 3:39
yes thanks I'm new here – ifree Aug 18 '11 at 3:42
No problem. Want me to edit it to more standard mathematical notation? – Arturo Magidin Aug 18 '11 at 3:45
yes thanks and how about the Minimal forms – ifree Aug 18 '11 at 3:49
There are algorithms for transforming propositional formulas into normal forms; see for example Wikipedia. Presumably, wolframalpha has programmed the algorithms in order to find the normal minimal forms. – Arturo Magidin Aug 18 '11 at 3:52
up vote 4 down vote accepted

By definition, $p\Rightarrow q$ is true if and only if the consequence $q$ is true, or the antecedent $p$ is false. You can see it in the truth table that defines the implication. That is, $p\Rightarrow q$ is true if and only if either $\neg p$ is true, or $q$ is true; i.e., if and only if $\neg p\lor q$ is true (what you write as $!p||q$).

Or you can simply look at the truth tables. The truth table of $\neg p\lor q$ is the same as the truth table of $p\Rightarrow q$: true if $p$ and $q$ are false; true if $p$ is false and $q$ is true; false if $p$ is true and $q$ is false; true if $p$ and $q$ are both true: $$\begin{array}{c|c||c} p & q & p\Rightarrow q\\ \hline 0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}\qquad\qquad \begin{array}{c|c|c|c} p & q & \neg p & \neg p\lor q\\ \hline 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 1 \end{array}.$$ The final columns are identical, so the two formulas take the same truth values given the same truth inputs: that is, they are propositionally equivalent.

share|cite|improve this answer
Thanks a lot! have a nice day:) – ifree Aug 18 '11 at 3:56

Using truth tables is a simple way to prove it.

share|cite|improve this answer

Your Answer


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.