ONLINE MATHEMATICS NOTES

By ICYINGENEYE Pacifique

VISIT RWANDA, THE BEAUTIFUL COUNTRY IN EAST AFRICA
Next topic >>
Topic 1: Discrete Mathematics
 
 

 

1. GENERALITIES

Discrete Mathematics encompasses many of those mathematics which are most directly applicable to computer science and communication engeneering. It incorporates a selection of concepts and techniques from classical mathematics, newly applied to modern problems.

Discrete Mathematics is often characterised as "non continuous mathematics" in the sense that it frequently deals with sets consisting of separated or spaced out numbers (or other elements). This characterisation serves to distinguish discrete mathematics from continous mathematics which includes differential and integral calculus.

A feature of the discrete sets we encounter is that they involve only a finite or countably infinite number of elements. To understand the difference between countably infinite and uncountably infinite, it is sufficient to say that the set of Natural numbers can be regarded as a typical countably infinite set whereas the set of Real numbers is an important example of an uncountably infinite.

The distinction between discrete and continuous mathematics may also noted in the study of Statistics. Continuous probability distributions may also invlove measurement (of some quantity such as height), whereas discrete probability distributions often involve counting the number of occurences of some phenomenon (such as the number of customers passing through a turn site during any five minutes period of time).

A more profound distribution can be seen in the area of optimisation. In continous mathematics maximazing or minimizing a quantity is commonly done by using differential calculus, while in discrete mathematics other methods must be employed.

1.1. Definitions

Discrete Mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of mathematics that all have in common the feature that they are "discrete" rather than "continuous". It is the application of mathematical techniques to logic. 

Informal logic is the study of natural language arguments. The study of fallacies is an important branch of informal logic. Since much informal argument is not strictly speaking deductive, on some conceptions of logic, informal logic is not logic at all.

Formal logic is the study of inference with purely formal content. An inference possesses a purely formal content if it can be expressed as a particular application of a wholly abstract rule, that is, a rule that is not about any particular thing or property.

Symbolic logic is the study of symbolic abstractions that capture the formal features of logical inference. Symbolic logic is often divided into two main branches: propositional logic and predicate logic.

Mathematical logic is an extension of symbolic logic into other areas, in particular to the study of model theory, proof theory, set theory, and recursion theory. Mathematical logic has two sides: syntax and semantics. Syntax is how we say things and semantics is what we mean.

1.2. Propositions

a) Initial terms

In any mathematical theory, new term are defined by using those that have been defined. However, this process has to start somewhere. A few initial terms necessarily remain undefined. In logic, the words sentence, true and false are initial undefined terms.

b) Definition and examples

A proposition or a statement is a sentence that is true or false but not both.

Example

- The sentence Canada is African country is a statement whose truth value is "false".
- The sentence Bujumbura is the capital of Burundi is a statement whose truth value is "true".
- The equality is a statement whose truth value is "true" for any value of x and y
- The equality is not a statement because for some values of x and y, the equality is true, whereas for others is false.

Notation

The two truth values of statement are true and false and are denoted by the symbols T and F respectively. Occasionally they are also denoted by the symbols 1 and 0 respectively. In this topic statements are denoted by letters such as P, Q, R, S, …

Truth table

We can always summarize the truth values of compound statement in a table called truth table truth table. If there are n distinct statements, we need to consider  possible combinations of truth values in order to obtain the truth table.

For one proposition P, there are possible combinations and the truth table is as follow

P
T
F

For two propositions P and Q, there are possible combinations and the truth table is as follow

P
Q
T
T
T
F
F
T
F
F

For three propositions P, Q and R, there are possible combinations and the truth tble is as follow

P
Q
R
T
T
T
T
T
F
T
F
T
T
F
F
F
T
T
F
T
F
F
F
T
F
F
F

2. LOGIC OF PROPOSITIONS

2.1. Negation, conjunction and disjunction

a. Molecular or compound statement

