Discrete Mathematics Notes - DMS

LOGIC AND SETS

2009-01-09T23:02:00.000-08:00

1.1. Sentences

In this section, we look at sentences, their truth or falsity, and ways of combining or connecting sentences

to produce new sentences.

A sentence (or proposition) is an expression which is either true or false. The sentence \2 + 2 = 4" is

true, while the sentence \_ is rational" is false. It is, however, not the task of logic to decide whether

any particular sentence is true or false. In fact, there are many sentences whose truth or falsity nobody

has yet managed to establish; for example, the famous Goldbach conjecture that \every even number

greater than 2 is a sum of two primes".

There is a defect in our de_nition. It is sometimes very di_cult, under our de_nition, to determine

whether or not a given expression is a sentence. Consider, for example, the expression \I am telling a

lie"; am I?

Since there are expressions which are sentences under our de_nition, we proceed to discuss ways of

connecting sentences to form new sentences.

Let p and q denote sentences.

Definition. (CONJUNCTION) We say that the sentence p ^ q (p and q) is true if the two sentences p,

q are both true, and is false otherwise.

Example 1.1.1. The sentence \2 + 2 = 4 and 2 + 3 = 5" is true.

Example 1.1.2. The sentence \2 + 2 = 4 and _ is rational" is false.

1 of 9

Definition. (DISJUNCTION) We say that the sentence p _ q (p or q) is true if at least one of two

sentences p, q is true, and is false otherwise.

Example 1.1.3. The sentence \2 + 2 = 2 or 1 + 3 = 5" is false.

Example 1.1.4. The sentence \2 + 2 = 4 or _ is rational" is true.

Remark. To prove that a sentence p_q is true, we may assume that the sentence p is false and use this

to deduce that the sentence q is true in this case. For if the sentence p is true, our argument is already

complete, never mind the truth or falsity of the sentence q.

Definition. (NEGATION) We say that the sentence p (not p) is true if the sentence p is false, and is

false if the sentence p is true.

Example 1.1.5. The negation of the sentence \2 + 2 = 4" is the sentence \2 + 2 6= 4".

Example 1.1.6. The negation of the sentence \_ is rational" is the sentence \_ is irrational".

Definition. (CONDITIONAL) We say that the sentence p ! q (if p, then q) is true if the sentence p

is false or if the sentence q is true or both, and is false otherwise.

Remark. It is convenient to realize that the sentence p ! q is false precisely when the sentence p is

true and the sentence q is false. To understand this, note that if we draw a false conclusion from a true

assumption, then our argument must be faulty. On the other hand, if our assumption is false or if our

conclusion is true, then our argument may still be acceptable.

Example 1.1.7. The sentence \if 2 + 2 = 2, then 1 + 3 = 5" is true, because the sentence \2 + 2 = 2"

is false.

Example 1.1.8. The sentence \if 2 + 2 = 4, then _ is rational" is false.

Example 1.1.9. The sentence \if _ is rational, then 2 + 2 = 4" is true.

Definition. (DOUBLE CONDITIONAL) We say that the sentence p $ q (p if and only if q) is true if

the two sentences p, q are both true or both false, and is false otherwise.

Example 1.1.10. The sentence \2 + 2 = 4 if and only if _ is irrational" is true.

Example 1.1.11. The sentence \2 + 2 6= 4 if and only if _ is rational" is also true.

If we use the letter T to denote \true" and the letter F to denote \false", then the above _ve de_nitions

can be summarized in the following \truth table":

p q p ^ q p _ q p p ! q p $ q

T T T T F T T

T F F T F F F

F T F T T T F

F F F F T T T

Remark. Note that in logic, \or" can mean \both". If you ask a logician whether he likes tea or co_ee,

do not be surprised if he wants both!

2 of 9

Example 1.1.12. The sentence (p _ q) ^ (p ^ q) is true if exactly one of the two sentences p, q is true,

and is false otherwise; we have the following \truth table":

p q p ^ q p _ q p ^ q (p _ q) ^ (p ^ q)

T T T T F F

T F F T T T

F T F T T T

F F F F T F

1.2. Tautologies and Logical Equivalence

Definition. A tautology is a sentence which is true on logical ground only.

Example 1.2.1. The sentences (p ^ (q ^ r)) $ ((p ^ q) ^ r) and (p ^ q) $ (q ^ p) are both tautologies.

This enables us to generalize the de_nition of conjunction to more than two sentences, and write, for

example, p ^ q ^ r without causing any ambiguity.

Example 1.2.2. The sentences (p _ (q _ r)) $ ((p _ q) _ r) and (p _ q) $ (q _ p) are both tautologies.

This enables us to generalize the de_nition of disjunction to more than two sentences, and write, for

example, p _ q _ r without causing any ambiguity.

Example 1.2.3. The sentence p _ p is a tautology.

Example 1.2.4. The sentence (p ! q) $ (q ! p) is a tautology.

Example 1.2.5. The sentence (p ! q) $ (p _ q) is a tautology.

Example 1.2.6. The sentence (p $ q) $ ((p _ q) ^ (p ^ q)) is a tautology; we have the following \truth

table":

p q p $ q (p $ q) (p _ q) ^ (p ^ q) (p $ q) $ ((p _ q) ^ (p ^ q))

T T T F F T

T F F T T T

F T F T T T

F F T F F T

The following are tautologies which are commonly used. Let p, q and r denote sentences.

DISTRIBUTIVE LAW. The following sentences are tautologies:

