CNF Calculator | Conjunctive Normal Form Converter | Zhegalkin Polynomial

How to use the calculator

1. Enter in the field logic function (for example, x1 ∨ x2) or its vector (for example, 10110101)
2. Specify the actions to be performed using the switches
3. Specify whether the output of the solution is required by the "With solution (By the steps)" switch
4. Click the "Let's go" button

Symbols used

As variables, the letters of the Latin alphabet are used, as well as numbers written after the letter (variable index). Thus, the variable names will be: a, x, a1, B, X, X1, Y1, A123 and so on.

To record logical operations you can use both normal keyboard characters (*, +, !, ^, ->, =), and symbols established in literature (∧, ∨, ¬, ⊕, →, ≡). If your keyboard does not have the desired operation symbol, then use the calculator keyboard (if it is not visible, press "Show Keyboard"), where both all logical operations and a set of the most commonly used variables are available.

To change the order of operations round brackets are used ().

The designations of logical operations

• AND: & • ∧ *
• OR: ∨ +
• NOT: ¬ !
• Exclusive OR (XOR): ⊕ ^
• Implication: -> → =>
• Equivalence: = ~ ≡ <=>
• Schaeffer stroke: ↑ |
• Pierce Arrow: ↓

What the calculator can do

• Build a truth table of the function
• Build a truth table by a binary vector
• Construct a perfect conjunctive normal form (CNF)
• Construct a perfect disjunctive normal form (DNF)
• Construct the Zhegalkin polynomial (by Pascal, triangle, and undefined coefficients methods)
• Determine whether a function belongs to each of the five Post's classes
• Build K-Map (Karnaugh Map)
• Minimize CNF and DNF
• Looking for fictitious variables

What is a Boolean function

Boolean function f(x1, x2, ... xn) — is any function of n variables x₁, x₂, ... x_n, in which its arguments take one of two values: either 0 or 1, and the function itself takes values 0 or 1. That is, it is a rule by which an arbitrary set of zeros and ones is assigned the value 0 or 1. Read more about Boolean functions on Wikipedia.

What is a truth table?

Truth table — is a table describing a logical function, namely reflecting all values of the function for all possible values of its arguments. The table consists of n+1 columns and 2n rows, where n is the number of variables used. The first n columns contain all possible values of arguments (variables) of the function, and the n+1th column contains values of the function that it takes on a given set of arguments.

Quite often there is a variant of the table in which the number of columns is equal to n + the number of logical operations. In such a table also the first n columns are filled with sets of arguments, and the remaining columns are filled with values of subfunctions included into the record of the function, which allows to simplify the calculation of the final value of the function at the expense of already intermediate calculations.

Logical operations

A logical operation is an operation on statements that allows you to make new statements by combining simpler ones. Conjunction (∧ or &), disjunction (∨ or |) are commonly referred to as basic operations, implication (→), negation (¬), equivalence (=), exclusive OR (⊕).

Truth table of logical operations

How to set a logic function

There are many ways to specify a Boolean function:

• truth table
• characteristic sets
• value vector
• Gray's matrix
• formulas

Let's look at some of them:

To define a function by a vector of values, you must write a vector of 2ⁿ zeros and ones, where n is the number of arguments on which the function depends. For example, a function of two arguments can be defined as follows: 0001 (AND operation), 0111 (OR operation).

To define a function as a formula, you need to write a mathematical expression consisting of function arguments and logical operations. For example, we can specify the following function: a∧b ∨ b∧c ∨ a∧c

Ways to represent a Boolean function

You can use formulas to get a huge variety of functions, and with different formulas you can get the same function. Sometimes it can be very useful to know how to construct a particular function, using only a small set of given operations, or using as few arbitrary operations as possible. Let's look at the basic ways of defining Boolean functions:

• Perfect disjunctive normal form (DNF)
• Perfect conjunctive normal form (CNF)
• Algebraic Normal Form (ANF, Zhegalkin polynomial)

Disjunctive normal form (DNF)

A simple conjunction is a conjunction of some finite set of variables, or their negations, with each variable occurring no more than once. A disjunctive normal form (DNF) is a disjunction of simple conjunctions. A perfect disjunctive normal form (DNF) is a DNF with respect to some given finite set of variables, each conjunction of which includes all variables of this set. For example, DNF is the function ¬abc ∨ ¬a¬bc ∨ ac, but it is not a disjunctive normal form because the last conjunction lacks the variable b.

Conjunctive normal form (CNF)

