Isaac Turner About Projects CV Contact Resources Freode Boolean Logic Intro Primary Operators Primary Operator Qs Secondary Operators Expression Forms Expression Form Questions Algebraic Laws Algabraic Laws Questions Boolean Logic Applet Web Security

Boolean Logic - Expression Forms

Logical values (true, false) and variables (a, b etc.) are together known as literals. Literals together with operations come under the term expressions. Examples of expressions are:

true
a'
(a . b) + (c => d)'

Negation Normal Form (NF)

An expression is in Negation Normal Form it if has no negated brackets and uses only AND, OR, NOT operators.

Expresssions in NNF:

(a + b) . (c + d)
(a + b) . c
true . (a + false)
a . b
a + b
a

Expresssions not in NNF:

(a . b)' + (c . d)
(a + b) => c
(a <=> b) + c
(a . b) != c
d + ((a + b) . c)'

Negation Normal Form (NNF) on Wikipedia.

Conjunctinve Normal Form (CNF)

Expressions in Conjunctive Normal Form are also in Normal Form - therefore they must have no negated brackets and use only AND, OR, NOT operators. In addition to this they must be a 'conjunction of literals or disjuctions of literals'. What does this mean? A conjunction is a fancy word for an AND operation. A disjunction is a fancy word for an OR operation. So, an expression is in CNF if it is an AND operation of literals (values and variables) or of OR operations of literals. It should be noted that an expression is in CNF if is only an OR of literals, or literals on their own. Lets look at some examples:

Expresssions in CNF:

(a + b) . (c + d)
(a + b) . c
true . (a + false)
a . b
a + b
a

Expresssions not in CNF:

(a . b) + (c . d)
(a + b)' . c
(true . a) + false
(a . b)'

Every expression has one or more equivalent expressions in Conjunctinve Normal Form. This means for any expression we can apply some rules to put it into Conjunctinve Normal Form.

Conjunctinve Normal Form on Wikipedia

Disjunctive Normal Form (DNF)

Expressions in Disjunctive Normal Form are also in Normal Form - therefore they also have no negated brackets and use only AND, OR, NOT operators. As well as this the definition of DNF is that expressions must be a 'disjunction of literals or conjunctions of literals'. Remembering from CNF (above) that a conjunction is an AND operation and a disjunction is an OR operation. An expression is in DNF if it is an OR operation on literals and AND operations of literals. It should be noted that like CNF, an expression is in DNF if is only an AND of literals, or literals on their own. Therefore one expression can be in both CNF and DNF. Lets look at some examples:

Expresssions in DNF:

(a . b) + (c . d)
(a . b) + c
true + (a . false)
a . b
a + b
a

Expresssions not in DNF:

(a + b) . (c + d)
(a + b) . c
true . (a + false)

Every expression has one or more equivalent expressions in Disjunctive Normal Form. This means for any expression we can apply some rules to put it into Disjunctive Normal Form.

Disjunctive Normal Form on Wikipedia

<< Secondary Operators | Introduction | Expression Form Questions >>