HOMEWORK #3: PROPOSITIONAL LOGIC

This is adapted from Russell & Norvig, 2nd edition, p. 237, #7.8.

Consider the following syntax and semantics for a propositional KR language:

Syntax: The following are all and only the atomic well-formed formulas ("wffs"):

Smoke, Fire, Big, Dumb, Heat.

Semantics:

[[Smoke]] = There is smoke.
[[Fire]] = There is fire.
[[Big]] = Someone is big.
[[Dumb]] = Someone is dumb.
[[Heat]] = There is heat.

A.

Using this language, represent the following English sentences:

1. If there is smoke, then someone is dumb.
2. Either there is no smoke, or someone is dumb.
3. If someone is not dumb, then there is no smoke.
4. There is smoke. If there is smoke, then there is fire. Therefore, there is fire.
   • Warning: This one is tricky! Is it a conjunction of 3 sentences, or is it an inference (i.e., an "argument")?

Note: Due to limitations of HTML, I will use:

• "~" for negation
• "->" for material conditional
• "<->" for biconditional.

1. (Smoke -> Smoke)

2. (Smoke -> Fire)

3. ((Smoke -> Fire) -> (~Smoke -> ~Fire))

4. (Smoke v Fire v ~Fire)

5. ((Smoke ^ Heat) -> Fire) <-> ((Smoke -> Fire) v (Heat -> Fire))

6. (Smoke -> Fire) -> ((Smoke ^ Heat) -> Fire)

7. Big v Dumb v (Big -> Dumb)

8. (Big ^ Dumb) v ~Dumb

B.

Using the semantics given above, translate these wffs into English.

C.

Using truth tables, determine which of the above wffs are:

• tautologies
  • i.e., true under all interpretations
  • i.e., true in all models
  • i.e., true for all possible assignments of truth values to the wff's atomic propositions.
• contradictions
  • i.e., false under all interpretations
  • i.e., false in all models
  • i.e., false for all possible assignments of truth values to the wff's atomic propositions.
• neither (sometimes called "contingent")