Discrete Mathematics for CS in Arabic - الرياضيات المتقطعة

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0, respectively. Instead of elementary algebra, where the values of the variables are numbers and the prime operations are addition and multiplication, the main operations of Boolean algebra are the conjunction (and) denoted as ∧, the disjunction (or) denoted as ∨, and the negation (not) denoted as ¬. It is thus a formalism for describing logical operations, in the same way, that elementary algebra describes numerical operations.

Boolean algebra was introduced by George Boole in his first book The Mathematical Analysis of Logic (1847) and set forth more fully in his An Investigation of the Laws of Thought (1854).[3] According to Huntington, the term "Boolean algebra" was first suggested by Sheffer in 1913, although Charles Sanders Peirce gave the title "A Boolean Algebra with One Constant" to the first chapter of his "The Simplest Mathematics" in 1880. Boolean algebra has been fundamental in the development of digital electronics and is provided for in all modern programming languages. It is also used in set theory and statistics.

A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. Example − The relation R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)} on set A={1,2,3} is an equivalence relation since it is reflexive, symmetric, and transitive.

Definition and Properties

A binary relation R from set x to y (written as xRyxRy or R(x,y)R(x,y)) is a subset of the Cartesian product x×yx×y. If the ordered pair of G is reversed, the relation also changes.

Generally an n-ary relation R between sets A1,…, and AnA1,…, and An is a subset of the n-ary product A1×⋯×AnA1×⋯×An. The minimum cardinality of a relation R is Zero and maximum is n2n2 in this case.

A binary relation R on a single set A is a subset of A×AA×A.

For two distinct sets, A and B, having cardinalities m and n respectively, the maximum cardinality of a relation R from A to B is mn.

Domain and Range

If there are two sets A and B, and relation R have order pair (x, y), then −

• The domain of R, Dom(R), is the set {x|(x,y)∈RforsomeyinB}{x|(x,y)∈RforsomeyinB}

• The range of R, Ran(R), is the set {y|(x,y)∈RforsomexinA}{y|(x,y)∈RforsomexinA}

Examples

Let, A={1,2,9}A={1,2,9} and B={1,3,7}B={1,3,7}

• Case 1 − If relation R is 'equal to' then R={(1,1),(3,3)}R={(1,1),(3,3)}

  Dom(R) = {1,3},Ran(R)={1,3}{1,3},Ran(R)={1,3}

• Case 2 − If relation R is 'less than' then R={(1,3),(1,7),(2,3),(2,7)}R={(1,3),(1,7),(2,3),(2,7)}

  Dom(R) = {1,2},Ran(R)={3,7}{1,2},Ran(R)={3,7}

• Case 3 − If relation R is 'greater than' then R={(2,1),(9,1),(9,3),(9,7)}R={(2,1),(9,1),(9,3),(9,7)}

  Dom(R) = {2,9},Ran(R)={1,3,7}

Relation or Binary relation R from set A to B is a subset of AxB which can be defined as
aRb ↔ (a,b) € R ↔ R(a,b).
A Binary relation R on a single set A is defined as a subset of AxA. For two distinct set, A and B with cardinalities m and n, the maximum cardinality of the relation R from A to B is mn.

Domain and Range:
if there are two sets A and B and Relation from A to B is R(a,b), then domain is defined as the set { a | (a,b) € R for some b in B} and Range is defined as the set {b | (a,b) € R for some a in A}.

Types of Relation:

1. Empty Relation: A relation R on a set A is called Empty if the set A is empty set.

2. Full Relation: A binary relation R on a set A and B is called full if AXB.

3. Reflexive Relation: A relation R on a set A is called reflexive if (a,a) € R holds for every element a € A .i.e. if set A = {a,b} then R = {(a,a), (b,b)} is reflexive relation.

4. Irreflexive relation : A relation R on a set A is called reflexive if no (a,a) € R holds for every element a € A.i.e. if set A = {a,b} then R = {(a,b), (b,a)} is irreflexive relation.

5. Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.i.e. The relation R={(4,5),(5,4),(6,5),(5,6)} on set A={4,5,6} is symmetric.

6. AntiSymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.i.e. The relation R = {(a,b)→ R|a ≤ b} is anti-symmetric since a ≤ b and b ≤ a implies a = b.

