1)  Consider the following strings in Lstring  (where x, y are variable symbols, P is a unary predicate symbol and Q is a binary predicate symbol):

⇒ QxPx    ;    A¬Qx¬y    ;    ¬ ⇒ AxAyQxy ⇒ PxAyPy    ;    ⇒ PyAx ⇒ PxQxy ⇒ ¬Py

a)  Compute the weight of each of the above strings.

b)  For each string above, determine, with justification, whether or not it is a formula in L.

c)  Compute the degree of each string that is a formula in L (from the above list).

a)  Let us recall the definition of the weight of a string. For s a string in Lstring , the weight of s, written as weight(s), is the integer obtained by taking the sum of:

1) −1 for each (occurrence of a) variable symbol in s;

2)  n − 1 for each (occurrence of an) n-ary predicate symbol in s;

3)  0 for each (occurrence of) ¬ in s;

4)  +1 for each (occurrence of) ⇒ in s;

5)  +1 for each (occurrence of) A in s.

We may use this definition to find the weight of each of the given strings (remembering that, below, x, y are variable symbols, P is a unary predicate symbol and Q is a binary predicate symbol):

· weight(⇒ QxPx) =  1 + 1 + (−1) + 0 + (−1) = 0

· weight(A¬Qx¬y) =  1 + 0 + 1 + (−1) + 0 + (−1) = 0

· weight(¬ ⇒ AxAyQxy ⇒ PxAyPy)  =  0 + 1 + 1 + (−1) + 1 + (−1) + 1 + (−1) +

(−1) + 1 + 0 + (−1) + 1 + (−1) + 0 + (−1) = −1

· weight(⇒ PyAx ⇒ PxQxy ⇒ ¬Py) =  1 + 0 + (−1) + 1 + (−1) + 1 + 0 + (−1) +

1 + (−1) + (−1) + 1 + 0 + 0 + (−1) = −1

b)  We are now trying to determine which, if any, of the above strings are formulae. Let us now consider some of the tools that we may use:

· A method that can be used to determine if any given string is a formula or not is one that invokes the defining properties of formulae:

(F1)  If P is an n-ary predicate symbol and x1 , ··· ,xn are variable symbols, then Px1 ··· xn is a formula.

(F2)  If α is a formula, then so is ¬α .

(F3)  If α, β are formulae, then so is ⇒ αβ .

(F4)  If x is a variable symbol and α is a formula, then Axα is a formula.

For each of the given strings of symbols, we may try to check to see whether the string can be constructed using these rules, by perhaps trying to construct it ourselves. If our string cannot be constructed using the rules above, then it is not a formula. If we can construct the string, step by step, “all the way” to the very end i.e. if we are able to construct the “whole” string, then the string is a formula.

Let us see how the definition can be used in order to determine which of the given strings are formulae and which are not.

· The string ⇒ QxPx is not a formula.

We note that, since Q is a binary predicate symbol, in a formula, Q would have to be followed by two variable symbols; here, Q is followed by a single variable symbol, x, and then a predicate symbol, P. As such, the “whole” string, ⇒ QxPx, cannot be a formula.

· The string A¬Qx¬y is not a formula.

We note that, in a formula, the A symbol would have to be followed by a variable symbol; here, A is followed by a ¬ symbol. As such, the “whole” string, A¬Qx¬y, cannot be a formula.

(Alternatively, we may note that, in a formula, each ¬ symbol would have to be followed by a formula; here, the “final”, rightmost, ¬ is followed by a single variable symbol, y, and there is no rule that allows a single variable symbol to be a formula. As such, the “whole” string, A¬Qx¬y, cannot be a formula.)

(Alternatively, we may note that, in a formula, each binary predicate symbol that may appear would have to be followed by two variable symbols; here, the binary predicate symbol Q is followed by a single variable symbol, x, and then a ¬ symbol. As such, the “whole” string, A¬Qx¬y, cannot be a formula.)

· The string ¬ ⇒ AxAyQxy ⇒ PxAyPy is a formula.

Using (F1), we may deduce that Px, Py and Qxy are formulae (since P is a 1-ary predicate symbol and Q is a 2-ary predicate symbol).

Since Py is a formula, we may use (F4) to show that AyPy is a formula, while, since Px and AyPy are formulae, we may use (F3) to show that ⇒ PxAyPy is a formula. Also, since Qxy is a formula, an application of (F4) shows that AyQxy is a formula, and, a further application of (F4) shows that AxAyQxy is a formula.

Then, since AxAyQxy and ⇒ PxAyPy are formulae, an application of (F3) shows that the string ⇒ AxAyQxy ⇒ PxAyPy is a formula.

