CmSc 180 Discrete Mathematics Name: ______

Final Exam

I. Propositional and Predicate logic

1. Fill in the corresponding truth values (T or F) of the expressions

P / Q / expression / Value
T / T / ¬P Λ Q
T / F / P V ¬ Q
F / T / ¬P  Q
F / F / ¬P → Q

2. Complete the logical identities:

P Λ P =

P Λ F =

P Λ T =

P V P =

P V T =

P V F =

P V ~P =

P Λ ~P =

  1. Represent as a propositional expression the sentence below, find its negation using De Morgan's laws, and translate in English the negation:

If the results are negative there is an error in the input or there is an error in the program.

Use the propositions P, Q and R:

P: The results are negative

Q: There is an error in the input

R: There is an error in the program

Expression:

Negation:

Translation:

  1. Match the disjunctive representations of the following conditional statements

P → Q P V Q

~P → Q P V ~Q

P → ~Q~P V ~Q

~P → ~Q~P V Q

  1. For the implication ~P → Q indicate which of the following expressions is its contrapositive, its converse and its inverse (circle the correct one):

Contrapositive:P → Q, ~Q → P, P → ~Q, ~P → ~Q, ~Q → ~P, Q → ~P

Inverse: P → Q, ~Q → P, P → ~Q, ~P → ~Q, ~Q → ~P, Q → ~P

Converse: P → Q, ~Q → P, P → ~Q, ~P → ~Q, ~Q → ~P, Q → ~P

6. Determine whether the following arguments are valid or invalid:

a. Premises:

  1. If it is stormy classes will be cancelled and the offices will be closed.
  2. It is stormy.

Therefore the offices are closed

ValidInvalid

b. Premises:

  1. If it is stormy classes will be cancelled and the offices will be closed.
  2. Classes are not cancelled

Therefore it is not stormy

ValidInvalid

d. Premises:

  1. If I work all night on this homework, I can answer all the exercises.
  2. If I answer all the exercises I will understand the material.

Therefore

If I don't work all night over this homework I will not understand the material.

ValidInvalid

e. Premises:

1. If Adams gets a Christmas bonus he will buy a new stereo or he will repair his car.

2. Adams doesn't buy a new stereo, but he repairs his car.

Therefore Adams has received a Christmas bonus.ValidInvalid

f. Premises:

  1. If my ceiling is not fixed, I will not pay the rent.
  2. If my ceiling is fixed we will have a party
  3. We don't have a party

.

Therefore I don't pay the rent. ValidInvalid

7. You are about to leave for school in the morning and discover you don’t have your glasses. You know the following statements are true:

a. If my glasses are on the kitchen table then I saw them at breakfast.

b. I was reading the newspaper in the living room or I was reading the newspaper in the kitchen.

c. If I was reading the newspaper in the living room then my glasses are on the coffee table.

d. I did not see my glasses at breakfast

e. If I was reading my book in bed, then my glasses are on the bed table.

f. If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table.

Where are the glasses?

Hints.The sentences above contain the following atomic statements represented by propositional variables

A = My glasses are on the kitchen table

B = My glasses are on the coffee table

C = My glasses are on the bed table

D = I was reading the newspaper in the kitchen

E = I was reading the newspaper in the living room

F = I was reading my book in bed

G = I saw my glasses at breakfast

1. Represent the sentences by propositional expressions using the variables above.

2. Using the inference rules of modus ponens, modus tollens and disjunctive syllogism

find out which of the statements A, B, or C can be concluded.

Write the solution as a sequence of arguments in the following way;

(use the abbreviations MT: modus tollens, MP: modus ponens, DS – disjunctive syllogism)

Like this:

g) from a) and d) by MT => ~A

h) from g) and …. by …. => ….

Etc.

8. Which one of the following statements is logically equivalent to the following statement: ``If you are not part of the solution, then you are part of the problem"

(Circle the correct answer)

a. If you are part of the solution, then you are not part of the problem.

b. If you are not part of the problem, then you are part of the solution.

c. If you are part of the problem, then you are not part of the solution.

d. If you are not part of the problem, then you are not part of the solution.

9. There is an island where two kinds of people live: knights that always tell the truth, and knaves that always lie. You visit the island and are approached by two natives A and B. A says: B is a knight. B says: A and I are of opposite type.What are A and B?

Hint: Assume that A is a knight and see what conclusions can be made. Assume that A is a knave and see what conclusions can be made.

