CHAPTER 3 There are 2 main types:

BOOLEAN ALGEBRA 1-Binary operators (2 inputs)-Most common

Subtopics 2-Unary operators (1 input)-Not common
3.0 Introduction
Simple logical operators are:
3.1 Simple logical Operators
(a) AND (b) OR (c) NOT
3.2 More logical Operators
These are related to Set Theory-Chapter 2.
3.3 Logical Expressions
Let inputs (operands) be A and B.
3.4 Logical Equivalences & Laws
Similar to sets A and B in Set theory.
3.0 Introduction
1-AND operator (ANDing)
Boolean Algebra is a branch of Mathematics using
This is a binary operator, also known as conjunction.
symbolic logic. Also known as Logical Algebra
It is equivalent to:
(Algebra of Logic) or Binary Algebra.
It was developed by George Boole (1815-1864). 1. Intersection  for sets i.e A  B
2. Multiplication X for Arithmetic
Logic was introduced by Aristotle (384-322 BC).
Boolean Algebra deals with only 2 values called 3. Electrical switches in Series
truth values. These values are given to Boolean Symbols & Notation:
inputs also known as Boolean variables. AVB (used here). Also AB, AXB, A  B
Boolean operators are applied to Boolean inputs AXB is equivalent to multiplying binary bits.
to give Boolean outputs in truth tables. Read AVB as”A and B”
Alternatively, we use Logical instead of Boolean. 2-OR operator (ORing)
For example; true / false, yes /no, on /off, 1 /0. This is a binary operator, also known as disjunction.
We shall be using T for true and F for false. It is equivalent to:
Digital electronics uses 1 for on and 0 for off. 1. Union  of sets i.e A  B
Logic 2. Addition  for Arithmetic
This refers to thinking and reasoning. 3. Electrical switches in Parallel
For example; Symbols & Notation: AVB (used here). Also AB
1-Hypotheses AB equivalent to adding binary bits.
Diploma programs in UICT take two years. Read AVB as”A or B”
DCS is a diploma program in UICT. 3-NOT operator
2-Conclusion This is a unary operator, also known as negation
DCS program takes two years. or logical compliment.
Other branches of Algebra include: It is equivalent to:
1-Elementary Algebra 1. Complement AC, A or A ̅ in sets
Inputs (values of variables) are numerical. 2. Inverter in logic circuits (digital electronics)
Arithmetic operators used are + and - . Symbols & Notation:
2-Abstract Algebra A elbow (used here). Also A tilde, A exclamation

Applications of Boolean Algebra Similar to Sets:

1-Modern Programming e.g c++, Java AC compliment, A prime, A ̅ overbar.
Boolean algebra operators are used to construct 
Read A as “Not A”
programming statements. Truth tables
2-Digital Electronics i.e digital gates They are mathematical tables used in logic.
Boolean algebra is used to analyse and simplify Truth tables are used in logical proofs.
digital circuits. Each truth table has columns and rows.
3-Set theory & Statistics Number of rows in a truth table is 2n,
3.1 Simple Logical operators where 𝑛 is number of inputs.
Closure property For example;
Logical operators act on one or more Boolean inputs 2 inputs A & B. No. of rows = 22 = 4
called operands to produce only one Boolean 3 inputs A, B & C. No. of rows = 23 = 8
output.
MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 1 of 8
The 2 forms of truth tables are: 3-NOT truth table
1-Expanded form
Each column has 1, 2 or 3 inputs i.e A, B, C.
Each row is a configuration of input /output values
i.e T for true and F for false.
2-Condensed form
Has cells (in rows and columns) for outputs.
This one has no condensed form.
To understand outputs:
1-AND truth table
Let A be a Set.
T not true T means false F ie not in set A
F not false F means true T ie in set A.

