# 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