The electronic textbook on the discrete mathematics. Methodical methods of their use in training in the discrete mathematics

2.1 Instrumental use of the computer – the software and methodical support

Instrumental use of the computer in educational activities for the discrete mathematics is successfully implemented in "model of two teachers" when the teacher of technology informatics works together with the teacher the subject teacher, helping and to it, and pupils to operation with a specific software environment.

But how to select such software products? In the market there is a large number of computer programs in which summary there are words "educational", "educational", etc. It causes bigger trust to them, but doesn't guarantee adequacy to the training program and style of teaching of the specific teacher. Data provided in different directories most often don't reflect existence and the maintenance of methodical materials. As for experience of use of these programs (except 2 — 3 most widespread names), it is separate and difficult generalizable.

Each software product shall be supported methodical both handbooks and educational seminars. Therefore the composition of program and methodical complexes, except compact disks includes educational and methodical literature.

2.2 What is discrete mathematics?

Discrete mathematics is the part of mathematics devoted to the study of discrete objects (Here discrete means consisting of distinct or unconnected elements). More generally, discrete mathematics is used whenever objects are counted, when relationships between finite (or countable) sets are studied, and when processes involving a finite number of steps are analyzed. A key reason for the growth in the importance of discrete mathematics is that information is stored and manipulated by computing machines in a discrete fashion.

There are several important reasons for studying discrete mathematics. First, through this course you can develop your mathematical maturity, that is, your ability to understand and create mathematical arguments. You will not get very far in your studies in the mathematical sciences without these skills. Second, discrete mathematics is the gateway to more advanced courses in all parts of the mathematical sciences. Discrete mathematics provides the mathematical foundations for many computer science courses, including data structures, algorithms, database theory, automata theory, formal languages, compiler theory, computer security, and operating systems. Students find these courses much more difficult when they have not had the appropriate mathematical foundations from discrete math.

2.2.1 Logic

The rules of logic specify the precise meaning of mathematical statements. For instance, the rules give us the meaning of such statements as, “There exists an integer that is greater than 100 that is a power of 2”, and “For every integer n the sum of the positive integers not exceeding n is ”. Logic is the basis of all mathematical reasoning, and it has practical applications to the design of computing machines, to artificial intelligence, to computer programming, to programming languages, and to other areas of computer science.

2.2.2 Propositions

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

Example. All the following statements are propositions.

1. Washington, D.C., is the capital of the United States of America.

2. Toronto is the capital of Canada.

3. 1 + 1 = 2.

4. 2 + 2 = 3.

Propositions 1 and 3 are true, whereas 2 and 4 are false.

Some sentences that are not propositions are given in the next example:

Example. Consider the following sentences:

1. What time is it?

2. Read this carefully.

3. x + 1 = 2.

4. x + y = z.

Sentences 1 and 2 are not propositions because they are not statements. Sentences 3 and 4 are not propositions because they are neither true nor false, since the variables in these sentences have not been assigned values.

Letters are used to denote propositions, just as letters are used to denote variables. The conventional letters used for this purpose are p, q, r, s, … The truth value of a proposition is true, denoted by T, if it is a true proposition and false, denoted by F, if it is a false proposition.

We now turn our attention to methods for producing new propositions from those that we already have. Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators.

Let p be a proposition. The statement “It is not the case that p ” is another proposition, called the negation of p. The negation of p is denoted by Ø p. The proposition Ø p is read “not p ”.

Example. Find the negation of the proposition “Today is Friday”.

Solution: The negation is “It is not the case that today is Friday”. This negation can be more simply expressed by “Today is not Friday”.

A truth table displays the relationships between the truth values of propositions.

Table 1. The truth table for the negation of a proposition
p	Ø p
T F	F T

The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. The negation operator constructs a new proposition from a single existing proposition. We will now introduce the logical operators that are used to form new propositions from two or more existing propositions. These logical operators are also called connectives.

Let p and q be propositions. The proposition “ p and q ”, denoted by , is the proposition that is true when both p and q are true and is false otherwise. The proposition is called the conjunction of p and q.

Example. Find the conjunction of the propositions p and q where p is the proposition “Today is Friday” and q is the proposition “It is raining today”.

Solution: The conjunction of these propositions, , is the proposition “Today is Friday and it is raining today”. This proposition is true on rainy Fridays and is false on any day that is not a Friday and on Fridays when it does not rain.

Table 2. The truth table for the conjunction of two propositions

