Boolean Algebra

Boolean Algebra
Boolean algebra is the sub area of algebra in which the values of the variables are the truth values that are either true or false, usually denoted 1 and 0 respectively. Instead of elementary algebra where the values of the variables are numbers, and the main operations are addition and multiplication, the main operations of Boolean algebra are the conjunction, disjunction and negation denoted by a dot (.), plus (+) and compliment(‘) respectively.

A proposition in Boolean algebra is an elementary atomic statement that either tends to true or false and no other value. So statements like “Which month is this?”, “When did you wake up?” are NOT propositions.
Whereas statements like –
It is raining.
Today is Monday etc… are propositions

Propositions can be of two types
 Simple Propositions
 Compound Propositions

A simple proposition is one that comprises of only a single proposition like “It is raining”, generally denoted by lower case letters like p, q, r…
A compound proposition on the other hand is a combination of two or more simple propositions (called components) joined together by connectives.

These connectives are also referred as “Sentential Connectives” and are of 4+1 types as the last one does not actually satisfy the definition of connective.

1. Disjunctive – is a truth-functional operator also known as inclusive. The logical connective that represents this operator is also known as “or”, and typically written as or . The “or” operator produces a result of true whenever one or more of its operands are true. For example, in this context, “A or B” is true if A is true, or if B is true, or if both A and B are true.

2. Conjunctive – is a truth functional (logical) operator and, also known as logical “and” results in true if both of its operands are true, otherwise the value of false. It is represented using ‘Λ’ or ‘.’

3. Conditional – also known as if then or implication represented by −> which states that if one argument is true then the other argument is true. So p  q means if p is rue then q is true. Conditional elimination can be represented as p −>q = p’ + q

4. Bi Conditional – also known as if and only if (IFF) or Equivalence represented by symbol <– −> which states either both arguments are true or both are false. Meaning p, q are either both true and both false.

5. Negation – Negation is not a connective, as it affects a single statement only. Represented by the symbol – , ‘ ~ etc…

Glossary of Terms

1. Truth Value is defined as truth or fallacy / falsity of a proposition.
2. Proposition in Boolean algebra is an elementary atomic statement that either tends to true or false and no other value.
3. WFF stands for Well Formed Formulae and is just another name for Proposition.
4. Truth table is a complete list of all possible truth values of a proposition.
5. Contingencies are propositions that have some combination of 1’s and 0’s in their truth column.
6. Tautology is proposition that have nothing but 1’s their truth column.
7. Contradiction / Fallacy is proposition that have nothing but 0’s their truth column.
8. Converse of a conditional proposition is determined by interchanging the Antecedent and Consequent, resulting in a new proposition. For e.g. p −>q results in q −>p
9. Inverse of a conditional proposition is determined by negating the Antecedent and Consequent, resulting in a new proposition. For e.g. p −>q results in p’ −>q’
10. Contrapositive of a conditional proposition is determined by interchanging the Antecedent and Consequent as well as negating them, resulting in a new proposition. For e.g. p −>q results in q’ −>p’

Syllogism

The logical process of drawing conclusion from given propositions is called Syllogism. The propositions used to draw the conclusions are known as Premises. Premises are denoted by a capital P, this can be achieved by two methods –
 Truth Table Method
 Algebraic Method

To draw a conclusion (C) from the given premises (P) we find the Conjunction of all the Premises as a Conditional of the Conclusion to be 1, So if the premises are P1, P2, P3 etc… and the conclusion to be drawn is C then we find –
P1.P2.P3….Pn  C and finally prove it to be 1

A few Theorems are as follows –

Sl	Theorem	Expression
1	Modus Ponens	From : p . pàq infer q
2	Chain Rule	From : (pàq) . (qàr) infer (pàr)
3	Modus Tollens	From : (pàq) . (~q) infer (~p)
4	Constructive Dilemma	From : (pàq) . (ràs) . (p+r) infer (q+s)
5	Destructive Dilemma	From : (pàq) . (ràs) . (~q+~s) infer (~p+~r)

Laws of Boolean Algebra

Binary Decision
Any decision which results into a YES (TRUE) or NO (FALSE) is called a binary decision.

BASIC POSTULATES OF BOOLEAN ALGEBRA
• If X = 0 then X = 1 and if X = 1 then X = 0
• Logical addition (OR relations)
 0+0=0
 0+1=1
 1+0=1
 1+1=1
• Logical multiplication (AND relations)
 0.0=0
 0.1=0
 1.0=0
 1.1=1
• Complement rules (NOT relations)
 0’ = 1
 1’ = 0

BASIC THEOREMS OF BOOLEAN ALGEBRA

Properties of 0 and 1
 0+X=X
 1+X=1
 0.X=0
 1.X=X

Idempotence law
 X+X=X
 X.X=X

Involution law
 (X’)’ = X