7. Transitive Relation: A relation R on a set A is called transitive if (a,b) € R and (b,c) € R then (a,c) € R for all a,b,c € A.i.e. Relation R={(1,2),(2,3),(1,3)} on set A={1,2,3} is transitive.

8. Equivalence Relation: A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. i.e. relation R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)} on set A={1,2,3} is equivalence relation as it is reflexive, symmetric, and transitive.

9. Asymmetric relation: Asymmetric relation is opposite of symmetric relation. A relation R on a set A is called asymmetric if no (b,a) € R when (a,b) € R.

   
   
   Important Points:
   1. Symmetric and anti-symmetric relations are not opposite because a relation R can contain both the properties or may not.
   2. A relation is asymmetric if and only if it is both anti-symmetric and irreflexive.
   3. Number of different relation from a set with n elements to a set with m elements is 2mn

   Ex:

        if R ={r1, r2, r3......rn} and S ={s1, s2, s3.....sm}

        then Cartesian product of R and S is:

         R X S = {(r1, s1), (r1, s2), (r1, s3)........., (r1, sn),

                  (r2, s1), (r2, s2), (r2, s3).........., (r2, sn),

                   .................

                  (rn, s1),(rn, s2), (rn, s3),........., (rn, sn)}

   This set of ordered pairs contains mn pairs.

   Now these pairs can be present in R X S or can be absent.

   So total number of possible relation = 2mn

   
   

   4. Number of Reflexive Relations on a set with n elements : 2n(n-1).

   A relation has ordered pairs (a,b). Now a can be chosen in n ways and same for b. So set of ordered pairs contains n2 pairs. Now for a reflexive relation, (a,a) must be present in these ordered pairs. And there will be total n pairs of (a,a), so number of ordered pairs will be n2-n pairs. So total number of reflexive relations is equal to 2n(n-1).

   5. Number of Symmetric Relations on a set with n elements : 2n(n+1)/2.

   
   
   

   A relation has ordered pairs (a,b). Now for a symmetric relation, if (a,b) is present in R, then (b,a) must be present in R.
   In Matrix form, if a12 is present in relation, then a21 is also present in relation and As we know reflexive relation is part of symmetric relation.
   So from total n2 pairs, only n(n+1)/2 pairs will be chosen for symmetric relation. So total number of symmetric relation will be 2n(n+1)/2.

   6. Number of Anti-Symmetric Relations on a set with n elements: 2n 3n(n-1)/2.

   A relation has ordered pairs (a,b). For anti-symmetric relation, if (a,b) and (b,a) is present in relation R, then a = b.(That means a is in relation with itself for any a).
   So for (a,a), total number of ordered pairs = n and total number of relation = 2n.

   if (a,b) and (b,a) both are not present in relation or Either (a,b) or (b,a) is not present in relation. So there are three possibilities and total number of ordered pairs for this condition is n(n-1)/2. (selecting a pair is same as selecting the two numbers from n without repetition) As we have to find number of ordered pairs where a ≠ b. it is like opposite of symmetric relation means total number of ordered pairs = (n2) – symmetric ordered pairs(n(n+1)/2) = n(n-1)/2. So, total number of relation is 3n(n-1)/2. So total number of anti-symmetric relation is 2n.3n(n-1)/2.

   7. Number of Asymmetric Relations on a set with n elements : 3n(n-1)/2.

   In Asymmetric Relations, element a can not be in relation with itself. (i.e. there is no aRa ∀ a∈A relation.) And Then it is same as Anti-Symmetric Relations.(i.e. you have three choice for pairs (a,b) (b,a)). Therefore there are 3n(n-1)/2 Asymmetric Relations possible.

   8. Irreflexive Relations on a set with n elements : 2n(n-1).

   A relation has ordered pairs (a,b). For Irreflexive relation, no (a,a) holds for every element a in R. It is also opposite of reflexive relation.
   Now for a Irreflexive relation, (a,a) must not be present in these ordered pairs means total n pairs of (a,a) is not present in R, So number of ordered pairs will be n2-n pairs.
   So total number of reflexive relations is equal to 2n(n-1).

   9. Reflexive and symmetric Relations on a set with n elements : 2n(n-1)/2.

   A relation has ordered pairs (a,b). Reflexive and symmetric Relations means (a,a) is included in R and (a,b)(b,a) pairs can be included or not. (In Symmetric relation for pair (a,b)(b,a) (considered as a pair). whether it is included in relation or not) So total number of Reflexive and symmetric Relations is 2n(n-1)/2 .
   