p	q
T T F F	T F T F	T F F F

Let p and q be propositions. The proposition “ p or q ”, denoted by , is the proposition that is false when p and q are both false and true otherwise. The proposition is called the disjunction of p and q.

Table 3. The truth table for the disjunction of two propositions
p	q
T T F F	T F T F	T T T F

The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, in an inclusive way. A disjunction is true when either of the two propositions in it is true or when both are true. For instance, the inclusive or is being used in the statement “Students who have taken calculus or computer science can take this class”. Here, we mean that students who have taken both calculus and computer science can take the class, as well as the students who have taken just one of the two subjects. On the other hand, we are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this class”. Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class. Similarly, when a menu at a restaurant states, “Soup or salad comes with an entree”, the restaurant almost always means that customers can have either soup or salad, but not both. Hence, this is an exclusive, rather than an inclusive, or.

Example. Find the disjunction of the propositions p and q where p is the proposition “Today is Friday” and q is the proposition “It is raining today”.

Solution: The disjunction of p and q, , is the proposition “Today is Friday or it is raining today”. This proposition is true on any day that is either a Friday or a rainy day (including rainy Fridays). It is only false on days that are not Fridays when it also does not rain.

Sometimes, we use or in an exclusive sense. When the exclusive or is used to connect the propositions p and q, the proposition “ p or q (but not both)” is obtained.

Let p and q be propositions. The exclusive or of p and q, denoted by , is the proposition that is true when exactly one of p and q is true and is false otherwise.

Table 4. The truth table for the exclusive or of two propositions
p	q
T T F F	T F T F	F T T F

Let p and q be propositions. The implication is the proposition that is false when p is true and q is false and true otherwise. In this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

Table 5. The truth table for the implication
p	q
T T F F	T F T F	T F T T

Because implications arise in many places in mathematical reasoning, a wide variety of terminology is used to express . Some of the more common ways of expressing this implication are: “if p, then q ”, “ p implies q ”, “if p, q ”, “ p only if q ”, “ p is sufficient for q ”, “ q if p ”, “ q whenever p ”, “ q is necessary for p ”.

We can build up compound propositions using the negation operator and the different connectives defined so far. Parentheses are used to specify the order in which the various logical operators in a compound proposition are applied. In particular, the logical operators in the innermost parentheses are applied first. For instance, is the conjunction of and . To cut down on the number of parentheses needed, we specify that the negation operator is applied before all other logical operators. This means that is the conjunction of and , namely , not the negation of the conjunction and , namely .

There are some related implications that can be formed from . The proposition is called the converse of . The contrapositive of is the proposition .

2.2.3 Bit operations

Computers represent information using bits. A bit has two possible values, namely, 0 (zero) and 1 (one). This meaning of the word bit comes from binary digit, since zeroes and ones are the digits used in binary representations of numbers. A bit can be used to represent a truth value, since there are two truth values, namely, true and false. We will use a 1 bit to represent true and a 0 bit to represent false. That is, 1 represents T (true), 0 represents F (false). A variable is called a Boolean variable if its value is either true or false. Consequently, a Boolean variable can be represented using a bit.

Table 7. Tables for the bit operations OR, AND and XOR.
x	y

Computer bit operations correspond to the logical connectives. By replacing true by a one and false by a zero in the truth tables for the operators Ù, Ú and Å, the tables shown in Table 7 for the corresponding bit operations are obtained. We will also use the notation OR, AND and XOR for the operators Ù, Ú and Å, as is done in various programming languages.

Information is often represented using bit strings, which are sequences of zeroes and ones. When this is done, operations on the bit strings can be used to manipulate this information.

A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.

Example. 101010011 is a bit string of length nine.

We can extend bit operations to bit strings. We define the bitwise OR, bitwise AND and bitwise XOR of two strings of the same length to be the strings that have as their bits the OR, AND and XOR of the corresponding bits in the two strings, respectively. We use the symbols Ù, Ú and Å to represent the bitwise OR, bitwise AND and bitwise XOR operations respectively.

2.2.4 Propositional Equivalences

An important type of step used in a mathematical argument is the replacement of a statement with another statement with the same truth value. Because of this, methods that produce propositions with the same truth value as a given compound proposition are used extensively in the construction of mathematical arguments.

We begin our discussion with a classification of compound propositions according to their possible truth values.

A compound proposition that is always true, no matter what the truth values of the propositions that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. Finally, a proposition that is neither a tautology nor a contradiction is called a contingency.

