5
$\begingroup$

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

  • 1
    Have you tried "slow and steady" approach? Open one after another... after another...2012-12-18

1 Answers 1

6

$$(\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$$


  • 0
    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!)2012-12-18
  • 0
    One might call me "not a colorful person", but I was never a big fan of colors... :-P2012-12-19
  • 0
    @Asaf: it simply helped to simplify any necessary explanation/justification. I'm not big on colors, either!2012-12-19
  • 0
    I have problems discerning between some of them and they mostly just hurt my eyes. See [this meta thread](http://meta.math.stackexchange.com/questions/4195/on-the-use-of-color-in-equations).2012-12-19