Finally, since ⇒ AxAyQxy ⇒ PxAyPy is a formula, an application of (F2) shows that ¬ ⇒ AxAyQxy ⇒ PxAyPy is a formula, as indicated above.

· The string ⇒ PyAx ⇒ PxQxy ⇒ ¬Py is not a formula.

We note that, if the string ⇒ PyAx ⇒ PxQxy ⇒ ¬Py were a formula, then, using (F3), the string PyAx ⇒ PxQxy ⇒ ¬Py would have to consist of two formulae.     This, latter, string “ends” with the string ⇒ ¬Py, which cannot be (the “end” part of) a formula; Py is a formula using (F1), and, then, ¬Py is a formula using (F2), but none of the defining rules of formulae allows us to have a ‘⇒’ symbol followed by only a single formula.

(Alternatively, we may note that, in PyAx  ⇒ PxQxy  ⇒ ¬Py, Py is a formula by (F1), since P is a 1-ary predicate symbol, so that, if PyAx ⇒ PxQxy ⇒ ¬Py were to consist of two formulae, the string Ax ⇒ PxQxy ⇒ ¬Py would have to be a formula.  Then, using (F4), the string ⇒ PxQxy ⇒ ¬Py would have to be a formula, and, hence, using (F3), the string PxQxy ⇒ ¬Py would have to consist of two formulae. Here, by (F1), Px is a formula, since P is a 1-ary predicate symbol, so, if PxQxy ⇒ ¬Py were to consist of two formulae, Qxy ⇒ ¬Py would have to be a formula; by (F1), Qxy is a formula, but none of the defining rules of formulae allows us to have a single formula that consists of a formula followed, on the right, by another, non-empty, string of symbols).

As a result, the “whole” string, ⇒ ¬Px ⇒ AxQxyPy ⇒ Px, is not a formula, as indicated above.

This essentially completes a possible solution to this part of the exercise. However, below, we describe two other tools that might be useful when trying to solve this part of the exercise.

· As we have seen in our lectures, if α is a formula, then

weight(α) = −1

So, we may safely say that any string with weight not equal to −1 cannot be a formula.   Therefore, using our answer to part (a), we may deduce that the first two strings given in the exercise, ⇒ QxPx and A¬Qx¬y, are not formulae.

· In order to identify other strings that are not formulae, we may also use the fact that, if α is a formula in L, and α is the concatenation βγ, for (non-empty) β , γ ∈ Lstring , then

weight(β) ≥ 0

So, if we start with each of the remaining potential formulae, and consider the weight at any stage along the sum (going from left to right), we should not reach −1 until the very end, if the string given is a formula. No proper initial segment of a formula will have a negative weight.

Let us see how this could be applied to the second string given above, A¬Qx¬y. Let us find the weights of its proper initial segments:

weight(A) =  1 = +1

weight(A¬) = weight(A) + weight(¬) =  1 + 0 = +1                weight(A¬Q) = weight(A¬) + weight(Q) =  1 + 1 = +2          weight(A¬Qx) = weight(A¬Q) + weight(x) = 2 + (−1) = +1 weight(A¬Qx¬) = weight(A¬Qx) + weight(¬) =  1 + 0 = +1

As such, no proper initial segment of the string has negative weight, as would be the case for a formula.

Note that this does not prove that the string is a formula; it only shows that it “could be” a formula (in fact, as shown earlier, this string is not a formula). So, the given result has not been helpful in determining whether or not ⇒ AxPyP¬x is a formula (in fact, as shown earlier, ⇒ AxPyP¬x is not a formula).

Similarly, if we find the weights of all proper initial segments of the third string, namely ¬ ⇒ AxAyQxy ⇒ PxAyPy, we find that no proper initial segment has negative weight is at the end of the string, as we might expect (given that this string is a formula, as shown earlier).

On the other hand, this result may be used to show that the fourth string given above, ⇒ PyAx ⇒ PxQxy ⇒ ¬Py, is not a formula.

For example, the proper initial segment ⇒ PyAx ⇒ PxQxy has weight −1:

weight(⇒ PyAx ⇒ PxQxy) = 1+0+(−1)+1+(−1)+1+0+(−1)+1+(−1)+(−1) = −1

and so we deduce that the “whole” string, ⇒ PyAx ⇒ PxQxy ⇒ ¬Py, is not a formula (since one of its proper initial segments has negative weight).

In conclusion, we may deduce that the third string given above is a formula, whereas the first, second and fourth strings are not.

So, in the given list, the only string which is a formula is:

¬ ⇒ AxAyQxy ⇒ PxAyPy

