Exercises for propositional logic i  (Page 4/5)

In that same board , is location $W$ safe? What is your informal reasoning? (List all your small steps.)Similarly for location $P$ .

Give a domain axiom of WaterWorld which was omitted in the ellipses in the WaterWorld domain axioms .

Even allowing for ellision, the list of WaterWorld domain axioms is incomplete, in a sense. The game reports how many pirates exist in total, butthat global information is not reflected in the propositions or axioms.

First, assume we only use the default WaterWorld board size and number of pirates, i.e. , five. Give samples of the additional axioms that we need.

Next, generalize your answer to model the program's ability to play the game with a different number of pirates.

Give one WFF which meets all three conditions:

• true in all WaterWorld boards(

  A theorem of WaterWorld

  )
• not already listed as one of the WaterWorld domain axioms , and
• not a tautology of propositional logic (can be made false in some truth assignment,though it may not be a truth assignment which satisfies the waterworld axioms).

In a truth table for two inputs, provide a column for each of the sixteen possible distinct functions. Give a small formula for each of these functions.

[Practice problem $—$ solution provided.]

Write the truth table for xnor , the negation of exclusive-or,What is a more common name for this Boolean function?

How many years would it take to build a truth table for a formula with 1000 propositions?Assume it takes 1 nanosecond to evaluate each formula.

A formula with 1000 propositions clearly isn't something you would create by hand. However, such formulas easily arise whenmodeling the behavior of a program with a 1000-element data structure.

Use truth tables to answer each of the following. Showing whether the connectives obey such properties via truth tables is one way ofestablishing which equivalences or inference rules we should use.

1. Show whether ⇒ is commutative.

2. Show whether ⊕ is commutative.

3. Show whether ⊕ is associative.

4. Prove that ∧ distributes over ∨: $\phi \land \psi \lor \theta \equiv (\phi \land \psi )\lor (\phi \land \theta )$

   This version is left-distributivity. Right-distributivity follows from this plus the commutativityof ∧.

5. Prove that ∨ distributes over ∧: $\phi \lor (\psi \land \theta )\equiv \phi \lor \psi \land \phi \lor \theta$

6. Show whether ∧ or ∨ distribute over ⇒.

7. Show whether ⇒ distributes over ∧ or ∨.

8. Show whether ∧ or ∨ distribute over ⊕.

9. Show whether ⊕ distributes over ∧ or ∨.