A simple disjunction is a disjunction of one or more variables, or their negations, with each variable included no more than once. Conjunctive normal form (CNF) is a conjunction of simple disjunctions. A perfect conjunctive normal form (CNF) is a CNF with respect to some given finite set of variables, each disjunction of which includes all variables of this set. For example, the CNF is the function (a ∨ b) ∧ (a ∨ b ∨ c), but it is not an SNF because the first disjunction lacks the variable c.

Algebraic Normal Form (ANF, Zhegalkin polynomial)

Algebraic normal form, Zhegalkin polynomial is a form of representation of logical function in the form of polynomial with coefficients of 0 and 1, where conjunction operation is used as product and exclusive OR is used as addition. Examples of Zhegalkin polynomials: 1, a, a⊕b, ab⊕a⊕b⊕1

Algorithm for constructing an DNF for a Boolean function

1. Construct a truth table for the function
2. Find all sets of arguments on which the function takes value 1
3. Write simple conjunctions for each of the sets according to the following rule: if in a set the variable takes value 0, it enters the conjunction with negation, otherwise without negation
4. Combine all simple conjunctions with a disjunction

Algorithm of CNF construction for a Boolean function

1. Build a truth table for the function
2. Find all sets of arguments on which the function takes the value 0
3. Write simple disjunctions for each of the sets according to the following rule: if in a set the variable takes value 1, it enters the disjunction with negation, otherwise without negation
4. Combine all simple disjunctions with a conjunction

Algorithm for constructing the Zhegalkin polynomial of a Boolean function

There are several methods of constructing the Zhegalkin polynomial, in this article we will consider the most convenient and simple of all.

1. Construct a truth table for the function
2. Add a new column to the truth table and write in 1, 3, 5... cells of the values from the same rows of the previous column of the truth table, and to the values in lines 2, 4, 6... add modulo two values from correspondingly 1, 3, 5... lines.
3. Add a new column to the truth table and overwrite the values of 1, 2, 5, 6, 9, 10... lines, and to 3, 4, 7, 8, 11, 12... lines add the overwritten values similarly to the previous point.
4. Repeat each time doubling the number of transferred and added elements until the length equals the number of rows in the table.
5. Write out Boolean sets where the value of the last column is one
6. Write the names of variables corresponding to the set instead of the ones in the sets (for the zero set write one) and join them using the exclusive OR operation.

Examples of constructing different representations of logical functions

Let us construct perfect disjunctive and disjunctive normal forms and the Zhegalkin polynomial for the function of three variables F = ¬ab∨¬bc∨ca

1. Let's build a truth table for the function

---

Construction of a perfect disjunctive normal form:

Let's find the sets on which the function takes a true value: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

Let us match the found sets with elementary conjunctions for all variables, and if a variable in the set takes value 0, it will be written with negation:

K₁: { 0, 0, 1 } — ¬a¬bc
K₂: { 0, 1, 0 } — ¬ab¬c
K₃: { 0, 1, 1 } — ¬abc
K₄: { 1, 0, 1 } — a¬bc
K₅: { 1, 1, 1 } — abc

Combine conjunctions using disjunction and get a perfect disjunctive normal form:

---

Construction of a perfect conjunctive normal form:

Find the sets on which the function takes a false value: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

Let us match the found sets with elementary disjunctions for all variables, and if a variable in the set takes value 1, it will be written with negation:

D₁: { 0, 0, 0 } — a∨b∨c
D₂: { 1, 0, 0 } — ¬a∨b∨c
D₃: { 1, 1, 0 } — ¬a∨¬b∨c

Combine disjunctions with conjunctions and obtain a perfect conjunctive normal form:

---

Construction of the Zhegalkin polynomial:

Add a new column to the truth table and write in lines 1, 3, 5, and 7 the values from the same lines in the previous column of the truth table, and add the values in lines 2, 4, 6 and 8 modulo 2 with the values from lines 1, 3, 5, and 7 correspondingly:

Add a new column to the truth table and write in lines 1 and 2, 5 and 6 the values from the same lines of the previous column in the truth table, and add the values in lines 3 and 4, 7 and 8 modulo 2 with the values from lines 1 and 2, 5 and 6 correspondingly:

Add a new column to the truth table and write in rows 1, 2, 3, and 4 the values from the same rows of the previous column of the truth table, and add the values in lines 5, 6, 7 and 8 modulo 2 with the values from correspondingly in lines 1, 2, 3, and 4:

The final result is the following table:

Write out the sets, on which the resulting vector takes a unit value, and instead of the units in the sets write the names of variables corresponding to the set (for the zero set write one):

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Combining these conjunctions using the exclusive or operation, we obtain the Zhegalkin polynomial: c⊕b⊕bc⊕ab⊕abc