Midterm Exam Practice Questions (and answers)

DISCLAIMER: THESE QUESTIONS DO NOT NECESSARILY REPRESENT WHAT WILL BE ON THE MIDTERM.

1. Are (p->q)->r and p->(q->r) logically equivalent? Justify your answer by using the rules of logic to simplify both expressions and also by using truth tables.
2. Define "rule of inference".
3. Classify each argument below as valid or invalid. If valid, give a proof. If invalid, give a counter-example.

   (a)     p->(q & r)
           not q
           ---------
           not p
   
   (b)     p->(q v r)
   	not q
           ---------
      	not p
   
   

4. Say whether the following are true or false. The universe is Z, the set of integers. Let E(x) = "x is even" and O(x) = "x is odd" and P(x) = "x is prime".
   1. for-all x [E(x)-> E(3x)]
   2. there-exists x [P(x) & (x > 2) & E(x)]
   3. ¬ there-exists x [E(x) & O(x)]
   4. ¬ for-all x [P(x) -> O(x)]
   5. for-all x ¬ [E(x) & O(x)]
   6. there-exists x [E(x) -> O(x)]
5. Prove using the rules of inference. Label each step.

   (a)  Xavier is a black cat.		(THIS ONE IS TRICKY)
        Xavier is not bad luck.
        Therefore not all black cats are bad luck.
   UNIVERSE = CATS.
   (b) All cats are pretty.
       All pretty animals are nice.    (this is not really true you know)
       Therefore all cats are nice.   (this is not true, but given the premises it would be true)
   UNIVERSE = animals 
   (c) All fun cities have amusement parks.
       Some city in Georgia is fun.
       Therefore some city in Georgia has an amusement park.
   UNIVERSE = cities.
        
   

6. Guess the formula for : sum from 0 to n of 1/2ⁱ = 1 + 1/2 + 1/4 + 1/8 + ... + 1/2ⁿ and prove it by induction. If you can't guess the formula it is in the solution with a link to the proof (high-tech).
   Hint: Try to guess the formala by making a table like:

        n   sum   guessed formula
       -----------------------------
        0    1
        1 1+1/2 = 3/2
        2 1+1/2 +1/4 = 7/4
        .
        .
        .
   

7. Answer the following counting questions.
   1. Two children have 10 videos. How many ways can they pick two videos to watch, one after the other, repeats allowed while their mother works on the computer?
   2. One student has 4 subjects to study for Monday. She plans to spend 30 minutes on each. How many ways can she order her subjects?
   3. How many necklaces can be made from 5 identical blue beads, 3 identical red beads, and 4 identical green beads?
   4. How many binary strings of length n have at least one 1 and at least one 0?
   5. How many ternary strings (strings of 0's, 1's and 2's) of length n do not contain any 2's? (trick)
   6. How many ternary strings of length n start and end with a 2?
   7. From 4 students, 4 professors, and 10 administrators how can you pick a board of 1 student, 2 professors and 5 administrators?
   8. There are 5 social event on a weekend and you only have time for 2. How many ways can you pick 2 to go to (assume they are all at different times)?

Solutions:

1. No. Using rules of logic we see that:

   (p->q)->r <=> not(p->q) V r			a->b <=>not a V b
             <=> not(not p V q) V r		same as above
             <=> (not not p & not q) V r		DeMorgan's Law
             <=> (p & not q) V r			Double Negations
             <=> (p V r) & (not q V r)		Distributive Law 
   p->(q->r) <=> not p V (q->r)			a->b <=> not a V b
   	  <=> not p V (not q V r)		same
   	  <=> not p V not q V r			associative
   

   This would not make a good test question because it is not crystal clear that these are not equivalent. But you can still do it as an exercise in simplifying. Using truth tables we get:

   p	q	r	p -> q	(p->q)->r	q->r	p->(q->r)
   0	0	0	1	0	1	1
   0	0	1	1	1	1	1
   0	1	0	1	0	0	1
   0	1	1	1	1	1	1
   1	0	0	0	1	1	1
   1	1	0	0	1	1	1
   1	0	1	0	1	0	0
   1	1	1	0	1	1	1

   So you can see they are not equivalent.

2. (a)  VALID.  Proof:
        1) p->(q & r) 			given
        2) not (q & r) -> not p       	p->q <=> not q -> not p
        3) (not q V not r) -> not p	3 and DeMorgan's Law
        4) not q				given
        5) not q V not r			4 and Disjunctive Amplification
        6) not p				5 and 3 and Modus Ponens
   
   (b) INVALID.  To find a counter-example look at the truth table.
      p  q  r   p->(q V r)   (p->(q V r)) & not q  [<--that stuff]->not p
      0  0  0   1			1			1
      0  0  1   1			1			1
      0  1  0   1			0			1
      0  1  1   1			0			1
      1  0  0   0			0			1
      1  0  1   1			1			0
      1  1  0   1			0			1
      1  1  1   1			0			1
   The last column should be a all 1's if the argument is valid.  It is not
   so any 0 rows will be counter-examples.  There is one 0 row: p = 1, q = 0, r = 1.
   Check that it is a counter-example.  The hypotheses: p ->(q V r) and not q must
   be true.  Not q is not 0 =1 which is good.
            p->(q v r) is 1 ->(0 v 1) which is 1->1 which is true.
   Now we want the conclusion to be false.  The conclusion is not p but p in this
   counter-example is true so not p is false.  
   

