SE 500 Fall 2025
HW #7: More Quantification; Predicate Logic
Due: 5:00pm, Friday, October 31

Exercises identified by number are from the Gries & Schneider text. Of course, in proving a numbered theorem, you may use only lower-numbered theorems.

Part A: Proofs

A1. Prove   (+i | 0≤i<m : (+j | 0≤j<n : f.i.j))  =  (+k | 0≤k<n : (+i | 0≤i<m : f.i.k))

A2. Prove   (+i,j | 0≤i≤j<n : f.i.j)  =  (+i | 0≤i<n : (+j | i≤j<n : f.i.j))

Keep in mind that the expression a≤b≤c is an abbreviation for the conjunction a≤b ∧ b≤c and that, by transitivity of ≤, a≤c is a consequence of that conjunction, so that the original expression is (by Theorem (3.60)) equivalent to  a≤b ∧ b≤c ∧ a≤c.

A3. Prove   (∀i,j | 0≤i≤j≤n : g.i ≤ g.j) = (∀i,j | 0≤i<j≤n : g.i ≤ g.j)

(Notice the subtle difference between the two ranges.)

Note: It is conventional to use ∀ as a quantification operator, even though it means the same thing as if ∧ had been used instead. (We call this a universal quantification.) Unlike ∧, we never use ∀ as a binary infix operator.

Hint #1: Starting with the LHS, rewrite the range R as R1 ∨ R2, where R1 (respectively, R2) covers all (i,j)-pairs in R's "truth set" in which i<j (respectively, i=j). Then use Axiom (8.16).

Hint #2: Manipulate the quantification having R2 as its range so as to obtain one of the form (∀i | Q : (∀j | j=i : P)), to which (8.14) can be applied.

Hint #3: Recall that ≤ is reflexive, which is to say that x ≤ x is true for all x.

Hint #4: If the body of a universal quantification is true, the whole quantification is equivalent to true. (See Theorem (9.8).)

A4. Do Exercise 9.2, which can be restated as follows:

Take (∀x |: P) ∧ (∀x |: Q) ≡ (∀x |: P∧Q) to be an axiom. Without using Theorem (8.15), and using no theorem numbered higher than (9.2), prove

(∀x | R : P) ∧ (∀x | R : Q) ≡ (∀x | R : P∧Q)

A5. Do Exercise 9.6, which can be restated as follows:

Prove (∀x | R∨Q : P) ≡ (∀x | R : P) ∧ (∀x | Q : P)

without using Axiom (8.18). (You probably will want to use Axiom (8.15), however.)

Part B: Translating between English and Predicate Logic

Let U be some set of persons that we take to be our "universe". Let L : U × U ⟶ Bool be the predicate corresponding to the "likes" relation among those persons. That is, for x,y ∈ U, the value of L.x.y corresponds to the truth value of the statement "x likes y". Let M : U ⟶ Bool be the predicate such that, for x ∈ U, the value of M.x corresponds to the truth value of the statement "x is male". For the sake of simplicity, assume then that ¬M.x corresponds to the statement "x is female".

Translate each of the following (English) statements into the language of predicate logic:

B1. There is a male who is liked by no one but himself.
B2. Every male likes at least two different females.
B3. Every person likes someone who does not like her/him back.
B4. There is no person who is liked by everybody.
B5. There are two females who like the same male but do not like each other.
B6. If there is a person who is liked by everyone, then there is also a person who is liked by no one except her/himself.
B7. Every female likes some male who is disliked by all her female friends. (Note: The statement "x and y are friends" translates to L.x.y ∧ L.y.x ∧ x≠y.)