ICS 6B
Fall 2013
Homework 2


Due: Wednesday, Oct 16

Covers Sections 1.5-1.7

  1. Predicates P and Q are defined below. The domain of discourse is the set of all positive integers. Are the following logical expressions propositions? If the answer is yes, indicate whether the statement is true or false.
    1. P(x)
    2. P(2)
    3. ∀x (Q(x) → ¬P(x))
    4. (∀x Q(x)) ∧ P(x)
    5. P(3) ∧ Q(49)

  2. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse must be the set of all real numbers.
    1. There is a number whose cube is equal to -2.
    2. The square of every number is at least 0
    3. The reciprocal of every number between 0 and 1 is greater than 1.
    4. There is no largest number.
    5. Every number has an additive inverse.

  3. In the following question, the domain of discourse is a group of people. Define the following predicates: Translate the following English statements into a logical expression with the same meaning:
    1. Someone who was sick yesterday went to work.
    2. Everyone who was sick yesterday did not go to work.
    3. At least one person was sick yesterday.
    4. No one went to work yesterday.
    5. Everyone who did not got work yesterday was sick.

  4. In the following question, the domain of discourse is the set of employees of a company. Define the following predicates as follows: Translate the following logical expressions into English:
    1. ∀x (A(x)→E(x)
    2. ∃x (E(x) ∧ ¬W(x))
    3. ∀x (W(x) → E(x))
    4. ∃x (¬A(x) ∧ E(x)

  5. Determine the truth value of each expression below if the domain is the set of all real numbers.
    1. ∀x∃y (xy > 0)
    2. ∃x∀y (xy = 0)
    3. ∀x∀y∃z (z = (x - y)/3)
    4. ∀x∀y (xy = yx)
    5. ∃x∃y∃z (x2 + y2 = z2)

  6. Define the domain of discourse for variables x and y to be the set of runners in a race. Define the predicate B(x, y) to mean that x beat y in the race. Give a logical expression equivalent to the following Engilsh statements.
    1. Everyone beat Sam.
    2. Someone was beat by everyone in the race.
    3. Sam beat exactly two people.
    4. Gretchen won the race.

  7. The domain of discourse is the members of a chess club. The predicate B(x, y) means that person x has beaten person y at some point in time. Give a logical expression equivalent to the following Engilsh statements.
    1. No one has ever beat Nancy.
    2. Everyone has been beaten before.
    3. Everyone has won at least one game.
    4. No one has beaten both Ingrid and Dominic.
    5. There are two members who have never been beaten.

  8. Write the negation of each of the following logical expressions so that all negations immediately precede predicates.
    1. ∀x ∃y ∃z P(y, x, z)
    2. ∃x ∃y P(x, y) ∧ ∀x ∀y Q(x, y)
    3. ∃x ∀y (P(x, y) ↔ P(y, x))
    4. ∃x ∀y (P(x, y) → Q(x, y))

  9. Translate each of the following Engilsh statements into logical expressions. The domain of discourse is the set of all integers.
    1. There are two numbers whose sum is equal to their product.
    2. The product of every two positive integers is positive.
    3. Every positive integer can be expresessed as the sum of the squares of four integers.
    4. There is a positive integer that is smaller than all other positive integers.

  10. Use the laws of logic to prove the conclusion from the hypotheses. Give propositions and predicatse variable names in your proof. The hypotheses are: Conclude that I will see the fire.

  11. Use the laws of logic to prove the conclusion from the hypotheses. Give propositions and predicatse variable names in your proof. Use the set of all students as the domain of discourse. The hypotheses are: Conclude that Larry and Hubert can take Algorithms.

  12. Use the laws of logic to prove the conclusion from the hypotheses. Give propositions and predicatse variable names in your proof. Use the set of all people as the domain of discourse. The hypotheses are: Someone in the orchestra is a good musician.

  13. Which of the following arguments are valid? Explain your reasoning.
    1. I have a student in my class who is getting an A. Therefore, John, a student in my class is getting an A.
    2. Every girl scouts who sells at least 50 boxes of cookies will get a prize. Suzy, a girl scout, got a prize. Therefore Suzy sold 50 boxes of cookies.

  14. Use the laws of logic to show that ∀x(P(x) ∧ Q(x)) implies that ∀x Q(x) ∧ ∀x P(x).