The notion of statement and of its truth value has been already introduced. In the case of simple statements, their truth values are fairly obvious. We introduce three symbols that are used to build more complicated statement (compound statements) out of simpler ones.

We have the symbols to denote respectively NOT, AND, OR . The statements that we consider initially are simple statements, called atomic or primary statements. New statements can be formed from atomic statements through the use of sentential connectives; the resulting statements are called molecular or compound statements.

b. Truth table of compound statements

Negation

The negation of a statement by introducing the word "not", denoted by prefixing the statement, has opposite truth value from the statement. It is denoted by or or .

From this definition, it follows that if P is true, then is false and vice-versa. The truth value of relative to P is given in the following table.

Truth table for negation
P
T
F
F
T

Strictly speaking, not is not a connective, since it does not join two propositions, and is not really a compound statement. However, not is a unary operation for the collection of propositions, and is a proposition if P is.

Conjunction

The conjunction (AND) of two statements P and Q is the statement P and Q denoted . It has the truth value true whenever both P and Q have the truth value true; otherwise it has the truth value false.

P
Q
T
T
T
T
F
F
F
T
F
F
F
F

Disjunction

The disjunction (OR) of two statements P and Q is the statement P or Q denoted . It has the truth value false only when P and Q have truth value false, otherwise it has the truth value true.

P
Q
T
T
T
T
F
T
F
T
T
F
F
F

Statement formula

Statement formulae are the compound statements formed by using the statements variables like P and Q and logic connectives (such as ). For eaxmple are statement formulae.

Example

Construct the truth table for

Solution

P
Q
T
T
F
F
F
F
T
F
F
T
F
T
F
T
T
F
T
T
F
F
T
T
F
T

Logical equivalence

Two statements formulae P and Q are said to be ligically equivalent if they have identical truth values for each possible substitution of statements for their statement variables. In this case we write .

Example

1) Double negation property :

P
T
F
T
F
T
F

2) De Morgan's laws: and

P
Q
T
T
F
F
T
F
T
F
F
F
T
F
F
T
F
T
T
F
T
F
F
T
T
F
F
T
T
F
T
F
F
F
T
T
F
T
F
T
T
T

Tautology and contradiction

A statement formula that is always true regardless of the truth valuess of the individual statements for its statement variables is said to be a tautology. In this case wea say a tautological statement.

A statement formula that is always false regardless of the truth valuess of the individual statements for its statement variables is said to be a contradiction. In this case wea say a contractory statement.

Theorem: Logical equivalences

For any statements P, Q and R; a tautology t and a contradiction c, the following equivalences hold

Commutative laws
Associative laws
Distributive laws
Identity laws
Negation laws
Double negation laws  
Idempotent laws
De Morgan's laws
Universal laws
Absorption laws
Negation laws

2.2. Conditional and biconditional statements

Conditional statement

Given two statements P and Q, the conditional statement is denoted by which we read "if P, then Q" or "P implies Q". The statement P is classed antecedent or hypothesis and Q is called the consequent or conclusion.

The conditional statement is false when Q is false while P is true, otherwise it is true.

P
Q
T
T
T
T
F
F
F
T
T
F
F
T

Phrasing of the conditional statement

Each of the following is equivalent to the conditional statement :

If P, then Q P implies Q
Q follows P Not P unless Q
Q if P P only if Q
whenever P, Q Q whenever P
P is sufficient for Q Q is necessary for P
P is a sufficient condition for Q Q is a necessary condition for P

Example

Rephrase the sentence "If it is Sunday, I must go to church."

Solution

Here are various ways of rephrasing the sentence:

"Its being Sunday implies that I go to church."

"I go to church if it is Sunday."

"It is Sunday only if I go to church."

"It can't be Sunday unless I go to church."

"To be Sunday is sufficient for me to go to church."

"That I go to church is a necessary condition for its being Sunday."

Example

Write the following statement in symbolic form: "If either John eats rice or Betty eats beans then Peter will not eat."

Solution

Let P denotes John eats rice, Q denotes Betty eats beans and R denotes Peter doesn't eat.

