211L1Solutions

Question 1

Prove the following statements. In each case write down the hypothesis and the conclusion of the statement.

(a) The integers 2, −7, 101 are rational numbers.

Hypothesis:

If 2, -7, and 101 are rational numbers,

Conclusion:

then they can be expressed in the form n/m where n and m are integers.

Solution

• Case 1: 2 can be written as 2/1 where n=2 and m=1
• Case 2: -1 can be written as –7/1 where n=-7 and m=1
• Case 3: 101 can be written as 101/1 where n=101 and m=1

(b) Every integer is a rational number.

Hypothesis:

If every integer is a rational number,

Conclusion:

then every integer can be expressed in the form n/m where n and m are integers.

Solution

• Since, n/1 = n. Every integer can be expressed in the form where the integer n/m = n where m=1.

(c) If p and q are rational numbers then so are p − q and p · q.

Hypothesis:

p and q are rational numbers

Conclusion:

then, p-q and p.q are also rational numbers.

Solution

• Since p and q are rational numbers, p can be represented as n/m and q can be represented at s/t where n,m,s,t are integers and m, t != 0.

• For p-q, this can be written as n/m - s/t. n/m - s/t = nt/mt - ms/mt = (nt-ms)/mt where (nt-ms) = i which is an integer, mt = j which is also a non zero integer. As such i/j is a rational number.

• For p.q, this can be written as n/m.x/t. This equals nx/mt where m,t != 0. nx can be written as i and mt can be written as j. These are both integer values. As such n/m.x/t = i/j which is a rational fraction.

(d) The sum of two even numbers is an even number.

Hypothesis:

If p and q are even numbers.

Conclusion:

then p+q is also an even number.

Solution

As p and q are even, they both have a factor of two. They can be rewritten as p=2P and 2=2Q. p+q is therefore 2P+2Q = 2(P+Q). It is clear that 2 is a factor of the result, and as such, the result must be even.

(e) The sum of even and an odd number is an odd number.

Hypothesis:

If p is an even number, and q is an odd number.

Conclusion:

then p+q is an odd number.

Solution

For p to be even, when divided by two, the remainder is zero. For q to be odd, when divided by two, its remainder is 1. Disregard the ambiguity of 0. p can be rewritten as 2P+0, and q as 2Q+1. 2P+2Q+1=2(P+Q)+1. 2 is not a factor of this result and as such, the conclusion holds true.

(f) Let n come from a set of N. If n^2 is an even number then n is also an even number.

Hypothesis:

If n^2 is an even natural number.

Conclusion:

then n is also an even number.

Solution

If n were not an even number, it would be written as 2p+1, as it would have a remainder of 1 when divided by 2. Since (2p+1)^2 = 4p^2 + 1 an odd number squared will always have an odd result. As such it is impossible for the square root of an even number to be an odd number.

(g) The sum of a rational number with an irrational number is an irrational number.

Hypothesis:

If p is a rational number, and q is an irrational number.

Conclusion:

then p+q is an irrational number.

Solution

If p is a rational number it can be written in the form n/m where n,m are integers and m != 0. If q is irrational, it can be written as q and not in a fractional of integers. Thus p+q= n/m +q . Since the result cannot be rationalised into a fraction made up of integers, it is irrational. Q.E.D.

(h) The product of a rational number with an irrational number is an irrational number.

Hypothesis:

If p is a rational number, and q is an irrational number.

Conclusion:

then p.q is an irrational number.

Solution

If p is a rational number it can be written in the form n/m where n,m are integers and m != 0. If q is irrational, it can be written as q and not in a fractional of integers. Thus p.q= (n.p)/m . Since the result cannot be rationalised into a fraction made up of integers, it is irrational. Q.E.D.

(i) Prove that for all numbers x and y we have |x + y| <= |x| + |y|.

Hypothesis:

For all numbers x and y,

Conclusion:

|x + y| <= |x| + |y|

Solution

• Where x is + and y is +
  • |x + y | = x + y, and |x| + |y| = x + y. Therefore where x and y are positive, |x + y| = |x| + |y|.
• Where x is - and y is +
  • |-x + y | = |y-x|. This will always be smaller or equal to the absolute value of y. |-x| + |y| = x + y. Therefore where x and y are positive, |-x + y| = |-x| + |y|.
• Where x is + and y is -
  • |x + -y | = |y-x|. This will always be smaller or equal to the absolute value of x. |x| + |-y| = x + y. Therefore where x and y are positive, |x + -y| = |x| + |-y|.
• Where x is - and y is -
  • |-x + -y | = x + y, and |x| + |y| = x + y. Therefore where x and y are positive, |x + y| = |x| + |y|.

Question 2

Consider the binary alphabet {a, b}. The string w = a1 . . . an, where each of a1, . . ., an is either a or b, has length n. The symbols a1, . . ., an are called symbols (or digits) of the string w. The symbol ai is called the ith symbol of the string. Say that two strings w and v are equal if they both have the same length, and each ith symbol of w equals the ith symbol of v. Do the following:

(a) List all strings of lengths 0, 1, 2, 3, and 4.

Solution

String length:      0        1        2        3        4
                   ""        a       aa      aaa     aaaa
                             b       ab      aab     aaab
                                     ba      aba     aaba
                                     bb      abb     aabb
                                             baa     abaa
                                             bab     abab
                                             bba     abba
                                             bbb     abbb
                                                     baaa
                                                     baab
                                                     baba
                                                     babb
                                                     bbaa
                                                     bbab
                                                     bbba
                                                     bbbb

(b) How many strings are there of length 3, 4, and 5.

Solution

For every string length n, there are 2^n strings. Thus for a string length of 3 there are 2^3=8 possible string combinations. For 4, 2^4=16 combinations and 5, 2^5=32 string combinations.

(c) Write down a formula that computes the number of strings of length n.

Solution

For any string length n, there are 2^n strings.

(d) Write down a formula that computes the number of strings of length at most n.

For all the strings up to a given length, the formula is:

Sum where x=o-n of 2^x

Prove that there exist irrational numbers a and b such that a^b is rational. (Hint: Use the number sqrt(2)).

let x and y be rational integers and a and b are irrational. a^b=x/y. Assume a is sqrt(2), b log(a) = log(x/y). b=log(x/ay). log(x/ay) cannot be expressed as a rational integer and as such b is irrational.

Question 3

Programming exercises

1. Write a program that, given n and alphabet 'Sigma' as inputs, outputs all strings of length n over the alphabet 'Sigma'.
   • Brute Force information from wiki
2. Write a program that given a fraction n/m, where n, m are integers and m 6= 0, outputs its reduced form.