In problems 10 and 11 translate the sentences in quantified expressions of predicate logic, write down the negated expression and then translate the negated expression in English.

10. All students need financial aid.

student(x), needs_aid(x)

expression:

negation:

translation:

11. Some horses do not fly

horse(x), fly(x)

expression:

negation:

translation:

12. Consider the expression:

 n (integer(n)  even_square(n)  even(n))

Which of the following sentences are equivalent to the above expression:

  1. All integers have even squares and are even.
  2. Given any integer whose square is even, that integer is itself even.
  3. There are some integers whose square is even.
  4. Any integer with an even square is even.
  5. All even integers have even squares.

II. Sets

13. True or False?

True / False
1  {2,3,1,5}
{1}  {2,3,1,5}
{1}  {2,3,1,5, {1}}
{1}  {2,3,1,5}
{1}  {2,3,{1},5}
{1,6}  {2,3,1,5}
{1,5}  {2,3,1,5}
{1}  {1, {1}}
{1}  {1, {1}}
  {1 ,2}
  {1 ,2}
  { , 1 ,2}
  { , 1 ,2}

14. Complete the identities below

a. A  ~A =Complementation Law

b A  ~A =Exclusion Law

c. A  E =Identity Laws

d. A  Ø =

e. A  E =Domination Laws

f. A  Ø =

g. A  A =Idempotent Laws

h. A  A =

i. ~(A  B) =De Morgan's Laws

j. ~(A  B) =

15. Let the universal set be the set R of all real numbers and let

A = {x  R | -2  x  1}, B = { x  R | -1 < x < 3}.

Find each of the following:

A  B =

A  B =

Ac =

Bc =

AcBc =

AcBc=

(A  B)c =

(A  B)c =

16.Writethe power set of A = {, {}}, B = {, 1, {,1}}

17. Let the universal set be all people. Within the universal set,

A is the set of all computer programmers,

B is the set of all accountants,

C is the set of all women,

D is the set of all people of age 40 and older.

Using set operations, write the expressions for the following sets:

  1. The set of all male computer programmers who are not accountants
  2. The set of all female accountants under 40
  3. The set of all female computer programmers of age 40 and older and all accountants under 40.

18. Represent by Venn diagrams (shadow the appropriate area):

a. (B  C) – A


  1. (A  C)  C)


  1. (A - B)  (B - C)



19. For each Venn diagram below write down the set expression corresponding to the shaded area


a) b)



c) d)

20. Let A = {1,2,3,4,5,6,7}. For each set below determine whether it is a partition of A or not. If the answer is negative, explain why the set is not a partition:

  1. {{1,2},{3,4,5,6},{7}}
  2. {{1,2},{3,4,5,6}, 7 }
  3. {{1,2}{2,4,5},{3,6,7}}
  4. {{2,3,4},{1,5,7}}

III. Counting

21. Five speakers are scheduled to address a convention. In how many different orders can they appear?

22. A baseball team has 2 catchers, 4 starting pitchers and 5 relief pitchers. A catcher, starting pitcher and relief pitcher must be chosen for an all-star game. In how many ways can this be done?

23. A foreman has a team of 15 workers. He needs 5 of them to unload a truck full of bricks, 3 to start mixing cement and 4 to clean up yesterday’s mess. In how many ways can he create the work groups?

24. A student honor society has 10 juniors and 13 seniors. According to its bylaws, the president and treasurer must be seniors, and the vice-president and secretary must be juniors. In how many ways can the four offices be filled by four different students?

25. In how many ways can 8 women be paired with 8 of 12 men at a dance?

26. From among a group of 6 men and 9 women how many three-member committees contain

a. only men or only women?

b. exactly one woman?

c. at least one woman?

27. How many 8-bit strings contain 6 or more 1s?

28. Five male college students each are bringing a date to the orchestra concert. The men bought tickets for 10 consecutive seats in row 17. In how many ways can all college students be seated at the concert ifeach male must be seated next to his date?

Optional problems:

Prove that the following formulas are true for all positive integral values of n.
Use mathematical induction. Choose 1) or 2)

  1. 1 + 3 + 5 + …. + (2n-1) = n2 (5% increase of the final grade)
  1. 1·2 + 2·3 + 3·4 + … + n(n+1) = n(n+1)(n+2)/3

(the dot stands for multiplication) (8% increase of the final grade)

1