-1

How can I write $P \Rightarrow Q$ and $P \Leftrightarrow Q$ using only $\neg$ and $\land$?

Rodrigo de Azevedo
  • 1
Eddie2020
  • 11
  • 2
    $P \to Q$ is $\lnot (P \land \lnot Q)$. – Mauro ALLEGRANZA Apr 28 '17 at 06:34
  • And $P \leftrightarrow Q$ is $(P \to Q) \land (Q \to P)$. – Mauro ALLEGRANZA Apr 28 '17 at 06:35
  • If $P\iff Q$ the we also have that $P\implies Q$. So writing $P\iff Q$ will suffice. – gebruiker Apr 28 '17 at 06:35
  • Thank you, the first question was answered using only $\land$ and $\neg$, but the second part you gave me the answer with an if\then and I am trying to figure out the answer with only $\land$ and $\neg$? – Eddie2020 Apr 28 '17 at 06:41
  • @Eddie2020 What is your definition of $P \iff Q$? One possible definition is $(P \implies Q) \wedge (Q \implies P)$. – Alex Vong Apr 28 '17 at 06:44
  • P if and only if Q. – Eddie2020 Apr 28 '17 at 06:47
  • @Eddie2020 How do you defined $P$ if and only if $Q$ then? Do you define it using truth table? (This is how it was done when I learned it.) – Alex Vong Apr 28 '17 at 06:49
  • Yes, with a truth table. P if and only if Q is only true when they are both true or they are both false. I just dont know how to show this same thing using only $\land$ and $\neg$, like i said. – Eddie2020 Apr 28 '17 at 06:52
  • @Eddie2020 OK. Then I think you can check $P \iff Q$ is the same as $(P \implies Q) \wedge (Q \implies P)$ using truth table and then use it to obtain an answer. – Alex Vong Apr 28 '17 at 06:55

2 Answers2

1

$P \Rightarrow Q$ is the same as $\lnot(P \land \lnot Q)$. This is a 'standard' substitution, but if you only remember that it's equivalent to $\lnot P \lor Q$ you can reach the desired form with De Morgan's Law.

Now, $P \Leftrightarrow Q$ is equivalent to $(P \Rightarrow Q) \land (Q \Rightarrow P)$, so plugging in the first result we get $(\lnot(P \land \lnot Q)) \land \lnot(Q \land \lnot P)$.

Glorfindel
  • 3,955
0

Another path to write $P\iff Q$ is to take the definition in your comment:

$P$ if and only if $Q$ is only true when they are both true or they are both false.

So writing this formally, $$(P\iff Q) = (P\land Q)\lor(\lnot P\land \lnot Q).$$ Now this is almost in the form you want, except for that $\lor$ in the middle. But for that you can use the relation $$\lnot(A\lor B) = \lnot A\land\lnot B$$ from which you get through negation $$A\lor B = \lnot(\lnot A\land\lnot B)$$ Now use $A=P\land Q$ and $B=\lnot P\land \lnot Q$ to arrive at $$(P\iff Q) = \lnot(\lnot(P\land Q)\land\lnot(\lnot P\land\lnot Q))$$

celtschk
  • 43,384