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 got this form:

(not M or V) and (A or not M) and (not B or M) and (B or V) and (A or not V) and (not A or B)

Or: $$(\neg M\vee V) \wedge (A\vee\neg M) \wedge (\neg B \vee M) \wedge (B\vee V) \wedge (A\vee\neg V)\wedge(\neg A \vee B)$$

Can anyone explain me how to solve it step by step? The result should be this:

A and B and M and V: $$A\wedge B \wedge M \wedge V$$

Wolfram Alpha link.

I dont know how to simplify the statement

share|improve this question
1  
Have you tried "slow and steady" approach? Open one after another... after another... –  Asaf Karagila Dec 18 '12 at 20:38

1 Answer 1

$$(\neg M\vee V) \wedge \color{blue}{(A\vee\neg M)} \wedge (\neg B \vee M) \wedge \color{red}{(B\vee V) \wedge} \color{blue}{(A\vee\neg V)}\wedge \color{red}{(\neg A \vee B)}\tag{1}$$

$$\color{blue}{[A \lor (\lnot V \land \lnot M)]} \land \color{red}{[B \lor (\lnot A \land V)]} \land \color{green}{(\lnot B \lor M) \land (\lnot M \lor V)}\tag{2}$$

$${[A \lor (\lnot V \land \lnot M)]} \land {[B \lor (\lnot A \land V)]} \land \color{green}{(B \rightarrow M) \land ( M \rightarrow V)}\tag{3}$$

$$\vdots$$

$$A \land B\land M\land V\tag{result}$$


Note: To "deduce" this, I've highlighted some initial steps:

  • $(1) \to (2)$ using
    • commutativity: $(P \lor Q) \equiv (Q \lor P)$ and $P \land Q \equiv Q \land P$,
    • associativity: $P\land (Q \land R) \equiv (P\land Q)\land R$,
    • distributive law (applied twice): $(P\lor Q) \land (P\lor R) \equiv P\lor (Q \land R)$, and
  • $(2)\to (3)$ using the identity ($\lnot P \lor Q) \equiv (P\rightarrow Q$),
  • It follows from $(3)$ (with more work needed to establish) that we must have $A$ and $B$; and since $B$, then also $M$; and since $M$, then also $V$. Why?

It also helps to use a truth-table, from which we can derive the conjunctive-normal form $(\text{result})$ of your expression given in $(1)$:

enter image description here

Note from the truth-table that the given expression evaluates to $\;T=$ true$\;$ only in the first row, if and only if $\;A,\text{ AND}\; B, \text{ AND}\;M, \text{ AND}\; V\;$ are all $\;T=$ true$\;$.
That is, we can conclude:
$$(\neg M\vee V) \wedge {(A\vee\neg M)} \wedge (\neg B \vee M) \wedge {(B\vee V) \wedge} {(A\vee\neg V)}\wedge {(\neg A \vee B)}$$ $$\iff A \land B \land M \land V$$


share|improve this answer
    
But this is not "multiplying out", this is circumventing the algebraic manipulation. If the OP is fine with it, then it's fine. But it might not be the case. (Also congratulation on a fresh new avatar!) –  Asaf Karagila Dec 18 '12 at 21:07
    
One might call me "not a colorful person", but I was never a big fan of colors... :-P –  Asaf Karagila Dec 19 '12 at 2:28
    
@Asaf: it simply helped to simplify any necessary explanation/justification. I'm not big on colors, either! –  amWhy Dec 19 '12 at 2:32
    
I have problems discerning between some of them and they mostly just hurt my eyes. See this meta thread. –  Asaf Karagila Dec 19 '12 at 2:40
    
+1 for formatting :) –  Parth Kohli Dec 19 '12 at 14:43

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.