Distribute ANDs over ORs in this sentence

Question

Can someone explain how we turn the sentence

$$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$

into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because the ANDs are inside the parenthesis that involves other ORs, and it's not so clear how the distribution works.

Answer 1

(1) The distributivity law

As we know, the distributivity law, states that

• $\vDash (\phi \land \psi)\lor \sigma \equiv (\phi \lor \sigma)\land(\psi \lor \sigma)$
• $\vDash (\phi \lor \psi)\land \sigma \equiv (\phi \land \sigma)\lor(\psi \land \sigma)$

where the former consists of its application on ∨ over ∧ and the latter on ∧ over ∨.

---

(2) The question

I assume your original sentence is:

$$[¬C(x,y)]∨[¬A(x)∨(B(x)∧C(x,y))] \tag{1}$$

In this case, by the distributivity law we have:

$$[¬C(x,y)]∨[\underbrace{(¬A(x)∨B(x))∧(¬A(x)∨C(x,y))}_{¬A(x)∨(B(x)∧C(x,y))}] \tag{2}$$

Then we apply the distribuition once again to obtain:

$$[\underbrace{¬C(x,y)∨(¬A(x)∨B(x))]∧[¬C(x,y)∨(¬A(x)∨C(x,y))}_{[¬C(x,y)]∨[(¬A(x)∨B(x))∧(¬A(x)∨C(x,y))}] \tag{3}$$

Which by associativity of $∨$, is in its conjunctive normal form: $$[\underbrace{¬C(x,y)∨¬A(x)∨B(x)}_{¬C(x,y)∨(¬A(x)∨B(x))}]∧[\underbrace{¬C(x,y)∨¬A(x)∨C(x,y))}_{¬C(x,y)∨(¬A(x)∨C(x,y))}] \tag{4}$$

---

(3) Some background

Recall the definition of conjunctive normal form (and finite disjunctions and conjunctions). As I said elsewhere:

Definition 1.3.7 (Finite conjunctions/disjunctions):

\begin{cases} \bigwedge_{i \leq 0} \varphi_i = \varphi_0\\ \bigwedge_{i \leq n+1} \varphi_i = \bigwedge_{i \leq n} \varphi_i \wedge \varphi_{n+1}\\ \end{cases}

\begin{cases} \bigvee_{i \leq 0} \varphi_i = \varphi_0\\ \bigvee_{i \leq n+1} \varphi_i = \bigvee_{i \leq n} \varphi_i \vee \varphi_{n+1}\\ \end{cases}

Definition 1.3.8 (Conjunctive Normal Form): If$$\varphi =\bigwedge_{i \leq n}\bigvee_{j \leq m} \varphi_{ij}$$ where $ϕ_{ij}$ is atomic or the negation of an atom, then $\varphi$ is a conjunctive normal form.

So it's easey to see that the above formula (4) fits the definition with $n=1$ and $m=2$, that is:

$$[¬C(x,y)∨¬A(x)∨B(x)]∧[¬C(x,y)∨¬A(x)∨C(x,y))] = \bigwedge_{i \leq 1}\bigvee_{j \leq 2} \varphi_{ij} $$

Now can you see who in (4) is $\varphi_{00}$, $\varphi_{01}$, $\varphi_{02}$ and $\varphi_{10}$, $\varphi_{11}$, $\varphi_{12}$?

Good work!