Tautologies and contradictions are often important in mathematical reasoning. The following table illustrates examples of a tautology and a contradiction using just one proposition.

Table 1. Examples of a tautology and a contradiction.
T F	F T	T T	F F

2.2.5 Logical Equivalences

Compound propositions that have the same truth values in all possible cases are called logically equivalent. We can also define this notion as follows: The propositions p and q are logically equivalent if is a tautology. The notation denotes that p and q are logically equivalent.

One way to determine whether two propositions are equivalent is to use a truth table. In particular, the propositions p and q are equivalent if and only if the columns giving their truth values agree. The following example illustrates this method.

Example. Show that and are logically equivalent.

Solution: Construct truth tables for each of these propositions.

Table 2. Truth tables for and .

p q
T T T F F T F F	T T T F	F F F T	F F T T	F T F T	F F F T

Since the truth tables of the propositions and agree for all possible combinations of the truth values of p and q, it follows that these propositions are logically equivalent.

Remark. A truth table of a compound proposition involving three different propositions requires eight rows, one for each possible combination of truth values of the three propositions. In general, 2 ⁿ rows are required if a compound proposition involves n propositions.

The following table contains important equivalences. In these equivalences, T denotes any proposition that is always true and F denotes any proposition that is always false.

Table 4. Logical equivalences.
Equivalence	Name
,	Identity laws
,	Domination laws
,	Idempotent laws
	Double negation law
,	Commutative laws
,	Associative laws
,	Distributive laws
,	De Morgan’s laws

We also have the following useful logical equivalences:

, ,

Example. Show that and are logically equivalent.

Solution: We could use a truth table to show that these compound propositions are equivalent. Instead, we will establish this equivalence by developing a series of logical equivalence, using one of the equivalences in Table 4 at a time, starting with and ending with . We have the following equivalences.

from the second De Morgan’s law

from the first De Morgan’s law

from the double negation law

from the distributive law

since

from the commutative law

from the identity law

Consequently, and are logically equivalent.

Example. Show that is a tautology.

Solution: To show that this statement is a tautology, we will use logical equivalences to demonstrate that it is logically equivalent to T.

by the logical equivalence

by the first De Morgan’s law

by the associative and commutative laws for disjunction

by Table 1 and the commutative law for disjunction

by the domination law

2.2.6 Functionally complete collection of logical operators

Theorem. Suppose that a truth table in propositional variables is specified. Then a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is true.

The resulting compound proposition is said to be in disjunctive normal form.

Example. Let the following table be given:

T T F F	T F T F	T F T T

Then by Theorem

A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators.

Corollary. forms a functionally complete collection of logical operators.

2.2.7 Predicates and Quantifiers

Statement involving variables, such as “ x > 3”, “ x = y + 3” and “ x + y = z ”, are often found in mathematical assertions and in computer programs. These statements are neither true nor false when the values of the variables are not specified. Here we will discuss the ways that propositions can be produced from such statements. The statement “ x is greater than 3” has two parts. The first part, the variable x, is the subject of the statement. The second part – the predicate, “is greater than 3” – refers to a property that the subject of the statement can have. We can denote the statement “ x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.

Example. Let P(x) denote the statement “ x > 3”. What are the truth values of P (4) and P (2)?

Solution: The statement P(4) is obtained by setting x = 4 in the statement “ x > 3”. Hence, P(4), which is the statement “4 > 3”, is true. However, P(2), which is the statement “2 > 3”, is false.

In general, a statement involving the n variables x ₁, x ₂, …, x_n can be denoted by P(x ₁, x ₂, …, x_n). A statement of the form P(x ₁, x ₂, …, x_n) is the value of the propositional function P at the n -tuple (x ₁, x ₂, …, x_n), and P is also called a predicate.

2.2.8 Quantifiers

When all the variables in a propositional function are assigned values, the resulting statement has a truth value. However, there is another important way, called quantification, to create a proposition from a propositional function. Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the universe of discourse. Such a statement is expressed using a universal quantification. The universal quantification of a propositional function is the proposition that asserts that P(x) is true for all values of x in the universe of discourse. The universe of discourse specifies the possible values of the variable x.

The universal quantification of P(x) is the proposition “ P(x) is true for all values of x in the universe of discourse”. The notation denotes the universal quantification of P(x). Here " is called the universal quantifier. The proposition is also expressed as “for all x P(x) ” or “for every x P(x) ”.

