Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 2 exercises

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 2

Exercise 2.1

A function of the form

    g : { A ∣ A is a structure } → { 0 , 1 }

is said to be finitary iff there exists a natural number n such that for all structures A and B, if A ( Pi ) = B ( Pi ) for every i < n, then g ( A ) = g ( B ).

Prove that for all finitary g, there is a sentence φ such that g is the truth table for φ.

Exercise 2.2

Prove that for every sentence φ, if φ is not logically equivalent to ⊥, then there exists a sentence logically equivalent to φ of the form

    ( Q0,0 ∧ Q0,1 ∧ ⋅ ⋅ ⋅ ∧ Q0,n ) ∨ ( Q1,0 ∧ Q1,1 ∧ ⋅ ⋅ ⋅ ∧ Q1,n ) ∨ ⋅ ⋅ ⋅ ∨ ( Qm,0 ∧ ⋅ ⋅ ⋅ ∧ Qm,n )

where each Qi,j is either Pj or ¬ Pj.

(This is called disjunctive normal form.)

As a hint, think about the truth table of φ.

Exercise 2.3

Prove that for every sentence φ, if φ is not logically equivalent to ⊤, then there exists a sentence logically equivalent to φ of the form

    ( Q0,0 ∨ Q0,1 ∨ ⋅ ⋅ ⋅ ∨ Q0,n ) ∧ ( Q1,0 ∨ Q1,1 ∨ ⋅ ⋅ ⋅ ∨ Q1,n ) ∧ ⋅ ⋅ ⋅ ∧ ( Qm,0 ∨ ⋅ ⋅ ⋅ ∨ Qm,n )

where each Qi,j is either Pj or ¬ Pj.

(This is called conjunctive normal form.)

Exercise 2.4

A set of symbols S is called complete iff for every sentence, there exists a logically equivalent sentence that is built up using only parameters and symbols in S.

The two previous exercises show that { ⊥ , ¬ , ∧ , ∨ } and { ⊤ , ¬ , ∧ , ∨ } are complete sets of symbols.

  1. Prove that the following are complete sets of symbols:

    1. { ¬ , ∧ }
    2. { ¬ , ∨ }
    3. { ¬ , → }
  2. Prove that the following are not complete sets of symbols:

    1. { ¬ }
    2. { ∧ , ∨ , → , ↔ }

      Hint: For 2.4.2.2, consider the structure A such that A ( Pn ) = 1 for every n.

Exercise 2.5

Define a binary operation NAND on the set of sentences by setting NAND ( φ , ψ ) equal to ¬ ( φ ∧ ψ ).

Let Σ be a theory such that

Prove that for every sentence, there is a logically equivalent sentence that belongs to Σ.

Exercise 2.6

  1. Prove that logical consequence ⊨ is a reflexive and transitive relation on the set of all sentences.

    (In other words, ⊨ is a partial ordering.)

  2. Prove that logical equivalence ╞╡ is a reflexive, symmetric and transitive relation on the set of all sentences.

    (In other words, ╞╡ is an equivalence relation.)

  3. Prove that ╞╡ has infinitely many equivalence classes and that each equivalence class is infinite.

Exercise 2.7

Let Σn be the set of sentences that involve only Pi for i < n.

Let ⊨n be the logical consequence relation ⊨ restricted to to Σn.

It follows easily from Exercise 2.6 that ⊨n is a partial ordering of Σn.

Let ╞╡n be the logical equivalence relation restricted to Σn.

