1 Consider the set of propositional formulas U p q p q

1. Consider the set of propositional formulas:

U = {¬p ? ¬ q, (p ? ¬q) ? ¬r, p ? r}

Provide an example of

(i) a non-satisfying interpretation

(ii) a satisfying interpretation

2. Provide an example of a formula A such that U ? A, where U is the set of formulas given in the Question 1.

3. Is the set of formulas of Question 1, {¬p ? ¬ q, (p ? ¬q) ? ¬r, p ? r}, closed under logical consequence?

4. Analyze the proof of the theorem and mention one rule of inference used in the proof.

Theorem Let n ? ?. If 7n + 6 is odd then n is odd.

Proof

Let us assume that n is not odd, that is, n is even. Then we have that n = 2k for some k ? ?. So

7n + 6 = 7(2k) + 6

= 2(7k) + 6

= 2(7k + 3)

From here we conclude that 7n + 6 is even in contradiction with the premise of the theorem. Therefore, if 7n + 6 is odd then n must be odd.

5.The proof in the Hilbert deductive system of a theorem known as conjunction elimination is provided. Write to the right of each step the number of the axiom or the name of the inference rule used. Note that the justification of the last step is already given.

Theorem conjunction elimination

Let A and B be arbitrary formulas of propositional logic. Then

? A ? B ? A

1.

? ¬A ? (B ? ¬A)

2.

? ¬(B ? ¬A) ? ¬¬A

3.

? ¬(B ? ¬A) ? A

4.

? A ? B ? A

3, definition of ? operator (¬(B ? ¬A) ? A ? B)

Solution

The first step in defining the semantics of PL is to provide a mechanism for evaluating the propositional variables. An interpretation I assigns to every propositional variable exactly one truth valueis an interpretation assigning true to P and false to Q, where . . . elides the (countably infinitely many) assignments that are not relevant to us. That is, I assigns to every propositional variable available to us (and there are countably infinitely many) a value. We usually do not write the elision. Clearly, many interpretations exist. Now given a PL formula F and an interpretation I, the truth value of F can be computed. The simplest manner of computing the truth value of F is via a truth table. Let us first examine truth tables that indicate how to evaluate each logical connective in terms of its arguments. First, a propositional variable gets its truth value immediately from I. Now consider the possible evaluations of F: it is either true or false. How is ¬F evaluated? The following table summarizes the possibilities, where 0 corresponds to the value false, and 1 corresponds to true:In particular, F1 F2 is false iff F1 is true and F2 is false. (Throughout the book, we use the word “iff” to abbreviate the phrase “if and only if”; one can also read it as “precisely when”.The top row is given by the subformulae of F. I provides values for the first two columns; then the semantics of PL provide the values for the remainder of the table. Hence, F evaluates to true under I.

This tabular notation is convenient, but it is unsuitable for the predicate logic . Instead, we introduce an inductive definition of PL’s semantics that will extend to . An inductive definition defines the meaning of basic elements first, which in the case of PL are atoms. Then it assumes that the meaning of a set of elements is fixed and defines a more complex element in terms of these elements. For example, in PL, F1 F2 is a more complex formula than either of the formulae F1 or F2. Recall that we want to compute whether F has value true under interpretation I. We write I |= F if F evaluates to true under I and I 6|= F if F evaluates to false. To start our inductive definition, define the meaning of truth symbolsSince true 6= false, both definitions yield the same (unique) truth values. Having completed the base cases of our inductive definition, we turn to the inductive step. Assume that formulae F, F1, and F2 have truth values. From these formulae, evaluate the semantics of more complex formulae