What is the minimal disjunctive normal form of this propositional logic formula?

286 Views Asked by At

I have the following formula: $(\neg A\land B\land C)\vee (\neg A\land B\land \neg C)\vee (\neg A\land \neg B)\vee (A\land C)\vee (A\land\neg C)$

After I did a Karnaugh Map for this formula I found out it is a tautology (in other words - all squares in the map are filled with ones). What is the minimal disjunctive normal form of this formula then?

1

There are 1 best solutions below

0
On BEST ANSWER

I'll show you how to prove the statement is tautology without Karnaugh's map:

$(1)$ distribution: $$(\neg A\land B\land C)\lor (\neg A\land B\land \neg C)\equiv(\neg A\land B)\land(C\lor\neg C)\equiv(\neg A\land B)$$ $(2)$distribution again: $$(\neg A\land B)\lor(\neg A\land\neg B)\equiv\neg A\land(B\lor\neg B)\equiv\neg A$$ $(3)$distribution once again: $$(A\land C)\lor(A\land\neg C)\equiv A\land(C\lor\neg C)\equiv A$$ $$$$ $$\underbrace{\underbrace{(\neg A\land B\land C)\lor(\neg A\land B\land \neg C)}_{\neg A\land B}\lor(\neg A\land \neg B)}_{\neg A}\lor\underbrace{(A\land C)\lor(A\land\neg C)}_{A}\equiv\neg A\lor A\equiv 1$$