FORMAL LOGIC

Computer Science School of Computing

1.1 Prove that the following propositional formula is unsatisfiable by means of a semantic argument, i.e. by arguing directly from the definitions of operators and formulas, their truth and satisfiability: (p(qr))((pq)(pr)) 1.2 Use a semantic tableau to prove that the following propositional formula is valid. (pq)((pr)(qr)) 1.3 Show that the formula in Question 1.2 is a theorem of the Gentzen system G. Annotate the lines of your proof with the rules used. 1.4 (i) Define the satisfiability and unsatisfiability of a set of formulas. (ii) Consider the following theorem: If UA then U{B}A for any formula B. Say U is a satisfiable set of formulas, but B is an unsatisfiable formula. Will U{B} not then be an unsatisfiable set, and does this not show that the theorem is incorrect? Explain your answers, referring to the definitions of satisfiability and unsatisfiability of a formula and a set of formulas