### Discrete Structure

Discrete Structure
Li Tak Sing(李德成)
Lecture 13
1
More examples on inductively
defined sets
Find an inductive definition for each set S
of strings.
1.
2.
3.
4.
Even palindromes over the set {a,b}
Odd palindromes over the set {a,b}
All palindromes over the set {a,b}
The binary numerals.
2
Solution
1. Basis:Λ ∈
induction:  ∈  ℎ ,  ∈
2. Basis:,  ∈
induction:  ∈  ℎ ,  ∈
3. Basis:Λ, ,  ∈
induction:  ∈  ℎ ,  ∈
4. Basis:0,1 ∈
induction:  ∈    ≠ 0 ℎ 1, 0 ∈

3
More examples on inductively
defined sets
Find an inductive definition for each set S
of lists.
1. {<a>, <a,a>, <a,a,a>,..}
2. {<1>, <2,1>, <3,2,1>,..}
3. {<a,b>, <b,a>, <a,a,b>, <b,b,a>, <a,a,a,b>,
<b,b,b,a>,...}
4. {L| L is a list with even length over {0,1,2}}
4
Solution
1. Basis:<  >∈
induction:  ∈  ℎ (, ) ∈
2. Basis:< 1 >∈
induction:  ∈  ℎ
(ℎ  + 1, ) ∈
3. Basis:< ,  >, < ,  >∈
induction:  ∈  ℎ
(ℎ  , ) ∈
4. Basis:<>∈
induction:  ∈
,  ∈ {0,1,2} ℎ  ∈
5
More examples on inductively
defined sets
Find an inductive definition for the set B of
binary trees that represent arithmetic
expressions that are either numbers in N
or expressions that use operations + or -.
6
Solution
Basis:(<>, 0, <>) ∈
induction: ,  ∈  ℎ  , +,  ,
, −,  ∈ ,
<>, , <> ∈ ,
ℎ (<>,  + 1, <>) ∈
7
More examples on inductively
defined sets
Find an inductive definition for each subset
S of NN.
1. S={(x,y)| y=x or y=x+1}
2. S={(x,y) | x is even and yx/2
8
Solution
1. Basis:(0,0) ∈
induction: ,  ∈  ℎ
+ 1,  + 1 , ,  + 1 ∈
2. Basis:(0,0) ∈
induction: , 0 ∈  ℎ  + 2,0 ∈

(, ) ∈    + 1 ≤
2
ℎ (,  + 1) ∈
9
Recursive Functions and Procedures
Procedure
A program that performs one or more actions.
A procedure may return one or more values
through its argument list. For example, a
statement like allocate(m,a,s) might perform the
action of allocating a block of m memory cells
and return the values a and s, where a is the
beginning address of the block and the s tells
whether the allocation was successful.
10
Definition of recursively defined
 A function or a procedure is said to be
recursively defined if it is defined in terms of
itself.
 If S is an inductively defined set, then we can
construct a function f with domain S as follow:
For each basis element xS, specify a value for f(x).
Give rules that, for any inductively defined element xS,
will define f(x) in terms of previously defined value of f.
11
Constructing a recursively defined
procedure
If S if an inductively defined set, we can
construct a procedure P to process the
elements of S as follows:
For each basis element xS, specify a set of
actions for P(x).
Give rules that, for any inductively defined
element xS, will define the actions of P(x) in
terms of previously defined actions of P.
12
Numbers
Sum of integers.
f(n)=0+1+2+...+n
Definition:
f(n)= if n=0 then 0 else f(n-1)+n
Alternatively, it can be written as
f(0)=0
f(n)=f(n-1)+n
This is known as the pattern matching method
13
Numbers
Adding odd numbers
f(n)=1+3+...+(2n+1)
Definition:
f(0)=1
f(n)=f(n-1)+(2n+1)
14
The rabbit program
 The Fibonacci numbers are the numbers in the sequence
0,1,1,2,3,5,8,13
where each number after the first two is computed by adding the
preceding two numbers.
 Assume that at the beginning there is one pair of rabbits. They give
birth to another pair of rabbit in one month.
 Let f(n) represents the number of pairs of rabbits at the n-th month.
At that time, there were only f(n-2) mature rabbits which give birth to
f(n-2) new rabbits. So the total number of rabbits is the total number
of rabbits at the (n-1)th month plus these newly born f(n-2) rabbits.
 So f(n)=f(n-1)+f(n-2)
 The sequence 0,1,1,2,3,... is called the Fibonacci numbers.
15
Sum and product notation
Sum of sequence a1,a2,....,an
n
a
 a 1  a 2  .....  a n
i
i 1
 Product of a sequence a1,a2,....,an
n

a i  a 1 a 2 ..... a n
i 1
16
Factorial
n!=12.....n
0!=1
n!=(n-1)!n
17
Examples
Construct a recursive definition for each of
the following functions, where all variables
are natural numbers.
1.
2.
3.
4.
f(n)=0+2+4+...+2n.
f(n)=floor(0/2)+floor(1/2)+....+floor(n/2).
f(n,k)=k+(k+1)+(k+2)+...+(k+n).
f(n,k)=0+k+2k+...+nk.
18
1.  0 = 0
=   − 1 + 2
2.  0 =
0
2

=   − 1 +
2
3.  0,0 = 0
0,  =  0,  − 1 + 1
,  =   − 1,  +  +
4.  0,  = 0
,  =   − 1,  +
19
Lists
f(n)=<n,n-1,..,1,0>
f(n)= if n=0 then <0> else cons(n,f(n-1))
Using the pattern matching method
f(0)=<0>
f(n)=cons(n,<n-1,...,1,0>)
=cons(n,f(n-1))
20
Recursive procedures
Let P(n) be the procedure that prints out
the numbers in the list <n,n-1,...,0>.
P(n): if n=0 then print(0)
else
print(n);
P(n-1)
fi
21
The distribute function
dist(3,<1,2,3>)=<(3,1),(3,2),(3,3)>
How to define this function recursively?
dist(x,L)= if L=<> then <>
else
(x,head(L))::dist(x,tail(L))
Pattern matching method:
dist(x,<>)=<>
dist(x,a::L)=(x,a)::dist(x,L)
22
The pairs function
pairs(<a,b,c>,<d,e,f>)=<(a,d),(b,e),(c,f)>
pairs(A,B)=if A=B=<> then <> else
(head(A),head(B))::pairs(tail(A),tail(B))
pairs(<>,<>)=<>,
pairs(x::T, y::U)=(x,y)::pairs(T,U)
23
Concatenation of Lists
cat(<a,b>,<c,d,e>)=<a,b,c,d,e>
cat(L,M)=if L=<> then M
else head(L)::cat(tail(L),M)
Pattern matching method:
cat(<>,A)=A
cat(x::L,A)=x::cat(L,A)
24
Sorting a list by insertion
sort(<>)=<>
sort(x::L)=insert(x,sort(L))
insert(x,S)=if S=<> then <x>
else if x<head(S) then x::s
else head(S)::insert(x,tail(S))
25
Example
Write recursive definition for the following
list functions.
1. The function "last" that returns the last elemnt
of a nonempty list. For example
last(<a,b,c>)=c
2. The function "front" that returns the list
obtained by removing the last element of a
nonempty list. For example
front(<a,b,c>)=<a,b>.
26
Solution
1.  <  > =
∷  =

=    =<> ℎ
ℎ()

2.  <  > =<>
∷  =  ∷

=   =<> ℎ <>

ℎ  ∷ (  )
27