CPSC 625 – Homework 4due: Monday, October 16, 20061. Determine whether the following sets of propositional formulas are valid, satisfiable (butnot valid), or unsatisfiable by giving a truth table for each. Be sure to label each table withyour conclusion (valid, etc.), and indicate which truth assignments are satisfying.a. {P → (Q → P )}b. {(P → (Q → R)) → ((P → Q) → (P → R))}c. {(P ∧ (P → Q)) → Q}d. {(P ∧ (P → Q)) → ¬Q}e. {((M → X) ∧ ¬X) → ¬M}f. {A → C, B → C, A ∨ B, ¬C}g. {P → Q, Q → R, P ∨ Q, ¬Q ∨ ¬R}h. {(A ⊕ B ⊕ C), ¬(A ⊕ B), ¬(A ⊕ C), ¬(B ⊕ C)}2. Derive a proof of the proposition A from the following set of sentences by rules ofinference. Recall that a proof contains a sequence of derivations labelled with the indexes ofthe sentences they were derived from, along with an indication of the inference rule used.{D ∧ E → A, F ∧ C → D, ¬(F ∧ C → B), C ∨ B → E}3. You are the proprietor of Sammy’s Sport Shop. You have just received a shipment of threeboxes filled with tennis balls. One box contains only yellow tennis balls, one box containsonly white tennis balls, and one contains both yellow and white tennis balls. You wouldlike to stock the tennis balls in appropriate places on your shelves. Unfortunately, the boxeshave been labelled incorrectly; the manufacturer tells you that you have exactly one box ofeach, but that each box is definitely labelled wrong.incorrect:whiteyellowbothobservations:&%'$&%'$&%'$yellow white yellowGiven the initial (incorrect) labelling of the boxes above, and the three observations, usePropositional Logic to derive the correct labelling of the middle box. Begin by writing downa knowledge base you will need (such as what observing a white ball drawn from box 21implies, that at most one box can contain yellow balls, etc.), along with the initial facts. Usepropositional symbols in the fo llowing form: O1Y means a yellow ball was drawn (observed)from box 1, L1W means box 1 was initially labelled white, a nd C1B means box 1 actuallycontains both types of tennis balls.a) Use rules of inference to prove that box 2 contains white tennis balls (i.e. generate thesentence C2W).b) Show that box 2 must contain white balls via a resolution refutation proof (may requireconverting some sentences to