7.2.3. Replacing Conjunction with Negation and Disjunction

Try these first

1. 1.

   What is the equivalent of 'p → q'?

   Hint

   Think about how you can express implication using disjunction.

2. 2.

   How do you express 'p ∧ q' using only negation and disjunction?

   Hint

   Consider De Morgan's laws.

3. 3.

   What is the equivalent of p → q?

   • ¬q ∨ p
   • ¬p ∨ q
   • p ∧ q

   Hint

   Remember how you transformed implications.

4. 4.

   True or False: {AND, OR, NOT} together form a functionally complete set.

   • True
   • False

   Hint

   Think about examples you’ve seen.

5. 5.

   Show how to express (p ∧ q) using only disjunction and negation.

   Hint

   Use De Morgan's laws to navigate through.

6. 6.

   Determine if {NOT, OR} is functionally complete and provide proof.

   Hint

   Consider the relationships between the operations you've learned.