MA-351 Homework 4, 2023
Due Thurs Nov. 30, 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.
-
Consider the Boolean expression
not
(
(
(a equiv b) implies c
)
and
(
(a nand b) xor c
)
)
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 operator not (x equiv y),
and x nand y is the Sheffer stroke not (x and y).
-
Find a CNF (with k clauses and no more than 3 literals per clause)
that is equivalent to this expression.
-
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.
-
Please write a Boolean expression
in the variables
a
and
b
using only the nand operator
that is equivalent to
the inhibition of b by a, which is
defined as a and (not b) and written as a/b.
Note that a and (not b) is equivalent to not (a implies b).