c)  Let us recall the definition of the degree of a formula.  If α is a formula (α ∈ L), then the degree of α, or deg(α), is the non-negative integer obtained by (starting from 0 and):

1)  adding 1 each time ¬ occurs in α;

2)  adding 2 each time ⇒ occurs in α;

3)  adding 1 each time A occurs in α .

We may use this to find the degree of the single string from the given list that is a formula, namely of ¬ ⇒ AxAyQxy ⇒ PxAyPy:

deg(¬ ⇒ AxAyQxy ⇒ PxAyPy) =  1 + 2 + 1 + 1 + 2 + 1 = 8

2)  Convert the following formulae in Lmath  to equivalent formulae in L (below, x, y are variable symbols, and P is a unary predicate symbol):

(3x)((Px) ∨ (¬ (¬ (Py))))    ;    (Ay)((Px ⇔ Py) ⇒ (¬ (Px)))

Let us transform the given formulae into formulae in L, as required. We start with:

· (3x)((Px) ∨ (¬ (¬ (Py))))

· (Ay)((Px ⇔ Py) ⇒ (¬ (Px)))

Note that we cannot use the symbols ‘3’, ‘∨’, ‘∧’, or brackets in L, and we must write strings of the form ‘α ⇒ β’ as ‘⇒ αβ’ .

Let us gradually transform these statements.

First let us avoid the use of the ‘⇔’ symbol above, by using the general convention that states that ‘α ⇔ β’ corresponds to ‘(α ⇒ β) ∧ (β ⇒ α)’:

· (3x)((Px) ∨ (¬ (¬ (Py))))

· (Ay)(((Px ⇒ Py) ∧ (Py ⇒ Px)) ⇒ (¬ (Px)))

Now, let us avoid the use of the ‘∨’ symbol above, by using the general convention that states that ‘α ∨ β’ corresponds to ‘(¬α) ⇒ β’:

· (3x)((¬ (Px)) ⇒ (¬ (¬ (Py))))

· (Ay)(((Px ⇒ Py) ∧ (Py ⇒ Px)) ⇒ (¬ (Px)))

Similarly, let us avoid the use of the ‘∧’ symbol above, by using the general convention that states that ‘α ∧ β’ corresponds to ‘¬(α ⇒ (¬β))’:

· (3x)((¬ (Px)) ⇒ (¬ (¬ (Py))))

· (Ay)((¬ ((Px ⇒ Py) ⇒ (¬ (Py ⇒ Px)))) ⇒ (¬ (Px)))

Next, let us avoid the use of the ‘3’ symbol above, by using the general convention that states that ‘(3x)(α)’ corresponds to ‘¬((Ax)(¬α))’:

· ¬ ((Ax)(¬ ((¬ (Px)) ⇒ (¬ (¬ (Py))))))

· (Ay)((¬ ((Px ⇒ Py) ⇒ (¬ (Py ⇒ Px)))) ⇒ (¬ (Px)))

Let us next rewrite strings of the form ‘α ⇒ β’ as ‘⇒ αβ’, starting with the innermost (“most bracketed”) ‘⇒’ symbols:

· ¬ ((Ax)(¬ (⇒ (¬ (Px))(¬ (¬ (Py))))))

· (Ay)((¬ ((⇒ PxPy) ⇒ (¬ (⇒ PyPx)))) ⇒ (¬ (Px)))

before dealing with the next innermost ‘⇒’ symbol(s):

· ¬ ((Ax)(¬ (⇒ (¬ (Px))(¬ (¬ (Py))))))

· (Ay)((¬ (⇒ (⇒ PxPy)(¬ (⇒ PyPx)))) ⇒ (¬ (Px)))

and finishing by dealing with the outermost ‘⇒’ symbol(s):

· ¬ ((Ax)(¬ (⇒ (¬ (Px))(¬ (¬ (Py))))))

· (Ay)(⇒ (¬ (⇒ (⇒ PxPy)(¬ (⇒ PyPx))))(¬ (Px)))

We have essentially completed the transformation of our Lmath formulae to formulae in L.              It now remains to remove all brackets present, since, in the setting of L, these are unnecessary (and, in any case, not allowed).

So, finally, as formulae in L, the given elements of Lmath become:

· ¬Ax¬ ⇒ ¬Px¬¬Py

· Ay ⇒ ¬ ⇒⇒ PxPy¬ ⇒ PyPx¬Px

3)  For each of the following propositions, use the semantic tableaux method to determine whether or not the proposition is a tautology (where α , β are taken to be distinct primitive propositions). If a proposition is not a tautology, describe every (type of) valuation for which it fails to be true.