Symbolique form is .

Example

In the same table, construct the truth table for

1)          2)          3)         4)   

By comparing results 1) and 2), and results 3) and 4) give your observation.

Solution

P
Q
T
T
F
F
T
T
F
F
T
F
F
T
F
F
T
T
F
T
T
F
T
T
F
F
F
F
T
T
T
T
F
F

Observation: and

Contrapositive of implication

The contrapositive of a conditional statement is a conditional statement defined as .

Converse and inverse of implication

The converse of a conditional statement is defined as . The conditional statement and its converse are not logically equivalent.

The inverse of a conditional statement is defined as . The conditional statement and its inverse are not logically equivalent.

The converse and the inverse of a conditional statement are logically equivalent.

Logical implication

When the compount statement is a tautology, we say that P logically implies Q and we wite .

Argument

An assertion that the conjunction of several statements logically implies another statement is known as an argument. If it is true that then we say that the argument is valid. An argument that is not valid is said to be fallacy or fallacious argument.

Rules of inference

Rules of inference are kinds of arguments which occur so frequently that they are given special names. They can help us to verify that an argument is valid.

Here, we are going to see two of the most important rules of inference.

1) Rule of Detachment

The rule of Detachment known by the name of Modus Ponens says that:

From Modus Ponens we dueduce another rule known by the name of Modus Tollens. Modus Tollens says that .

2) Law of Hypothetical Syllogism (or Transitive rule)

Transitive rule says that

Example

Consider the following argument:

"If the integer 35244 is divisible by 396, then the integer 35244 is divisible by 66. If the integer 35244 is divisible by 66, then the integer 35244 is divisible by 3. Therefore, if the integer 35244 is divisible by 396, then the integer 35244 is divisible by 3."

This argument illustrated the transitive rule by taking:
P: the integer 35244 is divisible by 396,
Q: the integer 35244 is divisible by 66 and
R: the integer 35244 is divisible by 3.

Biconditional statement

Given two statements P and Q, the biconditional statement is denoted by which we read "P if and only if Q" or "P is equivalent to Q".

The conditional statement is true when P and Q have the same truth values, otherwise it is false.

P
Q
T
T
T
T
F
F
F
T
F
F
F
T

Phrasing of the conditional statement

Each of the following is equivalent to the conditional statement :

P if and only if Q

P is necessary and sufficient for Q

P is equivalent to Q

Example

Rephrase the statement: "I teach math if and only if I am paid a large sum of money."

Solution

Some equivalent ways of phrasing the given sentence:

"My teaching math is necessary and sufficient for me to be paid a large sum of money."

"For me to teach math it is necessary and sufficient that I be paid a large sum of money."

Example

In the same table, construct the truth table for

1)          2)         

By comparing two results, give your observation.

Solution

P
Q
T
T
T
T
T
T
T
F
F
T
F
F
F
T
T
F
F
F
F
F
T
T
T
T

Observation:

Notice: The statements P and Q are logically equivalent if and only if the statement is a tautology. In this case we write .

3. PEDICATES AND QUANTIFIERS

In the previous subtopic, the statements were taken as basic units of statement calculus, and no analysis of any atomic statement was admitted. Only compound formulas were analysed, and this analysis was done by studying the forms of compound formulas, i.e the connection between the constituent atomic statements. It was not possible to express the fact that any two atomic statements have some features in common. In order to investigate questions of this nature, we introduce the concept of a predicate in an atomic statement. The logic based upon the analysis of predicates in any statement is called predicate logic.

In the previous chapter, we mentioned how sentences that involve a variable, such as x, need not be statements. For example, the sentence "The number x+2 is a even integer." is not necessarily true or false unless we know what value is substitued for x. If we restrict our choice to integers, then when x is replaced by -5, -1 or 3 for instance, the resulting statement is false. In fact, it is false whenever x is replaced by an odd integer. When an even integer is substitued for x, however, the statement is true.

We refer to the statement "The number x+2 is a even integer." as an open statement, which we formally define as follows.

