2

I am struggling with a simple logic problem. I need to convert into a disjunctive normal form the following: $\lnot (P \lor \lnot Q) \lor (\lnot P \iff Q)$

After turning the biconditionals into the equivalent conjunction/disjunction I got stuck. Any help please? Thank you!

Tian Vlašić
  • 1,318
Ladysuss
  • 37

2 Answers2

2

disjunctive normal form: $ (Q \wedge \neg P) \vee (\neg Q \wedge P) $

there may be a shorter proof than what I outline below...

$\lnot (P \lor \lnot Q) \lor (\lnot P \leftrightarrow Q)$

$\lnot (P \lor \lnot Q) \lor \Big[ (\lnot P \to Q) \wedge (Q \to \lnot P)\Big] $ definition of biconditional

$\lnot (P \lor \lnot Q) \lor \Big[ (\neg\neg P \vee Q) \wedge (\neg Q \vee \lnot P)\Big] $ implication law

$\lnot (P \lor \lnot Q) \lor \Big[ (P \vee Q) \wedge (\neg Q \vee \lnot P)\Big] $ double negation law

$(\neg P \wedge \neg\neg Q) \lor \Big[ (P \vee Q) \wedge (\neg Q \vee \lnot P)\Big] $ DeMorgan's law

$(\neg P \wedge Q) \lor \Big[ (P \vee Q) \wedge (\neg Q \vee \lnot P)\Big] $ double negation law

$\Big[ (\neg P \wedge Q) \vee (P \vee Q) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ distribution law

$\Big[ ((\neg P \wedge Q) \vee P) \vee ((\neg P \wedge Q) \vee Q)) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ distribution law

$\Big[ ((\neg P \wedge Q) \vee P) \vee Q) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ absorption law

$\Big[ ((\neg P \vee P) \wedge (Q \vee P)) \vee Q) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ distribution law

$\Big[ (T \wedge (Q \vee P)) \vee Q) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ negation law

$\Big[ (Q \vee P) \vee Q) \Big] \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ identity law

$(Q \vee P) \wedge \Big[ (\neg P \wedge Q) \vee (\neg Q \vee \lnot P) \Big] $ idempotent law

$(Q \vee P) \wedge \Big[ ((\neg P \wedge Q) \vee \neg Q) \vee ((\neg P \wedge Q) \vee \lnot P) \Big] $ distribution law

$(Q \vee P) \wedge \Big[ ((\neg P \wedge Q) \vee \neg Q) \vee \neg P \Big] $ absorption law

$(Q \vee P) \wedge \Big[ ((\neg P \vee \neg Q) \wedge (Q \vee \neg Q)) \vee \neg P \Big] $ distribution law

$(Q \vee P) \wedge \Big[ ((\neg P \vee \neg Q) \wedge T) \vee \neg P \Big] $ negation law

$(Q \vee P) \wedge \Big[ (\neg P \vee \neg Q) \vee \neg P \Big] $ identity law

$(Q \vee P) \wedge ( \neg P \vee \neg Q ) $ idempotent law

$ (Q \vee P) \wedge \neg P) \vee ((Q \vee P) \wedge \neg Q) $ distribution law

$ (Q \wedge \neg P) \vee (P \wedge \neg P) \vee (Q \wedge \neg Q) \vee (P \wedge \neg Q) $ distribution law

$ (Q \wedge \neg P) \vee F \vee F \vee (P \wedge \neg Q) $ negation law

$ (Q \wedge \neg P) \vee (P \wedge \neg Q) $ identity law

RyRy the Fly Guy
  • 5,950
  • 1
  • 11
  • 27
1

For the sake of completeness, I'd note a semantic method as an alternative:

As the first step, find the sets on which the propositional formula takes true value: $\{0, 1\}, \{1, 0\}$

Then, match these sets to conjunctions of all variables such that if a variable in the set takes false value, it will be represented negated, otherwise as it is. Thus, we get the minterms:

$Min_{1}:\{0, 1\}\implies\neg P\wedge Q$

$Min_{2}:\{1, 0\}\implies P\wedge\neg Q$

Combine conjunctions (minterms) by disjunction to obtain DNF:

$Min_{1}\vee Min_{2} = (\neg P\wedge Q)\vee (P\wedge\neg Q)$

By experience, we see that the result is in the simplest form. Otherwise, we can simplify it by the technique of Karnaugh map.

Tankut Beygu
  • 2,331