Logic is an interdisciplinary field that studies truth and reasoning. Informal logic seeks to characterize valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and argument patterns symbolically, using formal systems such as first-order logic. Within formal logic, mathematical logic studies the mathematical characteristics of logical systems, while philosophical logic applies them to philosophical problems such as the nature of meaning, knowledge, and existence. Systems of formal logic are also applied in other fields including linguistics, cognitive science, and computer science.

Logic has been studied since Antiquity, early approaches including Aristotelian logic, stoic logic, Anviksiki, and the Mohists. Modern formal logic has its roots in the work of late 19th-century mathematicians such as Gottlob Frege.

Predicate (mathematical logic)

In logic, a predicate is a symbol which represents a property or a relation. For instance, the first order formula {\displaystyle P(a)}, the symbol {\displaystyle P} is a predicate which applies to the individual constant {\displaystyle a}. Similarly, in the formula {\displaystyle R(a,b)} the predicate {\displaystyle R} is a predicate which applies to the individual constants {\displaystyle a} and {\displaystyle b}.

In the semantics of logic, predicates are interpreted as relations. For instance, in a standard semantics for first-order logic, the formula {\displaystyle R(a,b)} would be true on an interpretation of the entities denoted by {\displaystyle a} and {\displaystyle b} stand in the relation denoted by {\displaystyle R}. Since predicates are non-logical symbols, they can denote different relations depending on the interpretation used to interpret them. While first-order logic only includes predicates that apply to individual constants, other logics may allow predicates that apply to other predicates.

---------------------------

Propositional Function

The expression

x>5(2.7.1)(2.7.1)x>5

is neither true nor false. In fact, we cannot even determine its truth value unless we know the value of xx. This is an example of a propositional function, because it behaves like a function of xx, it becomes a proposition when a specific value is assigned to xx. Propositional functions are also called predicates.

Example 2.7.12.7.1

Denote the propositional function “x>5x>5” by p(x)p(x). We often write

p(x):x>5.(2.7.2)(2.7.2)p(x):x>5.

It is not a proposition because its truth value is undecidable, but p(6)p(6), p(3)p(3) and p(−1)p(−1) are propositions.

Example 2.7.22.7.2

Define

q(x,y):x+y=1.(2.7.3)(2.7.3)q(x,y):x+y=1.

Which of the following are propositions; which are not?

1. q(x,y)q(x,y)

2. q(x,3)q(x,3)

3. q(1,1)q(1,1)

4. q(5,−4)q(5,−4)

For those that are, determine their truth values.

Answer

hands-on Exercise 2.7.12.7.1

Determine the truth values of these statements, where q(x,y)q(x,y) is defined in Example 2.7.22.7.2.

1. q(5,−7)q(5,−7)

2. q(−6,7)q(−6,7)

3. q(x+1,−x)q(x+1,−x)

Although a propositional function is not a proposition, we can form a proposition by means of quantification. The idea is to specify whether the propositional function is true for all or for some values that the underlying variables can take on.

Universal Quantifier

Definition

The universal quantification of p(x)p(x) is the proposition in any of the following forms:

• p(x)p(x) is true for all values of xx.

• For all xx, p(x)p(x).

• For each xx, p(x)p(x).

• For every xx, p(x)p(x).

• Given any xx, p(x)p(x).

All of them are symbolically denoted by

∀xp(x),(2.7.4)(2.7.4)∀xp(x),

which is pronounced as

“for all xx, p(x)p(x)”.

The symbol ∀∀ is called the universal quantifier, and can be extended to several variables.

Example 2.7.32.7.3

The statement

“For any real number xx, we always have x2≥0x2≥0”

is true. Symbolically, we can write

∀x∈R(x2≥0),or∀x(x∈R⇒x2≥0).(2.7.5)(2.7.5)∀x∈R(x2≥0),or∀x(x∈R⇒x2≥0).

The second form is a bit wordy, but could be useful in some situations.

Example 2.7.42.7.4

The statement

∀x∈R(x>5)(2.7.6)(2.7.6)∀x∈R(x>5)

