7.1. Discrete Mathematics

Try these first

1. 1.

   What does it mean for a set of logical operators to be functionally complete?

   Hint

   Think about what it means to represent all logical scenarios.

2. 2.

   Convert the implication p → q using logical operators in the functionally complete set.

   Hint

   Remember that implication can always be expressed in terms of ORs.

3. 3.

   Which of the following sets is functionally complete?

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

   Hint

   Think about how each set can express logical statements.

4. 4.

   True or False: The expression p ↔ q can be rewritten as (p → q) AND (q → p).

   • True
   • False

   Hint

   Recall the definition of 'if and only if.'

5. 5.

   Demonstrate through transformations that the set {¬, ∨} can express any logical statement involving conjunction.

   Hint

   Consider how negation flips the truth conditions.

6. 6.

   Create a complex logical proposition and determine its satisfiability using truth assignment techniques.

   Hint

   Systematically try combinations until all parts of the proposition are satisfied.