0
$\begingroup$

All propositional statements can be written using only the logical connectives $\neg$ and $\vee$ Justify this fact by showing the following:

(a) Give a propositional statement that is equivalent to $p \wedge q$ using only $\neg$ and $\vee$ and prove that they are equivalent.

(b) Give a propositional statement that is equivalent to $p \leftrightarrow q$ using only $\neg$ and $\vee$ and prove that they are equivalent.

I used the truth table but I could not make $p \wedge q =\neg p \vee \neg q$; however , the truth tables shows

$\begin{matrix} p & q & p \wedge q & \neg p \vee \neg q\\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 \end{matrix}$

Completely opposite. What's wrong in my work? How can defeat this problem?

$\endgroup$
4
  • $\begingroup$ I am very Desperate answering these two questions $\endgroup$ – Forlan An West Jan 18 '16 at 0:18
  • 1
    $\begingroup$ Welcome to MathSE! You are more likely to get a good answer to your question if you follow a few guidelines. In particular, what have you tried so far, and just where are you stuck? This is not a homework-answering site: we want to see that you have put significant work into the problem. Telling us only that you are "desperate" does not help. $\endgroup$ – Rory Daulton Jan 18 '16 at 0:21
  • $\begingroup$ Looking at your truth table, you are so very close to having the correct propositional statement. Notice that $p \wedge q$ and $\neg p \vee \neg q$ have exactly the opposite values in your truth table. This suggests that you just need to wrap one more $\neg$ around $\neg p \vee \neg q$. $\endgroup$ – Mike Pierce Jan 18 '16 at 1:40
  • $\begingroup$ the one will cancel the ones inside the parentheses ¬(¬p∨¬q) $\endgroup$ – Forlan An West Jan 24 '16 at 19:59
0
$\begingroup$

Exactly as Mike Prince said. The wrong thing is in your equality.

P and Q = NOT (NOT P or NOT Q).

It is one of the standard De Morgan's laws:- https://en.m.wikipedia.org/wiki/De_Morgan%27s_laws

For part B of your question, first note that P --> Q is same same as (NOT P OR Q). So, the double implication would make it ((NOT P) OR Q) AND ((NOT Q) OR P). You can also express this more concisely as ( P AND Q) OR (NOT P AND NOT Q). In simple English, either both P and Q are true or both of them are false (they imply each other!).

$\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.