Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: Boolean and mathematical logic (201-N11)

Logic is the first course where an English sentence and a Boolean expression must say exactly the same thing. “If it rains, I take my umbrella” says nothing about what happens when it does not rain, and that is precisely what the truth table makes visible.

This sheet gathers the moves that earn marks in 201-N11: negating an implication without producing another one, applying De Morgan all the way, choosing between a truth table and the laws of Boolean algebra, and grouping in a Karnaugh map without inventing rectangles. It is written for CEGEP students in computer science programs; once it is read, the corrected exercise set on the same chapter puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

All the logic of the course comes down to the exact meaning of the implication: it is false in only one case, its contrapositive is equivalent to it, and its converse has nothing to do with it.

This chapter is part of 201-N11, Mathematics for Computer Science

The essentials

The implication is false in only one case

• $p\Rightarrow q$ is false ONLY on the row $p=1$ , $q=0$ . Everywhere else it is true.
• In particular, it is vacuously true as soon as $p$ is false: “if $2+2=5$ then the Moon is square” is a TRUE implication.
• $p\Rightarrow q=\lnot p\lor q$ , and therefore $\lnot(p\Rightarrow q)=p\land\lnot q$ : the negation of an implication is NOT an implication.
• A truth table with $n$ propositions has $2^{n}$ rows, and there are $2^{2^{n}}$ Boolean functions of $n$ variables.

The only row where the implication is false is the one where the hypothesis is true and the conclusion false; the other three make it true.

Remember the false row rather than the three true ones: it is the only one to memorize, and every other question of the chapter comes back to it.

Contrapositive, converse, negation

• Contrapositive of $p\Rightarrow q$ : $\lnot q\Rightarrow\lnot p$ . It is ALWAYS equivalent to it, and that is what justifies proof by contrapositive.
• Converse: $q\Rightarrow p$ . It has NO truth connection with the original: both can be true, both false, or one without the other.
• Negation: $p\land\lnot q$ . It asserts the hypothesis and negates the conclusion, with no arrow at all.

p\Rightarrow q

and its contrapositive

\lnot q\Rightarrow\lnot p

always have the same value; the converse

q\Rightarrow p

is only worth what its own contrapositive is worth.

The quick test: the contrapositive swaps AND negates both sides, the converse only swaps them. Only one of the two is equivalent to the original statement.

The Boolean laws that really matter

• De Morgan: $\overline{AB}=\overline{A}+\overline{B}$ and $\overline{A+B}=\overline{A}\,\overline{B}$ . The bar distributes while CHANGING the operator.
• Both distributive laws: $A(B+C)=AB+AC$ , but also $A+BC=(A+B)(A+C)$ , which has no counterpart in ordinary algebra.
• Absorption: $A+AB=A$ and $A(A+B)=A$ . Idempotence: $AA=A$ and $A+A=A$ .
• Complement: $A+\overline{A}=1$ and $A\overline{A}=0$ .

Absorption: the lens

AB

(orange) already lies inside

A

(blue); adding it changes nothing,

A+AB=A

Absorption is the least used law and the most profitable one: it removes a whole term at once, where factoring only rearranges.

Quantifiers and normal forms

• $\lnot(\forall x,\ P(x))=\exists x,\ \lnot P(x)$ and $\lnot(\exists x,\ P(x))=\forall x,\ \lnot P(x)$ : the quantifier flips, the property is negated.
• Canonical sum-of-products form: one term for each row where the function equals $1$ , with the variable COMPLEMENTED (barred) if it equals $0$ on that row.
• Karnaugh map: groups are rectangles of $2^{k}$ cells, opposite edges are adjacent, and a group of $2^{k}$ cells eliminates $k$ variables.

In a Karnaugh map, opposite edges are adjacent: the four corners form a group of four cells, which eliminates two variables.

In a Karnaugh map, one group may overlap another: it costs nothing and often makes the groups larger. What costs marks is a group too small that could have been doubled.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Negating an implication with another implication

2 marks, and the proof by contradiction that follows starts from something false

What not to write

“ $\lnot(p\Rightarrow q)=p\Rightarrow\lnot q$ .”

What to write

“ $\lnot(p\Rightarrow q)=p\land\lnot q$ : assert the hypothesis and negate the conclusion, with no arrow.”

The two columns agree only on the first two rows, where

p

is true; on the last two, where

p

is false, the wrong negation says the opposite of the right one.

Why: Negating “if $p$ then $q$ ” means exhibiting a counterexample: a case where $p$ is true and $q$ false. An implication, on the other hand, would stay true as soon as $p$ is false.

2. Taking the converse for the contrapositive

2 marks, and it is the reasoning error most often penalized in the course

What not to write

“If a number is divisible by $4$ then it is even; so if it is even then it is divisible by $4$ .”

What to write

