CmSc 175 Discrete Mathematics

Unit Exam 1 Solution

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 / F
T / F / ¬P V ¬Q / T
F / T / P →¬Q / T
F / F / ¬P → Q / F

2. Logical identities - fill in the right side (P, T, or F)

P Λ P =P

P V P =P

P V ~P =T

P Λ ~P =F

P V T =T

P Λ T =P

P V F =P

P Λ F =F

De Morgan’s Laws:

~( P V Q) = ~P Λ ~Q

~( P Λ Q) = ~P V ~Q

  1. Fill in the table below

Conditional / Disjunctive representation / Contrapositive / Converse / Inverse
~P → Q / P V Q / ~Q → P / Q → ~P / P → ~Q
~Q → ~P / Q V ~P / P → Q / ~P → ~Q / Q → P
  1. Represent the following disjunctions as conditionals

P V ~Q Q → P = ~P → ~Q

P V Q ~P → Q = ~Q → P

  1. Rephrase each of the following sentences as “if – then” sentences

Not having a business office hold is a necessary condition to register for classes

If you have a business hold you cannot register for classes

If you registered for classes you did not have a business hold.

A syntax error is a sufficient condition for a program not to run

If there is a syntax error the program will not run

If the program runs there is no syntax error

I will not succeed unless I find a sponsor

If I don’t find a sponsor I will not succeed

If I have succeeded I have found a sponsor

The program will terminate only if there are no infinite loops

If the program terminates there are no infinite loops

If there are infinite loops the program will not terminate

  1. 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"

Hint: represent the given sentences in propositional logic and determine which expressions are equivalent to the given one.

Let P = you are part of the problem, S = you are part of the solution

The given sentence is: ~S → P

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

S → ~P inverse, not equivalent

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

~P→ S contrapositive, equivalent

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

P→ ~S converse not equivalent

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

~P → ~S not equivalent

  1. Write the negations (in English) of the following sentences
  1. If you leave early you will avoid the traffic

You leave early but you don’t avoid the traffic

  1. I will not go to the party if Abel is invited

Abel is invited but I still go to the party

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

a. Some birds don't fly

bird(x), fly(x)

expression:  x bird(x) ~fly(x)

negation:  x bird(x) fly(x)

translation: All birds fly

b. No games are boring

game(x), boring(x)

expression:  x game(x)  ~boring(x)

negation:  x game(x) boring (x)

translation: Some games are boring

e. All healthy and happy people are wise

happy(x), healthy(x), wise(x)

expression:  x healthy(x) happy(x)  wise(x)

negation:  x healthy(x) happy(x)  ~wise(x)

translation: Some healthy and happy people are not wise

  1. Represent the following arguments in propositional logic and determine if they are valid or invalid. If valid, state the inference rules. If invalid, determine the type of error and show values for the propositional variables such that the premises are true but the conclusion is false:

a. Premises:Valid Invalid

inverse error

1. If John is playing, the team will win.

2. If the team does not win, the trip will be postponed.

3. John is playing.

Therefore the trip is not postponed

let P = John is playing, Q = the team will win, R = the trip will be postponed

The argument is:

P Q

~Q R

P

------

therefore ~R

Invalid, inverse error.

Let R = F, P = T, Q = T.

For these values the premises are true, but the conclusion is false

b. Premises: Valid Invalid

MT

  1. If you don’t leave early you will be late.
  2. If you oversleep you will not leave early.
  3. You are not late.

Therefore you have not overslept

let P = you will leave early, Q = you will be late, R = you oversleep

The argument is:

a. ~P Q

b. R ~P

c. ~Q

------

therefore ~R

From a) and c) by MT we conclude P, combining with b) by MT we conclude ~R

  1. Prove that s is true given the following premises :
  1. p  q
  2. u  ~p
  3. s V r
  4. ~u  ~r
  1. p From (1) by conjunctive simplification
  1. ~u From (2), (5) and MT
  1. ~r From (6), (4) and MP
  1. s From (5), (3) and DS

Extra credit problem:

Taking the long view on your education, you go to the Prestige corporation and ask what you should do in college to be hired when you graduate.

The Personnel Director replies that you will be hired only if you major in mathematics or computer science, get a B average or better, and take accounting.

You do, in fact, graduate as a math major, get a B+ average, and take accounting.

You return to Prestige Corporation, make a formal application, and are turned down.

Did the Personnel Director lie to you? Explain your answer.

The director did not lie.

Let H = the person is hired

R = the listed requirements are met

The director said: H only if R, equivalent to H  R

When H is false, the conditional is true.