Example 3.1a
A: Today is Saturday.
B: Today is weekend.
Write statements for logical expressions:
(a) AΛB (b) AVB (c) A
Solution:
(a) Today is Saturday And Today is weekend.
(b) Today is Saturday Or Today is weekend.
To understand outputs: (c) Today is Not Saturday
Let A and B be switches in Series. Hierarchy of the above 3 Operators
Refers to precedence to follow when evaluating
outputs for logical expressions.
What comes first, second, third, etc?
The order of precedence is: NOT, AND, OR
If both switches are on, light is on /True. 1st highest is NOT, 2nd is AND, 3rd lowest is OR.
TΛT output is T, otherwise F.
Operator Symbol Precedence
NOT  1st
2-OR truth table
AND Λ 2nd
OR V 3rd
Parentheses ( ) override precedence.
Analogous to BODMAS in Arithmetic.
Compare using BODMAS to evaluate:
(a) 2 + 3 x 4/2 – 1 (b) 2 + 3 x 4/(2 – 1)
Multiplication is done before Addition.
Addition done is before Subtraction.
Refer to Logical expressions later.
Example 3.1b
Evaluate logical expressions:
To understand ouputs: (a) TΛ FV T (b) TV(FΛT)
Let A and B be switches in Parallel. Solution:
(a) 1st 1 T ≡ 𝐹 Then TΛFVF
2nd 2 TΛF ≡ F Then FVF≡ F
TΛ FV T ≡ F
If both switches are off, light is off /False. (b) 1st (FΛT) ≡ 𝐹 Then TVF≡ TΛT
FVF output is F, otherwise T. 2nd TΛT≡ T
TΛ(FVT) ≡ T
MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 2 of 8
Qn.1 Evaluate logical expressions: Implication truth table
(a) TΛ FV T (b) TΛ(FVT)

Searching using AND, OR, & NOT

These operators help search engines to narrow
down or broaden search results eg using Google
search engine. For example:
1-education AND health
Displays items with both education and health.
2-Uganda OR Africa T  F output is F, otherwise T.
Displays items with Uganda or Africa. If A is T & B is F, output is F; otherwise T.
3-education NOT health Truth table outputs using Example
Displays items with education but not health. The 3 obvious cases are:
Exercise 3.1 TT output is T
1. Construct truth tables for the 3 logical operators He is sick implies He gets treatment. T
AND, OR and NOT using truth values F F output is T.
1 and 0 (as used in digital electronics). He is not sick implies He does not get treatment. T
2. A: Today is Saturday. TF output is T
B: Today is weekend. He is sick implies He does not get treatment. T
Write statements for logical expressions: The tricky case is:
(a) AΛB (b) AVB (c) A FT output is T
3. Evaluate logical expressions: He is not sick implies He gets treatment. True* Why?
(a) TV FΛT (b) (TVF)ΛT Qn.2 Explain truth table outputs for  using these:
A: He passes exams
3.2 More logical operators B: He gets a reward
1-Implication operator Special Terms related to implication
This is a binary operator, also known as Given: pq
conditional. p is premise or hypothesis
Symbols & Notation: q is conclusion or consequent
 (used here & Maths). Also  qp is converse of pq