Example. Express the statement “Every student in this class has studied calculus” as a universal quantification.

Solution: Let P(x) denote the statement “ x has studied calculus”. Then the statement “Every student in this class has studied calculus” can be written as , when the universe of discourse consists of the students in this class.

Many mathematical statements assert that there is an element with a certain property. Such statements are expressed using existential quantification.

The existential quantification of P(x) is the proposition “There exists an element x in the universe of discourse such that P(x) is true”. We use the notation for the existential quantification of P(x). Here $ is called the existential quantifier. The existential quantification is also expressed as “There is an x such that P(x) ”, “There is at least one x such that P(x) ”or “For some x P(x) ”.

The following table summarizes the meaning of the universal and the existential quantifiers:

Statement	When True?	When False?
	P(x) is true for every x.	There is an x for which P(x) is false.
	There is an x for which P(x) is true.	P(x) is false for every x.

Sometimes expressions involving quantifiers can be quite complicated. Translating a complicated expression into English helps understanding of its meaning.

Example. Translate the statement into English, where C(x) is “ x has a computer”, F(x, y) is “ x and y are friends”, and the universe of discourse for both x and y is the set of all students in your school.

Solution: The statement says that for every student x in your school x has a computer or there a student y such that y has a computer and x and y are friends. In other words, every student in your school has a computer or has a friend who has a computer.

The following examples show how to use logical operators and quantifiers to express English sentences.

Example. Express the statements “Some student in this class has visited Mexico” and “Every student in this class has visited either Canada or Mexico” using quantifiers.

Solution: Let the universe of discourse for the variable x be the set of students in your class. Let M(x) be the statement “ x has visited Mexico” and C(x) the statement “ x has visited Canada”. The statement “Some student in this class has visited Mexico” can be written as , The statement “Every student in this class has visited either Canada or Mexico” can be written as

Example. Express the statement “If somebody is female and is a parent, then this person is someone’s mother” as a logical expression.

Solution: Let F(x) be the statement “ x is female”, let P(x) be the statement “ x is a parent”, and let M(x, y) be the statement “ x is the mother of y ”. Since the statement in the example pertains to all people, we can write it symbolically as .

2.2.9 Binding variables

When a quantifier is used on the variable x or when we assign a value to this variable, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free. All the variables that occur in a propositional function must be bound to turn it into a proposition. This can be done using a combination of universal quantifiers, existential quantifiers, and value assignments.

In each of the following examples the universe of discourse for each variable is the set of real numbers.

Example. Let P(x, y) be the statement “ x + y = y + x ”. What is the truth value of the quantification ?

Solution: The quantification denotes the proposition “For all real numbers x and for all real numbers y, it is true that x + y = y + x ”. Since P(x, y) is true for all real numbers x and y, the proposition is true.

Example. Let Q(x, y) denote “ x + y = 0”. What are the truth values of the quantification and ?

Solution: The quantification denotes the proposition “There is a real number y such that for every real number x, Q(x, y) is true”. No matter what value of y is chosen, there is only one value of x for which x + y = 0. Since there is no real number y such that x + y = 0 for all real numbers x, the statement is false.

The quantification denotes the proposition “For every real number x there is a real number y such that Q(x, y) is true”. Given a real number x, there is a real number y such that x + y = 0; namely, y = – x. Hence, the statement is true.

The following table summarizes the meanings of the different possible quantifications involving two variables.

Statement	When True?	When False?
	P(x, y) is true for every pair x, y.	There is a pair x, y for which P(x, y) is false.
	For every x there is a y for which P(x, y) is true.	There is an x such that P(x, y) is false for every y.
	There is an x for which P(x, y) is true for every y.	For every x there is a y for which P(x, y) is false.
	There is a pair x, y for which P(x, y) is true.	P(x, y) is false for every pair x, y.

2.2.10 Negations

We will often want to consider the negation of a quantified expression. For instance, consider the negation of the statement “Every student in the class has taken a course in calculus”. This statement is a universal quantification, namely, , where P(x) is the statement “ x has taken a course in calculus”. The negation of this statement is “It is not the case that every student in the class has taken a course in calculus”. This is equivalent to “There is a student in the class who has not taken a course in calculus”. And this is simply the existential quantification of the negation of the original propositional function, namely, . This example illustrates the following equivalence: . Similarly, we can show that .