“The contrapositive is: if it is not even, it is not divisible by $4$ . The converse is false: $6$ is even without being divisible by $4$ .”

The multiples of

4

lie inside the even numbers: the implication and its contrapositive hold (the

7

, outside the even numbers, is outside them too). The

6

(red) refutes the converse.

Why: The contrapositive swaps AND negates; the converse only swaps. Only the first keeps the truth value, and it is the one used in proofs.

3. Applying De Morgan without changing the operator

1.5 marks, and the whole simplification that follows

What not to write

“ $\overline{A+B}=\overline{A}+\overline{B}$ .”

What to write

“ $\overline{A+B}=\overline{A}\,\overline{B}$ : the bar distributes by turning the OR into an AND.”

The bar distributes while changing the operator: outside

A\cup B

means outside

A

AND outside

B

; outside

A\cap B

means outside

A

OR outside

B

Why: “Neither one nor the other” is not “not one or not the other”. The two-row test is enough: for $A=1$ and $B=0$ , the first equals $0$ , the second would equal $1$ .

4. Forgetting the second distributive law

1 mark, and an expression twice as long as necessary

What not to write

“ $A+BC$ cannot be factored, so we leave it as it is.”

What to write

“ $A+BC=(A+B)(A+C)$ : in Boolean algebra, OR also distributes over AND.”

The region

A

plus the lens

B\cap C

is exactly the common part of

A\cup B

and

A\cup C

A+BC=(A+B)(A+C)

Why: It is the law with no counterpart in ordinary algebra, so the one nobody thinks of trying. It is mostly useful for bringing out an absorption.

5. Grouping three cells in a Karnaugh map

2 marks, and the expression obtained matches no circuit

What not to write

“These three adjacent cells equal $1$ , so I make them one group.”

What to write

“A group has $1$ , $2$ , $4$ or $8$ cells and forms a rectangle: I take one group of $2$ and another group of $2$ that overlap.”

On the left, a square of four cells, which eliminates two variables; on the right, three cells in an L, which form no term and must be covered by two groups of two.

Why: Each doubling of a group's size eliminates exactly one variable. A group of three cells eliminates nothing at all; it matches no term.

6. Negating a quantifier without flipping it

2 marks, and the negated statement says something else entirely

What not to write

“The negation of “all the servers respond” is “no server responds”.”

What to write

“It is “there is at least one server that does not respond”: the $\forall$ becomes $\exists$ and the property is negated.”

Why: Negating a universal statement takes a single counterexample, not a complete reversal. “None” is the negation of “at least one”, not of “all”.

7. Writing a canonical form without complementing the zero variables

1.5 marks, and a term that equals

1

on the wrong row

What not to write

“The row $A=1$ , $B=0$ , $C=1$ gives the term $ABC$ .”

What to write

“It gives $A\overline{B}C$ : a variable that equals $0$ on the row appears COMPLEMENTED in the term.”

Why: A term of the canonical form must equal $1$ on ITS row and $0$ everywhere else. Without the bar, it would equal $0$ precisely on the row it is supposed to describe.

8. Rejecting a vacuously true implication

1.5 marks, and two rows of a truth table

What not to write

“ $p$ is false, so $p\Rightarrow q$ makes no sense, nothing can be said.”

What to write

“When $p$ is false, $p\Rightarrow q$ is TRUE, whatever $q$ is: the promise has not been broken.”

Why: The implication claims nothing when its hypothesis is false. That is what makes true any property asserted “for every element” of an empty set.

9. Barring a single term under a NAND gate

2 marks, and the circuit drawn does not implement the required function

What not to write

“The output of a NAND gate is $\overline{A}\cdot B$ .”

What to write

“It is $\overline{A\cdot B}$ , that is $\overline{A}+\overline{B}$ : the bar covers the WHOLE product.”

The bubble of a NAND is on the OUTPUT: it negates the whole product (green). A bubble on a single input (red) implements

\overline{A}\cdot B

, a different function.

Why: The long bar is an operator in its own right: it is evaluated after the product. It is also what makes the NAND a universal gate, able to rebuild NOT, AND and OR on its own.

Which method to choose

Simplifying a Boolean expression

Look at the form of the expression, and at the number of variables.

If one term is contained in another, as in $A+AB$ → absorption: the longer term disappears

Example: $A+AB=A$

it is the most profitable simplification, the one to look for first
If a bar covers a whole parenthesis → De Morgan, changing the operator at each step down

Example: $\overline{A+BC}=\overline{A}(\overline{B}+\overline{C})$
If a common factor appears in several terms → factor, then look for $X+\overline{X}=1$

Example: $AB+A\overline{B}=A(B+\overline{B})=A$
If three or four variables, and a truth table available → Karnaugh map, with groups of $2^{k}$ cells as large as possible

