# Basic Discrete Structures that needs to be proof

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?

• I am very Desperate answering these two questions – Forlan An West Jan 18 '16 at 0:18
• 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. – Rory Daulton Jan 18 '16 at 0:21
• 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$. – Mike Pierce Jan 18 '16 at 1:40
• the one will cancel the ones inside the parentheses ¬(¬p∨¬q) – Forlan An West Jan 24 '16 at 19:59

## 1 Answer

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!).