7.1.2. Tutorial 1: Part II

Try these first

1. 1.

   Define a functionally complete set of logical operators.

   Hint

   Think of the operations that can represent any logical statement.

2. 2.

   State the result of the operation p ∧ ¬p.

   Hint

   What does AND mean with a statement and its negation?

3. 3.

   Which of the following sets is functionally complete?

   • {AND
   • OR}
   • {AND
   • NOT}
   • {OR
   • NOT}

   Hint

   Think about how each operator can combine truth values.

4. 4.

   A proposition is a tautology if its negation is:

   • satisfiable
   • unsatisfiable

   Hint

   Remember the definitions of tautology and negation.

5. 5.

   Given the expression (A ∧ B) → (C ∨ D), show through transformations it's equivalent to using only AND and NOT operators.

   Hint

   What transformations apply to implications in your logical toolkit?

6. 6.

   Show using resolution that the clauses {¬P, P ∨ Q} and {¬Q} lead to an unsatisfiable conclusion.

   Hint

   Identify pairs and systematically resolve until you observe a cancellation.