total 2 assignment

Math 150 Fall 2020 Homework 1

Due date: Friday, October 15, 2021 by 11:59pm

PLEASE UPLOAD ON GRADESCOPE

Recommendation. Many of the homework problems are close to problems listed on the Practice Problems sheet. It is a good idea to try the problems on Practice Problem sheet first to become comfortable with the topics.

1. In each of the following cases determine whether a given formula is a tau- tology and justify your conclusion. Do not use truth tables; give an argument based on reasoning instead. The point here is that it is not necessary to check all possible evaluations of sentential letters to decide whether the formulas below are tautologies. So try to focus only on those evaluations of sentential letters which are crucial. See Practice Problems 1, Problem # 1 for an example of what is meant by “argument based reasoning”. Additional examples will be done in the discussion.

(a) (A → B) → ((B → C) → (A → (B ∧ C)) (b) ((A → B) → (B → C)) → (A → (B ∧ C))

2. Given an L-formula ϕ, denote

lp(ϕ) = the number of occurrences of left parentheses in ϕ. b(ϕ) = the number of occurrences of sentential connectives ∧, ∨, → and ↔ in ϕ.

Give a proof of the following statements. Proceed by induction on complexity of formulas.

(a) If ϕ is an L-formula then lp(ϕ) = b(ϕ). (b) If ϕ is an L-formula built using only sentential connective ∧ and v is an

evaluation of sentential letters then v̄(ϕ) = 1 if and only if v(A) = 1 for all sentential letter which occur in ϕ.

It is important to take into account parentheses. In the lecture we said that if ϕ is an L-formula then we abbreviate ϕ in that we drop writing certain parentheses, as they do not have any influence on v̄(ϕ). For instance, if ϕ is a formula as in (b) we can drop all parentheses in ϕ. However, you cannot make use of this abbreviations here, because you work with ϕ from the syntactical point of view, i.e. you study them as sequences of symbols. Additionally, in (b) you are proving that such abbreviations make sense.

3. Consider sets of L-formulas Σ, Σ′, Γ, Γ′. Prove the following statements.

(a) If Σ ⊆ Σ′ and Σ |= Γ then Σ′ |= Γ. (b) Give an example of Σ ⊆ Σ′ and an L-formula σ such that Σ′ |= σ but

Σ 6|= σ. (c) If Γ ⊆ Γ′ and Σ |= Γ′ then Σ |= Γ. (d) Give an example of Γ ⊆ Γ′ and a set Σ such that Σ |= Γ but Σ 6|= Γ′.

4. Determine whether the following statements are true. If so, give a proof. If not give an example of evaluation of sentential letters which demonstrates it is false. Here A, B and Ak, k ∈ N are sentential letters.

1

2

(a) ¬A → A |= A (b) {A0 → B, . . . , An−1 → B} |= (A0 ∨ · · · ∨ An−1) → B (c) {Ak → B | k ∈ N} |= {(A0 ∨ · · · ∨ An−1) → B | n ∈ N} (d) {Ak → Ak+1 | k ∈ N} |= Γ where

Γ = {A0 → (A1 ∧ · · · ∧ An) | n ∈ N}

(e) {Ak → Ak+1 | k ∈ N} ∪ {Ak ↔ Bk | k ∈ N} |= Γ where

Γ = {A0 → (B1 ∧ · · · ∧ Bn) | n ∈ N}

As a hint, notice that (c) is an infinite variant of (b), so the argument for (b) should also help to approach (c). Also, (e) is just a more complicated variant of (d), so understanding (d) should help to approach (e).

PLEASE UPLOAD ON GRADESCOPE