High School Mathematics Extensions/Logic

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Introduction

Logic is the study of the way we reason. In this chapter, we focus on the methods of logical reasoning, i.e. digital logic, predicate calculus, application to proofs and the (insanely) fun logical puzzles.

Boolean algebra

In the black and white world of ideals, there is absolute truth. That is to say everything is either true or false. With this philosophical backdrop, we consider the following examples:

"One plus one equals two." True or false?

That is (without a doubt) true!

"1 + 1 = 2 AND 2 + 2 = 4." True or false?

That is also true.

But what about:

"1 + 1 = 3 OR Sydney is in Australia" True or false?

It is true! Although 1 + 1 = 3 is not true, the OR in the statement made the whole statement to be true if at least one of the statements is true.

Now let's consider a more puzzling example

"2 + 2 = 4 OR 1 + 1 = 3 AND 1 - 3 = -1" True or false?

The truth or falsity of the statements depends on the order in which you evaluate the statement. If you evaluate "2 + 2 = 4 OR 1 + 1 = 3" first, the statement is false, and otherwise true. As in ordinary algebra, it is necessary that we define some rules to govern the order of evaluation, so we don't have to deal with ambiguity.

Before we decide which order to evaluate the statements in, we do what most mathematician love to do -- replace sentences with symbols.
Let x represent the truth or falsity of the statement 2 + 2 = 4.
Let y represent the truth or falsity of the statement 1 + 1 = 3.
Let z represent the truth or falsity of the statement 1 - 3 = -1.

Then the above example can be rewritten in a more compact way:

x OR y AND z

To go one step further, mathematicians also replace OR by + and AND by ×, the statement becomes:

$x+y\times z$

Now that the order of precedence is clear. We evaluate (y AND z) first and then OR it with x. The statement "x + yz" is true, or symbolically

$x+yz=1$

where the number 1 represents "true".

There is a good reason why we choose the multiplicative sign for the AND operation. As we shall see later, we can draw some parallels between the AND operation and multiplication.

The Boolean algebra we are about to investigate is named after the British mathematician George Boole. Boolean algebra is about two things -- "true" or "false" which are often represented by the numbers 1 and 0 respectively. Alternative, T and F are also used.

Boolean algebra has operations (AND and OR) analogous to the ordinary algebra that we know and love.

Basic Truth tables

We have all had to memorize the 9 by 9 multiplication table and now we know it all by heart. In Boolean algebra, the idea of a truth table is somewhat similar.

Let's consider the AND operation which is analogous to the multiplication. We want to consider:

x AND y

where and x and y each represent a true or false statement (e.g. It is raining today). It is true if and only if both x and y are true, in table form:

The AND function
x	y	x AND y
F	F	F
F	T	F
T	F	F
T	T	T

We shall use 1 instead of T and 0 instead of F from now on.

The AND function
x	y	x AND y
0	0	0
0	1	0
1	0	0
1	1	1

Now you should be able to see why we say AND is analogous to multiplication, we shall replace the AND by ×, so x AND y becomes x×y (or just xy). From the AND truth table, we have:

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

To the OR operation. x OR y is FALSE if and only if both x and y are false. In table form:

The OR function
x	y	x OR y
0	0	0
0	1	1
1	0	1
1	1	1

We say OR is almost analogous to addition. We shall illustrate this by replacing OR with +:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1 (like 1 OR 1 is 1)

The NOT operation is not a binary operation like AND and OR, but a unary operation, meaning it works with one argument. NOT x is true if x is false and false if x is true. In table form:

The NOT function
x	NOT x
0	1
1	0

In symbolic form, NOT x is denoted x' or ~x (or by a bar over the top of x).

Alternative notations:

$x\times y=x\wedge y$

and

$x+y=x\vee y$

Compound truth tables

The three truth tables presented above are the most basic of truth tables and they serve as the building blocks for more complex ones. Suppose we want to construct a truth table for xy + z (i.e. x AND y OR z). Notice this table involves three variables (x, y and z), so we would expect it to be bigger than the previous ones.

To construct a truth table, firstly we write down all the possible combinations of the three variables:

x	y	z
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

There is a pattern to the way the combinations are written down. We always start with 000 and end with 111. As to the middle part, it is up to the reader to figure out.

We then complete the table by hand computing what value each combination is going to produce using the expression xy + z. For example:

000

x = 0, y = 0 and z = 0

xy + z = 0

001

x = 0, y = 0 and z = 1

xy + z = 1

We continue in this way until we fill up the whole table

x	y	z	xyORz
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

The procedure we follow to produce truth tables are now clear. Here are a few more examples of truth tables.

Example 1 -- x + y + z

x	y	z	x+y+z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Example 2 -- (x + yz)'

When an expression is hard to compute, we can first compute intermediate results and then the final result.