(a) (p ^ (q _ r)) $ ((p ^ q) _ (p ^ r));

(b) (p _ (q ^ r)) $ ((p _ q) ^ (p _ r)).

DE MORGAN LAW. The following sentences are tautologies:

(a) (p ^ q) $ (p _ q);

(b) (p _ q) $ (p ^ q).

INFERENCE LAW. The following sentences are tautologies:

(a) (MODUS PONENS) (p ^ (p ! q)) ! q;

(b) (MODUS TOLLENS) ((p ! q) ^ q) ! p;

3 of 9

These tautologies can all be demonstrated by truth tables. However, let us try to prove the _rst

Distributive law here.

Suppose _rst of all that the sentence p ^ (q _ r) is true. Then the two sentences p, q _ r are both

true. Since the sentence q _ r is true, at least one of the two sentences q, r is true. Without loss of

generality, assume that the sentence q is true. Then the sentence p^q is true. It follows that the sentence

(p ^ q) _ (p ^ r) is true.

Suppose now that the sentence (p ^ q) _ (p ^ r) is true. Then at least one of the two sentences (p ^ q),

(p^r) is true. Without loss of generality, assume that the sentence p^q is true. Then the two sentences

p, q are both true. It follows that the sentence q _ r is true, and so the sentence p ^ (q _ r) is true.

It now follows that the two sentences p^(q _r) and (p^q)_(p^r) are either both true or both false,

as the truth of one implies the truth of the other. It follows that the double conditional (p ^ (q _ r)) $ ((p ^ q) _ (p ^ r)) is a tautology.

Definition. We say that two sentences p and q are logically equivalent if the sentence p $ q is a

tautology.

Example 1.2.7. The sentences p ! q and q ! p are logically equivalent. The latter is known as the

contrapositive of the former.

Remark. The sentences p ! q and q ! p are not logically equivalent. The latter is known as the

converse of the former.

1.3. Sentential Functions and Sets

In many instances, we have sentences, such as \x is even", which contains one or more variables. We

shall call them sentential functions (or propositional functions).

Let us concentrate on our example \x is even". This sentence is true for certain values of x, and is

false for others. Various questions arise:

_ What values of x do we permit?

_ Is the statement true for all such values of x in question?

_ Is the statement true for some such values of x in question?

To answer the _rst of these questions, we need the notion of a universe. We therefore need to consider

sets.

We shall treat the word \set" as a word whose meaning everybody knows. Sometimes we use the

synonyms \class" or \collection". However, note that in some books, these words may have di_erent

meanings!

The important thing about a set is what it contains. In other words, what are its members? Does it

have any? If P is a set and x is an element of P, we write x 2 P.

A set is usually described in one of the two following ways:

_ By enumeration, e.g. f1; 2; 3g denotes the set consisting of the numbers 1; 2; 3 and nothing else;

_ By a de_ning property (sentential function) p(x). Here it is important to de_ne a universe U to

which all the x have to belong. We then write P = fx : x 2 U and p(x) is trueg or, simply,

P = fx : p(x)g.

The set with no elements is called the empty set and denoted by ;.

4 of 9

Example 1.3.1. N = f1; 2; 3; 4; 5; :::g is called the set of natural numbers.

Example 1.3.2. Z = f: : : ;��2;��1; 0; 1; 2; : : :g is called the set of integers.

Example 1.3.3. fx : x 2 N and �� 2 <>2g = f1g.

Example 1.3.4. fx : x 2 Z and �� 2 <>2g = f��1; 0; 1g.

Example 1.3.5. fx : x 2 N and �� 1 <>1g = ;.

1.4. Set Functions

Suppose that the sentential functions p(x), q(x) are related to sets P, Q with respect to a given universe,

i.e. P = fx : p(x)g and Q = fx : q(x)g. We de_ne

_ the intersection P \ Q = fx : p(x) ^ q(x)g;

