Homework No. 9 - Satisfiability
You are given the following logical expression (+ representing the logical OR, concatenation representing the logical AND):
(x + w)(w + z)
(a) Is this expression (already) in conjunctive normal form (CNF)?
If not, use the procedure described on the lectures to put it in CNF.
(b) Use the procedure described on the lectures -- by introducing new logical variables transform the given expression into a 3-CNF expression that is satisfiable if and only if the given expression is satisfiable.
(c) Construct an undirected graph from the 3-CNF expression that you constructed in (b) (following the procedure described on the lectures) and find one of the minimal node covers of that graph. What is the budget k?
Instructions:
Read the homework text carefully - the homework consists of 3 assignments [(a), (b), and (c)] each of which should be solved.
Do not write the solutions by hand. Use a text editor or some other software (you can try JFlap) and submit in the form of a pdf file - photos or scans of your handwriting will not be accepted !!!
Submit your solution in the form of a PDF file named <N09-LastnameFirstname.pdf> using just English alphabet characters (example: N09-KavsekBranko.pdf)!
Submissions not following these instructions will be rejected and graded with 0 points!!!