Complementary law
 X + X’ = 1
 X . X’ = 0

Commutative law
 X+Y=Y+X
 X.Y=Y.X

Associative law
 X+(Y+Z)=(X+Y)+Z
 X.(Y.Z)=(X.Y).Z

Distributive law
 X(Y + Z) = XY + XZ
 X + YZ = (X + Y)(X + Z)

Demorgan’s Law
 (X+Y)’ = X’.Y’
 (X.Y)’ = X’ + Y’

Steps to perform De Morgan’s law-
Complement the whole expression on which DeMorgan’s law needs to be applied, Change all ANDs to ORs and all ORs to ANDs, Then, Complement all the terms in the expression.

Principle of Duality
 Change each OR (+) to AND (.)
 Change each AND (.) to OR (+)
 Replace each 0 by 1 and 1 by 0

Canonical Forms of Boolean Expression (Minterm & Maxterm)

Boolean expressions which consist of a single variable for e.g. X’, Y etc… are called literals. They can be in either complimented of un-complimented forms.
So, A Boolean expression like, X+Y’Z consists of three literals.

We call the above expression as non-canonical of impure, in its purest form each and every term of the boolean expression will contain all the literal of the Boolean system.

A Boolean function can be expressed as a Sum of Products of all the variables within the Boolean System. Each of those product terms are called Minterms.

So a Minterm can be defined as product of all the literals of Boolean expression in complimented or un-complimented form within the logic system. And when a Boolean expression is represented purely as sum of minterms, it is said to be in Canonical Sum of Product form (Canonical SOP)

How to convert a non-canonical expression into Canonical SOP Form –
1. Identify the missing variable in each term of the expression.
2. Replace the missing variables with 1.
3. Replace 1 with sum of complimented and un-complemented form of the missing literal.
4. Expand using Distributive
5. Remove all duplicate terms.
6. Resulting expression will be a Canonical SOP with only Minterms

For e.g. express X+Y as minterms, So F(X,Y) = X+Y
= X.1 + 1.Y (Replacing the missing term with 1s
= X.(Y+Y’) + (X.X’)Y (Replacing 1 with sum of complimented and un-complimented term)
= XY + XY’ + XY + X’Y (Applying distributive)
= XY + XY’ + X’Y (Removing repeated term XY)

The Canonical SOP form can be represented in Shorthand Minterm Form by replacing the complimented terms with 0 and un-complimented form with 1 and finally expressing each term as decimal equivalent as subscript of m.
F(X,Y) = XY + XY’ + X’Y
F(X,Y) = 1.1 + 1.0 + 0.1
F(X,Y) = m3 + m2 + m1
The same Boolean function in SOP Cartesian Form is denoted by a ∑ of the terms
F(X,Y) = ∑ (1, 2, 3)

A Boolean function can also be expressed as a Product of Sums of all the variables within the Boolean System. Each of those product terms is called Maxterms.

So a Maxterm can be defined as sum of all the literals of Boolean expression in complimented or un-complimented form within the logic system. And when a Boolean expression is represented purely as sum of maxterms, it is said to be in Canonical Product of Sum form (Canonical POS)

How to convert a non-canonical expression into Canonical POS Form –
1. Identify the missing variable in each term of the expression.
2. Replace the missing variables with 0.
3. Replace 0 with product of complimented and un-complemented form of the missing literal.
4. Expand using Distributive Law.
5. Remove all duplicate terms.
6. Resulting expression will be a Canonical POS with only Maxterms.

For e.g. express XY as maxterms, So F(X,Y,Z) = X+Y’Z
= (X+0+0).(0+Y’+Z) (Replacing the missing term with 0’s
= (X+YY’+ZZ’).(XX’+Y’+Z) (Rep. 0 with product of complimented and un-complimentd)
= (X+Y+Z).(X+Y’+Z).(X+Y+Z’).(X+Y’+Z’).(X+Y’+Z).(X’+Y’+Z) (Applying distributive)
= (X+Y+Z).(X+Y’+Z).(X+Y+Z’).(X+Y’+Z’).(X’+Y’+Z) (Removing repeated term XY)

The Canonical POS form can be represented in Shorthand Maxterm Form by replacing the complimented terms with 1s and un-complimented terms with 0s (note this is just the opposite of what we do in case of SOP/Minterms) and finally expressing each term as decimal equivalent as subscript of M.

F(X,Y,Z) = (X+Y+Z).(X+Y’+Z).(X+Y+Z’).(X+Y’+Z’).(X’+Y’+Z)
F(X,Y,Z) = (0+0+0).(0+1+0).(0+0+1).(0+1+1).(1+1+0)
F(X,Y,Z) = M0.M2.M1.M3.M6

The same Boolean function in POS Cartesian Form is denoted by a ∏ of the terms
F(X,Y,Z) = ∏ (0, 1, 2, 3, 6)