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