CS 244/444

Exercise Set 1: Interpretations and Models

Based on material in B&L Ch 2

1. Consider a language containing only three propositional symbols, S, H, F, and no variables or other terms. Disregarding the domain D (since it would not be involved in interpreting the non-logical symbols), there are 8 distinct interpretations of the language. These interpretations can be specified in a table as follows:

  I(S) I(H) I(F)
I1 0 0 0
I2 0 0 1
I3 0 1 0
I4 0 1 1

Determine whether or not each of the following formulas is satisfiable and whether it is valid, by determining its value in each interpretation. (To motivate this example, suppose S is intended to mean "there is smoke", H, "there is heat", and F, "there is fire"). We use the symbols => for material implication, v for OR, & for AND, and ~ for NOT.

a.) (S => F) => (~S => ~F)

b.) (~(S => F)) => ~F

c.) (S v F) & (~S v F) & (F v ~S) & (~S v ~F)

2. B&L 2.7 Exercise 1 (page 28)

3. Let A and B be any two sentences (with no free variables). Prove that if A |= B (that is, A logically entails B), then the sentence A=>B is valid. Next, prove the converse, that if A=>B is valid, then A|=B. Note that your proof is an argument about interpretations, it is not itself in FOL.