7.3.2. Verification of Other Expressions

Try these first

1. 1.

   Define a functionally complete set of logical operators.

   Hint

   Think about the basic logical operators you know.

2. 2.

   What does negation do to a proposition?

   Hint

   Remember the effect of NOT on true statements.

3. 3.

   Which of the following sets of operators is functionally complete?

   • Just AND
   • AND and OR
   • AND
   • OR
   • and NOT

   Hint

   Think of the basic logical operations.

4. 4.

   True or False: If a proposition is a tautology, its negation is satisfiable.

   • True
   • False

   Hint

   Consider the definitions of tautology and satisfiability.

5. 5.

   Show that the expression p ∨ q is equivalent to ¬(¬p ∧ ¬q) using truth tables.

   Hint

   Remember that equivalence means they must have the same output for every input.

6. 6.

   Prove that the expression p → (q ∧ r) is functionally complete by expressing it with AND and NOT.

   Hint

   Focus on breaking down the implication step-by-step.