MA-351 Homework 4
Due at 4:59pm in my mailbox in SAS 3151, Thursday, November 29, 2018

All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

1. Consider the Boolean expression

   ((a equiv b) implies c) xor ((a nand c) and b)

   where x implies y is the implication operator (not x) or y, x equiv y is the equivalence operator [(x and y) or ((not x) and (not y))], x xor y, is the exclusive or not (x equiv y), and x nand y is the Sheffer stroke not (x and 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 using only the nand operator that is equivalent to a implies b.