Propositions, predicates and quantifiers

(1) Mathematica implements the quantifiers and as the functions ForAll and Exists.

For example, ForAll[x, x<1] produces the output .

Note that this is simply a quantified statement – it is a statement in the predicate calculus. The predicate “” is not a proposition, because it is not true or false. The variable “” has to be bound by a quantifier before we can decide the truth or falsity of ““.

We can check the truth value of ForAll[x, x<1] by applying the Mathematica function Resolve:

Resolve[ForAll[x, x<1] ]

False

Similarly we can quantify the predicate ”” by an existential quantifier:

Exists[x, x<1]

Again we can check the truth of this quantified statement using Resolve:

Resolve[Exists[x, x<1] ]

True

• Experiment with propositions on the one hand and predicates with unbound variables on the other to see the differing Mathematica outputs. Express, in your own words the difference between a proposition and a predicate.

Mathematica

Resolve[Exists[x, x<1] ]

True

For all value of x not be less than one, but x can be less than one or greater than one.  In mathematica gives a true because existing value of x can be less than one.

• Construct interesting examples of predicates in which all variables are bound by quantifiers, and check the truth or falsity of these statements using the Resolve function. Note: Resolve will work in general over the complex numbers where possible. So, for example, applying Resolve to the quantified statement ForAll[x,x^2 != -1] yields the truth value “False”. This is because the equation does in fact have complex solutions. However, if we restrict the domain of Resolve to the real numbers, as follows – Resolve[ForAll[x, x^2 != -1], Reals] – then the result is the truth value “True”.

Mthematica result

Resolve[ForAll[x, x^2 != -1], Reals]

True

The value of x^2 never be a negative value does not matter what value we pass for x we always get out put positive value, because square of x make the positive .

(2) For propositions the truth table for implication is false when, and only when is true and is false.  When are predicates with unbound variables, the situation is more delicate.

For example, let where are variables ranging over the set .

The implication is neither true nor false. There are specific values of for which  is true, and other values for which it is false.

How can we identify such values?

Using the Mathematica function RegionPlot we can visualize the set of points for which  is true:

p=x^2+y^2<1;

RegionPlot[p,{x,-1,1},{y,-1,1}]

Similarly we can visualize the set of points for which is true:

p=x+y>0;

RegionPlot[p,{x,-1,1},{y,-1,1}]

Using the same function we can visualize the region where is true:

RegionPlot[Implies[p, q], {x, -1, 1}, {y, -1, 1}]

We can check that this gives the same region on which is true:

RegionPlot[! p || q, {x, -1, 1}, {y, -1, 1}]

The function Boole gives us the indicator function of the region on which is true:

b=Boole[Implies[p,q]]

Indicator function of region on which p => q is true

Indicator function of region on which p=>q is false

We can find the area of this region, including a numerical approximation,  by integrating the indicator function:

Integrate[b,{x,-1,1},{y,-1,1}]

N[%]

2.4292

• Choose several different examples of regions on which is true for predicates defined by inequalities which could be algebraic or involve transcendental functions such as , and illustrate that these are the same regions for which  is true.

Union and intersection of sets

• Specifics:

(1) The region can be plotted using the Mathematica command RegionPlot:

A=RegionPlot[1/4 <= x^2 + (2 y)^2 <= 1, {x, -1, 1}, {y, -1, 1}]

We can change the color and make it translucent by adding a couple of options to the plot command:

A=RegionPlot[1/4 <= x^2 + (2 y)^2 <= 1, {x, -1, 1}, {y, -1, 1}, PlotStyle -> Directive[Red, Opacity[0.4]]]

We can plot the region similarly (but in a different color):

B=RegionPlot[y > x, {x, -1, 1}, {y, -1, 1}, PlotStyle -> Directive[Blue, Opacity[0.4]]]

Due to the figures being translucent we can overlay them and see their intersection:

Show[{A,B}]

The Mathematica function Boole applied to a region takes the value 1 on that region, and takes the value 0 outside the region. As a result, integrating Boole[R] for a region R gives the area of R:

NIntegrate[Boole[1/4 <= x^2 + (2 y)^2 <= 1], {x, -1, 1}, {y, -1, 1}]

1.1781 (= area of A)

Similarly, the area of B is calculated as

NIntegrate[Boole[y > x], {x, -1, 1}, {y, -1, 1}]