is false because xx is not always greater than 5. To disprove a claim, it suffices to provide only one counterexample. We can use x=4x=4 as a counterexample.

However, examples cannot be used to prove a universally quantified statement. Consider the statement

∀x∈R(x2≥0).(2.7.7)(2.7.7)∀x∈R(x2≥0).

By direct calculations, one may demonstrate that x2≥0x2≥0 is true for many xx-values. But it does not prove that it is true for every xx, because there may be a counterexample that we have not found yet. We have to use mathematical and logical argument to prove a statement of the form “∀xp(x)∀xp(x).”

Example 2.7.52.7.5

The statement

“Every Discrete Mathematics student has taken Calculus I and Calculus II”

is clearly a universally quantified proposition. To express it in a logical formula, we can use an implication:

∀x(x is a Discrete Mathematics student⇒x has taken Calculus I and Calculus II)(2.7.8)(2.7.8)∀x(x is a Discrete Mathematics student⇒x has taken Calculus I and Calculus II)

An alternative is to say∀x∈S(x has taken Calculus I and Calculus II)(2.7.9)(2.7.9)∀x∈S(x has taken Calculus I and Calculus II)where SS represents the set of all Discrete Mathematics students. Although the second form looks simpler, we must define what SS stands for.

Existential Quantifier

Definition

The existential quantification of p(x)p(x) takes one of these forms:

• There exists an xx such that p(x)p(x).

• For some xx, p(x)p(x).

• There is some xx such that p(x)p(x).

We write, in symbol,

∃xp(x),(2.7.10)(2.7.10)∃xp(x),

which is pronounced as

“There exists xx such that p(x)p(x).”

The symbol ∃∃ is called the existential quantifier. It can be extended to several variables.

Notice the pronouciation includes the phrase "such that". Don't forget to say that phrase as part of the verbalization of a symbolic existential statement.

Example 2.7.62.7.6

To prove that a statement of the form “∃xp(x)∃xp(x)” is true, it suffices to find an example of xx such that p(x)p(x) is true. Using this guideline, can you determine whether these two propositions

1. ∃x∈R(x>5)∃x∈R(x>5)

2. ∃x∈R(x−−√=0)∃x∈R(x=0)

are true?

Answer

Example 2.7.72.7.7

The proposition

“There exists a prime number xx such that x+2x+2 is also prime”

is true. We call such a pair of primes twin primes.

hands-on Exercise 2.7.22.7.2

Name a few more examples of twin primes.

Example 2.7.82.7.8

The proposition

“There exists a real number xx such that x>5x>5”

can be expressed, symbolically, as

∃x∈R(x>5),or∃x(x∈R∧x>5).(2.7.11)(2.7.11)∃x∈R(x>5),or∃x(x∈R∧x>5).

Notice that in an existential quantification, we use ∧∧ instead of ⇒⇒ to specify that xx is a real number.

hands-on Exercise 2.7.32.7.3

Determine the truth value of each of the following propositions:

1. For any prime number xx, the number x+1x+1 is composite.

2. For any prime number x>2x>2, the number x+1x+1 is composite.

3. There exists an integer kk such that 2k+12k+1 is even.

4. For all integers kk, the integer 2k2k is even.

5. For any real number xx, if x2x2 is an integer, then xx is also an integer.

hands-on Exercise 2.7.42.7.4

The proposition

“The square of any real number is positive”

is a universal quantification

“For any real number xx, x2>0x2>0.”

Is it true or false?

Negation with Quantifiers

To negate that a proposition always happens, is to say there exists an instance where it does not happen.

To negate that a proposition exists, is to say the proposition always does not happen.

Symbolically:

∀xP(x)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯≡∃xP(x)¯¯¯¯¯¯¯¯¯¯∀xP(x)¯≡∃xP(x)¯

and

∃xP(x)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯≡∀xP(x)¯¯¯¯¯¯¯¯¯¯∃xP(x)¯≡∀xP(x)¯

hands-on Exercise 2.7.52.7.5

Negate the propositions in Hands-On Exercise 2.7.32.7.3

Example 2.7.92.7.9

The statement

“All real numbers xx satisfy x2≥0x2≥0”

can be written as, symbolically, ∀x∈R(x2≥0)∀x∈R(x2≥0). Its negation is ∃x∈R(x2<0)∃x∈R(x2<0). In words, it says “There exists a real number xx that satisfies x2<0x2<0.”