3.1. Predicates

A predicate is a declarative setence which contains one or more variables and it is not a stetement but it become a statement when variables in it are replaced by certain allowable choices.

In this topic, we will denoe predicates by capital letters followed by its variable. For example, is a predicate P with variable x and y.

Domain of interpretation or universe of discourse or simply a domain, denoted by D, is the set of all possible values for the variables of a described predicate.

How often a predicate becomes true can depend on the choice of domain.

Example

Let be the predicate and let the domain of interpretation be D={0,1,2}. Then, this predicate may become true or false depending on how we choose x and y. Choosing x=0 and y=1, the predicate is true sice 0+1=1 but choosing x=2 and y=0, the predicate is false sice .

Notice: It is useful to be able to quantify how often a predicate associated with a particular domain becomes true statement. This can be done by use of quantifiers.

3.2. Quantifiers

Qnatifiers are certain words, symbols or groups of words that help us to know how the given predicate becomes true, whether it is satisfied by no element of a domain or one element or some elements or all elements. They tell us about the quantity

We have two most important quantifiers:

1. The existential quantifier ∃ (there exists)

If, for a predicate , there exist at least one value x in domain for which is true then we write .

Example

Given the predicate with D={0,1,2,3}. This predicate is true only when x={0,1}, for other values in the domain it is false. So is true.

Notice: Also often used in predicate logic is the unique existetnial quantifier (∃!) whic means that there exist a unique ...For example, the unique existential quantifier can be used in the following statement: "Every real number has a unique cube root."

2. The universal quantifier ∀ (for all)

If, for a predicate , no matter what value of x from the domain is choosen is true then we write .

Example

Given the predicate with D={0,1,2,3}. This predicate is true for all values in the domain. So is true.

Negation of quantifiers

Let write down the negation of the following statements:

1. Some people fear mathematics.

2. All women have breasts

The negation is

1. No people fear mathematics. We can rephrase this statement by saying: All people do not fear mathematics.

2. Some women do not have breasts.

Using symbolic form we can say:

1. Let x represents people and represents x fear mathematics. We can write, in symbolic form, the first statement as . The negation is

2. Let x represents women and represents x have breasts. We can write, in symbolic form, the second statement as . The negation is

From these two statements and their negations, we can write the following equivalences:

Note that the two qunatifiers we have seen can be mixed in a single statement formula.

Example

Negate the statement:

1. All grapefruit are pink.

2. Some celebrities are modest.

Solution

1. Negation

There exists at least one grapefruit that is not pink
or: There exists a grapefruit that is not pink
or: There exists one grapefruit that is not pink
or: Some grapefruit are not pink.

2. No celebrities are modest.

Example

Negate the statement:

1.                    2.

Solution

1.             2.

Arguments with quantified statements

We already saw what that the converse of a conditional statement is defined as and the inverse of a conditional statement is defined as .

An argument form consisting of two premises and a conclusion is called a syllogism. The first and second premises are called the major premise and minor premise, respectively.

Modus Ponens

, if  then
 for a particular a, therefore 

Example

All human beings are mortal.
Felix is a human being.
Therefore, Felix is mortal.  

Modus Tollens

, if  then
  for a particular a, therefore 

Example

All human beings are mortal.
Felix is not mortal.
Therefore, Felix is not human being.

Converse error

The following argument is invalid:

, if  then
 for a particular a, therefore   

The above argument would be valid if the major premise is replaced by its converse. But, since a conditional statement is not logically equivalent to its converse such replacement cannot be made in general. So, this argument exhibits the converse error.

Example

All human beings are mortal.
Felix is mortal.
Therefore, Felix is a human being.  

Inverse error

The following argument is invalid:

, if  then
  for a particular a, therefore   

The above argument would be valid if the major premise is replaced by its inverse. But, since a conditional statement is not logically equivalent to its inverse such replacement cannot be made in general. So, this argument exhibits the inverse error.

Example

All human beings are mortal.
Felix is not a human being.
Therefore, Felix is not mortal.  