2 (= area of B)

• Calculate the areas of and .

p = 1/4 <= x^2 + (2 y)^2 <= 1
q = y > x

1/4 <= x^2 + 4 y^2 <= 1

y > x

RegionPlot[p || q, {x, -2, 2}, {y, -2, 2}]

• What is the connection between ?

A = 1/4 <= x

The intersection of two sets A and B is the collection of points which are in A and in B. Below is a graph of the region where A and B intersect:

The relationship:-

area(A\[Union)B) = area(A)+area(B) -area(A)\[Intersection]area(B)

area(A) = 1.1781       area(B)=2   area(A+B) =3.1781

Area(A):- It  is a circle area whose radius varies from 1/2 to 1.

Area(B):- It is a triangular area y>x.

Area(A\[Union]B):- it means a sum of area(A) and area(B)

• Try this for several different choices of

Assume we have two sets A and B defined as:

A = 2y > x

B = .5 <= 2x + .25y <= 2

The regions are plotted below:

Here is two sets A and B are in symbols,

A = {x is an even integer from 1 to 10}

B = {x is an odd integer from 1 to 10}

A\[Union] B = {all no. from 1 to 10}

A\[Intersection] B ={0}

Be careful not to make the sets too complicated – the numerical integration procedure NIntegrate might not stably converge if the regions are too complicated.

• Investigate the areas of the unions and intersections of 3 sets in the plane.

Example:- If A = {2}, B = {2, 5, 8}, C = {1, 2, 3, 4, 5} what are B intersect C, A intersect C, A intersect B intersect C, A union B union C, A union B intersect C, and A intersect B union C?

B\[Intersection]C = {2,5}

A\[Intersection]C = {2}

A\[Intersection]B\[Intersection]C = {2}

A\[Union]\B[Union]\C = {1,2,3,4,5,8}

A\[Union]\B\[Intersection]\C = {2,5}

A\[Intersection]\B\[Union]\C = {2}

(2) By definition sets do not have repeated elements. Mathematica creates lists in wich order matters, and in which repeats are possible. For example the following are two different lists:

A= {1,7,3,6,9,b,10,a}

B= {a, a, b, 1,3,3,6,7,7,9,10,10}

However, when we apply the Mathematica function Union to these sets we get the following:

Union[A]

{1, 3, 6, 7, 9, 10, a, b}

Union[B]

{1, 3, 6, 7, 9, 10, a, b}

The effect of the Union function is to delete repeats of elements in a list and order the list where possible. The Union function allows us to therefore to deal with lists as sets.

We can generate two sets of random integers as follows:

A = Union[Table[RandomInteger[{1, 50}], {i, 1, 20}]]

{1, 2, 11, 13, 15, 16, 18, 21, 29, 32, 33, 36, 37, 39, 40, 43, 48, 49}

B = Union[Table[RandomInteger[{1, 50}], {i, 1, 20}]]

{1, 2, 5, 7, 8, 9, 16, 24, 25, 27, 30, 32, 33, 34, 35, 37, 46, 47}

Then we can find the set-theoretic union and intersection as follows:

{1, 2, 5, 7, 8, 9, 11, 13, 15, 16, 18, 21, 24, 25, 27, 29, 30, 32, 33, 34, 35, 36, 37, 39, 40, 43, 46, 47, 48, 49}

{1, 2, 16, 32, 33, 37}

Note: in Mathematica, type the following to get the union sign: Esc un Esc, and type Esc inter Esc to get the intersection sign.

• Illustrate the distributive and absorptive laws for sets through examples such as those above.

Distributive law

An example A = {2,0,1}, B = {2, 5, 8,0}, C = {1, 2, 3, 4, 5,0}

(a) A \[Union] (B \[Intersection] C) = (A \[Union] B) \[Intersection] (A \[Union] C)

Left hand side

A \[Union] (B \[Intersection] C) = A \[Union]{2,5,0} = {0,1,2,5}

Right hand side

(A \[Union] B) \[Intersection] (A \[Union] C) = {0,1,2,5,8}\[Intersection]\{0,1,2,3,4,5} = {0,1,2,5}

Left hand side = Right hand side

(b) A \[Intersection] (B \[Union] C) = (A \[Intersection]\B) \[Union] (A \[Intersection] \C)

 Left Hand Side