_ the union P [ Q = fx : p(x) _ q(x)g;

_ the complement P = fx : p(x)g; and

_ the di_erence P n Q = fx : p(x) ^ q(x)g.

The above are also sets. It is not di_cult to see that

_ P \ Q = fx : x 2 P and x 2 Qg;

_ P [ Q = fx : x 2 P or x 2 Qg;

_ P = fx : x 62 Pg; and

_ P n Q = fx : x 2 P and x 62 Qg.

We say that the set P is a subset of the set Q, denoted by P _ Q or by Q _ P, if every element of P

is an element of Q. In other words, if we have P = fx : p(x)g and Q = fx : q(x)g with respect to some

universe U, then we have P _ Q if and only if the sentence p(x) ! q(x) is true for all x 2 U.

We say that two sets P and Q are equal, denoted by P = Q, if they contain the same elements, i.e.

if each is a subset of the other, i.e. if P _ Q and Q _ P.

Furthermore, we say that P is a proper subset of Q, denoted by P _ Q or by Q _ P, if P _ Q and

P 6= Q.

The following results on set functions can be deduced from their analogues in logic.

DISTRIBUTIVE LAW. If P; Q;R are sets, then

(a) P \ (Q [ R) = (P \ Q) [ (P \ R);

(b) P [ (Q \ R) = (P [ Q) \ (P [ R).

DE MORGAN LAW. If P;Q are sets, then with respect to a universe U,

(a) (P \ Q) = P [ Q;

(b) (P [ Q) = P \ Q.

We now try to deduce the _rst Distributive law for set functions from the _rst Distributive law for

sentential functions.

Suppose that the sentential functions p(x), q(x), r(x) are related to sets P, Q, R with respect to a

given universe, i.e. P = fx : p(x)g, Q = fx : q(x)g and R = fx : r(x)g. Then

P \ (Q [ R) = fx : p(x) ^ (q(x) _ r(x))g

and

(P \ Q) [ (P \ R) = fx : (p(x) ^ q(x)) _ (p(x) ^ r(x))g:

5 of 9

Suppose that x 2 P \ (Q [ R). Then p(x) ^ (q(x) _ r(x)) is true. By the _rst Distributive law for

sentential functions, we have that

(p(x) ^ (q(x) _ r(x))) $ ((p(x) ^ q(x)) _ (p(x) ^ r(x)))

is a tautology. It follows that (p(x) ^ q(x)) _ (p(x) ^ r(x)) is true, so that x 2 (P \ Q) [ (P \ R). This

gives

P \ (Q [ R) _ (P \ Q) [ (P \ R): (1)

Suppose now that x 2 (P \ Q) [ (P \ R). Then (p(x) ^ q(x)) _ (p(x) ^ r(x)) is true. It follows from the

_rst Distributive law for sentential functions that p(x) ^ (q(x) _ r(x)) is true, so that x 2 P \ (Q [ R).

This gives

(P \ Q) [ (P \ R) _ P \ (Q [ R): (2)

The result now follows on combining (1) and (2).

1.5. Quanti_er Logic

Let us return to the example \x is even" at the beginning of Section 1.3.

Suppose now that we restrict x to lie in the set Z of all integers. Then the sentence \x is even" is only

true for some x in Z. It follows that the sentence \some x 2 Z are even" is true, while the sentence \all

x 2 Z are even" is false.

In general, consider a sentential function of the form p(x), where the variable x lies in some clearly

stated set. We can then consider the following two sentences:

_ 8x, p(x) (for all x, p(x) is true); and

_ 9x, p(x) (for some x, p(x) is true).

Definition. The symbols 8 (for all) and 9 (for some) are called the universal quanti_er and the exis-

tential quanti_er respectively.

Note that the variable x is a \dummy variable". There is no di_erence between writing 8x, p(x) or

writing 8y, p(y).

Example 1.5.1. (LAGRANGE'S THEOREM) Every natural number is the sum of the squares of four

integers. This can be written, in logical notation, as

8n 2 N; 9a; b; c; d 2 Z; n = a2 + b2 + c2 + d2:

Example 1.5.2. (GOLDBACH CONJECTURE) Every even natural number greater than 2 is the sum

of two primes. This can be written, in logical notation, as

8n 2 N n f1g; 9p; q prime; 2n = p + q:

It is not yet known whether this is true or not. This is one of the greatest unsolved problems in

mathematics.

1.6. Negation

Our main concern is to develop a rule for negating sentences with quanti_ers. Let me start by saying

that you are all fools. Naturally, you will disagree, and some of you will complain. So it is natural to

suspect that the negation of the sentence 8x, p(x) is the sentence 9x, p(x).

6 of 9

There is another way to look at this. Let U be the universe for all the x. Let P = fx : p(x)g. Suppose

_rst of all that the sentence 8x, p(x) is true. Then P = U, so P = ;. But P = fx : p(x)g, so that if

the sentence 9x, p(x) were true, then P 6= ;, a contradiction. On the other hand, suppose now that the

sentence 8x, p(x) is false. Then P 6= U, so that P 6= ;. It follows that the sentence 9x, p(x) is true.

Now let me moderate a bit and say that some of you are fools. You will still complain, so perhaps

none of you are fools. It is then natural to suspect that the negation of the sentence 9x, p(x) is the

sentence 8x, p(x).

To summarize, we simply \change the quanti_er to the other type and negate the sentential function".

Suppose now that we have something more complicated. Let us apply bit by bit our simple rule. For

example, the negation of

8x; 9y; 8z; 8w; p(x; y; z;w)

9x; (9y; 8z; 8w; p(x; y; z;w));

which is

9x; 8y; (8z; 8w; p(x; y; z;w));

which is

9x; 8y; 9z; (8w; p(x; y; z;w));

which is

9x; 8y; 9z; 9w; p(x; y; z;w):

It is clear that the rule is the following: Keep the variables in their original order. Then, alter all the

quanti_ers. Finally, negate the sentential function.

Example 1.6.1. The negation of the Goldbach conjecture is, in logical notation,

9n 2 N n f1g; 8p; q prime; 2n 6= p + q:

In other words, there is an even natural number greater than 2 which is not the sum of two primes. In

summary, to disprove the Goldbach conjecture, we simply need one counterexample!

7 of 9

Problems for Chapter 1

1. Using truth tables or otherwise, check that each of the following is a tautology:

a) p ! (p _ q) b) ((p ^ q) ! q) ! (p ! q)

c) p ! (q ! p) d) (p _ (p ^ q)) $ p

e) (p ! q) $ (q ! p)

2. Decide (and justify) whether each of the following is a tautology:

a) (p _ q) ! (q ! (p ^ q)) b) (p ! (q ! r)) ! ((p ! q) ! (p ! r))

c) ((p _ q) ^ r) $ (p _ (q ^ r)) d) (p ^ q ^ r) ! (s _ t)

e) (p ^ q) ! (p ! q) f) p ! q $ (p ! q)

g) (p ^ q ^ r) $ (p ! q _ (p ^ r)) h) ((r _ s) ! (p ^ q)) ! (p ! (q ! (r _ s)))

i) p ! (q ^ (r _ s)) j) (p ! q ^ (r $ s)) ! (t ! u)

k) (p ^ q) _ r $ ((p _ q) ^ r) l) (p q) (q p).

m) (p ^ (q _ (r ^ s))) $ ((p ^ q) _ (p ^ r ^ s))

3. For each of the following, decide whether the statement is true or false, and justify your assertion:

a) If p is true and q is false, then p ^ q is true.

b) If p is true, q is false and r is false, then p _ (q ^ r) is true.