Read AB as “A implies B” pq is inverse of pq
Also read AB as “if A then B” qp is contrapositive of pq
It means ”if A is true, then B is true”. 2-Equivalence operator
A implies B, but not B implies A This is a binary operator, also known as
If AB is true, BA is not true. biconditional.
However, BA is true Symbols & Notation:
AB (used here). Also AB. Maths A≡B
Example 3.2a Read AB as “A is equivalent to B”
Find the output for A⇒B and B⇒A for:
Also AB as “A if and only if B”
(a) A: 𝑥 + 3 = 5 and B: 𝑥 = 2 Also written as A IFF B
(b) A: 𝑥 = 2 and B: 𝑥 2 = 4 It means ”if A is true, then B is true, and vice versa”.
Solution: A implies B, also B implies A
(a) AB output is T & BA output is T If AB is true, also BA is true.
(b) AB output is T & BA output is F
BA output is F because Example 3.2c
𝑥 2 = 4 implies 𝑥 = ±2 Find the output for AB and BA for:
(c) A: 𝑥 + 3 = 5 and B: 𝑥 = 2
(d) A: 𝑥 = 2 and B: 𝑥 2 = 4

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 3 of 8
Solution: Solution:
Similar as for implication; (a) 1st T ≡ 𝐹 Then TFFT F
(a) AB output is T & BA output is T 2nd FF ≡ T Then TTT F
(b) AB output is T & BA output is F 3rd TT≡ T Then TT F
BA output is F because 4th TF≡ F Then T F ≡ 𝐹
𝑥 2 = 4 implies 𝑥 = ±2 TFTT F≡ 𝐹
Equality truth table (b) 1st FT) ≡ 𝐹 Then T F T F
2nd  F≡ T Then TT T F
3rd TT≡ T Then TT F
4th T F≡ F Then T F ≡ 𝐹
T (FT) T F≡ 𝐹
We use Math symbol ≡ to avoid confusion with .
Qn.3 Evaluate logical expressions:
(a) TF TTF
(b) TF (T T) F
Both T  T & F  F output is T; otherwise F.
If both are T or both F, output is T; otherwise F. 3-NAND operator
Truth table outputs using Example This is a binary operator, meaning Not AND.
A: He is sick AND followed by NOT ie  (AΛB).
B: He gets treatment Symbols /Notation:  (used here). Also A/B
The 2 obvious cases are: AB ≡  (AΛB)
TT output is T NAND truth table
He is sick is equivalent to He gets treatment. T A B AΛB AB ≡  (AΛB)
F F output is T.
He is not sick is equivalent to He does not get T T T F
treatment. T. T F F T
The 2 cases derived from implication are:
TF output is F. Since T⇒F output is F. F T F T
He is sick is equivalent to He does not get F F F T
treatment. F
FT output is F. Since F⇐T output is F. T  T output is F, otherwise T.
He is not sick is equivalent to He gets treatment. F If both are T, output is F; otherwise T.
Hierarchy of all the above 5 Operators 4-NOR operator
The order of precedence is: This is a binary operator, meaning Not OR.
NOT, AND, OR, ,  OR followed by NOT ie  (AVB).
1st highest is NOT, and last lowest is Equivalence. Symbol /Notation:  (used here)
AB ≡  (AVB)
Operator Symbol Precedence Truth table
NOT  1st A B AVB AB ≡  (AVB)
AND Λ 2nd T T T F
OR V 3rd T F T F
Implication  4th F T T F
Equivalence  5th F F F T
Example 3.2d F  F output is T, otherwise F.
Evaluate logical expressions: If both are F, output is T; otherwise F.
(a) TFTT F Logical operators left out in this course are:
(b) T (FT) T F Exclusive OR & Inclusive OR.

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 4 of 8
Exercise 3.2 (c) pq
1. Explain truth table outputs for  using these:
A: He passes exams
B: He gets a reward
2. Given: pq
Draw a single truth table for:
(a) converse qp
(b) inverse pq
(c) contrapositive qp
3. Find the output for A⇒B and AB for: Qn.4 Use truth tables and evaluate logical
A: 𝑥 = 2 and B: 𝑥 + 3 = 5 expressions:
A: 𝑥 2 = 4 and B: 𝑥 = 2 (a) pVq (b) pVq (c) pq
4. Evaluate logical expressions: Complex logical expressions
(a) T F (TT) F Contain more logical inputs and logical operators;
(b) T (F T) T F including parenthesis () to enforce precedence.
Example 3.3b
3.3 Logical Expressions
Use truth tables and evaluate logical expressions:
Also known as Boolean expression or logical
propositions; are logical statements that result to (a) pVqΛr (b) pΛ(qVr) (c) p(qr)
truth value true / T or false / F. Solution:
They contain logical inputs and logical operators. (a) pVqΛr 1st Λ 2nd V
We use lower case letters 𝑝, 𝑞, 𝑟, etc, for logical
propositions. Where 𝑝 is for 𝑝𝑟𝑜𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛, and
other letters that follow 𝑝 in alphabetical order.
Use truth table and order of precedence to evaluate
output ie NOT, AND, OR, , .
Simple logical expressions
Contain fewer logical inputs and logical operators.
Example 3.3a (b) pΛ(qVr) 1st () 2nd Not 3rd Λ
Use truth tables and find truth values for logical
expressions:
(a) pΛq (b) pΛq (c) pq
Solution:
(a) pΛq

(c) p(qr)

(b) pΛq

Qn.5 Use truth tables and evaluate logical