A \[Intersection] (B \[Union] C) = A \[Intersection]{0,1,2,3,4,5,8} = {0,1,2}

Right Hand Side

(A \[Intersection]\B) \[Union] (A \[Intersection] \C) = {0,2}\[Union]\{0,1,2} = {0,1,2}

Left Hand Side = Right Hand Side

Absorptive law

An example A = {2,0,1}, B = {2, 5, 8,0}, C = {1, 2, 3, 4, 5,0}(a) A\[Union]\(A\[Intersection]\B) = AA\[Union]\{0,2} = {0,1,2} = A(b) A\[Intersection]\(A\[Union]\B) = AA\[Intersection]\{0,1,2,5,8} = {0,1,2} = A

• Illustrate through examples such as those above.

An example A = {2,0,1}, B = {2, 5, 8,0}, C = {1, 2, 3, 4, 5,0}

Left Hand Side: A\[Union] B = |{0,1,2,5,8}| = length is 5

Right Hand Side: 3 + 4 -| {0,2} = 3+4-2 = 5

Left Hand Side =  Right Hand Side

Question 4. Generating primes

• Background. The recursively defined sequence

a(n)=a(n-1)+GCD(n,a(n-1)), a(1)=7

has the remarkable property that the difference

g(n):=a(n)-a(n-1), n>1

is either 1 or a prime number: A NATURAL PRIME-GENERATING RECURRENCE _ROWLAND

• Specifics:
  • For successive values of the integer n, compute the number dp(n) of distinct primes generated as , that are less than or equal to n.

  

  • Plot dp(n) as a function of n. What properties does this function have? Increasing, one-to-one, onto?

  a[n_] := a[n] = a[n – 1] + GCD[n, a[n – 1]]
  a[1] = 7;

  F[k_] := Length[Union[DeleteCases[Table[a[n] – a[n – 1], {n, 2, k}], x_ /; x == 1]]]
  T = Table[{k, F[k]}, {k, 2, 5000}];
  ListPlot[T]

  

  The recursive function that calculate the prime numbers without 1’s and without repeating numbers. Yes, this function is increasing one to one

Question 3. Fibonacci numbers

The Fibonacci numbers are determined by the following recursive relation:

• Use Mathematica to calculate and plot

f[0]:=1;

f[1]:=1;

f[n]=f(n-1)+f(n-2);

T=Table[{n,f (n)/f},{n,0,50}];

ListPlot[T]

• Estimate the growth rate of

The exponential growth rate is growing fast as same value of n. So, f(n) has same growing rate the n is growing.

• Use the fact that if then to get a more precise estimate of the growth rate of .

f[0] := 1;
f[1] := 1;
f[n] := f[n – 1] + f[n – 2];

R[n_] := Fibonacci[n]/Fibonacci[n – 1];

T = Table[{n, R[n]}, {n, 0, 50}];
ListPlot[T]

Rc[n -] := 1 + 1/R[n – 1];
Tc = Table[{n, Rc[n]}, {n, 0, 50}];
ListPlot[Tc]

From the above it clearly shows that function R[n_] := Fibonacci[n]/Fibonacci[n – 1]; and function Tc = Table[{n, Rc[n]}, {n, 0, 50}]; converse at same point 1.61803.

Question 2. Dijkstra’s fusc function

• Background

fusc(n) = fusc(n/2) if n is even, and

fusc(n ) = fusc((n-1)/2) + fusc((n+1)/2) if n is odd,

with fusc(0) = 0 and fusc(1) = 1.

• Plot fusc(n) as a function of n up to 10,000
• Plot a table of values of fusc(n) alongside n for n up to 99. Verify from the table that for n < 100,  fusc(n) is a multiple of 2 exactly when is a multiple of 3.
• Write the statement

“For all n, fusc(n)is a multiple of 2 exactly when is a multiple of 3” ………(*)

in first-order logic. (see here for more on quantification).

• Prove the statement (*) above is true:
  • First prove that if n is a multiple of 3 then fusc(n) is a multiple of 2. Do this by splitting int0 two cases: (1) n is twice an even number (2) n is twice an odd number. Utilize induction.

  Second, prove that If is a not a multiple of 3 then fusc(n)is not a multiple of 2. Consider the two ways in which an integer is not a multiple of 3 and use induction.

