# Newbie Needs Help with CNF of Formula

• MHB
• ion88
In summary, the conjunctive normal form for this formula is (¬B ∨ C), which does not match the truth table. To convert it to the correct form, you need a Karnaugh map.
ion88
Hello I'm new here. Can someone please help me with the conjunctive normal form for this formula ?
(((A -> (B -> C)) & (A -> B)) & A) <-> C
I don't know if i did this right or not. If not what should i do ?

#### Attachments

• mhb_inline_0001.png
85.4 KB · Views: 69
ion88 said:
Hello I'm new here. Can someone please help me with the conjunctive normal form for this formula ?
(((A -> (B -> C)) & (A -> B)) & A) <-> C
I don't know if i did this right or not. If not what should i do ?
Hello ion88.

This is the truth table you need to fill in:

$$\displaystyle \begin{array}{|c|c|c|c|c|c|c|c|}\hline A & B & C & B\to C & A\to(B\to C) & A\to B & (A\to(B\to C))\,\&\,(A\to B) & ((A\to(B\to C))\,\&\,(A\to B))\,\&\,A \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 1 \\ \hline 0 & 1 & 0 \\ \hline 0 & 1 & 1 \\ \hline 1 & 0 & 0 \\ \hline 1 & 0 & 1 \\ \hline 1 & 1 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array}$$

When you have done, compare the last column with the $C$ column.

Olinguito said:
Hello ion88.

This is the truth table you need to fill in:

$$\displaystyle \begin{array}{|c|c|c|c|c|c|c|c|}\hline A & B & C & B\to C & A\to(B\to C) & A\to B & (A\to(B\to C))\,\&\,(A\to B) & ((A\to(B\to C))\,\&\,(A\to B))\,\&\,A \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 1 \\ \hline 0 & 1 & 0 \\ \hline 0 & 1 & 1 \\ \hline 1 & 0 & 0 \\ \hline 1 & 0 & 1 \\ \hline 1 & 1 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array}$$

When you have done, compare the last column with the $C$ column.

Sory but I don't even know what programming language is that

ion88 said:
Sory but I don't even know what programming language is that

Hi ion88, welcome to MHB! (Wave)

No worries.
I believe you've already correctly filled in the table, which is what MarkFL uploaded for you.

I'm afraid it also means that the conjunctive normal form that you had found (¬B ∨ C), is not correct.
We can verify by checking (¬B ∨ C) against your truth table, and see that it does not match. (Worried)

The easiest way to convert your truth table to conjunctive form, is through a so called Karnaugh Map.
It looks like this:
\begin{tikzpicture}
%preamble \usepackage{karnaugh-map}
\node {
\begin{karnaugh-map}[4][2][1][AB][C]
\minterms{0,1,2,3,7}
\maxterms{4,5,6}
\implicant{0}{2}
\implicant{3}{7}
\end{karnaugh-map}
};
\end{tikzpicture}
From this Karnaugh Map, we can deduce that the corresponding disjunctive expression is:
(A & B) ∨ ¬C​
That is, the green rectangle corresponds to (A & B), and the red rectangle corresponds to ¬C.
The resulting expression is true if we are in the green rectangle OR in the red rectangle.

We can convert it to conjunctive normal form by using the distributivity of boolean expressions:
(A & B) ∨ ¬C = (A ∨ ¬C) & (B ∨ ¬C)​
(Thinking)

## 1. What is CNF (Conjunctive Normal Form) of a formula?

CNF is a standard form used in propositional logic to represent logical statements. It is a conjunction of clauses, where each clause is a disjunction of literals. In other words, it is a logical statement that consists of AND operations between multiple OR operations.

## 2. Why is it important to convert a formula into CNF?

Converting a formula into CNF makes it easier to analyze and manipulate logical statements. It helps in identifying the logical structure of a formula and simplifying it. CNF is also used in automated theorem proving and other applications in logic.

## 3. How do I convert a formula into CNF?

The process of converting a formula into CNF involves a few steps. First, eliminate any implications and bi-conditional operators by using logical equivalences. Then, use De Morgan's laws to move the negation inwards. Finally, distribute the disjunctions over conjunctions to get the CNF form.

## 4. Can all logical statements be converted into CNF?

Yes, any logical statement can be converted into CNF using the steps mentioned in the previous answer. However, the resulting CNF statement may contain a large number of clauses and may not be very intuitive to understand.

## 5. Are there any online tools to help with converting formulas into CNF?

Yes, there are many online tools available that can help with converting formulas into CNF. Some popular ones include Wolfram Alpha, Truth Table Generator, and Logic Calculator. However, it is important to double-check the results as these tools may not always give the most simplified CNF form.

Replies
3
Views
2K
Replies
17
Views
1K
Replies
2
Views
1K
Replies
5
Views
1K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
1
Views
743
Replies
3
Views
2K
Replies
3
Views
2K
Replies
3
Views
1K