The formula is proved tautology using Truth Table but gives another answer if solved with formula

Question

I am trying to prove by formula that the following formula is a tautology but I am not able to do so, although I have proved it as a tautology with truth table

 (A∨B) ∧ (¬B∨C) → A∨C

¬((A∨B) ∧ (¬B∨C)) ∨  A∨C
 (¬A∧¬B) ∨ (B∧¬C)  ∨  A∨C
¬A∨(B∧¬C) ∧ ¬B∨(B∧¬C) ∨  A∨C              (Distributive Law)
(¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨B) ∧ (¬B∨¬C ∨ A∨C )  
(¬A∨B) ∧ (¬A∨¬C) ∧  T   ∧  (¬B∨A ∨  T) 
∴(¬A∨B) ∧ (¬A∨¬C) 

By using Truth table, I am able to prove it as a tautology. Am I doing something wrong in the second method?

Answer 1

Your mistake is here:

¬A∨(B∧¬C) ∧ ¬B∨(B∧¬C) ∨  A∨C              (Distributive Law)
(¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨B) ∧ (¬B∨¬C ∨ A∨C )  

The result should be:

¬A∨(B∧¬C) ∧ ¬B∨(B∧¬C) ∨  A∨C              (Distributive Law)
((¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨B) ∧ (¬B∨¬C)) ∨ A∨C   

So be careful with those parentheses! In fact, I believe your mistake was partly based on the fact that you didn't use parentheses in the statement before. That is, instead of:

¬A∨(B∧¬C) ∧ ¬B∨(B∧¬C) ∨  A∨C              (Distributive Law)

I would use parentheses to make the structure of the statement really clear:

((¬A∨(B∧¬C)) ∧ (¬B∨(B∧¬C))) ∨  A∨C              (Distributive Law)

Doing that makes it less likely to make mistakes.

By the way, to continue to put this in to CNF (you asked about this in the comments):

((¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨B) ∧ (¬B∨¬C)) ∨ A∨C (Complement)

((¬A∨B) ∧ (¬A∨¬C) ∧ $\top$ ∧ (¬B∨¬C)) ∨ A∨C (Identity)

((¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨¬C)) ∨ A∨C (Distribution)

((¬A∨B) ∨ (A∨C)) ∧ ((¬A∨¬C) ∨ (A∨C)) ∧ ((¬B∨¬C) ∨ (A∨C)) (Association)

(¬A∨B ∨ A∨C) ∧ (¬A∨¬C ∨ A∨C) ∧ (¬B∨¬C ∨ A∨C) (Complement x 3)

($\top$ ∨B ∨C) ∧ ($\top$ ∨¬C ∨C) ∧ ($\top$ ∨¬B∨ A) (Identity x 3)

$\top$ ∧ $\top$ ∧ $\top$

$\top$

(you're not going to get any 'interesting' clauses exactly because this is a tautology!)

Also, here is an easier way to show that your statement is a tautology. It relies on a little known equivalence called Concensus:

$(P \lor Q) \land (\neg Q \lor R) \Leftrightarrow (P \lor Q) \land (\neg Q \lor R) \land (P \land R)$

(It's basically the Resolution rule, but as an equivalence)

Applied to your statement:

$((A \lor B) \land (\neg B \lor C)) \rightarrow (A \lor C) \Leftrightarrow$ (Concensus)

$((A \lor B) \land (\neg B \lor C) \land (A \lor C)) \rightarrow (A \lor C) \Leftrightarrow $ (Implication)

$\neg ((A \lor B) \land (\neg B \lor C) \land (A \lor C)) \lor (A \lor C) \Leftrightarrow$ (DeMorgan)

$\neg (A \lor B) \lor \neg (\neg B \lor C) \lor \neg (A \lor C) \lor (A \lor C) \Leftrightarrow$ (Complement)

$\neg (A \lor B) \lor \neg (\neg B \lor C) \lor \top \Leftrightarrow$ (Identity)

$\top$

Answer 2

It looks like you may have forgotten some parentheses here. As a rule of thumb parentheses (even when slightly overused) can make a huge difference in Logic. For example in your approach:

$$¬[(A∨B) ∧ (¬B∨C)] ∨ (A∨C)$$ $$ [(¬A∧¬B) ∨ (B∧¬C)] ∨ (A∨C)$$ $$[¬A∨(B∧¬C) ∧ ¬B∨(B∧¬C)] ∨ (A∨C)$$

$$[(¬A∨B) ∧ (¬A∨¬C) ∧ (¬B∨B) ∧ (¬B∨¬C)] ∨ (A∨C)$$

And this is where the mistake happened.

However, there is an easier approach from step 2 above. Incidentally you can drop/re-arrange, a lot of parentheses because the clauses share the same logical connective. Namely:

$$¬[(A∨B) ∧ (¬B∨C)] ∨ (A∨C)$$ $$ [(¬A∧¬B) ∨ (B∧¬C)] ∨ (A∨C)$$ $$ (¬A∧¬B) ∨ (B∧¬C) ∨ (A) ∨ (C)$$ $$ (¬A∧¬B) ∨ (A) ∨ (B∧¬C) ∨ (C)$$ $$ [(¬A∧¬B) ∨ (A)] ∨ [(B∧¬C) ∨ (C)]$$ $$ [(¬A∨A)∧(¬B∨A)] ∨ [(B∨C) ∧(¬C ∨ C)]$$ $$ [T∧(¬B∨A)] ∨ [(B∨C) ∧ T]$$ $$ (¬B∨A) ∨ (B∨C)$$ $$ (¬B)∨ (A) ∨ (B) ∨(C) $$ $$ (¬B)∨ (B) ∨ (A) ∨(C) $$ $$ (¬B∨B) ∨ (A) ∨(C) $$ $$ T ∨ (A) ∨(C) $$ $$T$$