fusc[n_]:=If[EvenQ[n]ŠTrue,fusc[n/2],fusc[(n-1)/2]+fusc[(n+1)/2]];

fusc[0]:=0;

fusc[1]:=1;

t1=SessionTime[];

T=Table[{n,fusc[n]},{n,0,10000}];

fusc[n_]:=If[EvenQ[n]==True,fusc[n/2],fusc[(n-1)/2]+fusc[(n+1)/2]];

fusc[0]:=0;

fusc[1]:=1;

t1=SessionTime[];

A=Table[{n,fusc[n]},{n,0,99}];

Grid[A]

Question 1. The central binomial coefficent

• • The binomial coefficients are defined recursively as follows:
    1. for all integers n,k>0
    2. for all integers
    3. for all integers
  • plot the central binomial coefficient as a function of for

  bc[n_,k_]:=bc[n,k]=bc[n-1,k-1]+bc[n-1,k];

  bc[n_,0]:=bc[n,0]=1;

  bc[0,k_]:=bc[0,k]=If[k>0,0,1];

  A=Table[{n,bc[2*n,n]},{n,0,25}];

  ListLogPlot[A,Filling->Axis]

  

  • Find upper bounds for, or determine, the rate of growth of as a function of .
  • Imagine walking on the grid below, from the red dot (the “origin”) to any other dot by walking UP one step or RIGHT one step at a time:

  

  (a+b)^n = C(n,0)a^nb^0 +  C(n,1)a^(n-1)b^1+ ……+C(n,k)a^(n-k)b^i+….+C(n,n)a^0b^n

  If consider a is moving right and b is up.

  The red ball moves right or up. Than the red ball has to pass the coefficient of  C(n-1,k) and C(n-1,k-1).

  • Show that the number of different paths from the origin to a dot that is k steps UP and n-k steps RIGHT (or vice versa),where , is

  (0,0) ->(k,n-k) let consider (0,0) -> (x,y) than C(x+y,x) that means k=x and y=n-k

C(k+(n-k),k) = C(n,k)

• For the dots that are 15 steps away from the origin calculate how many different paths there are to that dot.

x+y = 15;

(x+y): (0,15) -> C(15,0)

(1,14)->C(15,1)

(2,13)->C(15,2)
………….

(15,0)->(0,15)

• Use Mathematica to expand and examine the coefficients of the powers . Is this a coincidence?

Expand[(a+b)^15]

a^15 + 15 a^14 b + 105 a^13 b^2 + 455 a^12 b^3 + 1365 a^11 b^4 +  3003 a^10 b^5 + 5005 a^9 b^6 + 6435 a^8 b^7 + 6435 a^7 b^8 +  5005 a^6 b^9 + 3003 a^5 b^10 + 1365 a^4 b^11 + 455 a^3 b^12 +  105 a^2 b^13 + 15 a b^14 + b^15

• What is special about “15″?

• A block tower of 2 colors is built as a vertical stack of blocks, with a bottom and a top. Below are several block towers of height 5:

• How many block towers of height 5 are there and what are they?

These are white or black on 5 towers.

• What does this have to do with the binomial expansion of ?

(0,5) -> C(5,0), (1,4)->C(5,1), (2,3)->C(5,2), (3,2)->C5,3), (4,1)->C(5,1),and (5,0)->C(5,5)

• What does it have to do with the number of walks on the grid, above, to points that are 5 steps from the origin?

let a is white and b is black than

aaaaa -> n=5 ->a^5b^0

aaabb -> n=5 ->a^3b^2

babab ->n=5 ->a^2b^3

bbbab -> n=5 ->a^1b^4

bbbbb -> n=5 ->a^0b^5

• What connection is there between block towers of height n, the binomial expansion of and walks on the grid to points that are n steps from the origin?

C(n,k) = C(n-1,k)+C(n-1,k-1) is binomial coefficient.

Using (a+b)^5 =a^5+C(5,1)a^4b+C(4,2)a^3b^2+C(3,2)a^2b^3+C(4,1)a^1b^4+b^5

if we consider a is white block and b is black block than total number is equal to be sum of all coefficients.

Propositions, predicates and quantifiers

(1) Mathematica implements the quantifiers and as the functions ForAll and Exists.

For example, ForAll[x, x<1] produces the output .

