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 am asked to show the following argument is valid:

I know you need to use the rules of inference like modus ponens/converse fallacy but I'm confused because it doesn't look like any of the forms I've learned about?

$$N\to B\lor S\\ S\to W\lor A \\ M\to N\land W \\ \text{therefore, }M\to B\lor A$$

I don't want to use the truth table because it will be real long. If someone can get me started i would really appreciate the help. thx

share|cite|improve this question
After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. If you don't do this, people are less likely to answer your later questions. – MJD Oct 1 '12 at 3:35
up vote 2 down vote accepted

No valid argument can prove this. Suppose $M, N, S$ and $W$ are true, and $A$ and $B$ are false. Then the three premisses are all true, but the conclusion is false.

share|cite|improve this answer
As a way to find this, the only way to make the conclusion false is to have $M$ true and $A$ and $B$ false. To make the premises true you then (from the third) need $N$ and $W$ true. Then from the first you need $S$ to be true. Now check that the second is satisfied and you are done. – Ross Millikan Oct 1 '12 at 4:28

You could turn your question into a binary decision diagram (BDD). If you assure that these BDDs are short and unique for logical equivalence classes, than you can read-off from the BDDs the following:

1) If the BDD has the form "true", then it is a tautology.

2) If the BDD has the form "false", then its negation is a tautology.

3) In all other cases the BDD nor its negation is a tautology.

In case 2) and 3) there is a model of the BDD that make it false. Let's give it a try, and let's convert your problem into a BDD via the program in ( * ) and ( ** ). We get the following result:

?- convert((n=>b v s)&(s=>w v a)&(m=>n & w)=>(m=>b v a),X).
X = (a->true;b->true;m->(n->(s->(w->false;true);true);true);true)

So it indeed differs from "true" and should be thus falsifiable. By extracting a CNF from the BDD we can also read off a counter model. Let's also do it for your problem:

?- cnf((a->true;b->true;m->(n->(s->(w->false;true);true);true);true),[],L).
L = [not(w),not(s),not(n),not(m),b,a] 

So the only counter model is w=1, s=1, n=1, m=1, b=0, a=0.

Proof: If the BDD is not "true", then the CNF will at least contain one row. From this row we can directly construct a model that falsifies the row, for unmentioned propositional variables add either false or true, for mentioned propositional variables add a value that falsifies the literal in the row. Since by construction no propositional variable occurs twice in a row, the row can be falsified. Since the row is falsified the whole CNF is falsified.

( * ) Invert, Inter and Union on BDDs with Lexical Variable Order:

( ** ) Convert, DNF and CNF for BDDs:

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.