Negation	Equivalent statement	When is negation true?	When false?
		P(x) is false for every x. There is an x for which P(x) is false.	There is an x for which P(x) is true. P(x) is true for every x.

2.2.11. Sets

Here we study the fundamental discrete structure upon which all other discrete structures are built, namely, the set. Sets are used to group objects together. Often, the objects in a set have similar properties. For instance, all the students who are currently enrolled in your school make up a set. Likewise, all the students currently taking a course in discrete mathematics at any school make up a set. In addition, those students enrolled in your school who are taking a course in discrete mathematics form a set that can be obtained by taking the elements common to the first two collections. The language of sets is a means to study such collections in an organized fashion.

The objects in a set are also called the elements, or members, of a set. A set is said to contain its elements.

There are several ways to describe a set. One way is to list all the members of a set, when this is possible. We use a notation where all members of the set are listed between braces. For example, the notation { a, b, c, d } represents the set with the four elements a, b, c, d.

Example. The set V of all vowels in the English alphabet can be written as V = { a, e, i, o, u }.

Uppercase letters are usually used to denote sets. The letters N, Z and R will be reserved to represent the set of natural numbers {0, 1, 2, 3, …}, the set of integers {…, –2, –1, 0, 1, 2, …} and the set of real numbers respectively.

Two sets are equal if and only if they have the same elements.

Example. The sets {1, 3, 5} and {3, 5, 1} are equal, since they have the same elements. Note that the order in which the elements of a set are listed does not matter.

Another way to describe a set is to use set builder notation. We characterize all those elements in the set by stating the property or properties they must have to be members. For instance, the set O of all odd positive integers less than 10 can be written as O = { x | x is an odd positive integer less than 10}.

We often use this type of notation to describe sets when it is impossible to list all the elements of the set. For example, the set of all real numbers can be written as R = { x | x is a real number}.

Sets can also be represented graphically using Venn diagrams, named after the English mathematician John Venn, who introduced their use in 1881. In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle. Inside this rectangle, circles or other geometrical figures are used to represent sets. Sometimes points are used to represent the particular elements of the set. Venn diagrams are often used to indicate the relationships between sets.

We will now introduce notation used to describe membership in sets. We write to denote that a is an element of the set A. The notation denotes that a is not a member of the set A. Note that lowercase letters are usually used to denote elements of sets.

There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by Æ. Often, a set of elements with certain properties turns out to be the null set. For instance, the set of all positive integers that are greater than their squares is the null set.

The set A is said to be a subset of B if and only if every element of A is also an element of B. We use the notation to indicate that A is a subset of B.

The null set is a subset of every set, that is, whenever S is a set. Furthermore, note that every set is a subset of itself, that is, whenever S is a set.

When we wish to emphasize that a set A is a subset of the set B but that , we write and say that A is a proper subset of B.

One way to show that two sets have the same elements is to show that each set is a subset of the other. In other words, we can show that if A and B are sets with and , then A = B.

Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by | S |.

Example. Let A be the set of odd positive integers less than 10. Then | A | = 5.

Example. Since the null set has no elements, it follows that |Æ| = 0.

A set is said to be infinite if it is not finite. For example, the set of positive integers is infinite.

2.2.12 Cartesian products

The order of elements in a collection is often important. Since sets are unordered, a different structure is needed to represent ordered collections. This is provided by ordered n-tuples.

The ordered n-tuple is the ordered collection that has a ₁ as its first element, a ₂ as its second element, …, and a_n as its n ^th element.

We say that two ordered n -tuples are equal if and only if each corresponding pair of their elements is equal. In other words, if and only if for i = 1, 2, …, n. In particular, 2-tuples are called ordered pairs. The ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d. Note that (a, b) and (b, a) are not equal unless a = b.

Let A and B be sets. The Cartesian product of A and B, denoted by , is the set of all ordered pairs (a, b) where and . Hence, .

Example. What is the Cartesian product of A = {1, 2} and B = {a, b, c}?

Solution: The Cartesian product is

The Cartesian products and are not equal, unless A = Æ or B = Æ or unless A = B.

The Cartesian product of the sets A ₁, A ₂, …, A_n, denoted by , is the set of ordered n -tuples , where a_i belongs to A_i for i =1, 2, …, n. In other words,

for i =1, 2, …, n }.

2.2.13 Set operations

Let A and B be sets. The union of the sets A and B, denoted by , is the set that contains those elements that are either in A or in B, or in both. Thus, .

