Transform the propositional logic formulas to CNF

Question

I tried to transform above given propositional formula to CNF form but my last CNF was different with given solution in Student Portal. 

1. Please anyone can confirm my half solution is correct? 

2. How can I simplify after step 2 to reach to (c|!d)&(d|!c) as final solution?

Thank you!

Answer 1

1. What you did looks correct at first glance. But you can just use the propositional logic teaching tools to verify whether you transformation is correct. If you correctly transformed a formula A to an equivalent formula B, then the teaching tools will tell you that (A) <-> (B) is a tautology.
2. Let's continue here:
   (a | c <-> (d & c)) → ((c|b|a)→¬b|(d<->a)) // let's start with the two implications, the implication on the right also leads to an application of De-Morgan's rule
   ¬(a | c <-> (d & c)) | ((¬c&¬b&¬a)|¬b|(d<->a)) // If we satisfy (¬c&¬b&¬a)|¬b by satisfying the conjunction, we have already satisfied ¬b. Thus, the conjunction is redundant, and we can drop it
   ¬(a | c <-> (d & c)) | (¬b|(d<->a)) // Let's do a Shanon-Decomposition by a
   a ? (¬(d & c) | ¬b|d) : (¬(c <-> (d & c)) | (¬b|¬d)) // already simplified 0<->X and 1<->X, now apply some de-morgan
   a ? (¬d | ¬c | ¬b|d) : (¬(c <-> (d & c)) | ¬b|¬d) // a disjunction of something and its negation is a tautology, also: c<->c&d = c→d = ¬c | d
   a ? (true) : (¬(¬c | d) | ¬b | ¬d) // De-Morgan
   a ? (true) : (c & ¬d | ¬b | ¬d) // again, we can drop c&¬d as ¬d makes it redundant
   a ? (true) : (¬b | ¬d) // we write the if-then-else-operator as a conjunction of two implications
   (a → true) & (¬a → (¬b|¬d)) // something→true is certainly a tautology and can be dropped from this conjunction
   a | ¬b | ¬d

Comments

Thanks for your clarification. Please you may elaborate as below:

 1. a ? (¬d | ¬c | ¬b|d) : (¬(c <-> (d & c)) | ¬b|¬d) // a disjunction of something and its negation is a tautology, also: c<->c&d = c→d = ¬c | d (how conclude this?)

 2. a ? (true) : (c & ¬d | ¬b | ¬d) // again, we can drop c&¬d as ¬d makes it redundant (may elaborate more how we can drop c&¬d totally?)

Thanks in advance.

---

1. Why is c<->c&d = c→d? A biimplication is a conjunction of two implications: (c → c&d) & (c&d → c). The right implication is just a tautology. The left implication c→c&d can be simplified to c→d. Do you see why?
2. Why is c & ¬d | ¬d = ¬d? Let's look at all possible assignments. For the not-satisfying assignments, it's trivial. They neither satisfy c&¬d nor ¬d. Removing one of them doesn't make a non-satisfying assignment satisfying. What about the satisfying assignments? The satisfying assignment could satisfy ¬d. Or it could satisfy c&¬d. If it does so, it also satisfies ¬d. Hence, all satisfying assignment satisfy ¬d, and adding or removing (c&¬d) doesn't change the satisfying assignments.