expressions:
(a)  pV(qΛr) (b) pΛ(qVr) (c) p(qr)

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 5 of 8
Exercise 3.3 2-Logical Laws
Use truth tables and find truth values for logical Also known as Boolean laws or logical
expressions: equivalence laws; are special cases of logical
1. (a) pΛq (b) pq equivalences.
They can also be shown using truth tables, but not
(c) pVq (d) pq using other logical laws.
2. (a) p Λ ( q V r) (b) p V (q Λ r) 1-Commutative, Associative & Distributive Laws
Similar to Set theory Laws.
3. (a)  p Λ (q  r) (b) (p  q) Λ (q  r) a-Commutative laws
AΛB ≡ BΛA AVB≡BVA
4. (a) p  (q  r) (b) p  ( q  r)
Also written as:
4 Logical Equivalences & Laws
AxB≡BxA A+B≡B+A
1-Logical Equivalences
b-Associative laws
Also known as logical propositions or
(A Λ B) Λ C ≡ AΛ(BΛC)
propositional equivalences;
(A V B) V C≡ A V (B V C)
are 2 logical propositions with equal truth values
Also written as:
(true /T or false /F).
(A x B) x C ≡ A x (B x C)
There are 2 methods used to show this:
(A + B) + C≡ A +(B + C)
1-Truth tables
c-Distributive laws*
Recommended in this course unit, because it
A Λ (B V C) ≡ (A Λ B) V (A Λ C)
involves simple logical expressions.
A V (B Λ C) ≡ (A V B) Λ (A V C)
2-Logical laws
Also written as:
Used in digital electronics, because it involves
A x (B + C) ≡ (A x B) + (A x C)
complex logical expressions.
A + (B x C) ≡ (A + B) x (A + C)
We use Math symbol ≡ for equivalence to avoid
3-de Morgan’s laws or theorems*
confusion with .
Similar to Set theory Laws.
Example 3.4a  (A Λ B) ≡ B V A  (A V B) ≡ B Λ  A
Show these logical equivalences using truth tables:
Also written as:
(a) pq ≡ pVq (b) pq ≡ qp  (A x B) ≡ B +  A  (A + B) ≡ B x  A
Solution:
4-AND & OR laws
(a) pq ≡ pq a-AND laws
AT≡A AF≡F
AA≡A A  A ≡ F
Also written as:
AxT≡A AxF≡F
AxA≡A A x A ≡ F
p𝑞 & pq have same pattern of truth values. b-OR laws
(b) pq ≡ qp Example of conditional AF≡A AT≡T
AA≡A A  A ≡ A
Also written as:
A+F≡A A+T≡T
A+A≡A A + A ≡ T
Qn.7 Research and write these logical laws:
(a) Identity, Null, Negation & Dual negation Laws
pq & qp have same pattern of truth values. (b) Idempotent, Absorption & Conditional
Qn.6 Show the logical equivalences using truth Also refer to these logical theorems;
tables: complementary, duality, transposition, and
(a) (pq) ≡ pq (b) pq ≡ pΛq redundancy.

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 6 of 8
Example 3.4b 2-Contradiction
Show these logical laws using truth tables: It is always false. Results in only F.
(a) AΛT ≡ A AΛA ≡ F ie Negation law
(b)  (A Λ B) ≡ B V A
3-Contingency
(c) A Λ (B V C) ≡ (A Λ B) V (A Λ C) It is neither true nor false. Results into both T and F.
Solution: Example 3.4c
(a) AΛT ≡ A Show that the logical expression:
(a) AVA is a tautology
(b) AΛA is a contradiction
Solution:
A and AΛT have same pattern of truth values. (a) AVA is tautology
(b)  (A Λ B) ≡ B V A

AVA is tautology since all truth values are T.

(b) AΛA

AΛA is a contradiction since all truth values are F.

Two propositions p and q are logically equivalent if
logical expression p  q is a tautology.
 (A Λ B) & B V A have same pattern of truth Example 3.4d
values. Show that this logical expression is tautology using
(c) A Λ (B V C) ≡ (A Λ B) V (A Λ C) truth tables: pq pVq
To save on space; Solution:
Let P be A Λ (B V C) & Q be (A Λ B) V (A Λ C) To save on space;
Let A be pq pVq & B be pq  qp
(a) pq pVq

A Λ (B V C) & (A Λ B) V (A Λ C) have same pattern of pq pVq is a tautology since all truth values
truth values. are T.
Qn.8 Show these logical laws using truth tables: Qn.9 Show that this logical expression is tautology
(a) A  F ≡ F using truth tables: p  q  q  p
(b) A  T ≡ T Exercise 3.4
(c) A V (B Λ C) ≡ (A V B) Λ (A V C) 1. Show these logical laws using truth tables:
The 3 special logical propositions (a) A  A ≡ A
1-Tautology (b) A  F ≡ A
It is always true. Results in only T. (c)  (A V B) ≡ B Λ  A
AVA ≡ T ie Negation law (d) A V (B Λ C) ≡ (A V B) Λ (A V C)

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 7 of 8
2. Show these logical equivalences using truth
tables:
(a) p  q ≡  p   q
(b)  (p  q) ≡ p   q
(c) p  q ≡ (p  q) Λ (q  p)
(d) (pr)V(qr) ≡ (pΛq) r
3. Show that these logical expressions are
tautologies using truth tables:
(a) (p  q)  (q  p)
(b)  (p  q)  p  q
(c) p  q  p Λ  q

MUSINGO STEPHEN LECTURER DEPT OF ICT & ENG UICT 0782-506878 Page 8 of 8