It follows easily from Exercise 2.6 that ╞╡n is an equivalence relation on Σn.

  1. Prove that each ╞╡n equivalence class is infinite but there are only finitely many ╞╡n equivalence classes.
  2. Consider the following two diagrams.

    [⊤]
    |
    [⊥]
           
    [⊤]
    / \
    [P0] [¬ P0]
    \ /
    [⊥]

    The diagram on the left indicates that, considering Σ0 under ╞╡0, there are only two equivalence classes, those of ⊥ and ⊤.

    Also, moving up the left diagram corresponds to the relation ⊨0 between members of the equivalence classes.

    The diagram on the right indicates that, considering Σ1 under ╞╡1, there are only four equivalence classes, those of ⊥, P0, ¬ P0 and ⊤.

    Also, moving up the right diagram corresponds to the relation ⊨1 between members of the equivalence classes.

    Now choose a complete set of representatives for Σ2 under ╞╡2 and draw a corresponding diagram for the partial ordering ⊨2.

Exercise 2.8

Describe a computer algorithm for deciding whether an string of symbols is a sentence in Polish notation without parentheses or commas. Then, should it be a sentence, the algorithm continues by computing the truth table and deciding whether the sentence is valid or not.

Exercise 2.9

Complete the proof of Soundness Theorem 2.3.

Exercise 2.10

Complete the proof of Finiteness of Deductions Lemma 2.4.

Exercise 2.11

Let Σ be a theory.

Assume that for every natural number n, either Pn belongs to Σ or ¬ Pn belongs to Σ.

  1. Prove that Σ is complete.
  2. Prove that if Σ is consistent, then Σ has exactly one model.

Exercise 2.12

Let T be a set such that

Assume that for every natural number n, there is a member of T of length n.

A famous result called Konig's Infinity Lemma says that there exists an infinite sequence < bi ∣ i = 0, 1, 2, … > such that, for every natural number n, the finite sequence < bi ∣ i < n > belongs to T.

Prove this fact by writing down a certain theory Σ that depends on T, verifying that the hypothesis of Theorem 2.10 holds, applying Theorem 2.10 to find a model A of Σ and using A to find an appropriate < bi ∣ i = 0, 1, 2, … >.

(In fact, this is a rather convoluted way to prove Konig's Infinity Lemma but the connection to the Compactness Theorem is interesting.)

Exercise 2.13

Complete the proof of Theorem 2.11.

In other words, address the ¬-in, R1, R2 and R3 rules in the right-to-left direction of the proof.

Exercise 2.14

Let Σ be a theory.

Describe a computer algorithm for listing all of the proofs from Σ.

Running the algorithm, the hypothetical computer would output p0 , then p1 , then p2 etc. so that

    { q ∣ q is a proof from Σ } = { pn ∣ n is a natural number }

Your algorithm will use Σ as an oracle, which means that in addition to the usual commands, it may query whether a given sentence belongs to Σ.

Exercise 2.15

What if your hypothetical computer were your actual computer but it could run forever without breaking down when left in isolation without any sort of interaction with other devices or beings. In particular, it has its own limitless power source.

You write a program based on your algorithm from Exercise 2.14 and run the program on your hypothetical computer. Will it perform as expected? Explain.

Exercise 2.16

Find a justification for the deduction

    { } ⊢ ( φ → ψ ) ↔ ( ( ¬ ψ ) → ( ¬ φ ) ).

The sentence ( ¬ ψ ) → ( ¬ φ ) is called the contrapositive of the sentence φ → ψ.

Exercise 2.17

Let φ and ψ be sentences such that φ ⊨ ψ but ψ ⊭ φ .

Prove that there is a sentence χ such that

    φ ⊨ χ but χ ⊭ φ

and

    χ ⊨ ψ but ψ ⊭ χ .

Suggestions:

1) Think about the special case in which φ is F and ψ is any satisfiable sentence.

2) Think about how this is related to Exercise 2.7.

Exercise 2.18

Let I and J be subsets of ω

Let φ be a sentence built up from Pn for n ∈ I.

Let ψ be a sentence built up from Pn for n ∈ J.

Assume φ ⊨ ψ.

Prove that there is a sentence χ that is built up from Pn for n ∈ I ∩ J such that φ ⊨ χ and χ ⊨ ψ .

Suggestion: First think about I = { 0 , 1 } and J = { 1 , 2 } .