Example: four minterms giving $AB+AC+BC$
If more than four variables → go back to the Boolean laws: the Karnaugh map becomes unreadable

Example: five variables would give $32$ cells

A simplification is always CHECKED on the complete truth table: two equal expressions must agree on all $2^{n}$ rows, not only on the ones you looked at.

Negating a statement, piece by piece

Find the main connective, the one that structures the statement.

If the statement is an implication $p\Rightarrow q$ → its negation is $p\land\lnot q$ , with no arrow

Example: “if the badge is valid then the door opens” is negated by “the badge is valid AND the door does not open”
If the statement is a conjunction $p\land q$ → $\lnot p\lor\lnot q$

Example: negating “tall and fast” gives “not tall or not fast”
If the statement is a disjunction $p\lor q$ → $\lnot p\land\lnot q$

Example: negating “red or blue” gives “neither red nor blue”
If the statement begins with “for all” → “there is at least one... that does not...”

Example: a single counterexample is enough to negate a universal statement
If the statement begins with “there exists” → “for all..., not...”

Example: negating “there is a solution” requires ruling them all out

When several quantifiers follow one another, flip them one at a time, from left to right, without changing their ORDER: swapping a $\forall$ and an $\exists$ changes the statement.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Proving that two Boolean expressions are equivalent

When to use it: The question asks you to show an identity, or to check a simplification.

1 Choose the method and state it: complete truth table, or chain of laws.
2 By table: draw up the $2^{n}$ rows, one column per subexpression, and compare the two final columns.
3 By the laws: start from the MORE COMPLICATED side and transform it, naming the law used on each line.
4 Conclude with a sentence, recalling that the equality holds on every row.

Concluding sentence

“ $A+AB=A(1+B)=A\cdot 1=A$ , by distributivity then by $1+B=1$ : the two expressions are equivalent.”

The trap: Transforming both sides at once and meeting in the middle without saying so: the work becomes unreadable and the marker can no longer follow the chain.

Marking: 1 mark for stating the method, 1 mark per law correctly named, 1 mark for the conclusion.

Translating a specification into a Boolean expression

When to use it: A problem describes in words the conditions for opening a door, triggering an alarm or validating an input.

1 Name each condition with a letter and write its meaning in full next to it.
2 Spot the words that carry the connectives: “and”, “or”, “unless”, “except if”, “only if”.
3 Write the complete truth table rather than guessing the expression.
4 Simplify with a Karnaugh map, then check on two chosen rows of the table.

Concluding sentence

“ $F=AB+AC+BC$ : the door opens when at least two of the three authorizations are present.”

The trap: Translating “ $A$ only if $B$ ” as $B\Rightarrow A$ : it is $A\Rightarrow B$ , the other way around.

Marking: 1 mark for the notation, 2 marks for the table, 1 mark for the simplification, 1 mark for the sentence that returns to the context.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Two well-chosen rows of the table

After a simplification, test the starting expression and the final expression on one row where they equal $1$ and one where they equal $0$ .

$A=1$ , $B=0$ , $C=0$ : the majority function equals $0$ , and $AB+AC+BC$ also equals $0$ .
Counting rows and terms

A table with $n$ variables has $2^{n}$ rows, and the canonical form has as many terms as there are rows equal to $1$ .

Four rows equal to $1$ out of eight: the canonical form has exactly four terms.
The size of Karnaugh groups

Reread each group: $1$ , $2$ , $4$ or $8$ cells, in a rectangle. A group of $2^{k}$ cells must remove exactly $k$ variables from the term.

A group of $2$ cells that leaves three variables out of three: the term has not been reduced.
What the bar covers

Check what each bar covers: a single variable, or a whole expression. A long bar is evaluated last.

$\overline{AB}$ equals $1$ for $A=1$ , $B=0$ , whereas $\overline{A}B$ equals $0$ .

The typical problem, taken apart

Access control: at least two authorizations out of three

A server room opens when at least two of the three managers $A$ , $B$ and $C$ have swiped their badges.

Draw up the truth table, write the canonical form, then simplify with a Karnaugh map.

Three badges, one door: the output equals

1

as soon as at least two inputs equal

1

, which the truth table will translate.

Step 1

Truth table: $F=1$ on the rows $011$ , $101$ , $110$ and $111$ , that is four rows out of eight.

Why

Draw up the table BEFORE guessing the expression: “at least two out of three” has no direct translation into connectives, and any attempt to write it down at once goes wrong.

Step 2

Canonical form: $F=\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC$ .

Why

One term per row equal to $1$ , with the zero variables complemented. Four rows give four terms: the count can be checked at a glance.

Step 3

Karnaugh map: three groups of two cells, which overlap on the cell $ABC$ .

Why

The overlap costs nothing and lets each group reach size $2$ . Refusing to overlap would leave groups of a single cell, hence terms with three variables.