4. MATHEMATICAL REASONING

4.1. Methods of proof

Some mathematical theorems have the form . To prove a theorem of the first kind, we would usually try to find a number or element x which has the required property .

Example

Prove that there exists a number x whith the property that, for every real number y , xy=x.

Solution

x=0 has the property described in the theorem, and we have proved that the theorem is true.

Mostly we will concentrate on the other kind of the theorem. In particular, we consider theorems of the kind .

Direct proof

In a direct proof, we assume that the hypothesis, , is true and try to deduce that the conculsion, , is also true.

Example

Proove that if m is an even integer then is odd.

Solution

Since m is even, we have for some integer a. Then,

.

Since is an integer, we conclude hat is odd.

For some theorems a direct prrof can be hard to proove. An alternative method that can sometimes be easier is the contrapositive proof.

Contrapositive proof

In a contrapositive proof, we assume that the conculsion, , is false and we try to deduce that the hypothesis, , is also false.

Example

Prove that, for every integer x, if is an odd number then so is x.

Solution

The theorem has the structure if then is odd then x is odd. So the contrapositive is if x is even then is even.

Since x is even, and we have

So, is even as required.

Disproving conjecture

If a statement is described as a tehorem, then it is usually a true statement. A statement which is clained to be a theorem is known as a conjecture. It only becomes a theorem after someone ahs proved it for the firat time. Suppose that a conjecture turns to be false, it has to be disproved. For example, the Fermat's last theorem, which was really a conjecture for 358 years until it was proved.

Suppose a conjecture has the form . To disprove it, it to prove that its negation is true which means . For example to disprove the claim: "There exists an even number x for which 3x is odd" is simply to prove "For every even number x, 3x is even."

Example

Disprove the conjecture: "For every integer x, 7x is an odd number."

Solution

To disprove this conjecture, we only need to find the counterexample. One of that will do is x=2, then 7x=14 which is even.

Note that x=2 is not the only counterexample that can be found; every integer is a counterexample.

4.2. Proof of correctness

"When we have written a program, how do we check that it is correct?"

A popular suggestion is to run it using test data. If there are synthatic errors, execution will stop in mid-program. If, instead, we can check that an output results is the output corresponding to the test data. But, it is dangerous to conclude that the program will always give the correct results. The test data may have special characteristics which lead to a correct result in that particular case in spite of logical errors which may remaind in the program.

Testing a large number of different input may still not ensure that the program is free of logical errors, for there may be some unnoticed feature common to all those input which leads to a correct result, but which may be not a feature of all possible inputs. The only way to ensure that the program is correct is to prove it.

Logic based programming languages are most suitable for systematic program verification. However, there are widely applicable general principles involved in analysis program correctness. I am going to explore some of them like assignment rule, condition rule and loop rule.

Assertions

Let us denote by x an arbitrary collection of input values to some progrma or program segment P. The actions of P transform x into a corresponding group of output values y.The notation suggests that the y values depend on the x values through the actons of program P.

A predicate describe conditions tha the input values are supposed to satisfy. For example, if a program is supposed to find the square root of a positive number, then x consists of one input value, x, and might be "".

A predicate R describes conditions that the output values are supposed to satisfy. These conditions will often involved the input values as well, so R has the form . In our square root case, if y is the simple output value, then y is supposed to be the square root of x, so R(x,y) would be .

Program P is correct if the application is valid. In other words, whenever Q is true about the input values, R should be true about the input and output values. For the square root case, the above statement is written as .

The implication (1) is called a Hoare Triple, named for the British computer scientist Anthony Hoare. The initial assertion Q and the final assertion R are also called the percondition and postcondition respectively for the program P.

The implcation (1) is a standard predicate formula notation, but the traditional program correctness notation for (1) is: which means that: "If a program P is executed when Q is true, then R will be true immediately after executon." Note that in the Hoare notation, the universal quantifier does not explicitly appear, it is understood.