Note that this is simply a quantified statement – it is a statement in the predicate calculus. The predicate “” is not a proposition, because it is not true or false. The variable “” has to be bound by a quantifier before we can decide the truth or falsity of ““.

We can check the truth value of ForAll[x, x<1] by applying the Mathematica function Resolve:

Resolve[ForAll[x, x<1] ]

False

Similarly we can quantify the predicate ”” by an existential quantifier:

Exists[x, x<1]

Again we can check the truth of this quantified statement using Resolve:

Resolve[Exists[x, x<1] ]

True

• Experiment with propositions on the one hand and predicates with unbound variables on the other to see the differing Mathematica outputs. Express, in your own words the difference between a proposition and a predicate.

Resolve[ForAll[x, x<1] ]

False

For all value of x can not be true less than 1 because can be greater than 1 too(x>1), in this function fail.

• Construct interesting examples of predicates in which all variables are bound by quantifiers, and check the truth or falsity of these statements using the Resolve function. Note: Resolve will work in general over the complex numbers where possible. So, for example, applying Resolve to the quantified statement ForAll[x,x^2 != -1] yields the truth value “False”. This is because the equation does in fact have complex solutions. However, if we restrict the domain of Resolve to the real numbers, as follows – Resolve[ForAll[x, x^2 != -1], Reals] – then the result is the truth value “True”.

Resolve[ForAll[x, x^2 != -1], Reals]

True

In this case value of x^2 never be negative value, because does not matter what value we pass for x the output makes positive value.

(2) For propositions the truth table for implication is false when, and only when is true and is false.  When are predicates with unbound variables, the situation is more delicate.

For example, let where are variables ranging over the set .

The implication is neither true nor false. There are specific values of for which  is true, and other values for which it is false.

How can we identify such values?

Using the Mathematica function RegionPlot we can visualize the set of points for which  is true:

p=x^2+y^2<1;

RegionPlot[p,{x,-1,1},{y,-1,1}]

Similarly we can visualize the set of points for which is true:

p=x+y>0;

RegionPlot[p,{x,-1,1},{y,-1,1}]

Using the same function we can visualize the region where is true:

RegionPlot[Implies[p, q], {x, -1, 1}, {y, -1, 1}]

We can check that this gives the same region on which is true:

RegionPlot[! p || q, {x, -1, 1}, {y, -1, 1}]

The function Boole gives us the indicator function of the region on which is true:

b=Boole[Implies[p,q]]

Indicator function of region on which p => q is true

Indicator function of region on which p=>q is false

We can find the area of this region, including a numerical approximation,  by integrating the indicator function:

Integrate[b,{x,-1,1},{y,-1,1}]

N[%]

2.4292

• Choose several different examples of regions on which is true for predicates defined by inequalities which could be algebraic or involve transcendental functions such as , and illustrate that these are the same regions for which  is true.

Recursive Function:

Let talk about recursive function, what is it and how it works?

Recursive function is a function call itself. Here is common recursive relation for factorial: – n! =n*(n-1)*(n-2)*(n-3)*……

If is define then it stop at a certain term (n+1);

Let see if  n=5;

5! =5*4*3*2*1*1 (Using above formula and last term be 0! =1)

It takes long time for big number of n, in computer programming we can finish in few lines:

while(n>0)

x=n*(n-1);

n=n-1;

end

Question From Matrix: (1) A relation on a finite set

A relation on a finite set is a subset of .

Generally we will write a finite set as an ordered list

We can think of a relation in terms of a matrix, that has an entry 1 in the spot if and has a 0 entry otherwise.

We can generate random relations using these matrices:

From the below Matrix says that

First row: two vector or points showing from point 1 and 1 itself

Second row: two vector or points showing from point 2

Third row: only one vector or point showing from point 3

Four row: none vector or point showing from point 4

These are the correlation between Matrix diagram and Matrix element vectors

Graph Theory Question Number 6. Crossing Number

Investigate the crossing number of complete bipartite graphs for small values of . Focus, especially on the case ; that is, investigate the crossing number of for small values of n.

internet search and my analysis,Crossing number is increasing by gradually if I put the drawing in certain format below format shows less no of crossing number. I have done for K(3,2),K(3,3), and K(3,4).

Below Drawing is K(3,2) there is no crossing number.

Below Drawing is K(3,3) there is one crossing number.

Below Drawing is K(3,4) there is two crossing number.