Step 4

Reading the groups: $F=AB+AC+BC$ .

Why

Each group of $2^{1}$ cells eliminates one variable, the one that changes inside the group. We go from four terms of three letters to three terms of two letters.

Step 5

Check on two rows: for $A=1$ , $B=0$ , $C=0$ , $AB+AC+BC=0$ ; for $A=1$ , $B=1$ , $C=0$ , it equals $1$ .

Why

One row at $0$ and one row at $1$ are enough to catch almost all grouping errors, in ten seconds.

Step 6

With NAND gates: $F=\overline{\overline{AB}\cdot\overline{AC}\cdot\overline{BC}}$ .

Why

A sum of products is built with two levels of NAND gates, by double negation. This is the form required as soon as a circuit must be built with a single type of gate.

The conclusion, written out

“The access control function simplifies to $F=AB+AC+BC$ : the door opens as soon as at least two of the three managers have swiped their badges.”

The classic mistake on this problem: Writing $F=ABC$ by reading “two out of three” as a conjunction, or grouping the three cells of the row $A=1$ into a single group of three.

Learn by heart

• $p\Rightarrow q$ is FALSE only on the row $p=1$ , $q=0$ ; it is vacuously true as soon as $p$ is false.
• $\lnot(p\Rightarrow q)=p\land\lnot q$ : the negation of an implication is not an implication.
• The contrapositive $\lnot q\Rightarrow\lnot p$ is equivalent; the converse $q\Rightarrow p$ is not.
• De Morgan: the bar distributes while CHANGING the operator, in both directions.
• Absorption: $A+AB=A$ and $A(A+B)=A$ . Second distributive law: $A+BC=(A+B)(A+C)$ .
• Negating a quantifier: $\forall$ becomes $\exists$ , and vice versa, while the property is negated.
• Karnaugh map: rectangles of $1$ , $2$ , $4$ or $8$ cells, opposite edges adjacent, and a group of $2^{k}$ cells eliminates $k$ variables.

Frequently asked questions

Why is an implication true when the hypothesis is false?

Because an implication promises something only in the case where its hypothesis comes true. If it does not come true, the promise has not been broken, so the statement is not false. This is what makes true any property asserted for all the elements of an empty set.

What is the difference between the contrapositive and the converse?

The contrapositive swaps the two sides and negates both of them; it is always equivalent to the original statement, which lets you prove one by proving the other. The converse merely swaps the two sides without negating them, and it has no truth connection with the original statement.

How do you negate an implication?

By asserting the hypothesis and negating the conclusion, with no arrow at all in the result. Negating means exhibiting a counterexample: a case where the hypothesis is true and the conclusion false. Writing another implication as the negation is the most frequent error of the chapter.

How many cells can a group contain in a Karnaugh map?

One, two, four or eight, and the group must form a rectangle, with opposite edges of the map counted as adjacent. Each doubling of the size eliminates one variable from the resulting term. A group of three cells matches no term and is never allowed.

Should you use a truth table or the laws of Boolean algebra?

The truth table always proves, but it gets long beyond three variables, with sixteen rows for four. The Boolean laws are faster when an absorption or a De Morgan step jumps out at you. For three or four variables, the Karnaugh map combines both advantages.

Practise it

Corrected exercises: Boolean and mathematical logic, 201-N11

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

10 corrected exercises
100 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Next sheet Proof techniques

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-n11-boolean-logic. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. With a B.Sc. in computer science from McGill and an M.Sc. in applied computer science from Concordia, I teach Boolean logic the way you will use it next: in the conditions of a program, in database queries and in circuits.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: Boolean and mathematical logic (201-N11)

The essentials

The implication is false in only one case

Contrapositive, converse, negation

The Boolean laws that really matter

Quantifiers and normal forms

The mistakes that cost marks

1. Negating an implication with another implication

2. Taking the converse for the contrapositive

3. Applying De Morgan without changing the operator

4. Forgetting the second distributive law

5. Grouping three cells in a Karnaugh map

6. Negating a quantifier without flipping it

7. Writing a canonical form without complementing the zero variables

8. Rejecting a vacuously true implication

9. Barring a single term under a NAND gate

Which method to choose

Simplifying a Boolean expression

Negating a statement, piece by piece

How the answer is expected to be written

Proving that two Boolean expressions are equivalent

Translating a specification into a Boolean expression

Check before you hand in

The typical problem, taken apart

Access control: at least two authorizations out of three

Learn by heart

Frequently asked questions

Why is an implication true when the hypothesis is false?

What is the difference between the contrapositive and the converse?

How do you negate an implication?

How many cells can a group contain in a Karnaugh map?

Should you use a truth table or the laws of Boolean algebra?

Corrected exercises: Boolean and mathematical logic, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?