c) The sentence (p $ q) $ (q $ p) is a tautology.

d) The sentences p ^ (q _ r) and (p _ q) ^ (p _ r) are logically equivalent.

4. List the elements of each of the following sets:

a) fx 2 N : x2 < 45g b) fx 2 Z : x2 < 45g c) fx 2 R : x2 + 2x = 0g d) fx 2 Q : x2 + 4 = 6g e) fx 2 Z : x4 = 1g f) fx 2 N : x4 = 1g

5. How many elements are there in each of the following sets? Are the sets all di_erent?

a) ; b) f;g c) ff;gg d) f;; f;gg e) f;; ;g

6. Let U = fa; b; c; dg, P = fa; bg and Q = fa; c; dg. Write down the elements of the following sets:

a) P [ Q b) P \ Q c) P d) Q

7. Let U = R, A = fx 2 R : x > 0g, B = fx 2 R : x > 1g and C = fx 2 R : x < 2g. Find each of the

following sets:

a) A [ B b) A [ C c) B [ C d) A \ B

e) A \ C f) B \ C g) A h) B

i) C j) A n B k) B n C

8. List all the subsets of the set f1; 2; 3g. How many subsets are there?

9. A, B, C, D are sets such that A [ B = C [ D, and both A \ B and C \ D are empty.

a) Show by examples that A \ C and B \ D can be empty.

b) Show that if C _ A, then B _ D.

10. Suppose that P, Q and R are subsets of N. For each of the following, state whether or not the

statement is true, and justify your assertion by studying the analogous sentences in logic:

a) P [ (Q \ R) = (P [ Q) \ (P [ R). b) P _ Q if and only if Q _ P.

c) If P _ Q and Q _ R, then P _ R.

8 of 9

11. For each of the following sentences, write down the sentence in logical notation, negate the sentence,

and say whether the sentence or its negation is true:

a) Given any integer, there is a larger integer.

b) There is an integer greater than all other integers.

c) Every even number is a sum of two odd numbers.

d) Every odd number is a sum of two even numbers.

e) The distance between any two complex numbers is positive.

f) All natural numbers divisible by 2 and by 3 are divisible by 6.

[Notation: Write x j y if x divides y.]

g) Every integer is a sum of the squares of two integers.

h) There is no greatest natural number.

12. For each of the following sentences, express the sentence in words, negate the sentence, and say

whether the sentence or its negation is true:

a) 8z 2 N, z2 2 N b) 8x 2 Z, 8y 2 Z, 9z 2 Z, z2 = x2 + y2

c) 8x 2 Z, 8y 2 Z, (x > y) ! (x 6= y) d) 8x; y; z 2 R, 9w 2 R, x2 + y2 + z2 = 8w

13. Let p(x; y) be a sentential function with variables x and y. Discuss whether each of the following is

true on logical grounds only:

a) (9x; 8y; p(x; y)) ! (8y; 9x; p(x; y)) b) (8y; 9x; p(x; y)) ! (9x; 8y; p(x; y))

9 of 9

INTRODUCTION TO INEQUALITIES

2008-12-15T00:09:00.000-08:00

Abstract. This is a somewhat modified version of the notes I had prepared for a lecture on inequalities

that formed part of a training camp organized by the Association of Mathematics Teachers of India for

preparation for the Indian National Mathematical Olympiad (INMO) for students from Tamil Nadu.

1. Basic idea of inequalities

1.1. What we need to prove. An “inequation” is an expression of the form:

F _ 0

where F is an expression in terms of certain variables. An “inequality”’ is an inequation that is

satisfied for all values of the variables (within a certain range).

For instance:

x2 − x + 1 _ 0

and

x2 − x − 1 _ 0

are both inequations. Among these, the first inequation is true for all real x, while the second

inequation is true for all values of x within a certain range.

Thus, when we talk of an inequality, we have the following in mind:

• The underlying inequation

• The range of values over which the inequality is true

A strict inequation is an inequation of the form:

F > 0

where F is an expression in terms of the variables.

Given any inequation F _ 0 we can consider the corresponding strict inequation F > 0.

Thus, when studying an inequality, we are interested in:

• The underlying inequation

• The range of values over which the inequality is true

• The values for which exact equality holds

Some other points to note:

• Any inequation of the form F _ G where F and G are both expressions can be written in the

standard form as F −G _ 0. The original inequation is true for precisely those values for which

the standard form is true. The equality conditions are also the same.

• An inequation of the form F _ G can be expressed as G−F _ 0. Again, the original inequation

is true for precisely those values for which the standard form is true. The equality conditions

are also the same.

c Vipul Naik, B.Sc. (Hons) Math and C.S., Chennai Mathematical Institute.

1.2. No square is negative. This basic inequality states:

x2 _ 0

The range is all x 2 R and equality holds iff x = 0.

This can be generalized to something of the form:

(f(x1, x2, . . . , xn))2 + (g(x1, x2, . . . , xn))2 _ 0