3. Given below is the English equivalent of the logical expression and its truth value.
   1. For all integers x, if x is even then 3x is even.: TRUE
   2. There exists an integer x such that x is prime and x > 2 and x is even. FALSE
   3. There does not exist an integer x such that x is both even and odd. TRUE
   4. All integers x are not both even and odd. TRUE
   5. There exists an integer x such that if x is even then x is odd. TRUE. This is an example where we do not get the result we intended while using -> and there-exists. Consider x = 1. E(1) is FALSE so E(1)->O(1) is FALSE->TRUE which is TRUE. So the statement is true. (in a meaningless way).

4. (a)  Xavier is a black cat.			
        Xavier is not bad luck.		
        Therefore not all black cats are bad luck.
   Let B(x) = "x is black" and L(x) = "x is bad luck".
   Proof: The conclusion we are trying to prove is: not for all x [B(x) ->L(x)]
   
   The tricky part here is going from what we are given, which is basically
     there-exists x [B(x) & not L(x)]
   to what we are trying to prove: not for-all x [B(x)->L(x)].
   These two are equivalent.  You can see this by doing double negation and DeMorgan's Law.
   It is easier to see if you start from the "not for-all x [B(x)->L(x)]" but in the proof
   we have to go the other direction.  This would  be extra credit on a test.
   
        1 B(Xavier)			 given
        2 not L(Xavier)			 given
        3 B(xavier) & not L(Xavier) 	 1 and 2 and conjunction
        4 there-exists x [B(x) & not L(x)]	 3 and existential generalization
        5 not for-all x not [B(x) & not L(x)]  4 and double negation
        6 not for-all x [not B(x) V L(x)]	    5 and DeMorgan's Law
        7 not for-all x [B(x) -> L(x)]         6 and a-> b <=> not a V b.
   UNIVERSE = CATS.
   (b) All cats are pretty.
       All pretty things are nice.
       Therefore all cats are nice.   
   Let P(x) = "x is pretty" and N(x) = "x is nice" and C(x) = "x is a cat".
   The conclusion to show is : for-all x[C(x)->N(x)].
   
   Proof:
      1) for-all x [C(x)->P(x)]  		given
      2) for-all x [P(x) -> N(x)] 		given
      3) C(m)->P(m)  for general animal m  Universal Generalization and 1
      4) P(m)->N(m) 			2 and Universal Specification
      5) C(m)->N(m)			4 and 5 and law of the syllogism
      6 for-all x [C(x)->N(x)]		5 and Universal Generalization
   
   (c) All fun cities have amusement parks.
       Some city in Georgia is fun.
       Therefore some city in Georgia has an amusement park.
   	UNIVERSE = cities.
   Let F(x) = "x is fun" and A(x) = "A has an amusement park" and G(x) = "x is in Georgia".
   We are trying to show there-exists x [G(x) & F(x)].
   
   Why did we make G(x) a predicate when we didn't make "Pat Summitt" a predicate in the
   quiz problem?  Because "georgia" is not a memeber of the Universe (cities).  "in Georgia"
   is an attribute of a city.  A city may be in Georgia or not in Georgia.  So "in Georgia"
   is a predicate.
   
   Proof:
       1) for-all x [F(x) -> A(x)]		given
       2) there-exists x [G(x) & F(x)]	given
       3) G(c) & F(c) for SOME c 		2 and existential specification
       4) F(c)->A(c)			1 and Universal Specification
       5) G(c)				3 and law of conjunction
       6) F(c)				ditto
       7) A(c)				4 and 6 and Modus Ponens
       8) G(c) & A(c)			5 and 7 and conjunction
       9 there-exists x [G(x) & A(x)]	8 and existential  generalization
   

5. The formula is 2 - 1/2ⁿ . Click Here to see the proof by induction.
6. 1. There are 10 ways to pick the first video and 10 ways to pick the second so 10*10 =100.
   2. 4!
   3. This is a problem of permutations with repetition: 12!/(3!4!5!).
   4. 2ⁿ - the number with only 1's (1) or only 0's (1) so 2ⁿ - 2
   5. A ternary string with no 2's is a binary string so 2ⁿ.
   6. There are 3ⁿ ternary strings of length n. Since the first and last positions must be 2, there are n-2 free positions. The answer is: 3^n-2.
   7. 4*C(4,2)*C(10,5) = 4*(4!/2!2!)*(10!/5!5!) = 4*6*252 = 6048 (I think).
   8. C(5,2) = 10.