3
$\begingroup$

Given there are 2 logical variables $p$, $q$ . Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent without using the truth table.

And here is my steps: $(p \land q) \lor (\neg p \land \neg q)$

I get this). What should I do in order to get rid of it? ps: I am studing from Discrete mathematics and its application 7th edition rosen thanks

$\endgroup$
  • $\begingroup$ I mentioned in question without using truth table $\endgroup$ – JAWA Jan 13 '14 at 20:53
  • 3
    $\begingroup$ Like in your previous question you need to show the rules you're allowed to use. Otherwise it will be completely up to luck whether you get an answer that happens to use only the particular rules you have. $\endgroup$ – Henning Makholm Jan 13 '14 at 21:16
  • $\begingroup$ @HenningMakholm I upvoted your comment, but thinking more on this I'm not sure if it's correct in this context. In this context I'd think you can always use the principle of bivalence. The principle of bivalence doesn't necessitate using truth tables, and you can show this to hold using just the principle of bivalence (though, of course, it's not a formal proof). $\endgroup$ – Doug Spoonwood Jan 20 '14 at 23:05
2
$\begingroup$

In the question before we have seen that $$\begin{array}{cl} & \left(p\land q \right)\lor \left(\neg p \land \neg q\right) \\ \Longleftrightarrow & \left( p\Longleftrightarrow q\right) \end{array}$$

Thus $$\begin{array}{cl} & \left(p\Longleftrightarrow \neg q\right)\\ \Longleftrightarrow & \left(p\land \neg q \right)\lor \left(\neg p \land q\right) \\ \Longleftrightarrow & \left(\left(p\land \neg q \right)\lor \neg p\right) \land \left(\left(p\land \neg q \right)\lor q\right) \\ \Longleftrightarrow & \left(\neg p\lor \neg q \right) \land \left(p \lor q\right) \\ \Longleftrightarrow & \neg\left(p\land q \right) \land \left(p \lor q\right) \\ \Longleftrightarrow & \neg\left(p\land q \right) \land \neg\left(\neg p \land \neg q\right) \\ \Longleftrightarrow & \neg\left(\left(p\land q \right)\lor \left(\neg p \land \neg q\right)\right) \\ \Longleftrightarrow & \neg\left( p\Longleftrightarrow q\right) \end{array}$$

$\endgroup$
1
$\begingroup$

Suppose p true. Then (p⟺q) has the same truth value as q. Thus, ¬(p⟺q) has the same truth value as ¬q. Also, (p⟺¬q) has the same truth value as ¬q.

Suppose p false. Then (p⟺q) has the same truth value as ¬q. Consequently, ¬(p⟺q) has the same truth value as ¬¬q. Also, (p⟺¬q) has the same truth value as ¬¬q.

$\endgroup$
0
$\begingroup$

So $(p \iff q)$ is equivalent to $(p \land q) \lor (\lnot p \land \lnot q)$, and $(p \iff \lnot q)$ (where we want to get after symbolic manipulations) is equivalent to $(p \land \lnot q) \lor (\lnot p \land q)$ (so if we get here via valid manipulations, we're done). Then you can take the negation of this, and use De Morgan's laws:

$$ \lnot (A \lor B) \equiv \lnot A \land \lnot B $$ so $$ \lnot\left((p \land q) \lor (\lnot p \land \lnot q)\right) \equiv \lnot(p \land q)\land \lnot(\lnot p \land \lnot q) $$

and $$ \lnot (A \land B) \equiv \lnot A \lor \lnot B $$ so $$ \lnot(p \land q)\land \lnot(\lnot p \land \lnot q) \equiv (\lnot p \lor \lnot q)\land (p \lor q) $$

See if you can finish the proof from here: continue to De Morgan's laws (sometimes you might need to use them "in reverse": $A \lor B = \lnot \lnot (A \lor B) = \lnot (\lnot A \land \lnot B)$ for example)

$\endgroup$
0
$\begingroup$

I would first point out that each statement is equivalent to $(p \land \lnot q) \lor (\lnot p \land q)$, rather than $(p \land q) \lor (\lnot p \land \lnot q)$.

Left to right, we have the hypothesis is equivalent to $(p \land \lnot q) \lor (\lnot p \land q)$. Then in either case, both $p \rightarrow \lnot q$ and $\lnot q \rightarrow p$ hold, so that $p \leftrightarrow \lnot q$ holds.

Right to left, assume that $(\lnot p \land q)$ does not hold, you want to show $(p \land \lnot q)$. If $p$, use the hypothesis to show that $\lnot q$. If $\lnot q$, use the hypothesis to show that $p$. In both cases, $(p \land \lnot q)$. I hope that helps.

$\endgroup$
0
$\begingroup$

Simply we can find that $p \leftrightarrow q$ is equal to $\neg(p \underline{\vee} p)$. and IF p BE TRUE q MUST BE FALSE & CONVERSELY. it means that we have $(p \rightarrow \neg q) \wedge (\neg q \rightarrow p)$ (we have a symmetry between p and q.)

$\endgroup$
0
$\begingroup$

One way to see this is with the method of analytic tableaux. You start with the negation of $$(\neg (p\leftrightarrow q))\leftrightarrow (p\leftrightarrow \neg q)\tag{1}$$ then apply a series of contradiction-hunting rules to get

enter image description here,

which is closed (i.e., it ends in contradictions), meaning that $(1)$ is a tautology; that is, $\neg (p\leftrightarrow q)$ and $p\leftrightarrow \neg q$ are logically equivalent.

These notes (in pdf form) explain the method in detail.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.