The range is all x 2 R and equality holds iff f(x1, x2, . . . , xn) = g(x1, x2, . . . , xn) = 0.

Problem 1. Prove that x4 − x2y2 + y4 _ 0 for all real x and y, equality holding iff x = y = 0.

Proof. We use:

x4 − x2y2 + y4 = (x2 − y2)2 + (xy)2

Thus, (x2 − y2) plays th role of f above and xy plays the role of g

Clearly then, the left-hand-side is nonnegative, and is 0 if and only if x2 = y2 and xy = 0, thus forcing

x = y = 0. _

We can extend the idea to sums of more than two squares:

Problem 2. Prove that a2 + b2 + c2 + ab + bc + ca _ 0 with equality holding only if a = b = c = 0.

Proof. The left-hand-side can be expressed as 1/2(a2 + b2 + c2 + (a + b + c)2). So it is nonnegative and

can be zero only if a = b = c = 0.

Alternatively, the left hand side can also be written as 1/2((a+b)2 +(b+c)2 +(c+a)2) and is hence

nonnegative, taking the value 0 if and only if a = b = c = 0 _

Another problem (for which I’m not writing the solution here):

Problem 3. Prove that a2 + b2 + c2 − (ab + bc + ca) _ 0 with equality holding only if a = b = c.

It turns out that one of the solution techniques for the previous problem can be applied to this one.

1.3. Manipulating about the inequality symbol. The following results are typically used for manipulating

inequalities:

• We can add two inequalities. The greater side gets added to the greater side, the smaller side

to the smaller side. If either inequality is strict, the resultant inequality is again strict. More

generally, the set of values for which the resultant inequality becomes equality is the intersection

of the corresponding sets for each inequality.

• We can multiply both sides of an inequality by a positive number. In general, however, we cannot

multiply two inequalities.

2. Mean inequalities

2.1. Definition of means. A mean is a good notion of average for a collection of numbers. A mean of

n numbers is thus typically a function from n-tuples of reals to reals, such that:

• If all the members of the tuple are equal, the mean should be equal to all of them. That is, if

a = a1 = a2 = . . . an then the mean of a1, a2, . . . , an is a.

• The mean is a symmetric function of all the elements of the tuple, that is, if the elements are

permuted, the value of the mean remains unchanged. That is, the mean of a1, a2, . . . , an is the

same as the mean of a_(1), a_(2), . . . , a_(n).

• The mean of a collection of positive numbers should be between the smallest number and the

largest number. That is, if a1 _ a2 _ . . . _ an, the mean lies between a1 and an.

• The mean is an increasing function in each of the arguments. That is, if ai _ a0i, then the mean of

a1, a2, . . . , ai−1, ai, ai+1, . . . , an is less than or equal to the mean of a1, a2, . . . , ai−1, a0i, ai+1, . . . , an.

We now define some typical notions of mean:

Definition. (1) The arithmetic mean(defined) of n real numbers a1, a2, a3, . . . , an is defined as:

a1 + a2 + . . . an

The arithmetic mean is a well-defined notion for any collection of real numbers (positive, negative

or zero).

(2) The geometric mean(defined) of n positive real numbers a1, a2, a3, . . . , an is defined as

(a1a2 . . . an)1/n

The geometric mean is defined only for positive numbers.

(3) The quadratic mean(defined) or the root-mean-square of n real numbers a1, a2, a3, . . . , an is

defined as:

a21

+ a22

+ . . . + a2

(4) The harmonic mean(defined) of n nonzero real numbers a1, a2, a3, . . . , an is defined as:

a−1

1 + a−1

2 + . . . + a−1

−1

For two positive reals a and b, these boil down to the formulas:

Name of the mean Value

Arithmetic mean (a+b)

Geometric mean pab

Quadratic mean

a2+b2

Harmonic mean 2ab

a+b

2.2. Inequalities for two variables.

Claim. For positive reals a and b, Q.M. _ A.M. _ G.M. _ H.M.

Proof. We prove Q.M. _ A.M. The remaining proofs follow along similar lines:

What we would like to show is that, for all reals a and b:

a2 + b2

2 _

a + b

Since the left side is nonnegative, it suffices to show that the square of the left side is greater than or

equal to the square of the right side. That is, we need to show that:

a2 + b2

2 _

(a + b)2

But the latter rearranges to (a − b)2 _ 0. This tells us that the inequality is valid for all real a and b

with equality holding iff a = b. _

Let’s look at the pattern. The Q.M. is essentially obtained by taking the arithmetic mean of squares

and then taking squareroot. The A.M. is obtained by taking the arithmetic mean of first powers and

then taking the first root. The H.M. is obtained by taking the arithmetic mean of inverses and then

taking the inverse. This suggests a general definition:

Mr(a, b) =

ar + br

_1/r

Then the quadratic mean is M2, the arithmetic mean is M1, and the harmonic mean is M−1.

By this definition, M0 does not make sense. But it turns out that, through a suitable limit argument,

we can take M0 as the geometric mean. In that case, we have:

M2 _ M1 _ M0 _ M−1

We also know that:

2 _ 1 _ 0 _ −1

Does this suggest something?

2.3. The mean inequalities: an explanation. Let a and b be positive reals. What can we say about

the behaviour of Mr(a, b) as r varies from −1 to 1. It turns out that as r ! −1, Mr approaches

min{a, b}, and as r ! 1, Mr ! max{a, b}. Thus, as r steadily increases, Mr(a, b) steadily goes from

the minimum to the maximum.

