-1

Why is $\neg(P\land Q)$ equivalent to $\neg P\lor\neg Q$, and how do we prove it?

Thanks!

Lord_Farin
  • 17,743
abla
  • 7
  • 2
    Write down the truth tables and compare them. – Michael Greinecker Oct 25 '13 at 09:35
  • If you search for De Morgan's laws, you'll find ample questions that discuss this. – Lord_Farin Oct 25 '13 at 10:04
  • If you want a proof without using truth table you can define a function $v(P)$ that is called truth value. if $P$ is true then $v(P)=1$ and if $P$ is false then $v(P)=0$. Then following formula in logic is true. $$v(\neg P)=1-v(P)$$ $$v(P\land Q)=v(P)v(Q)$$ $$v(P\lor Q)=v(P)+v(Q)-v(P)v(Q)$$ Now if you use above formulas you can see that $$v(\neg(P\land Q))=v(\neg P\lor\neg Q)=1-v(P)v(Q).$$ – user91500 Oct 27 '13 at 17:16

1 Answers1

2

First of all you have the following acts in logic: ∧:Conjugation ∨:Divorcement ¬ :Negation

In Boolean Calculus there also the following:

$\bigoplus$:either(where we have true or 1 only if one of the operators in the act is true ,e.x $0 \bigoplus 0=0$, $0 \bigoplus 1=1$, $1 \bigoplus 0=1$, $1 \bigoplus 1=0$.

$<->$:which is the equality

$->$:implication.

All these Boolean acts can be described with the non boolean ones like:

$P∨Q$=$¬(¬P∧¬Q)$

$P->Q$=$¬P∨Q$

$P<->Q$=$(P->Q)∧(Q->P)$

$P \bigoplus Q$=$¬(P<->Q)$

Now a main tool for these things is the distributive property.

With all these you can get minimal forms.

Now for the $¬(P∧Q)=¬P∨¬Q$

When you use $¬$ in front of a bracket it acts on every operators in the bracket.So the $∧$ becomes $∨$ and everything that has $¬$ then doesn't because $¬(¬P)=P$,because if you say no to no then it's yes!

Haha
  • 5,648
  • many thanks for your help, sorry for the miss leading i want the Proof of the De Morgan's laws in implication – abla Oct 25 '13 at 11:25