Every Theorem in Mathematics, or any subject for that matter, is supported by underlying proofs. These proofs are nothing but a set of arguments that are conclusive evidence of the validity of the theory.
The arguments are chained together using Rules of Inferences to deduce new statements and ultimately prove that the theorem is valid.

Important Definitions :

1. Argument – A sequence of statements, premises, that end with a conclusion.
2. Validity – A deductive argument is said to be valid if and only if it takes a form that makes it impossible for the premises to be true and the conclusion nevertheless to be false.
3. Fallacy – An incorrect reasoning or mistake which leads to invalid arguments.

Structure of an Argument :
As defined, an argument is a sequence of statements called premises which end with a conclusion.

Rules of Inference

• If we have an implication tautology that we'd like to use to prove a conclusion, we can write the rule like this:p→qp∴q

  • This corresponds to the tautology ((p→q)∧p)→q.

  • The ∴ symbol is therefore.

  • The first two lines are premises.

  • The last is the conclusion.

  • This inference rule is called modus ponens (or the law of detachment).

• Here are the rules of inference that we can use to build arguments:NameRuleModus ponenspp→q∴qModus tollens¬qp→q∴¬pHypothetical syllogismp→qq→r∴p→rDisjunctive syllogismp∨q¬p∴qAdditionp∴p∨qSimplificationp∧q∴pConjunctionpq∴p∧qResolutionp∨q¬p∨r∴q∨r

• Using these rules by themselves, we can do some very boring (but correct) proofs.

• e.g. “If I am sick, there will be no lecture today;” “either there will be a lecture today, or all the students will be happy;” “the students are not happy.”

  • Translate into logic as: s→¬l, l∨h, ¬h.

  • Then we can reach a conclusion as follows:

    1. l∨h [hypothesis]

    2. ¬h [hypothesis]

    3. l [disjunctive syllogism using (1) and (2)]

    4. s→¬l [hypothesis]

    5. ¬s [modus tollens using (3) and (4)]

  • So, I am not sick.

  • Notice a similar proof style to equivalences: one piece of logic per line, with the reason stated clearly.

In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called elements, or terms). The number of elements (possibly infinite) is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers (the positions of elements in the sequence) to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an index set that may not be numbers to another set of elements.

For example, (M, A, R, Y) is a sequence of letters with the letter 'M' first and 'Y' last. This sequence differs from (A, R, M, Y). Also, the sequence (1, 1, 2, 3, 5, 8), which contains the number 1 at two different positions, is a valid sequence. Sequences can be finite, as in these examples, or infinite, such as the sequence of all even positive integers (2, 4, 6, ...).

The position of an element in a sequence is its rank or index; it is the natural number for which the element is the image. The first element has index 0 or 1, depending on the context or a specific convention. In mathematical analysis, a sequence is often denoted by letters in the form of {\displaystyle a_{n}}, {\displaystyle b_{n}} and {\displaystyle c_{n}}, where the subscript n refers to the nth element of the sequence;[1] for example, the nth element of the Fibonacci sequence {\displaystyle F} is generally denoted as {\displaystyle F_{n}}.

In computing and computer science, finite sequences are sometimes called strings, words or lists, the different names commonly corresponding to different ways to represent them in computer memory; infinite sequences are called streams. The empty sequence ( ) is included in most notions of sequence, but may be excluded depending on the context.

In mathematics, summation is the addition of a sequence of any kind of numbers, called addends or summands; the result is their sum or total. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, polynomials and, in general, elements of any type of mathematical objects on which an operation denoted "+" is defined.

Summations of infinite sequences are called series. They involve the concept of limit, and are not considered in this article.

The summation of an explicit sequence is denoted as a succession of additions. For example, summation of [1, 2, 4, 2] is denoted 1 + 2 + 4 + 2, and results in 9, that is, 1 + 2 + 4 + 2 = 9. Because addition is associative and commutative, there is no need of parentheses, and the result is the same irrespective of the order of the summands. Summation of a sequence of only one element results in this element itself. Summation of an empty sequence (a sequence with no elements), by convention, results in 0.

A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms,[2][3][4] along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation". Presenting many cases in which the statement holds is not enough for a proof, which must demonstrate that the statement is true in all possible cases. An unproven proposition that is believed to be true is known as a conjecture, or a hypothesis if frequently used as an assumption for further mathematical work.[5]