a)  (¬ (α ⇔ β)) ⇒ ((¬α) ∨ β)

b)  (α ⇔ β) ⇒ ((α ∧ β) ∨ ((¬α) ∧ (¬β)))

Let us start by giving a complete set of the basic rules for propositional semantic tableaux, which we will allow ourselves to use:

¬¬α

α

α ∨ β

④④④④④④④④④ ❈❈❈❈❈❈❈❈❈

α β

α ∧ β

α , β

α ⇒ β

¬α✇✇✇✇✇✇✇✇✇✇ ❊❊❊❊❊❊❊❊❊ β

α ⇔ β

✈✈✈✈✈✈✈✈✈ ❑❑❑❑❑❑❑❑❑❑

α , β                                 ¬α , ¬β

¬(α ∨ β)

¬α , ¬β

¬(α ∧ β)

✉ ■

✉ ■

✉ ■

✉ ■

✉ ■

✉ ■

✉ ■

✉ ■

✉ ■

¬α                                 ¬β

¬(α ⇒ β)

α , ¬β

¬(α ⇔ β)

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

石 ▲

α , ¬β                                  ¬α , β

a)  Consider (¬ (α ⇔ β)) ⇒ ((¬α) ∨ β):

We form a semantic tableau starting from ¬ ((¬ (α ⇔ β)) ⇒ ((¬α) ∨ β)).

¬ ((¬ (α ⇔ β)) ⇒ ((¬α) ∨ β))

¬ (α ⇔ β) , ¬ ((¬α) ∨ β)

¬¬α , ¬β

石 石

石 石

石 石

石 石

石 石

石

石

石

石

石

石

石

石

石

石

石

石

石

石

α

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

▼

α , ¬β

open

¬α , β

closed

Since there exists (at least) one open branch, we deduce that (¬ (α ⇔ β)) ⇒ ((¬α) ∨ β) is not a tautology.

By examining the open branches, we may deduce that the original proposition fails to be true for any valuation v for which v(α) = 1 and v(β) = 0; for such a valuation v, it necessarily holds that v ((¬ (α ⇔ β)) ⇒ ((¬α) ∨ β)) = 0.

b)  Consider (α ⇔ β) ⇒ ((α ∧ β) ^ ((¬α) ∧ (¬β))):

We form a semantic tableau starting from ¬ ((α ⇔ β) ⇒ ((α ∧ β) ^ ((¬α) ∧ (¬β)))).

¬ ((α ⇔ β) ⇒ ((α ∧ β) ^ ((¬α) ∧ (¬β))))

α ⇔ β , ¬ ((α ∧ β) ^ ((¬α) ∧ (¬β)))

¬ (α ∧ β) , ¬ ((¬α) ∧ (¬β))

♥ ♥

♥ ♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

♥

¬α

✁✁✁✁✁✁✁✁✁✁✁✁✁✁✁✁

α , β           ¬α , ¬β

c☎☎☎☎☎☎☎☎☎☎☎☎¬ β

α β

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

持

¬β

❂❂❂❂❂❂❂❂❂❂❂❂❂❂❂

α , β          ¬α , ¬β

c☎☎☎☎☎☎☎☎☎☎☎☎¬ β

α β

closed

closed

closed closed

All branches are closed, so that (α ⇔ β) ⇒ ((α ∧ β) ^ ((¬α) ∧ (¬β))) is a tautology.

4)  For each of the following, use the semantic tableaux method to determine whether or not the given semantic implication holds (where α , β , γ are taken to be distinct primitive propositions).  If a semantic implication does not hold, describe every (type of) valuation for which it fails to hold.

a)  {(α ∧ β) ⇒ γ} |= β ⇒ (α ⇒ γ)

b)  {(α ^ β) ⇒ γ} |=  (γ ⇒ α) ⇒ β

When solving this exercise, we will use the basic rules for propositional semantic tableaux, given in our lectures and in the solutions of the two previous sample exercises:

¬¬α

α

α ^ β

❈❈❈❈❈❈❈❈❈

α

¬(α ^ β)

¬α , ¬β

α ∧ β

α , β

¬(α ∧ β)

✉ ✉ ✉ ✉ ✉ ✉ ✉ ✉ ¬α

■ ■ ■ ■ ■ ■ ■ ■ ■ ¬β

α ⇒ β

✇✇✇✇✇✇✇✇✇✇

¬(α ⇒ β)

α , ¬β

α ⇔ β

✈✈✈✈✈✈✈✈✈

¬α , ¬β

¬(α ⇔ β)

石 石 石 石 石 石 石 石 石 石 α , ¬β