Homework 02 solution

$30.00

Description

1.4.1 Show whether each logical expression is a tautology, contradiction or neither.

(c) (p → q) ↔ p

(e) (¬p ∨ q) ↔ (p ∧ ¬q)

1.4.2 Use truth tables to show that the following pairs of expressions are logically equivalent.

(b) ¬(p ↔ q) and ¬p ↔ q

(c) ¬p → q and p ∨ q

1.4.4 Determine whether the following pairs of expressions are logically equivalent. Prove your answer. If the pair is logically equivalent, then use a truth table to prove your answer.

  1. ¬(p ∨ ¬q) and ¬p ∧ q

  1. ¬(p ∨ ¬q) and ¬p ∧ ¬q

  1. p ∧ (p → q) and p → q

  1. p ∧ (p → q) and p ∧ q

1.4.5 Define the following propositions:

  • j: Sally got the job.

  • l: Sally was late for her interview

  • r: Sally updated her resume.

Express each pair of sentences using a logical expression. Then prove whether the two expressions are logically equivalent.

  1. If Sally did not get the job, then she was late for her interview or did not update her resume.

If Sally updated her resume and did not get the job, then she was late for her interview.

  1. If Sally did not get the job, then she was late for interview or did not update her resume.

If Sally updated her resume and was not late for her interview, then she got the job.

1.5.1 (a)

Logical Statement

Steps

(p → q) ∧ (q ∨ p)

Conditional Identities

Commutative Laws

Distributive Laws

Commutative Laws

Complement Laws

q

Identity Laws

1.5.2

Logical Statement

Law

Conditional Identities

Double Negation Laws

p = p

Absorption Laws

(c) (p → q) ∧ (p → r) ≡ p → (q ∧ r)

(f) ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q

1.5.5 Show that the two sentences below are logically equivalent. Express each pair of sentences using a logical expression. Then prove whether the two expressions are logically equivalent. Note: you can assume that x and y are real numbers, so if x is not irrational, then x is rational, and if x is not rational, then x is an irrational number.

  • If x is a rational number and y is an irrational number then x-y is an irrational number.

  • If x is a rational number and x-y is an rational number then y is a rational number.

1.6.4 The domain for this problem is a set a, b,c, d. The table below shows the value of three predicates for each of the elements in the domain. For example, Q(b) is false because the truth value in row b, column Q is F.

P

Q

R

a

T

T

F

b

T

F

F

c

T

F

F

d

T

F

F

Which statements are true? Justify your answer.

  1. x P(x)

  2. x P(x)

  3. x Q(x)

  4. x Q(x)

  5. x R(x)

  6. x R(x)

1.6.5 P(x) is a predicate and the domain for the variable x is {1, 2, 3, 4}. For each of the logical expressions given, give an equivalent logical expression that does not use quantifiers.

  1. x P(x)

  1. x P(x)

1.7.6 In the following question, the domain of discourse is the set of employees of a company. Define the following predicates:

  • A(x): x is on the board of directors

  • E(x): x earns more than $100,000

  • W(x): x works more than 60 hours per week

Translate the following logical expressions into English:

  1. x (A(x) → E(x))

  2. x (E(x) ∧ ¬W(x))

1.7.7 The domain of discourse is a group working on a project at a company. Define the following predicates.

  • D(x): x missed the deadline.

  • N(x): x is a new employee.

Consider a situation in which there are five people in the group. The following table gives values for the predicates D and N for each member of the group. For example, Bert did not miss the deadline because the truth value in the row labeled Bert and the column labeled D(x) is F.

Using these values, determine whether each quantified expression evaluates to true or false. Then translate the statement into English.

Name

D(x)

N(x)

Sam

T

F

Beth

T

T

Melanie

F

T

Al

T

T

Bert

F

T

(b) ∀x ((x ≠ Sam) → N(x))

(d) ∀x (¬D(x) → ¬N(x))