Rather than simply having an initial predicate and a final predicate, a program or program segment is broken down into individual statements , with predicates inserted between statements as well as at the beginning and end.These predicates are also called assertions because they assert what is supposed to be true about the program variables at that point in the program. Thus we have where are assertions. The intermediate assertions are often obtained by working backward from the output assertion R.

P is provably correct if each of the following implication holds

                                             

A proof of correctness for a program or program segment P consists of producing this sequence of valid implications, that is, producing a proof sequence of predicates formulae.

Assignment rule

Suppose that statements is an assignment statement of the form x=e; that is, the variable x takes on the value of e, where e is some expression. The Hoare triple to prove correctness of this one statement has the form . For this triple to be valid, the assertions must be related in a particular way.

Example

Consider the following assignment statement together with the given precondition and post condition:

For every x, if before the statement is executed, then after the value of x is reduced by 1, it will be the case that . Therefore the given assignment statement is valid.

Condition rule

A conditonal statement is aprogram of the form: If condition B then

When this statement is excuted, a condition B that is either true or false is evaluated. If B is true, program segment is excuted, but if B is false, program segment is excuted.

Example

Verify the correctness of the following program segment with the precondition and postcondition

Here the precondition is n=5, and the condition B to be evaluated is n>=10. To apply the conditional rule, we must prove that

hold.

The first implication is true because its hypothesis is false; the secon is also true by using the assignment rule and working back the postcondition.

Thus, the conditional rule allows us to conclude that the program segment is correct.

Loop rule

Suppose that is a loop statement in the form

where B is a condition that is either true or false and P is a program segment.

When this statement is excuted, condition B is evaluated. If B is true, program segment P is excuted and the B is evaluated again. If B is still true, program segment P is excuted again, then B is evaluated again, and so forth. If condition B is ever evaluated to false, the loop terminate.

The Haore triple form that can be used when is a loop statement imposes a relationship between the precondition and postcondition. The precondition Q holds before the loop is entered; strangely enough, one requrement is that Q must continue to hold after the loop terminates (which means that we should look for a Q that we want to be true when the loop terminate). Such relation Q is called a loop invariant. In addition, the condition for loop termination () must be true as well. Thus, the Hoare triple will have the form .

Example

Consider the following pseudocode function, which is supposed to return the value xy for non negative integers x and y.

This function conditions a loop; the condition B for continued loop execution is "i is not equal to x". The condition fo loop termination is i=x. When the loop terminate it is claimed in the comment that j has the value of xy. Given that i=x when the loop terminates, the assertion that j=ix would also have to be true. Thus on the loop termination, if the function does what is claimed, the assertion is true.

To use the loop rule of inference we must prove that is a loop invariant. The quantifier x and y remain unchanged throughout he function, but values of change within the loop. We let i and j denote the values of i and j respectively after n iterations of the loop. Then is the statement . We prove that holds for all as follows:

is the statement whic is true because after zero iterations of the loop, both i and j have been assigned the value 0.

Assume

We show that

We have:

We have proved that Q is a loop invariant. The loop rule of inference allows us to infer that after the loop statement is exited, the condition holds, which in this case becomes .

Therefore at this point the statement is true, which is exactly what the function is intended to compute.

Notice: The proof done here is called Proof by induction. This will be seen in Sequences and Series.

5. APPLICATION IN SET THEORY

The following table shows how logic and set theory are related.

Consider three statements P, Q and R. Also consider three sets A, B and C

Law
Logic
Set theory
Commutative laws

Associative laws

Distributive laws

Idempotent laws

De Morgan's laws

References

  1. E. Ngezahayo & P. Icyingeneye. Advanced Mathematics for Rwanda Schools Learner's Book 4, Fountain Publishers Ltd, 2016.
  2. Seymour Lipschutz. Schaum’s outline of Theory and Problems of Finite Mathematics. New York, Schaum Publisher, 1966.
 
 

About Us

Contact Us

Terms and Conditions

Privacy Statement

     

© 2020 ICYINGENEYE PACIFIQUE