CS70-Homework 1 Solved

 

Classify the following statements as being one of the following, where x and y are arbitrary propositions, and justify your answers (e.g., using a truth table)

•   True for all combinations of x and y (Tautology)

•   False for all combinations of x and y (Contradiction)

•   Neither

(a)    x∧(x =⇒ y)∧(¬y)

(b)   x =⇒ (x∨y)

(c)    (x∨y)∨(x∨¬y)

(d)   (x =⇒ y)∨(x =⇒ ¬y)

(e)    (x∨y)∧(¬(x∧y))

(f)     (x =⇒ y)∧(¬x =⇒ y)∧(¬y)

2      Miscellaneous Logic
(a)    Let the statement, (∀x ∈ R)(∃y ∈ R) G(x,y), be true for predicate G(x,y).

For each of the following statements, decide if the statement is certainly true, certainly false, or possibly true, and justify your solution. (If possibly true, provide a specific example where the statement is false and a specific example where the statement is true.)

(i)        G(3,4)

(ii)      (∀x ∈ R) G(x,3)

(iii)     ∃y G(3,y)

(iv)     ∀y ¬G(3,y)

(v)      ∃x G(x,4)

(b)   Give an expression using terms involving ∨,∧ and ¬ which is true if and only if exactly one of X,Y, and Z is true.

3       Propositional Practice
Convert the following English sentences into propositional logic and the following propositions into English. State whether or not each statement is true with brief justification.

(a)             There is a real number which is not rational.

(b)             All integers are natural numbers or are negative, but not both.

(c)             If a natural number is divisible by 6, it is divisible by 2 or it is divisible by 3.

(d)             (∀x ∈ R)(x ∈ C)

(e)             (∀x ∈ Z)(((2 | x)∨(3 | x)) =⇒ (6 | x)) (f) (∀x ∈ N)((x 7) =⇒ ((∃a,b ∈ N)(a+b = x)))

4      Proof by?

(a)    Prove that if for any two integers x and y, if 10 does not divide xy, then 10 does not divide x and 10 does not divide y. In notation: (∀x,y ∈ Z) (10 - xy) =⇒ ((10 - x) ∧ (10 - y)). What proof technique did you use?

(b)   Prove or disprove the contrapositive.

(c)    Prove or disprove the converse.

5      Prove or Disprove
(a)    (∀n ∈ N) if n is odd then n2 +2n is odd.

(b)   (∀x,y ∈ R) min(x,y)=(x+y−|x−y|)/2.

(c)    (∀a,b ∈ R) if a+b ≤ 10 then a ≤ 7 or b ≤ 3.

(d)   (∀r ∈ R) if r is irrational then r+1 is irrational.

(e)    (∀n ∈ Z+) 10n2 n!.

6       Preserving Set Operations
For a function f, define the image of a set X to be the set f(X)= {y | y = f(x) for some x ∈ X}. Define the inverse image or preimage of a set Y to be the set f−1(Y)= {x | f(x) ∈ Y}. Prove the following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.

Hint: For sets X and Y, X =Y if and only if X ⊆Y and Y ⊆ X. To prove that X ⊆Y, it is sufficient to show that (∀x)((x ∈ X) =⇒ (x ∈Y)).

(a) f−1(A∪B)= f−1(A)∪ f−1(B). (b) f−1(A∩B)= f−1(A)∩ f−1(B).

(c)     f−1(A\B)= f−1(A)\ f−1(B).

(d)    f(A∪B)= f(A)∪ f(B).

(e)     f(A∩B) ⊆ f(A)∩ f(B), and give an example where equality does not hold.

(f)      f(A\B) ⊇ f(A)\ f(B), and give an example where equality does not hold.