(f) ∀x (¬N(x) → D(x))

English Translation: For every x, if x is not a new employee, then x missed the deadline.

1.7.10 A student club holds a meeting.

Define the following predicates:

  • M(x): person x came to the meeting on time.

  • O(x): person x is an officer of the club.

  • D(x): person x has paid his or her club dues.

The domain is the set of all members of the club. The names of the members and their truth values for each of the predicates is given in the following table. Indicate whether each expression is true or false. If a universal statement is not true, give a counterexample. If an existential statement is true, give an example.

Name

M(x)

O(x)

D(x)

Hillary

T

F

T

Bernie

F

T

F

Donald

F

T

F

Jeb

F

T

T

Carly

F

T

F

(a) ∀x ¬(O(x) ↔ D(x))

Name

O(x)

D(x)

O(x) ↔ D(x)

¬(O(x) ↔ D(x))

Hillary

F

T

F

Bernie

T

F

F

Donald

T

F

F

Jeb

T

T

T

Carly

T

F

F

(b) ∀x ((x ≠ Jeb) → ¬(O(x) ↔ D(x)))

Name

O(x)

D(x)

x ≠ Jeb

O(x) ↔ D(x)

¬(O(x) ↔ D(x))

(x ≠ Jeb) → ¬(O(x) ↔ D(x))

Hillary

F

T

T

F

T

T

Bernie

T

F

T

F

T

T

Donald

T

F

T

F

T

T

Jeb

T

T

F

T

F

T

Carly

T

F

T

F

T

T

(c) ∀x (¬O(x) → D(x))

Name

O(x)

D(x)

¬O(x)

(¬O(x) D(x))

Hillary

F

T

T

Bernie

T

F

F

Donald

T

F

F

Jeb

T

T

F

Carly

T

F

F

(d) ∃x (M(x) ∧ D(x))

Name

M(x)

D(x)

M(x) ∧ D(x)

Hillary

T

T

Bernie

F

F

Donald

F

F

Jeb

F

T

Carly

F

F

(e) ∀x (M(x) ∨ O(x) ∨ D(x))

Name

M(x)

O(x)

D(x)

M(x) ∨ O(x)

M(x) ∨ O(x) ∨ D(x))

Hillary

T

F

T

T

Bernie

F

T

F

T

Donald

F

T

F

T

Jeb

F

T

T

T

Carly

F

T

F

T

(f) ∀x ¬D(x)

  • D(Hillary) = T

  • ¬D(Hillary) = ¬T = F

Name

D(x)

¬D(x)

Hillary

T

Bernie

F

Donald

F

Jeb

T

Carly

F

(h) D(Bernie) ∧ O(Bernie)

Name

O(x)

D(x)

D(Bernie) ∧ O(Bernie)

Bernie

T

F

(i) ∃x (O(x) → M(x))

Name

M(x)

O(x)

O(x) → M(x)

Hillary

T

F

Bernie

F

T

Donald

F

T

Jeb

F

T

Carly

F

T

(j) ∃x (M(x) ∧ O(x) ∧ D(x))

Name

M(x)

O(x)

D(x)

M(x) ∧ O(x)

M(x) ∧ O(x) ∧ D(x))

Hillary

T

F

T

F

Bernie

F

T

F

F

Donald

F

T

F

F

Jeb

F

T

T

F

Carly

F

T

F

F

1.8.2 In the following question, the domain of discourse is a set of male patients in a clinical study. Define the following predicates:

  • P(x): x was given the placebo

  • D(x): x was given the medication

  • M(x): x had migraines

Translate each statement into a logical expression. Then negate the expression by adding a negation operation to the beginning of the expression. Apply De Morgan’s law until each negation operation applies directly to a predicate and then translate the logical expression back into English.

(a) Every patient was given the medication.

(c) There is a patient who took the medication and had migraines.

(e) There is a patient who had migraines and was given the placebo.