Homework assignment 02

Homework assignments

Homework assignment 04

1.4   Predicate Logic

1. (for all x)[A(x) -> B(x)]-> [(there exists x)A(x) -> (there exists x)B(x)]
   We use the deduction method to rewrite the argument with (there exists x)A(x) as further hypothesis and (there exists x)B(x) as conclusion.

   1.	(for all x)[A(x) -> B(x)]	hyp
   2.	(there exists x)A(x)	hyp
   3.	A(s)	ei, 2
   4.	A(s) -> B(s)	ui, 1
   5.	B(s)	mp, 3,4
   6.	(there exists x)B(x)	eg, 5

   The converse is false, as can be checked with the following interpretation: DOI is the world, A(x) is ``x is an ananas'' and B(x) is ``x is a banana''.
2. There is some movie star who is richer than everyone. Anyone who is richer than anyone else pays more taxes than anyone else does. Therefore, there is a movie star who pays more taxes than anyone. DOI: americans, M(x), R(x,y), T(x,y)
   The above statement can be written as:
   (there exists x)(for all y)[M(x) /\ R(x,y)] /\ (for all x)(for all y)[R(x,y)-> T(x,y)] -> (there exists x)(for all y)[M(x) /\ T(x,y)]

   1.	(there exists x)(for all y)[M(x) /\ R(x,y)]	hyp
   2.	(for all x)(for all y)[R(x,y)-> T(x,y)]	hyp
   3.	(for all y)[M(s) /\ R(s,y)]	ei,1
   4.	M(s) /\ R(s,y)	ui,3
   5.	(for all y)[R(s,y)-> T(s,y)]	ui,2
   6.	R(s,y)-> T(s,y)	ui,5
   7.	R(s,y)	simp,4
   8.	T(s,y)	mp,6,7
   9.	M(s)	simp,4
   10.	M(s) /\ T(s,y)	con,7,9
   11.	(for all y)[M(s) /\ T(s,y)]	ug,10
   12.	(there exists x)(for all y)[M(x) /\ T(x,y)]	eg,11

1.6   Proof of Correctness

1. Verify the correctness of the following program segment with the assertions shown.

   {z = 3}
     x := z + 1
     y := x + 2
   {y = 6}
     if y > 0 then
       z := y + 1
     else
       z := 2 * y
     endif
   {z = 7}
   

   Given the precondition {z=3} and the postcondition {y=6}, working backwards, from y := x + 2, we get {x=4}. From x:=z+1, we get {z=3}, which is the precondition. The second part is checked analogously, by verifying the two Hoare triples: {y=6 /\ y>0}z:=y+1{z=7} and {y=6 /\ y<0}z:=2*y{z=7}. Note that the precondition in the second case is clearly contradictory, so we actually don't have to check anything.

2.1   Proof Techniques

1. For 2<= n <= 4, n² >= 2ⁿ.
   Assuming that n is an integer, the finite size of the system allows for a simple exhaustive proof:

   n=2	n2=4 >= 4 = 2n
   n=3	n2=9 >= 8 = 2n
   n=4	n2=16>= 16 = 2n.

2. Let A be the average of n numbers x₁, x₂,..., x_n. Prove that at least one of x₁, x₂,..., x_n is greater than or equal to A.
   
   By definition, the average A can be written as:

   A    =

   x1+x2+...+xn n

   .

   
   Let's do a proof by contradiction. If we assume that the above statement is false, all the values x_i are strictly less than the average A:
   x₁< A, x₂ < A, ..., x_n< A.
   Therefore,

   x1+x2+···+xn<

   nA n

   =A,

   which yields a contradiction:

   A =

   x1+x2+...+xn n

   < A

   Conclusion: at least one of x₁, x₂,..., x_n is greater than or equal to A.
   
   
3. Prove that (2)^1/3 is not a rational number.
   Let's do a proof by contradiction, assuming that (2)^1/3 is rational. If this is the case, we can write (2)^1/3 = p/q, where p and q are integers that are relatively prime.

   (2) 1/3	=	p q
   2	=	( ( ( ( p q ) ) ) ) 3
   2	=	p3 q3
   2q3	=	p3

   From this, we know that p³ must be even, and since an odd number times an odd number is odd, p must be even. It follows that we can write p=2n, for some integer n. Thus, 2q³ = p³ = 8n³, which means that q³ = 4n³. By the same reasoning as above, q is also even. This is in contradiction with the fact that they are not relatively prime.
   
   Conclusion: (2)^1/3 is not a rational number.
4. Any positive integer can be written as the sum of the squares of two integers.
   This is false because 7 cannot be written as the sum of the squares of two integers. As 1²+1² = 2, 1²+2² = 5, 1²+3² = 10, 2²+2² = 8, and all other combinations are greater. Thus, it is false that any positive integer can be written as the sum of the squares of two integers.
5. The product of two rational numbers is rational.
   Since both numbers are rational, we can write them as p₁/q₁ and p₂/q₂. The product is than p₁/q₁× p₂/q₂ = p₁p₂/q₁q₂. And, since an integer times another integer is always an integer, p₁p₂ and q₁q₂ in p₁p₂/q₁q₂ are both integers. Thus, by definition, p₁p₂/q₁q₂ is a rational number.
6. The sum of two rational numbers is rational.
   Since both numbers are rational, we can write them as p₁/q₁ and p₂/q₂. The sum is than p₁/q₁+p₂/q₂ = p₁q₂+q₁p₂/q₁q₂. Since an integer times another integer is always an integer, p₁q₂, q₁p₂ and q₁q₂ in p₁q₂+q₁p₂/q₁q₂ are all integers. Furthermore, since an integer plus another integer is always an integer, p₁q₂+q₁p₂/q₁q₂ is a rational number.
7. The product of two irrational numbers is irrational.
   This is false, as a counterexample, the product of the irrational number (2)^1/2 by itself is 2, which is obviously rational.
8. The sum of a rational number and an irrational number is irrational.
   Let's do a proof by contradiction. Assume we have a rational x and an irrational y such that the sum z=x+y is rational. Then, y=z-x. But we know that the difference of two rational numbers is rational. Therefore, y is rational, which is in contradiction with our hypothesis. QED.

Homework assignment 02

Homework assignments

Homework assignment 04