The explanation for this can be sought by viewing the r as a kind of weighting of a and b. The greater

the value of r, the greater the dominance of the bigger term, and hence, the greater the mean is to the

bigger term.

2.4. The mean inequalities for many variables. The same phenomena which we observe for two

variables also generalize to more than two variables. We define:

Mr(a1, a2, . . . , an) =

1 + ar

2 + . . . ar

_1/r

Again, as r ! −1, Mr approaches the minimum of the ans, and as r ! 1, Mr approaches the

maximum of the ans.

3. Cauchy-Schwarz inequality

3.1. Statement. Let (a1, a2, . . . , an) and (b1, b2, . . . , bn) be two n-tuples of real numbers. Then:

(

a2i

)(

b2i

) _ (

(aibi))2

With equality holding if and only if one of the tuples is zero or if bi = _ai for some fixed _ independent

of i (that is, the tuple of bis is a scalar multiple of the tuple of ais).

3.2. Vector interpretation. The vector interpretation of Cauchy Schwarz inequality looks at both

a = (a1,ma2, . . . , an) and b = (b1, b2, . . . , bn) as vectors in Rn. Then, the left-hand-side is:

|a|2 |b|2

where |a| denotes the magnitude or length of the vector a

The right-hand-side is the square of the dot product of the vectors, which is the same as:

(a.b)2 = |a|2 |b|2 cos2 _

where _ is the angle between the vectors. Since cos2 _ _ 1 and quality holds if and only if a and b are

collinear, we get a geometric proof of Cauchy-Schwarz inequality.

3.3. A trigonometric problem. Consider the following problem:

Problem 4. Maximize

a cos _ + b sin _

as a function of _ where a and b are fixed reals (and not both zero).

The idea is to view this as a dot product of vectors (a, b) and (cos _, sin _). We have:

(a2 + b2)(cos2 _ + sin2 _) _ (a cos _ + b sin _)2

Since cos2 _ + sin2 _ = 1, we obtain:

(a cos _ + b sin _) _

a2 + b2

A necessary and sufficient condition for the magnitude of the left-hand side to be pa2 + b2 is that

a/ cos _ = b/ sin _, giving tan _ = b/a. Among the two possible values for the pair (cos _, sin _) we must

pick the one making a cos _ + b sin _ positive.

3.4. A geometric problem. Consider the following problem:

Problem 5. Let A and B be two points in a plane at distance 1. Find the maximum length of a path

from A to B, comprising at most n line segments, with the property that at every stage, the distance

from B is reducing.

The answer is pn.

Proof. The idea of the proof is to use induction on n. Let f(n) denote the maximum value for a given n.

We observe that any such optimal path is memoryless in the following sense:

Suppose is a path from A to B comprising at most n line segments, and suppose that the first line

segment of ends at a point P. Now, the part from P to B must be composed of (n − 1) line segments

with the property that at every stage, the distance from B is reducing.

Now, whatever path we choose, we could replace it by a path of maximum length from P to B

comprising (n − 1) line segments and with the property that distance from B is reducing. Since the

original thing was longest, we conclude that the part from P to B must also be the longest one.

Now what is the longest possible path of (n − 1) line segments from P to B? Since lengths scale, it

is the length PB times the value f(n − 1). We thus get:

length of = AP + PBf(n − 1)

Thus the maximum of the possible lengths of is the maximum over all P of the above expression.

Now, from the fact that along the path AP, the distance from P is steadily reducing, we obtain that

the angle \APB is either obtuse or right. Thus, in particular, for any given length AP, we have:

PB _

1 − AP2

If equality does not hold, we could replace P by another point Q such that AQ = AP and such that

\AQB = _/2. Then, QB would be greater than PB, and hence, the length of the longest path would

increase. Hence, we conclude that equality does indeed hold for the longest path, viz \APB = _/2.

Let _ be \BAP. Then AP = cos _ and PB = sin _. We thus get:

length of = max

cos _ + f(n − 1) sin _

Thus, applying the result of the previous problem:

f(n) =

1 + (f(n − 1))2

Since f(1) = 1 (clearly) we get f(n) = pn. _

4. Rearrangement and Chebyshev inequality

4.1. Rearrangement inequality: statement. Let (a1, a2, . . . , an) and (b1, b2, . . . , bn) be two n-tuples

of real numbers such that a1 _ a2 _ . . . _ an and b1 _ b2 _ . . . bn. Let _ be a permutation of the

numbers 1, 2, . . . , n. Then:

aibi _

aib_(i)

In other words, the sum of pairwise products is maximum if we pair the largest with the largest, the

second largest with the second largest, and so on.

Equality holds if and only if, for each i, ai = a_(i) or bi = b_(i).

Further:

aib_(i) _

aibn+1−i

In other words, the sum of pairwise products is minimum if we pair the largest with the smallest, the

second largest with the second smallest, and so on.

4.2. Idea behind the inequality. Think of it as a resource allocation problem. For instance, suppose

a thief has 3 bags and 3 kinds of coins (gold, silver, copper) to pack in them, and she must pack a

different kind of coin in each bag. Assume further that the coins are available in unlimited quantities.

Then, in order to maximize her loot, she will put the gold coins in the biggest bag, the silver coins in

the second biggest bag, and the copper coins in the third biggest bag.

The idea is: send the most to the best. Such an allocation principle is often called a greedy allocation

principle.

The Rearrangement inequality is best proved for two elements, and then extended by induction. Let

