80-310/610 Logic and Computation Fall 2001

Homework #5

Due Wednesday, September 26

1. Finish reading section 1.3, and start reading section 1.4 in van Dalen.

2. A binary truth function is a function f(x, y) that takes values of x and y in the set {0, 1} to a value in the set {0, 1}. Note that a binary truth function is defined uniquely by its truth table.

a. How many different binary truth functions are there?

b. Two binary truth functions don’t depend on any of their arguments: the constant 0 function and the constant 1 function. How many binary truth functions depend only on one of their two arguments?

c. We’ve already seen a number of binary truth functions that depend on both arguments, namely those corresponding to the connectives ∧, ∨, →, ↔, ⊕ (exclusive or), | (nand, or the sheffer stroke), and ↓ (nor). (The last three are defined by p⊕q ≡ ¬(p ↔ q), p|q ≡ ¬(p∧q), p ↓ q ≡ ¬(p ∨ q).)

What are the remaining ones? You can define them in words, in terms of the other connectives, or with truth tables.

3. ⋆ Show that if k is a natural number and φ_{1}, …, φ_{k} are propositional formulas, then [[φ_{1} ∧ … ∧ φ_{k}]]_{v} = 1 if and only if [[φ_{i}]]_{v} = 1 for each i from 1 to k. Remember that, for example, φ_{1}∧φ_{2}∧φ_{3} is an abbreviation for ((φ_{1} ∧ φ_{2}) ∧ φ_{3}). Do this carefully, using only the definition of [[·]]_{v}.

4. ⋆ Show that if φ_{1}, …, φ_{k} and ψ are in PROP, then the following is true:

{φ, …, φ_{k}} ⊧ ψ if and only if ⊧ φ_{1} ∧ … ∧ φ_{k} → ψ.

Once again, do this carefully, using the definition of semantic entailment.

5. Show that if {φ} ⊧ ψ and {ψ} ⊧ θ then {φ} ⊧ θ.

6. ⋆ Do problem 1a on page 20 of van Dalen.

7. Do problems 2, 3, 5, and 6 on page 21 of van Dalen.

8. Do problem 1 on page 27.

9. ⋆ Use “algebraic means” (as in the notes and on page 23 of the textbook) to do problem 2 on page 28 of van Dalen.

10. Use “algebraic means” to show that the following are all tautologies:

a. ((φ ∧ ¬ψ) ∨ ψ) ↔ (φ ∨ ψ)

b. (φ → ¬φ) → ¬φ

c. (φ → ψ) ↔ (¬ψ → ¬φ)

d. φ → (ψ → φ ∧ ψ)

11. ⋆ Let ≡ be any equivalence relation on a set X. For any element a in X, let [a] denote the equivalence class of a, defined by

[a] = {b ∈ X | b ≡ a}.

Show that for any elements a and b of X, a ≡ b if and only if [a] = [b]. (Remember that two sets said to be are equal if and only if they have exactly the same elements.)

12. ⋆ Now let ≡ denote equivalence modulo 5 on the natural numbers. In other words, a ≡ b holds iff a − b is a multiple of 5, that is, iff there is an integer c such that a − b = 5c.

a. Define the operation of addition ⊕ on equivalence classes by

[a] ⊕ [b] = [a + b].

Show that this operation is well defined, that is, if a ≡ a′ and b ≡ b′ then a + b ≡ a′ + b′.

b. Define exponentiation ↑ on equivalence classes by

[a] ↑ [b] = [a^{b}].

Show that exponentiation is not well-defined.

13. ∘ In the problem above, show that multiplication on equivalence classes, defined by [a] ⊗ [b] = [a × b], is well-defined.