Problem 2) In this problem, all variables range over the set of all integers. Recall that the relation a | b (read "a divides b") is defined as
1. Formulate the following statement in English and prove that it is true (for all x, a, b):
. . .
Using common precedence rules, the above statement should be interpreted as
. . .
2. Same as (1), but for the statement
. . .
3. Prove again the statement in (2), but rather than proving it from scratch, give a proof using the statement in part (1).
Problem 3) For each of the following statements:
. . .Formulate the statement in prepositional logic. You may use all of the
. . .standard logic connectives and quantifiers. You may also use integer
. . .constants (1, 2, 3, etc.), arithmetic operations (+, ×, etc.), the
. . .predicate

, and the relation a|b.
. . .State if the statement is true or false.
. . .Prove your answer correct; i.e., prove either the statement or the
. . .negation of the statement. In all statements, the variables range of
. . .the set of nonnegative integers.
1. The product of any two odd integers is odd.
2. For any two numbers x and y, the sum x + y is odd if and only if the product x × y is odd.
3. For all integers a, b, and c, if a divides b and b divides c, then a divides c.
Problem 4) Also in this problem, all variables range over the nonnegative integers. Recall the definition of "prime":
. . .\, =\, ''\left(n\, >\, 1\right)\, \wedge\, \left(\forall m.(m|n)\, \rightarrow\, (m=1)\, \vee\, (m=n)\right)'';)
i.e., a number bigger than 1 is prime if and only if it is only divisible by 1 and itself. A number is composite if it can be written as the product of smaller numbers:
. . .\, =\, ''\exists a.b(a<n)\, \wedge\, (b<n)\, \wedge\, (n=a\times b)'')
Prove that any number bigger than 1 is prime if and only if it is not composite. You can break up your proof into two parts as follows:
. . .1. First prove that for any n > 1, if n is prime, then n is not composite.
. . .2. Next prove that for any n > 1, if n is not composite, then n is prime.
In the solution to this problem you can use (without proof) the fact that for any positive integers x and y, if x | y, then x
< y. Remember that your solution will be graded both for correctness and clarity. This is especially important for this problem, as the proof involved is a bit longer than the proofs in the previous problems.