Example. Find the union of the sets {1, 3, 5} and {1, 2, 3}. Solution:

Let A and B be sets. The intersection of the sets A and B, denoted by , is the set containing those elements in both A and B. Thus, .

Example. Find the intersection of the sets {1, 3, 5} and {1, 2, 3}. Solution:

Two sets are called disjoint if their intersection is the empty set.

Example. Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Since , A and B are disjoint.

Let A and B be sets. The difference of the sets A and B, denoted by , is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A. Thus, .

Example. The difference of {1, 3, 5} and {1, 2, 3} is the set {5}. This is different from the difference of {1, 2, 3} and {1, 3, 5}, which is the set {2}.

Once the universal set U has been specified, the complement of a set can be defined.

Let U be the universal set. The complement of the set A, denoted by , is the complement of A with respect to U. In other words, the complement of the set A is . Thus, .

Example. Let A = {a, e, i, o, u} (where the universal set is the set of letters of the English alphabet). Then .

2.2.14 Set identities

Identity	Name
	Identity laws
	Domination laws
	Idempotent laws
	Complementation law
	Commutative laws
	Associative laws
	Distributive laws
	De Morgan’s laws

Example. Prove that by showing that each set is a subset of the other.

Solution: First, suppose that . It follows that . This implies that or . Hence, or . Thus, . This shows that .

Now suppose that . Then or . It follows that or . Hence, . Therefore, . This demonstrates that . Since we have demonstrated that each set is a subset of the other, these two sets must be equal and the identity is proved.

Another way to verify set identities is to use set builder notation and the rules of logic.

Functions

Let A and B be sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write .

If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f(a) = b, we say that b is the image of a and a is a pre-image of b. The range of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B.

Example. Let f be the function that assigns the last two bits of a bit string of length 2 or greater to that string. Then, the domain of f is the set of all bit strings of length 2 or greater, and both the codomain and range are the set {00, 01, 10, 11}.

Let f ₁ and f ₂ be functions from A to R. Then and are also functions from A to R defined by

2.3.1 One-to one and onto functions

Some functions have distinct images at distinct members of their domain. These functions are said to be one-to-one.

A function f is said to be one-to-one, or injective, iff implies that x = y for all x and y in the domain of f. A function f is said to be an injection if it is one-to-one.

Remark. A function f is one-to-one iff whenever .

Example. Determine whether the function from the set of integers to the set of integers is one-to-one.

Solution: The function is not one-to-one because, for instance, , but .

2.3.2 Inverse functions and compositions of functions

Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that . The inverse function of f is denoted by . Hence, when .

If a function f is not a one-to-one correspondence, we cannot define an inverse function of f.

A one-to-one correspondence is called invertible since we can define an inverse of this function. A function is not invertible if it is not a one-to-one correspondence, since the inverse of such a function does not exist.

Example. Let f be the function from the set of integers to the set of integers such that . Is f invertible, and if it is, what is its inverse?

Solution: The function f has an inverse since it is a one-to-one correspondence, as we have shown. To reverse the correspondence, suppose that y is the image of x, so that . Then . This means that is the unique element of Z that is sent to y by f. Consequently, .

Example. Let f be the function from Z to Z with . Is f invertible?

Solution: Since , f is not one-to-one. If an inverse function were defined, it would have to assign two elements to 1. Hence, f is not invertible.

Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted by , is defined by .

Example. Let g be the function from the set { a, b, c } to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the function from the set { a, b, c } to the set {1, 2, 3} such that f(a) = 3, f(b) = 2, and f(c) = 1. What is the composition of f and g, and what is the composition of g and f?

Solution: The composition is defined by ,

, and .

Note that is not defined, because the range of f is not a subset of the domain of g.

2.3.3 Methods of proof

Two important questions that arise in the study of mathematics are:

(1) When is a mathematical argument correct?

(2) What methods can be used to construct mathematical arguments?

This section helps answer these questions by describing various forms of correct and incorrect mathematical arguments.

A theorem is a statement that can be shown to be true. We demonstrate that a theorem is true with a sequence of statements that form an argument, called a proof. To construct proofs, methods are needed to derive new statements from old ones. The statements used in a proof can include axioms or postulates, which are the underlying assumptions about mathematical structures, the hypotheses of the theorem to be proved, and previously proved theorems. The rules of inference, which are the means used to draw conclusions from other assertions, tie together the steps of a proof.

Дата добавления: 2015-11-16