A. Determine whether each of the following is a tautology, a contradiction or neither:

p (p q)

(p q) (p q)

(p q) (q p)

(p q) p

(p q) (p q)

(p q) (p q)

(p q) (p q)

(p q) (r p)

B. Proof

Prove that (p q) (p q)

Prove that (p q) and (p q) are logically equivalent propositions.

Prove that (p

Test validity

Test the validity of the following arguments.

Ekow is either a Teaching Assistant or a Researcher. If he is a Teaching Assistant, then he has big feet. Ekow has not got big feet so he is a Researcher.

What is search algorithm completeness?

Consider the search problem represented in Figure 1, where a is the start node and f is the goal node. Would you prefer DFS or BFS for this problem? Why?

Figure 1: Comparing BFS and DFS