x	y	z	x+yz	(x+yz)'
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	1	0

Example 3 -- (x + yz')w

x	y	z	w	(x+yz')w
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	0
1	1	1	1	1

Exercise

Produce the truth tables for the following operations:

1. NAND: x NAND y = NOT (x AND y)
2. NOR: x NOR y = NOT (x OR y)
3. XOR: x XOR y is true if and ONLY if one of x or y is true.

Produce truth tables for:

1. xyz
2. x'y'z'
3. xyz + xy'z
4. xz
5. (x + y)'
6. x'y'
7. (xy)'
8. x' + y'

Laws of Boolean algebra

In ordinary algebra, two expressions may be equivalent to each other, e.g. xz + yz = (x + y)z. The same can be said of Boolean algebra. Let's construct truth tables for:

xz + yz

(x + y)z

xz + yz

x	y	z	xz+yz
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

(x + y)z

x	y	z	(x+y)z
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

By comparing the two tables, you will have noticed that the outputs (i.e. the last column) of the two tables are the same!

Definition

We say two Boolean expressions are equivalent if the output of their truth tables are the same.

We list a few expressions that are equivalent to each other

x + 0 = x

x × 1 = x

xz + yz = (x + y)z

x + x' = 1

x × x' = 0

x × x = x

x + yz = (x + y)(x + z)

Take a few moments to think about why each of those laws might be true.

The last law is not obvious but we can prove that it's true using the other laws:

${\begin{matrix}(x+y)(x+z)&=&x(x+z)+y(x+z)\\&=&xx+xz+xy+yz\\&=&x+xz+xy+yz\\&=&x(1+z+y)+yz\\&=&x+yz\end{matrix}}$

It has been said: "the only thing to remember in mathematics is that there is nothing to remember. Remember that!". You should not try to commit to memory the laws as they are stated, because some of them are so deadly obvious once you are familiar with the AND, OR and NOT operations. You should only try to remember those things that are most basic, once a high level of familiarity is developed, you will agree there really isn't anything to remember.

Simplification

Once we have those laws, we will want to simplify Boolean expressions just like we do in ordinary algebra. We can all simplify the following example with ease:

${\begin{matrix}xyzw'+xyzw&=&xyz(w+w')\\&=&xyz\end{matrix}}$

the same can be said about:

${\begin{matrix}(x+y)(x'+y')&=&x(x'+y')+y(x'+y')\\&=&xx'+xy'+yx'+yy'\\&=&0+xy'+yx'+0\\&=&xy'+yx'\end{matrix}}$

From those two examples we can see that complex-looking expressions can be reduced very significantly. Of particular interest are expressions of the form of a sum-of-product, for example:

xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z

We can factorise and simplify the expression as follows

$xyz+xyz'+xy'z+x'yz+x'y'z'+x'y'z$

$=\ xy(z+z')+xy'z+x'yz+x'y'(z'+z)$

$=\ xy+xy'z+x'yz+x'y'$

$=\ x(y+y'z)+x'(yz+y')$

It is only hard to go any further, although we can. We use the identity:

x + yz = (x + y)(x + z)

If the next step is unclear, try constructing truth tables as an aid to understanding.

${\begin{matrix}&=&\ x(y+z)+x'(z+y')\\&=&\ xy+xz+x'z+x'y'\\&=&\ xy+(x+x')z+x'y'\\&=&\ xy+z+x'y'\\\end{matrix}}$

And this is as far as we can go using the algebraic approach (or any other approach). The algebraic approach to simplification relies on the principle of elimination. Consider, in ordinary algebra:

x + y - x

We simplify by rearranging the expression as follows

(x - x) + y = y

Although we only go through the process in our head, the idea is clear: we bring together terms that cancel themselves out and so the expression is simplified.

De Morgan's theorems

So far we have only dealt with expressions in the form of a sum of products e.g. xyz + x'z + y'z'. De Morgan's theorems help us to deal with another type of Boolean expressions. We revisit the AND and OR truth tables:

{

}

You would be correct to suspect that the two operations are connected somehow due to the similarities between the two tables. In fact, if you invert the AND operation, i.e. you perform the NOT operations on x AND y. The outputs of the two operations are almost the same:

{

}

The connection between AND, OR and NOT is revealed by reversing the output of x + y by replacing it with x' + y'.

{

}

Now the two outputs match and so we can equate them:

(xy)' = x' + y'

this is one of de Morgan's laws. The other which can be derived using a similar process is:

(x + y)' = x'y'

We can apply those two laws to simplify equations:

Example 1
Express x in sum of product form

${\begin{matrix}x&=&(ab'+c)'\\&=&(ab')'c'\\&=&(a'+b)c'\\&=&a'c'+bc'\end{matrix}}$

Example 2
Express x in sum of product form

${\begin{matrix}x&=&(a+b+c)'\\&=&(a+b)'c'\\&=&a'b'c'\\\end{matrix}}$This points to a possible extension of De Morgan's laws to 3 or more variables.

Example 3
Express x in sum of product form

${\begin{matrix}x&=&[(a'+c)\cdot (b+d')]'\\&=&(a'+c)'+(b+d')'\\&=&ac'+b'd\\\end{matrix}}$

Example 4
Express x in sum of product form

${\begin{matrix}x&=&[(a+bc)\cdot (d+ef)]'\\&=&(a+bc)'+(d+ef)'\\&=&a'(bc)'+d'(ef)'\\&=&a'(b'+c')+d'(e'+f')\\&=&a'b'+a'c'+d'e'+d'f'\\\end{matrix}}$

Another thing of interest we learnt is that we can reverse the truth table of any expression by replacing each of its variables by their opposites, i.e. replace x by x' and y' by y etc. This result shouldn't have been a surprise at all, try a few examples yourself.

De Morgan's laws

$(x+y)'=x'y'$

$(xy)'=x'+y'$

Exercise

1. Express in simplified sum-of-product form:
   1. z = ab'c' + ab'c + abc
   2. z = ab(c + d)
   3. z = (a + b)(c + d + f)
   4. z = a'c(a'bd)' + a'bc'd' + ab'c
   5. z = (a' + b)(a + b + d)d'
2. Show that x + yz is equivalent to (x + y)(x + z)

Propositions

We have been dealing with propositions since the start of this chapter, although we are not told they are propositions. A proposition is simply a statement (or sentence) that is either TRUE or FALSE. Hence, we can use Boolean algebra to handle propositions.

There are two special types of propositions -- tautology and contradiction. A tautology is a proposition that is always TRUE, e.g. "1 + 1 = 2". A contradiction is the opposite of a tautology, it is a proposition that is always FALSE, e.g. 1 + 1 = 3. As usual, we use 1 to represent TRUE and 0 to represent FALSE. Please note that opinions are not propositions, e.g. "42 is an awesome number" is just an opinion, its truth or falsity is not universal, meaning some think it's true, some do not.

Examples

• "It is raining today" is a proposition.
• "Sydney is in Australia" is a proposition.
• "1 + 2 + 3 + 4 + 5 = 16" is a proposition.
• "Earth is a perfect sphere" is a proposition.
• "How do you do?" is not a proposition - it's a question.
• "Go clean your room!" is not a proposition - it's a command.
• "Martians exist" is a proposition.

Since each proposition can only take two values (TRUE or FALSE), we can represent each by a variable and decide whether compound propositions are true by using Boolean algebra, just like we have been doing. For example "It is always hot in Antarctica OR 1 + 1 = 2" will be evaluated as true.

Implications

Propositions of the type if something something then something something are called implications. The logic of implications are widely applicable in mathematics, computer science and general everyday common sense reasoning! Let's start with a simple example

"If 1 + 1 = 2 then 2 - 1 = 1"

is an example of implication, it simply says that 2 - 1 = 1 is a consequence of 1 + 1 = 2. It's like a cause and effect relationship. Consider this example:

John says: "If I become a millionaire, then I will donate $500,000 to the Red Cross."

There are four situations:

1. John becomes a millionaire and donates $500,000 to the Red Cross
2. John becomes a millionaire and does not donate $500,000 to the Red Cross
3. John does not become a millionaire and donates $500,000 to the Red Cross
4. John does not become a millionaire and does not donate $500,000 to the Red Cross

In which of the four situations did John NOT fulfill his promise? Clearly, if and only if the second situation occurred. So, we say the proposition is FALSE if and only if John becomes a millionaire and does not donate. If John did not become a millionaire then he can't break his promise, because his promise is now claiming nothing, therefore it must be evaluated TRUE.

If x and y are two propositions, x implies y (if x then y), or symbolically

$x\Rightarrow y$

has the following truth table:

x	y	$x\Rightarrow y$
0	0	1
0	1	1
1	0	0
1	1	1

For emphasis, $x\Rightarrow y$ is FALSE if and only if x is true and y false. If x is FALSE, it does not matter what value y takes, the proposition is automatically TRUE. On a side note, the two propositions x and y need not have anything to do with each other, e.g. "1 + 1 = 2 implies Australia is in the southern hemisphere" evaluates to TRUE!

If

$(x\Rightarrow y)\ {\mbox{AND}}\ (y\Rightarrow x)$

then we express it symbolically as

$x\Leftrightarrow y$.

It is a two way implication which translates to x is TRUE if and only if y is true. The if and only if operation has the following truth table:

x	y	$x\Leftrightarrow y$
0	0	1
0	1	0
1	0	0
1	1	1

The two new operations we have introduced are not really new, they are just combinations of AND, OR and NOT. For example:

$x\Rightarrow y=x'+y$

Check it with a truth table. Because we can express the implication operations in terms of AND, OR and NOT, we have open them to manipulation by Boolean algebra and de Morgan's laws.

Example 1
Is the following proposition a tautology (a proposition that's always true)

$[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$

Solution 1

$=\ [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$

$=\ [(x'+y)(y'+z)]'+(x'+z)$

$=\ (x'+y)'+(y'+z)'+x'+z$

$=\ xy'+yz'+x'+z$

$=\ y'+y+x'+z$

$=\ 1$

Therefore it's a tautology.

Solution 2
A somewhat easier solution is to draw up a truth table of the proposition, and note that the output column are all 1s. Therefore the proposition is a tautology, because the output is 1 regardless of the inputs (i.e. x, y and z).

Example 2
Show that the proposition z is a contradiction (a proposition that is always false):

z = xy(x + y)'

Solution

${\begin{matrix}z&=&xy(x+y)'\\&=&xy(x'y')\\&=&0\\\end{matrix}}$

Therefore it's a contradiction.

Back to Example 1, :$[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$. This isn't just a slab of symbols, you should be able translate it into everyday language and understand intuitively why it's true.

Exercises

1. Decide whether the following propositions are true or false:
   1. If 1 + 2 = 3, then 2 + 2 = 5
   2. If 1 + 1 = 3, then boys don't like mud
2. Show that the following pair of propositions are equivalent
   1. $x\Rightarrow y$ : $y'\Rightarrow x'$

Logic Puzzles

Puzzle is an all-encompassing word, it refers to anything trivial that requires solving. Here is a collection of logic puzzles that we can solve using Boolean algebra.

Example 1

We have two type of people -- knights or knaves. A knight always tell the truth but the knaves always lie.

Two people, Alex and Barbara, are chatting. Alex says :"We are both knaves"

Who is who?

We can probably work out that Alex is a knave in our heads, but the algebraic approach to determine Alex 's identity is as follows:

Let A be TRUE if Alex is a knight

Let B be TRUE if Barbara is a knight

There are two situations, either:

Alex is a knight and what he says is TRUE, OR

he is NOT a knight and what he says is FALSE.

There we have it, we only need to translate it into symbols:

A(A'B') + A'[(A'B')'] = 1

we simplify:

(AA')B' + A'[A + B] = 1

A'A + A'B = 1

A'B = 1

Therefore A is FALSE and B is TRUE. Therefore Alex is a knave and Barbara a knight.

Example 2

There are three businessmen, conveniently named Archie, Billy and Charley, who order martinis together every weekend according to the following rules:

1. If A orders a martini, so does B.
2. Either B or C always order a martini, but never at the same lunch.
3. Either A or C always order a martini (or both)
4. If C orders a martini, so does A.

1. $A\Rightarrow B$ or $A'+B=1$ (simplified from: $AB+A'B'+A'B=1$
2. $B'C+BC'=1$
3. $A+C=1$
4. $C\Rightarrow A$ or $C'+A=1$ (simplified from: $CA+C'A'+C'A=1$

Putting all these into one formula and simplifying:

${\begin{matrix}1&=&(A'+B)(B'C+BC')(A+C)(C'+A)\\&=&(A'+B)(B'C+BC')(AC'+AA+CC'+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+0+AC)\\&=&(A'+B)(B'C+BC')(AC'+A+AC)\\&=&(A'+B)(B'C+BC')(C'+1+C)A\\&=&(A'+B)(B'C+BC')(1)A\\&=&(A'+B)(B'C+BC')A\\&&{\mbox{Now that we know that }}A=1{\mbox{ we can substitute that in:}}\\&=&(0+B)(B'C+BC')1\\&=&(B)(B'C+BC')\\&&{\mbox{Now that we know that }}B=1{\mbox{ we can substitute that in:}}\\&=&(1)(0C+1C')\\&=&C'\\&&{\mbox{If }}1=C'{\mbox{ then }}C=0\\&&ABC'=1\end{matrix}}$

Exercises

Please go to Puzzles/Logic puzzles.

Problem Set

1. Decide whether the following propositions are equivalent:

$x'\Rightarrow y'$

$y\Rightarrow x$

2. Express in simplest sum-of-product form the following proposition:

$(x\Leftrightarrow y)\Rightarrow z$

3. Translate the following sentences into symbolic form and decide if it's true:

a. For all x, if x² = 9 then x² - 6x - 3 = 0

b. We can find a x, such that x² = 9 and x² - 6x - 3 = 0 are both true.

4. NAND is a binary operation:

x NAND y = (xy)'

Find a proposition that consists of only NAND operators, equivalent to:

(x + y)w + z

5. Do the same with NOR operators. Recall that x NOR y = (x + y)'

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.