a1 _ a2 and b1 _ b2. Then we have:

(a1 − a2)(b1 − b2) _ 0

Manipulating this gives us:

a1b1 + a2b2 _ a1b2 + a2b1

The rearrangement inequality thus illustrates the general statement the principles of optimization and

equality are often at crossroads.

To use this to prove the result globally, we start with the expression

i aib_(i) and locate indices i, j

for which i <>but _(i) > _(j). We then change the permutation to one sending i to _(j) and j to _(i)

(and having the same effect as _ on the others). This local change increases the value of the expression

and hence it is clearly not the optimum value.

Note here that equality holds only if ai = aj or b_(i) = b_(j).

4.3. An application of rearrangement. Consider the following problem I had mentioned earlier:

Prove that a2 + b2 + c2 − (ab + bc + ca) _ 0 with equality holding only if a = b = c.

This problem can also be solved using the rearrangement inequality. First observe that since the

expression is symmetric in a, b and c, we can assume without loss of generality that a _ b _ c.

Consider the triple (a, b, c). This is an ordered triple with the property that the elements are in nonincreasing

order. Then (b, c, a) is a permutation of this expression. Thus, by rearrangement inequality:

aa + bb + cc _ ab + bc + ca

Which gives us what we want.

Also note that in this case, equality holds if and only if a = b = c.

4.4. Chebyshev inequality. Chebyshev inequality says that sending the most to the best is better

than giving the average to the average. More formally, if (a1, a2, . . . , an) and (b1, b2, . . . , bn) are two

n-tuples of decreasing reals:

aibi _

i ai

i bi

Where equality holds iff either all the ais are equal or all the bis are equal.

4.5. Fundamental difference between Chebyshev and Cauchy-Schwarz. Both the Chebyshev

and the Cauchy-Schwarz inequalities are similar in the following sense:

• They are both true for all reals

• They both provide bounds of

i aibi

But they are different in the following ways:

• In Chebyshev, it is important to order the ais and bis in descending order, whereas Cauchy-

Schwarz is applicable for any ordering

• Chebyshev gives a bound in terms of

i ai and

i bi while Cauchy-Schwarz gives a bound in

terms of the sums of their squares.

• Chebyshev provides a lower bound on

i aibi while Cauchy-Schwarz provides an upper bound

• The equality case is different in both. In Chebyshev, equality holds if all the elements in one of

the tuples are equal. In Cauchy-Schwarz, equality holds if the two tuples are scalar multiples of

one another.

A word of caution, though, when deciding whether to apply Chebyshev or Cauchy-Schwarz. Just

because the inequality seems to require a lower bound on

i FiGi, does not mean that Chebyshev is the

one to be used. In fact, we could still use Cauchy-Schwarz by taking ai = FiGi and bi to be 1/Fi.

5. Nesbitt’s inequality

5.1. Statement of the inequality.

Problem 6 (Nesbitt’s inequality). For positive a, b and c, prove that:

b + c

+ b

c + a

+ c

a + b _

with equality holding if and only if a = b = c.

5.2. Applying Cauchy-Schwarz (direct application fails). To apply Cauchy-Schwarz we need to

put the terms a

b+c and its analogues on the left side, which means we should view each of them as a

square. Their squareroots are

b+c and its analogues. Thus, one tuple is:

b + c

c + a

a + b

We would like the other tuple to be ��pb + c,pc + a,pa + b something that cancels the denominator. A natural choice is

. Unfortunately, this fails to yield the answer, because the expression that we

get is upper-bounded, rather than lower-bounded, in the case of equality.

5.3. Applying Chebyshev. Consider the tuples (a, b, c) and ((b + c)−1, (c + a)−1, (a + b)−1). We first

need to determine whether they are arranged in the same order. Assume without loss of generality that

a _ b _ c. Then b + c _ c + a _ a + b, and taking inverses, we obtain that the second tuple also has its

coordinates in descending order.

We are thus in a position to apply Chebyshev’s and obtain that the give expression is at least:

(a + b + c)((b + c)−1 + (c + a)−1 + (a + b)−1)

Now using A.M.-H.M. inequality for the quantities (b + c), (c + a) and (a + b), we get the required

result.

5.4. A short proof. Another way of proving the result is to add and subtract 3, thus writing it as:

(a + b + c)

b + c

c + a

a + b

And now apply the A.M.-H.M. inequality.

6. A past IMO problem

6.1. The problem statement.

Problem 7 (IMO 1995). Prove that if a, b and c are positive reals such that abc = 1, then:

a3(b + c)

b3(c + a)

c3(a + b) _

The first trick is to put x = 1/a, y = 1/b and z = 1/c. The left-hand side becomes:

y + z

+ y2

z + x

+ z2

x + y

6.2. Cauchy-Schwarz. After this point, the first possibility to consider is Cauchy-Schwarz. Since we

want to lower-bound the sum here, we must view x2

y+z and its analogues as squares of a tuple. The other

tuple is obtained by cancelling denominators from third tuple. We thus have tuples:

py + z

pz + x

px + y

and

��py + z,pz + x,px + y

We apply Cauchy-Schwarz to these tuples, and then use A.M.-G.M. inequality and the fact that

xyz = 1.

If we keep track of the inequality constraints at each step, we obtain that equality holds if and only

if x = y = z = 1, and hence a = b = c = 1.

Index

arithmetic mean, 2

Cauchy-Schwarz inequality, 3

Chebyshev inequality, 5

geometric mean, 2

harmonic mean, 2

mean

