Math

Do not submit this page:

Logical Equivalences and Rules of Inference

Propositional Equivalence Name p q p q   Definition of Conditional

p T p

p F p

 

 

Identity Laws

p T T

p F F

 

 

Domination Laws

p p p

p p p

 

 

Idempotent Laws

 p p   Double Negation Law

p q q p

p q q p

  

  

Commutative Laws

   

   

p q r p q r

p q r p q r

    

    

Associative Laws

     

     

p q r p q p r

p q r p q p r

     

     

Distributive Laws

 

 

p q p q

p q p q

    

    

De Morgan’s Laws

 

 

p p q p

p p q p

  

  

Absorption Laws

p p T

p p F

 

 

Negation Laws

   p q p q q p     Definition of Biconditional

Do not submit this page:

Propositional Rules of Inference Name p

p q

q







Modus Ponens

q

p q

p









Modus Tollens

p q

q r

p r







 

Hypothetical Syllogism

p q

p

q









Disjunctive Syllogism

p

p q



 

Addition

p q

p







Simplification

p

q

p q



 

Conjunction

p q

p r

q r





 

 

Resolution

Math 11: Final Exam

Name: ____________________________ ID:____________________________________

1. a) Using a truth-table, show that    p q r p q r    

b) Using logical equivalences, show that    p q r p q r    

2. Domain = bit strings (all strings of 0’s and 1’s),  : starts with a 0 and ends with a 0S s s s

a) Find a Finite State Automata for S.

b) Find a regular expression for S.

3. a) Give a direct proof:

If 1n is odd, then 1n is odd.

b) Give a direct proof or a proof by contraposition:

If 2n is odd, then n is odd.

4. Recall a deck of cards has four suits (including hearts) and there are 13 cards in each suit.

a) What is the probability that all the cards in a five card hand will be hearts?

b) What is the probability that all the cards in a five card hand will be the same suit?

c) What is the probability that a five card hand will have exactly three cards of the same suit?

5. Use Djikstra’s Algorithm to find the shortest path from 0 to 6. Show enough work to convince me you

understand the process.

6. a) Find  gcd 259,70 with E’s algorithm.

b) Use your answer from a) to find integers a and b such that 259 70 7a b    . Correct numbers without using your answer above = no credit.

c) Find integers a and b such that 259 70 14a b   

6 d) Solve 25 16mod32x  . You answer should be positive and less than 32.

e) Find the smallest positive x that satisfies:

200x  , 1mod3x  , 4mod5x  and 6mod7x 

Extra Credit (3 percentage points): Upload this exam to gradescope on time without help.

If you are uploading your own pictures, problems must be assigned to the correct pages and your submission

needs to be well lit – no shadows.