Homework assignment 01

Homework assignments

Homework assignment 03

1.2   Propositional Logic

1. Prove the following argument using propositional logic:
   (B -> C)]/\ (A \/ D')/\ B -> (D -> C)
   We use the deduction method to rewrite the argument with D as further hypothesis and C as conclusion.

   1.	A -> (B -> C)	hyp
   2.	A \/ D'	hyp
   3.	B	hyp
   4.	D	hyp
   5.	D' \/ A	comm,2
   6.	D -> A	imp,3
   7.	A	mp,4,6
   8.	B -> C	mp,1,7
   9.	C	mp,3,8

2. Given (A' -> B') /\ B /\ (A -> C) -> C, use propositional logic to prove that the argument is valid.

   1.	A' -> B'	hyp
   2.	B	hyp
   3.	A -> C	hyp
   4.	B -> A	contraposition,1
   5.	A	mp,2,4
   6.	C	mp,5,6

3. Given [A -> (B -> C)]-> [B -> (A -> C)], use propositional logic to prove that the argument is valid.

   1.	A -> (B -> C)	hyp
   2.	A' \/ (B -> C)	imp,1
   3.	A' \/ (B' \/ C)	imp,2
   4.	A' \/ (C \/ B')	comm,3
   5.	(A' \/ C) \/ B'	ass,4
   6.	(A -> C) \/ B'	imp,5
   7.	B' \/ (A -> C)	comm,6
   8.	B -> (A -> C)	imp,7

4. Given (A /\ B) -> (A -> B')', use propositional logic to prove that the argument is valid.

   1.	A /\ B	hyp
   2.	((A /\ B)')'	dn,1
   3.	(A' \/ B')'	De Morgan,2
   4.	(A -> B')'	imp,3

1.3   Quantifiers, Predicates, and Validity

1. Using the predicate symbols shown and appropriate quantifiers, write each English language statements as a predicate wff. (The domain is the whole world.)
   

   B(x) is ``x is a bee.''

   F(x) is ``x is a flower.''

   L(x,y) is ``x loves y.''

   1. All bees love all flowers.
      (for all x)[B(x)-> (for all y)(F(y)-> L(x,y))]
   2. Some bees love all flowers.
      (there exists x)[B(x) /\ (for all y)(F(y)-> L(x,y))]
   3. All bees love some flowers.
      (for all x)[B(x) -> (there exists y)(F(y) /\ L(x,y))]
   4. Every bee hates only flowers.
      (for all x)(for all y)[B(x) /\ L(x,y)' -> F(y)]
   5. Only bees love flowers.
      (for all x)[(there exists y)(F(y) /\ L(x,y)) -> B(x)]
   6. Every bee loves only flowers.
      (for all x)(for all y)[B(x) /\ L(x,y) -> F(y)]
   7. No bee loves only flowers.
      (for all x)[(for all y)(L(x,y)-> F(y)) -> B(x)']
      [(there exists x)[(for all y)(L(x,y)-> F(y))]]'
   8. Some bees love some flowers.
      (there exists x)[B(x) /\ (there exists y)(F(y) /\ L(x,y))]
   9. Some bees love only flowers.
      (there exists x)[B(x) /\ (for all y)(L(x,y) -> F(y))]
   10. Every bee hates some flowers.
       (for all x)[B(x) -> (there exists y)(F(y) /\ L(x,y)')]
   11. Every bee hates all flowers.
       (for all x)[B(x) -> (for all y)(F(y) -> L(x,y)')]
   12. No bee hates all flowers.
       (for all x)[B(x) -> (there exists y)(F(y) /\ L(x,y))]
2. Write the negation of each of the following.
   1. Statement: Only students eat pizza.
      Negation: There exists something, which is not a student, that eats pizza.
   2. Statement: Every student eats pizza.
      Negation: There exists a student which does not eat pizza.
   3. Statement: Some students eat only pizza.
      Negation: No student only eats pizza.
3. Decide whether each of the following wffs is valid or invalid. Justify your answer.
   1. (there exists x)A(x) <-> ((for all x)[A(x)]')'
      The above statement is a simple case of double negation. The first negation of (there exists x)A(x) is (for all x)[A(x)]', the second is merely ((for all x)[A(x)]')', thus (there exists x)A(x) <-> ((for all x)[A(x)]')'.
   2. (for all x)P(x) \/ (there exists x)Q(x) -> (for all x)[P(x) \/ Q(x)]
      Invalid. Take as domain of interpretation the integers, P(x) is ``x is positive'', and Q(x) is ``x is negative''. The hypothesis is then true, but not the conclusion.
      
      
   3. (for all x)A(x) -> ((there exists x)[A(x)]')'
      The above statement, like 17(a), is a simple case of double negation. The first negation of (for all x)A(x) is (there exists x)[A(x)]', the second is merely ((there exists x)[A(x)]')', thus (for all x)A(x) -> ((there exists x)[A(x)]')'.
   4. (for all x)[P(x) \/ Q(x)] -> (for all x)P(x) \/ (there exists y)Q(y)
      Assume every element of the domain verifies P or Q. There are two cases:
      • At least one element verifies Q: (there exists y) Q(y)
      • No element satisfies Q. But then they all need to satisfy P: (for all x) P(x).

1.4   Predicate Logic

1. Consider the wff (for all y)(there exists x)Q(x,y) -> (there exists x)(for all y)Q(x,y).
   1. Find an interpretation to prove that this wff is not valid.
      In the DOI of integers, the initial statement: for all integers y, there exists an integer x which is larger. Is not the same as: there exists an integer x which is larger than all integers y.
   2. Find the flaw in the following ``proof'' of this wff.

      1.	(for all y)(there exists x)Q(x,y)	hyp
      2.	(there exists x)Q(x,y)	ui,1
      3.	Q(a,y)	ei,2
      4.	(for all y)Q(a,y)	ug,
      5.	(there exists x)(for all y)Q(x,y)	eg,4

      The flaw is in step 4, as Q(a,y) was deduced by ei from the wff in step 3, where y is free: the choice of a depends on y!
2. Either prove that the wff, (there exists x)[P(x) -> Q(x)]/\ (for all y)[Q(y)-> R(y)] /\ (for all x)P(x) -> (there exists x)R(x), is a valid argument or give an interpretation in which it is false.

   1.	(there exists x)[P(x)-> Q(x)]	hyp
   2.	(for all y)[Q(y) -> R(y)]	hyp
   3.	(for all x)P(x)	hyp
   4.	P(x) -> Q(x)	ei,1
   5.	Q(x) -> R(x)	ui,2
   6.	P(x)	ui,3
   7.	Q(x)	mp,4,6
   8.	R(x)	mp,5,7
   9.	(there exists x)R(x)	eg,8

3. The equivalence of Exercise 26 says that if it is false that every element of the domain has property P, then some element of the domain fails to have property P, and vice versa. The element that fails to have property P is called a counterexample to the assertion that every element has property P. Thus a counterexample to the assertion
   (for all x)(x is odd)
   in the domain of integers is the number 10, an even integer (of course, there are lots of other counterexamples to this assertion).
   
   Find counterexamples in the domain of integers to the following assertions (An integer x>1 is prime if the only factors of x are 1 and x.)
   1. (for all x)(x is negative)
      A counterexample would be 2, or any positive integer.
   2. (for all x)(x is the sum of even integers)
      A counterexample would be 5, or any odd integer.
   3. (for all x)(x is prime-> x is odd)
      The only counterexample is 2.
   4. (for all x)(x prime -> (-1)^x = -1)
      The only counterexample is 2, as it produces 1=-1.
   5. (for all x)(x prime -> 2^x-1 is prime)
      The first counterexample is 11, as 2¹¹-1 = 2047 which is not prime. Other counterexamples include: 11, 23, 29, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 101, 103, 109, 113, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 523, 541,...

Homework assignment 01

Homework assignments

Homework assignment 03