arithmetic, 2

geometric, 2

harmonic, 2

quadratic, 2

quadratic mean, 2

rearrangement inequality, 4

Boolean Algebra

2008-08-12T04:36:00.001-07:00

Boolean algebra is one of the most interesting and important algebraic structure which has significant applications in switching
circuits, logic and many branches of computer science and engineering.

Boolean algebra can be viewed as one of the special type of lattice.

A complemented distributive lattice with 0 and 1 is called Boolean algebra.
Generally Boolean algebra is denoted by (B, *, Å , ', 0, 1).

Example 1 :

( P(A), Ç , È , ', f, A) is a Boolean algebra. This is an important example of Boolean algebra [In fact the basic properties of
the (P (A), Ç , È , ' ) led to define the abstract concept of Boolean algebra]. Further, it can be proved that every finite Boolean
algebra must be isomorphic to (P (A), Ç , È , ' , f , A) for a suitably chosen finite set A. [refer [2]].

Example 2:

The structure ( Bⁿ = {0,1}ⁿ , *, Å , 1, 0 ) is a Boolean algebra, where Bⁿ is an n-fold Cartesian product of
{0,1} and the operations *, Å , are defined below.
We have Bⁿ = {( l₁, l₂, … , l_n) / l_r = 0 or 1, 1 £ r £ n}
(i₁, i₂, … , i_n) * (j₁, j₂, … , j_n) = (min (i₁, j₁), min (i₂, j₂), .., min (i _n, j_n) )
(i₁, i₂, … , i_n) Å (j₁, j₂,…, j_n) = (max ( i₁, j₁), max ( i₂, j₂), … , max ( i_n, j_n) )
(l₁, l₂, l₃, … , l_n)' = (l₁', l₂', …. , l_n'),

1 = (1,1, …, 1) is the greatest element of Bⁿ.
0 = (0, 0,0, … ,0) is the least element of Bⁿ.
Since B is distributive, Bⁿ is distributive. From the definition of unary operation " ' ",

it is clear that Bⁿ is complemented. Further, it has 0 and 1. Thus, (Bⁿ, *, Å , ', 0,1) is a Boolean algebra.
For the case n = 3 we have,
B³ = {000, 100, 010, 001, 110, 101, 011, 111}.
The structure of the B³ is given in the following Hasse diagram.

The Boolean algebra (Bⁿ, *, Å , ', 0,1) plays an important role in the construction of switching circuits, electronic circuits and
other applications. Also it can be proved that every finite Boolean algebra is isomorphic to the above Boolean algebra
(Bⁿ, *, Å , ', 0,1), for some n. Thus, it is interesting to observe that number of elements in any finite Boolean algebra must be
always 2ⁿ, for some n.

Let (B, *, Å , ' , 0,1) be a Boolean algebra and S Í B. If S contains the elements 0 and 1 and is closed under the
operation *, Å and ' then (S, *, Å , ', 0,1) is called sub Boolean algebra.

Example 1:

Consider the Boolean algebra (P ({1,2,3}), Ç , È , ' ,f , {1,2,3})

Then (S = {f , {1}, {2,3}, {1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
Similarly, S = ({f ,{3},{1,2},{1,2,3}}, Ç , È , ', f , {1,2,3}) is also sub Boolean algebra.
But (S = ({f, {1}, {2,3}, {1,2,3}}, Ç , È ,' , f , {1,2,3})) is not a sub Boolean algebra.

[Find why it is not a sub Boolean algebra].

If we have two Boolean algebras (B₁, *₁, Å ₁, ', 0₁, 1₁) and (B₂, *₂, Å ₂, '', 0₂, 1₂) then we can get new Boolean algebra
by taking direct product of these two Boolean algebras. The direct product of these Boolean algebra is the Boolean algebra
(B₁ ´ B₂, *₃, Å ₃, ''', 0₃, 1₃); where for any two elements (a₁, b₁) and (a₂, b₂) Î B₁ ´ B₂,

(a₁,b₁) * (a₂,b₂) = (a₁*₁a₂, b₁*₂b₂)

(a₁,b₁)Å (a₂,b₂) = (a₁Å ₁a₂, b₁Å ₂b₂)

(a₁,b₁) ''' = (a₁', b₁'')

0₃=(0₁,0₂) and 1₃=(1₁,1₂).

Let (B, *, Å , ', 0_B , 1_B) and (A, Ç , È, - , 0_A, 1_A) be two Boolean algebra. A mapping

f : B A is called a Boolean homomorphism if f preserves all the Boolean operations, that is,

f (a * b) = f (a) Ç f (b).
f (a Å b) = f (a) È f (b).

f (0_B) = 0_A.
f (1_B) = 1_A.

A bijective Boolean homomorphism is called Boolean isomorphism.

Exercise:

Prove that mapping f defined in the exercise 1 of the Section 3.3.3 is a Boolean isomorphism.
In every Boolean algebra, prove that (x * y)' = x' Å y' and (x Å y)' = x' * y', for all x, y.
In a Boolean algebra B, for all x, y Î B, prove that
x £y x * y = 0x' Å y = 1x * y = xx Å y = y.

fig ( i ) fig ( ii ) fig ( iii )

Show that in a Boolean algebra the following are equivalent for any a and b.
( i ) a' Ú b = 1
( ii ) a b' = 0.
The Boolean algebras (P (A₃), Ç , È, ', A₃, f) and D₃₀, where A₃ = {1,2,3} are (Boolean) isomorphic? Justify your
answer.