Comprehesive knowledge on computing and information technology
Amazing
AUTOMATATHEORY
Recursive Definitions
Set Definition
- A precise definition aids in carrying out proof
- A concise definition assists understanding
- Recursive definitions are precise and concise
- Recursive definitions are self-referential
A recursive definition is a three-step process:
- Define basic set members
- Give rules for constructing more set members from the ones already known
- Exclude all set members except those created by the first two steps
Examples of Recursive Definitions
The set EVEN is defined recursively as follows:
- Rule 1: 2 is in EVEN
- Rule 2: If x is in EVEN, then x+2 is in EVEN
- Rule 3: Only elements defined by rules above are in EVEN 1 and 2
The last rule is called an EXCLUSION RULE (it prevents members from sneaking into a set by unknown means, and it is tacitly presumed in recursive definitions.)
Definition of Set EVEN
How else can the set EVEN be defined recursively?
- Rule 1: 2 is in EVEN
- Rule 2: If x is in EVEN, then x+2 is in EVEN
- Rule 3: If x is even (x+1)*2 is even
- Rule 4: Only elements defined by rules above are in EVEN
Definition aides Proof
Supposing you want to prove that the sum of any two numbers in EVEN is also in EVEN, which definition would best serve your purpose?
Supposing you want to prove that the product of any two numbers in EVEN is also in EVEN, which definition would best serve your purpose?
Recap
A recursive definition is better than another if it produces shorter proofs for set membership.
Set EVEN has fine definitions that are non recursive later in the course, we shall be interested in certain sets that have no better definition than the recursive one
The choice of whether or not to use a recursive definition depends on:
- How easy is it to understand the other possible definitions?
- What types of theorems do we wish to prove about the set?
Example – Set of Integers
Following is a recursive definition of the positive integers:
- Rule I: 1 is in INTEGERS.
- Rule II: If x is in INTEGERS, then so is x + 1.
How would you define INTEGERS to include both positive and negative integers?
Example – Set POLYNOMIAL
Definition of the set POLYNOMIAL :
- Rule 1: Any natural number is in POLYNOMIAL
- Rule 2: The variable x is in POLYNOMIAL
- Rule 3: If p and q are in POLYNOMIAL then so are p + q, p-q, (p) and (pq)
- Rule 4: Exclusion rule
Set POLYNOMIAL
Use the definition of POLYNOMIAL to prove that is in 3x - 2 is in POLYNOMIAL
Use the definition of POLYNOMIAL to prove that 4x + 2x -6 is in POLYNOMIAL
The Power of Recursive Definitions
Suppose in a calculus class we prove that:
- the derivative of the sum of two functions is the sum of the derivatives
- And that the derivative of the product fg is f’g + fg’
- And that the derivative of a number is always 0
- And that the derivative of x is 1
Using the recursive definition of POLYNOMIAL and these proofs it is now a trivial exercise to show that all POLYNOMIALS can be differentiated, how?
We don’t yet know the most efficient alg orithm for doing this but we know that it can be done.
The Power of Recursive Definitions
Perhaps even more importantly recursive definitions can be used to show that certain tasks are theoretically impossible for any computer to perform…
But that is beyond the scope of this course…
Recursion in the Real World
Rule 1: The children of MOI are all elements of the set DESCENDANTS
Rule 2: if x is an element of DESCENDANTS then so are x’s children.
Recursion in Mathematics
Definition of set FACTORIAL:
Rule 1: 0! = 1
Rule 2: n! = n (n – 1)!
Recursive Definitions of earlier Languages
L1=x += {x xx xxx xxxx ...}
L odd= X 2n-1 for n > 0 ={x xxx xxxxx ...}
L4= X * = {˄ xx xxxx xxxxx ...}
Kleene Closure e.g. S*
An Important Language – Arithmetic Expressions
What constitutes a valid arithmetic expression (AE) that can be typed on one line, in a computer-digestible form?
What is the alphabet?
Are the following strings in language AE?
- (3 + 5) + 6)
- 2(/8 + 9)
- (3 + (4 – 8) )
- 2) – (4
What rules govern formation of correct AE strings?
Example – Arithmetic Expressions
Recursive definition of AE most natural way rather than a list of forbidden substrings, parentheses requirements and rules!
Rule 1: Any number (positive, negative or zero) is in AE
Rule 2: If x is in AE then so are (x) and –(x)
Rule 3: If x and y are in AE then so are x + y, x –y, x * y, x / y, x ** y
Arithmetic Expressions
Is the arithmetic expression (4 +25 / (10 ** 2) / 5 in AE?
Is the arithmetic expression (2 + 5) * (6 * (9 –2)/5)/4 * (2 + 9) – 1 in AE?
How does the recursive definition allow us to simply carry out such proofs?
Proving Theorems
THEOREM 2: No arithmetic expression can contain the character $
THEOREM 3: No arithmetic expression can begin or end with the symbol /
Example from LOGIC
Definition of the set WFF (well-formed formulae):
Σ = → ¬ ( ) a b c d ...
Rule 1: Any single Latin letter is a WFF e.g. a b c d
Rule 2: If p is a WFF, then so are (p) and ¬p
Rule 3: If p and q are WFFs then so is p → q
Are the following in WFF?
- p→ ((p→ p) → q)
- p→
- → p
- p→ p
- p) → p(
Ready to get started?
Start your journey to mastering the art of logic and arithmetic expressions today!
Oh, and the best bit...It's free!