MA-351 Homework 4, 2024
Due Tue Nov. 26, at 23:59pm.

All solutions must be submitted on the Moodle web site for the class at wolfware.ncsu.edu. You may upload a photo of your handwritten solution or a file of your typed solution.
Note my office hours on my schedule.

1. Consider the Boolean expression

   ¬ ( ( c ⇒ (a ⇔ b) ) ⊕ ( (a nor b) nand c ) )

   where ¬ is negation "not"; x ⇒ y is the implication operator: (¬ x) ∨ y; x ⇔ y is the equivalence operator: [(x ∧ y) ∨ ((¬ x) ∧ (¬ y))]; x ⊕ y is the exclusive or operator: ¬ (x ⇔ y); (x nand y) is the Sheffer stroke: ¬ (x ∧ y); and (x nor y) is the negated inclusive or: ¬ (x ∨ y).
   1. Find a CNF (with k clauses and no more than 3 literals per clause) that is equivalent to this expression.
   2. Draw the graph corresponding to the CNF that has a clique of size k if and only if the CNF is satisfiable. For a satisfying assignment, identify the corresponding clique.
2. Please write a Boolean expression in the variables a, b using only the nand operator that is equivalent to a ⊕ b. Your expression should not have more then 8 nand's.