Proofs employ logic expressed in mathematical symbols, along with natural language which usually admits some ambiguity. In most mathematical literature, proofs are written in terms of rigorous informal logic. Purely formal proofs, written fully in symbolic language without the involvement of natural language, are considered in proof theory. The distinction between formal and informal proofs has led to much examination of current and historical mathematical practice, quasi-empiricism in mathematics, and so-called folk mathematics, oral traditions in the mainstream mathematical community or in other cultures. The philosophy of mathematics is concerned with the role of language and logic in proofs, and mathematics as a language.

Methods of proof

1. Direct proof.

2. Proof by mathematical induction.

3. Proof by contraposition.

4. Proof by contradiction.

5. Proof by construction.

6. Proof by exhaustion.

7. Probabilistic proof.

8. Combinatorial proof.

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

— Concrete Mathematics, page 3 margins.

A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n.[3] The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and in some form is the foundation of all correctness proofs for computer programs.[4]

Although its name may suggest otherwise, mathematical induction should not be confused with inductive reasoning as used in philosophy (see Problem of induction). The mathematical method examines infinitely many cases to prove a general statement, but does so by a finite chain of deductive reasoning involving the variable n, which can take infinitely many values.

Recursion

Recursion means "defining a problem in terms of itself". This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

For example, we can define the operation "find your way home" as:

1. If you are at home, stop moving.

2. Take one step toward home.

3. "find your way home".

Here the solution to finding your way home is two steps (three steps). First, we don't go home if we are already home. Secondly, we do a very simple action that makes our situation simpler to solve. Finally, we redo the entire algorithm.

The above example is called tail recursion. This is where the very last statement is calling the recursive algorithm. Tail recursion can directly be translated into loops.

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ (listen)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems or to perform a computation.[1][2] Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. In contrast, a heuristic is a technique used in problem solving that uses practical methods and/or various estimates in order to produce solutions that may not be optimal but are sufficient given the circumstances.[3] [4]

As an effective method, an algorithm can be expressed within a finite amount of space and time,[5] and in a well-defined formal language[6] for calculating a function.[7] Starting from an initial state and initial input (perhaps empty),[8] the instructions describe a computation that, when executed, proceeds through a finite[9] number of well-defined successive states, eventually producing "output"[10] and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.[11]

The concept of algorithm has existed since antiquity. Arithmetic algorithms, such as a division algorithm, were used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC.[12] Greek mathematicians later used algorithms in 240 BC in the sieve of Eratosthenes for finding prime numbers,[13] and the Euclidean algorithm for finding the greatest common divisor of two numbers.[14] Arabic mathematicians such as al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.[15]

The word algorithm itself is derived from the name of the 9th-century mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose nisba (identifying him as from Khwarazm) was Latinized as Algoritmi.[16] A partial formalization of the modern concept of algorithm began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert in 1928. Later formalizations were framed as attempts to define "effective calculability"[17] or "effective method".[18] Those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's Formulation 1 of 1936, and Alan Turing's Turing machines of 1936–37 and 1939.

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.[1] Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.[2]

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

— Niklaus Wirth, Algorithms + Data Structures = Programs, 1976[3]

Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure)[4] do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for.

Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization.

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics."[1][note 1] Number theorists study prime numbers as well as the properties of mathematical objects made out of integers (for example, rational numbers) or defined as generalizations of the integers (for example, algebraic integers).

Integers can be considered either in themselves or as solutions to equations (Diophantine geometry). Questions in number theory are often best understood through the study of analytical objects (for example, the Riemann zeta function) that encode properties of the integers, primes or other number-theoretic objects in some fashion (analytic number theory). One may also study real numbers in relation to rational numbers, for example, as approximated by the latter (Diophantine approximation).

The older term for number theory is arithmetic. By the early twentieth century, it had been superseded by "number theory".[note 2] (The word "arithmetic" is used by the general public to mean "elementary calculations"; it has also acquired other meanings in mathematical logic, as in Peano arithmetic, and computer science, as in floating-point arithmetic.) The use of the term arithmetic for number theory regained some ground in the second half of the 20th century, arguably in part due to French influence.[note 3] In particular, arithmetical is commonly referred as an adjective to number-theoretic