A Concise Introduction to the Fundamentals of Classical Logic

Brandon Bennett School of Computing University of Leeds [email protected]

January 2002

Section 1

Concepts and Uses of Logic

1.1 Logical Form

A form of an object is a structure or pattern which it exhibits. A logical form of a linguistic expression is an aspect of its structure which is relevant to its behaviour with respect to inference. To illustrate this we consider a mode of inference which has been recognised since ancient times (the Romans called it modus ponens). An example of this type of inference is the following: If Leeds is in Yorkshire then Leeds is in the UK Leeds is in Yorkshire Therefore, Leeds is in the UK The statements above the line are the premisses (or assumptions) upon which the inference depends and the statement below the line is the conclusion. The logical form of an inference is obtained by abstracting away from the specic content of the statements involved so that the essential pattern of the inference is shown. This can be done by replacing complex expressions whose structure is irrelevant to the argument by single letters. Then for this example we shall have: If P then Q P Therefore Q

Examination of inference patterns has revealed that certain constructs such as If . . . then . . . are of particular signicance. To represent logical form in a clear and unambiguous way these constructs are represented by special symbols. In this case the usual representation is: (P Q) P Q (The therefore has now been dropped it can be regarded as the meaning of the horizontal bar.) 2

1.2

Propositions

The preceding argument can be explained in terms of propositional logic. A proposition is an expression of a fact. The symbols, P and Q, represent propositions and the logical symbol is called a propositional connective. Many systems of propositional logic have been developed. We shall be studying classical i.e. the best established propositional logic. In classical propositional logic it is taken as a principle that: Every proposition is either true or false and not both. Complex Propositions and Connectives Propositional logic deals with inferences governed by the meanings of propositional connectives. These are expressions which operate on one or more propositions to produce another more complex proposition. The connectives dealt with in standard propositional logic correspond to the natural language constructs: . . . and . . ., . . . or . . . it is not the case that. . . if . . . then . . .. Symbols for the Connectives The propositional connectives are represented by the following symbols: and or if . . . then not (P Q) (P Q) (P Q) P

More complex examples: ((P Q) R), (P (Q R)) Brackets prevent ambiguity which would otherwise occur in a formula such as P Q R. Propositional Formulae We can precisely specify the well-formed formulae of propositional logic by the following (recursive) characterisation: Each of a set, P , of propositional constants Pi is a formula. If is a formula so is . If and are formulae so is ( ). 3

 If and are formulae so is ( ). If and are formulae so is ( ). The propositional connectives , and are respectively called negation, conjunction, disjunction and implication.

1.3

Proposition Symbols and Schematic Variables

The symbols P , Q etc. occurring in propositional formulae should be understood as abbreviations for actual propositions such as It is Tuesday and I am bored. But in dening the class of propositional formulae I used Greek letters ( and ) to stand for arbitrary propositional formulae. These are called schematic variables. Schematic variables are used to refer classes of expression sharing a common form. Thus they can be used for describing patterns of inference. For example, the formulae (A B ), ((P Q) R), (G (P G)) and (F F ) are all instances of the form ( ) and hence can all take part in modus ponens inferences. Note that if a schematic variable occurs more than one in a formula or argument pattern, an instance must match each occurence with an identical expression (so e.g. (P Q) is not an instance of ( )); however, dierent schematic variables may match identical expressions in an instance (so (P P ) is an instance of ( ). (Strictly speaking, in the rst section, when I exibited the logical form of a modus ponens argument, I should have used schematic letters. But I think that making this rather subtle distinction right at the begining would not have been very helpful.)

1.4

From Natural Language to Propositional Logic

In translating a natural language such as English into propositional logic we must be aware of the meanings of all the propositional connectives and be able to recognise them amid the various idiomatic forms of expression used in the language. Use of the English connectives and and or corresponds quite well with its use in logic; however, we must be aware that these words often occur connecting expressions which are not propositions. In such cases we need to rephase the sentence in a form where they do connect propositions. For instance John loves Mary and Susan must be rendered as John loves Mary and John loves Susan. If . . . then . . . constructions are quite easy to spot; but note that the form if means If then rather than if then . Assertions of the forms if and only if and just in case are both equivalent to If then and if then . A sentence of the form otherwise means the same as If not then ; and nally sentences of the form If then otherwise should be regarded as meaning If then and if not then .

Section 2

Inference Rules
2.1 Patterns of Deduction

An inference rule characterises a pattern of valid deduction. In other words, it tells us that if we accept as true a number of propositions called premisses which match certain patterns, we can deduce that some further proposition is true this is called the conclusion. Thus we have seen that from two propositions with the forms and we can deduce . We also know that inferences from (P Q) and P to Q or from ((A B ) C ) and (A B ) to C (etc.) are of this form. An inference rule can be regarded as a special type of re-write rule: one that preserves the truth of formulae i.e. if the premisses are true so is the conclusion.

Some Simple Examples

Here are some other simple examples of inference forms: And Elimination And Introduction

Or Introduction

Not Elimination

2.2

Logical Arguments and Proofs

We must now be more precise about what is meant by a logical argument. A logical argument consists of a set of propositions {P1 , . . . , Pn } called premisses and a further proposition C , the conclusion. Notice that in speaking of an argument we are not concerned with any sequence of inferences by which the conclusion is shown to follow from the premisses. Such a sequence is called a proof.

A set of inference rules constitutes a proof system. Inference rules specify a class of primitive arguments which are justied by a single inference rule. All other arguments require proof by a series of inference steps.

2.2.1

A 2-Step Proof Example

Suppose we know that If it is Tuesday or it is raining John stays in bed all day then if we also know that It is Tuesday we can conclude that John is in Bed. Using T , R and B to stand for the propositions involved, this conclusion could be proved in propositional logic as follows: (( T R) B ) B Here we have used the or introduction rule followed by good old modus ponens T (T R)

2.2.2

Theorems

A theorem of a proof system is a formula which can be proved true without assuming any premisses to be true. For example every formula of the form ( ) is a theorem of classical propositional logic.

2.3
2.3.1

Provability and Validity

Provability

To assert that C can be proved from premisses {P1 , . . . , Pn } in a proof system S we write: P1 , . . . , P n S C This means that C can be derived from the formulae {P1 , . . . , Pn } by a series of inference rules in the proof system S . When it is clear what system is being used we may omit the subscript S on the symbol.

2.3.2

Validity

An argument is called valid if its conclusion is a consequence of its premisses. Otherwise it is invalid. This needs to be made more precise: One denition of validity is: An argument is valid if it is not possible for its premisses to be true and its conclusion is false. Another is: in all possible circumstances in which the premisses are true, the conclusion is also true. To assert that the argument from premisses {P1 , . . . , Pn } to conclusion C is valid we write: P1 , . . . , Pn |= C

2.3.3

Provability vs Validity

We have dened provability as a property of an argument which depends on the inference rules of a logical proof system. Validity on the other hand is dened by appealing directly to the meanings of formulae and to the circumstances in which they are true or false. Later we shall look in more detail at the relationship between validity and provability. This relationship is of central importance in the study of logic. To characterise validity we shall need some precise specication of the meanings of logical formulae. Such a specication is called a formal semantics.

Section 3

Predicate Logic
3.1 Relations

In propositional logic the smallest meaningful expression that can be represented is the proposition. However, even atomic propositions (those not involving any propositional connectives) have internal logical structure. In predicate logic atomic propositions are analysed as consisting of a number of individual constants (i.e. names of objects) and a predicate, which expresses a relation between the objects. R(a, b, c) Loves(john, mary)

With many binary (2-place) relations the relation symbol is often written between its operands e.g. 4 > 3. Unary (1-place) relations are also called properties Tall(tom).

3.2

Universal Quantication

Useful information often takes the form of statements of general property of entities. For instance, we may know that every dog is a mammal. Such facts are represented in predicate logic by means of universal quantication. Given a complex formula such as (Dog(spot) Mammal(spot)), if we remove one or more instances of some individual constant we obtain an incomplete expression (Dog(. . .) Mammal(. . .)), which represents a (complex) property. To assert that this property holds of all entities we use the notation: x[Dog(x) Mammal(x)] in which is the universal quantier symbol and x is a variable indicating which property is being quantied.

3.2.1

An Argument Involving Quantication

An argument such as:

Everything in Yorkshire is in the UK Leeds is in Yorkshire Therefore Leeds is in the UK can now be represented as follows: x[Inys(x) Inuk(x)] Inys(l) Inuk(l)

3.3

Translating Natural Language into Predicate Logic

The predicate logic representation allows us to show much more of the structure of natural language statements and to account for many more types of inference than propositional logic. However, translating into predicate logic is a little more complicated. Whilst the idea of a relation and its correspondence to natural language forms of expression is fairly straightforward, the use of quantiers is much more dicult to master because the logical representation of quantiers is rather dierent from the way they are expressed in natural language. The reason for this is that the logical representation is designed to be unambiguous, wheras natural languages have evolved for ease of communication and often contain many constructs which are potentally ambiguous (this ambiguity is in practice very often removed by the context of a statement). To translate from English into predicate logic one must rst have a clear understanding of the logical representation and what it is supposed to mean. Then given some English sentence one tries to rephrase it so as to preserve the meaning but state it in a way that is closer to the logical quantier representation. Thus the sentence Every dog barks could be stated (rather unnaturally) as For every entity x, if x is a dog then x barks. This would then be represented as: x[dog(x) barks(x)] Notice how in translating a statement of the form Every s or perhaps Every is a , we not only use the universal quantier but also introduce an implication, rendering the sentence as For every x, if (x) then (x). With existential statements the logical representation again departs from natural language forms of expression. A statement There is a black dog is rendered as There is some entity x, such that x is black and x is a dog : x[black(x) dog(x)] Here the extra connective and is used to assert two properties of an entity, whereas in English they are simply combined in the expression black dog. Every red block is on a blue block: x[(red(x) block(x)) y [blue(y ) block(y ) on(x, y )]] 9

Notice here that the existential quantier conveyed very subtly in the English statement the existential construct about blue blocks is expressed simply by refering to them in a certain way. We could investigate at great lenght the nuances of translation into predicate logic but the underlying principle is always to think of the meaning of a sentence rather than its structure and then try to capture this meaning in the logical representation. You will be expected to be able to translate sentences of a similar complexity to the last example but no more complex than that.

10

Section 4

Uses of Logic
Logic has always been important in philosophy and in the foundations of mathematics and science. Here logic plays a foundational role: it can be used to check consistency and other basic properties of precisely formulated theories. In computer science, logic can also play this role it can be used to establish general principles of computation; but it can also play a rather dierent role as a component of computer software: computers can be programmed to carry out logical deductions. Such programs are called Automated Reasoning systems.

4.1

Formal Specication of Hardware and Software

Since logical languages provide a exible but very precise means of description, they can be used as specication language for computer hardware and software. A number of tools have been developed which help developers go from a formal specication of a system to an implementation. However, it must be realised that although a system may completely satisfy a formal specication it may still not behave as intended there may be errors in the formal specication.

4.2

Formal Verication

As well as being used for specifying hardware or software systems, a logical description can be used to verify properties of systems. If is a set of formulae describing a computer system and is a formula expressing a property of the system that we wish to ensure (eg. might be the formula x[Employee(x) age(x) > 0]), then we must verify that: |= We can do this using a proof system S if we can show that:
S

11

4.3

Logical Databases

A set of logical formulae can be regarded as a database. A logical database can be queried in a very exible way, since for any formula , the semantics of the logic precisely specify the conditions under which is a consequence of the formulae in the database. Often we may not only want to know whether a proposition is true but to nd all those entities for which a particular relation, , holds. e.g. query: (x, y, z ) ? Ans: x = actress, y = bishop, z = cauliower or x = octopus, y = whelk, z = sea-cucumber

4.4

Logic and Intelligence

The ability to reason and draw consequences from diverse information may be regarded as fundamental to intelligence. As the principal intention in constructing a logical language is to precisely specify correct modes of reasoning, a logical system (i.e. a logical language plus some proof system) might in itself be regarded as a form of Articial Intelligence. However, formal logical inference seems to have a very dierent character to everyday commonsense reasoning. These issues go beyond the scope of this course but they should certainly be considered by anyone seriously interested in AI.

12

Section 5

The Sequent Calculus

A sequent calculus is a proof system of a particular form. Its rules do not operate on ordinary formule but on special expressions called sequents. The use of sequents allows all the necessay rules of inference to be stated in a uniform way. Sequent calculi are very convienient from the point of view of the use of logic in computer science: they are easy to implement in a language such as Prolog and they facilitate systematic methods for proving (or disproving) logical arguments.

5.1

Sequents

A sequent is an expression of the form: 1 , . . . , m 1 , . . . , n

(where all the s and s are logical formulae). This asserts that: If all the s is true then at least one of the s is true. This notation as we shall soon see is very useful in presenting inference rules in a concise and uniform way. The sequent is equivalent to a formula of the form: ((1 . . . m ) (1 . . . n )) The use of the symbol as above is the most common notation used for writing a sequent. However it is a bit confusing because the is also used to denote the relation of provability holding between a set of premisses and a conclusion; but a sequent is probably best understood as a special kind of formula.

5.1.1

Special forms of sequent

A sequent with a single formula on the r.h.s.: 1 , . . . , m

13

Corresponds to a logical argument in the sense that it asserts that if all the s are true then is true. The sequent is thus true if the argument with premisses 1 , . . . , m and conclusion is valid. A sequent with an empty left-hand side: 1 , . . . , n asserts that at least one of the s is provable without assuming any premisses to be true. Such a formula is called a logical theorem. A sequent with an empty right-hand side: 1 , . . . , m asserts that the set of premisses {1 , . . . , m } is inconsistent, which means that a formula of the form ( ) is provable from this set.

5.2

Sequent Calculus Inference Rules

A sequent calculus inference rule species a pattern of reasoning in terms of sequents rather than formulae. Eg. a sequent calculus and introduction is specied by: , and , [ ]

( ),

where and are any series of formulae. In a sequent calculus we also have rules which introduce symbols into the premisses: , , [ ] ( ),

5.3

Sequent Calculus Proof Systems

To assert that a sequent is provable in a sequent calculus system, SC, I shall write:
SC 1 , . . . , m

1 , . . . , n

Construing a proof system in terms of the provability of sequents allows for much more uniform presentation than can be given in terms of provability of conclusions from premisses. We start by stipulating that all sequents of the form , ,

are immediately provable. It is clear that if and some other formulae are true then it must be the case that or at least one of some formulae must be true. Thus any sequent in which the same formulae occurs on both sides of the is valid. We then specify how each logical symbol can be introduced into the left and right sides of a sequent (see next slide). 14

5.4

A Propositional Sequent Calculus

Axiom: , , Re-write: = Rules: , , ( ), , [ ] , and , ( ), , , ( ), , [ , ] and [ [ ]

and

( ),

, [ ,

(Exercise: Show that the rules [ rewrite rule = ( ).)

] can be replaced by the

5.5

Sequent Calculus Proofs

The beauty of the sequent calculus system is its reversibility. To test whether a sequent, , is provable we simply apply the symbol introduction rules backwards. Each time we apply a rule, one connective is eliminated. With some rules two sequents then have to be proved (the proof branches) but eventually every branch will terminate in a sequent containing only atomic propositions. If all these nal sequents are axioms, then is proved, otherwise it is not provable. Note that the propositional sequent calculus rules can be applied in any order. This calculus is easy to implement in a computer program.

5.6
5.6.1

Proof Examples
Example 1

This rst example shows how a modus ponens inference is validated using the sequence calculus. The conclusion is an instance of a modus ponens-type argument: axiom P Q, P [ ] P, P Q

and

axiom Q, P Q Q Q [ r.w.]

(P Q), P (P Q), P

[ ]

15

1. First the re-write rule [ r.w.] is applied to replace the formula with an equivalent disjunction (the equivalence of these formulae is explained in the secion on formal semantics for propositional logic). 2. Next, the rule [ ] is applied to eliminate the disjunction: to prove a sequent with a disjunction on the left, we have to prove each of the two sequents having just one of the disjuncts on the left. In this case one of these sequents is an axiom since it contains Q on both sides. 3. Finally the [ ] rule is applied. The P formula is moved over to the right and the negation eliminated. The result is another axiom a sequent with P on both sides.

5.6.2

Example 2
Axiom P, Q Q Axiom [ ] Q, P and P Q, Q [ ] P Q, (P Q) [ ] P, Q, (P Q) [ ] (P Q) P, Q [ ] (P Q) (P Q) [ r.w.] (P Q) (P Q)

5.6.3

Example 3

Now we shall look quite a long proof of the following sequent: ((P Q) R), (P S ), (Q S ) (R S )

Although the proof is long and rather tedious there is nothing particularly clever about it it is just a case of applying rules until each branch of the proof terminates in a sequent which is an axiom. I have broken the proof tree up into four parts. This is just because the whole proof tree would be far too wide to t onto the page.

16

Q, P

Axiom R, S, Q Q, P

Axiom S, Q, P R, S and Q, P R, S, S R, S, (Q S )

[ ] [ ]

P P, P

Axiom R, S, (Q S ), P R, S, (Q S )

[ ]

and

Q, P

: R, S, (Q S )

(P Q), P

R, S, (Q S )

[ ]

(P Q), P

: R, S, (Q S )

and

(P Q), S

Axiom R, S, (Q S )

(P Q), (P S )

R, S, (Q S )

[ ]

: (P Q), (P S ) R, S, (Q S ) and ((P Q) R), (P S )

Axiom R, (P S ) R, S, (Q S ) R, S, (Q S ) R, S [ ] [ ]

[ ]

((P Q) R), (P S ), (Q S ) ((P Q) R), (P S ), (Q S )

(R S )

The rules of the propositional sequent calculus can be applied in any order and this will not aect the possibility of proving any sequent. However, the size of the resulting proof tree may vary with dierent sequences of rule applications. In the above example I have applied non-branching rules before branching rules; and when applying a branching rule I have always been able to nd an application where one of the branches is an axiom (this is not possible in all proofs). This strategy minimizes the size of a proof tree but it may still be very large.

5.6.4

Example 4

For the nal example we shall look at what happens when we try to prove an invalid sequent. P, Q P and Q, Q P P P [ ]

(P Q), Q (P Q), Q

[ r.w.]

For all invalid propositional sequents, after applying enough rules, we will end up with (at least) one branch ending in a sequent consisting entirely of atomic propositions (i.e. no connectives), which is not an axiom i.e. no proposition occurs on both sides of the sequent.

17

Section 6

Formal Semantics
We have seen that a notion of validity can be dened independently of the notion of provability: An argument is valid if it is not possible for its premisses to be true and its conclusion is false. We could make this precise if we could somehow specify the conditions under which a logical formulae is true. Such a specication is called a formal semantics or an interpretation for a logical language.

6.1

Interpretation of Propositional Calculus

To specify a formal semantics for propositional calculus we take literally the idea that a proposition is either true or false. We say that the semantic value of every propositional formula is one of the two values t or f which are called truth-values. For the atomic propositions this value will depend on the particular fact that the proposition asserts and whether this is true. Since propositional logic does not further analyse atomic propositions we must simply assume there is some way of determining the truth values of these propositions. The connectives are then interpreted as truth-functions which completely determine the truth-values of complex propositions in terms of the values of their atomic constituents.

6.2

Truth-Tables

The truth-functions corresponding to the propositional connectives , and can be dened by the following tables: f f t t f t f t ( ) f f f t 18 f f t t f t f t ( ) f t t t

f t

t f

These give the truth-value of the complex proposition formed by the connective for all possible truth-values of the component propositions.

6.2.1

The Truth-Function for

The truth-function for is dened so that a formulae ( ) is always true except when is true and is false: f f t t f t f t ( ) t t f t

So the statement If logic is interesting then pigs can y is true if either Logic is interesting is false or Pigs can y is true. Thus a formula ( ) is truth-functionally equivalent to ( ).

6.3

Propositional Models

A propositional model for a propositional calculus in which the propositions are denoted by the symbols P1 , . . . , Pn , is a specication assigning a truth-value to each of these proposition symbols. It might by represented by, e.g.: { P1 = t , P2 = f , P3 = f , P4 = t , . . . } Such a model determines the truth of all propositions built up from the atomic propositions P1 , . . . , Pn . (The truth-value of the atoms is given directly and the values of complex formulae are determined by the truth-functions.) If a model, M, makes a formula, , true then we say that M satises .

6.4

Validity in terms of Models

Recall that an arguments being valid means that: in all possible circumstances in which the premisses are true the conclusion is also true. From the point of view of truth-functional semantics each model represents a possible circumstance i.e. a possible set of truth values for the atomic propositions. To assert that an argument is truth-functionally valid we write P1 , . . . , Pn |=T F C and we dene this to mean that ALL models which satisfy ALL of the premisses, P1 , . . . , Pn also satisfy the conclusion C .

19

Section 7

Soundness and Completeness

7.1 Soundness

A proof system is sound with respect to a formal semantics if: Every argument which is provable with the system is also valid according to the semantics. Using the symbols and |= the soundness of a proof system S with respect to a semantics M can be formally dened by stating that: If
S

then

|=M C.

7.2

Completeness

A proof system is complete with respect to a formal semantics if: Every argument which is valid according to the semantics is also provable using the proof system. So the completeness of a proof system S with respect to a semantics M can be formally dened by stating that: If |=M C then
S

C.

7.3

Semantic Adequacy of a Proof System

The notions of soundness and completeness are of fundamental importance to the analysis of logical proof systems. If a proof system is to adequtely reect a formal semantics it must be both sound and complete. I.e. we require that:
S

if and only if

|=M C.

For such a system S , the set of arguments which are provable is exactly the same as the set of arguments which are valid with respect to the formal semantics M .

20

7.4

Soundness and Completeness of the Sequent Calculus

It can be shown that the system of sequent calculus rules, SC, is both sound and complete with respect to the truth-functional semantics for propositional formulae. C if and only if |=T F C. Thus, SC (How this can be show is beyond the scope of this course.)

21

Section 8

Reasoning in Predicate Logic

8.1 Dening in Terms of

We shall shortly look at sequent rules for handling the universal quantier. Predicate logic formulae will in general contain both universal () and existential () quantiers. However, in the same way that in propositional logic we saw that ( ) can be replaced by ( ), the existential quantier can be eliminated by the following re-write rule. [( )] = [( )]

These two forms of formula are equivalent in meaning.

8.2

The Sequent Rule for

[ ] *

(), [( )],

The * indicates a special condition: The constant must not occur anywhere else in the sequent. This restriction is needed because if occurred in another formulae of the sequent then it could be that () is a consequence which can only be proved in the special case of . On the other hand if is not mentioned elsewhere it can be regarded as an arbitrary object with no special properties. Thus if the property (. . .) can be proven true of an arbitrary object it must be true of all objects.

8.2.1

Examples

As an example we now prove that the formula x[P (x) P (x)] is a theorem of predicate logic. This formula asserts that every object either has or does not have the property P (. . .). P (a) P (a) P (a), P (a) [ [ [ ] ] ]

(P (a) P (a))

x[P (x) P (x)] 22

Here the (reverse) application of the [ ] rule could have been used to introduce not only a but any name, since no names occur on the LHS of the sequent. Now consider the follwing illegal application of [ ]: P (b) P (b) P (b)] x[P (x)] ]

This is an incorrect application of the rule, since b already occurs on the LHS of the sequent. (Just because b has the property P (. . .) we cannot conclude that everything has this property.)

8.3

A Sequent Rule for

A formula of the form [( )] clearly entails () for any name . Hence the following sequent rule clearly preserves validity: (), [( )], [ ]

But, the formulae () makes a much weaker claim than [( )]. This means that this rule is not reversible since, the bottom sequent may be valid but not the top one. Consider the case: F (a) x[F (x)] (F (a) F (b)) (F (a) F (b)) [ ]

8.4

A Reversible Version

A quantied formula [( )] has as consequences all formulae of the form (); and, in proving a sequent involving a universal premiss, we may need to employ many of these instances. A simple way of allowing this is by using the following rule: (), [( )], [( )], [ ]

When applying this rule backwards to test a sequent we nd a universal formulae on the LHS and add some instance of this formula to the LHS. Note that the universal formula is not removed because we may later need to apply the rule again to add a dierent instance.

23

8.4.1

An Example Needing 2 Instantiations

We can now see how the sequent we considered earlier can be proved by applying the [ ] rule twice, to instantiate the same universally quantied property with two dierent names. F (a), F (b), x[F (x)] F (a) and F (a), F (b), x[F (x)] (F (a) F (b)) (F (a) F (b)) (F (a) F (b)) [ [ ] ] F (b) [ ]

F (a), F (b) x[F (x)] F (a), x[F (x)] x[F (x)]

8.5

Termination Problem

We now have the problem that the (reverse) application of [ ] results in a more complex rather than a simpler sequent. Furthermore, in any application of [ ] we must choose one of (innitely) many names to instantiate. Although there are various clever things that we can do to pick instances that are likely to lead to a proof, these problems are fundamentally insurmountable. This means that unlike with propositional sequent calculus, there is no general purpose automaitc procedure for testing the validity of sequents containing quantied formulae. In propositional logic we could always tell if a sequent was invalid because after applying suciently many rules we would end up with a sequent containing only atomic propositions which was not an axiom. However, with predicate logic this need not happen because when we the [ ] rule, the universal quantier cannot be eliminated because we may need to apply it again later to yield a dierent instance of the formula.

24

Section 9

Decision Procedures and Decidability

A decision procedure for some class of problems is an algorithm which can solve any problem in that class in a nite time (i.e. by means of a nite number of computational steps). Generally we will be interested in some innite class of similar problems such as: 1. problems of adding any two integers together 2. problems of solving any polynomial equation 3. problems of testing validity of any propositional logic sequent 4. problems of testing validity of any predicate logic sequent

9.1

Decidability

A class of problems is decidable if there is a decision procedure for that class; otherwise it is undecidable. Problem classes 13 of the previous slide are decidable, whereas class 4 is known to be undecidable. Undecidability of testing validity of entailments in a logical language is clearly a major problem if the language is to be used in a computer system: a function call to a procedure used to test entailments will not necessarily terminate.

9.1.1

Semi-Decidability

A problem class, where we want a result Yes or No for each problem, is called (positively) semi-decidable if every positive case can be veried in nite time but there is no procedure which will refute every negative case in nite time. Despite the fact that predicate logic is undecidable, the rules that we have given for the quantiers do give us a complete proof system for predicate logic. Furthermore, it is even possible to devise a strategy for picking instants in applying the [ ] rule, such that every valid sequent is provable in nite time. However, there is no procedure that will demonstrate the invalidity of every invalid sequent in nite time. Hence, although predicate logic is not decidable it is semi-decidable. 25

Section 10

Possible Questions on Classical Logic

If you have understood these notes you should be able to answer the following types of questions about classical logic: Concepts: You may be asked to dene one or more of the logical concepts which have been introduced in the course. These include: proposition, inference rule, proof, validity, provability, propositional model, truth-functional semantics, soundness, completeness, decidability and semi-decidability. Logical Representation: You may be asked to translate natural language sentences into either propositional or predicate logic. Semantics: You may be asket about the truth-functional semantics for propositional logic. You need to know the truth-tables for each connective. Given a propositional model, you should be able to determine whether a formula is made true or false by the model and whether the model satises a given formula (it satises just those formulae which it makes true). Sequent Calculus: You may be asked to carry out a short proof using the sequent calculus (possibly including the quantier rules). You should give a proof tree with the sequent to be proved at the root of the tree. In these notes proof trees have been given with the root at the bottom but, if you nd it more convenient, you may put the root (i.e. the sequent to be proved) at the top and expand the proof tree downwards. Uses of Logic: You may be asked about uses of logic in computer systems or about diculties associated with the use of logic. Be aware that these notes do not cover everything you need to know about logic for the AR34 course. This material is intended only to provide a basic grounding in classical logic which provides a foundation for understanding Knowledge Representation and Reasoning techniques used in AI.

26

Section 11

Exercises
1. (a) Translate the following sentences into propositional logic. Give a key indicating the meaning of each propositional letter. i. If the mug was droped and it was fragile it is now broken. (1 mark) ii. Toby is neither happy nor sad he is confused. (1 mark) iii. Jeremy eats toast for breakfast except on Friday. (1 mark) (b) Give truth-tables for the propositional connectives and . marks) (2

(c) A model M for a propositional language is represented by the following structure: {A = t , B = f , C = f } i. What truth-value is assigned to the formula ((A B ) C ) by M ? (1 mark) ii. Does M satisfy the formula (A (B C )) ? (1 mark) (d) Using the rules of the sequent calculus prove the following propositonal argument: P, (P Q) (Q R) (3 marks) (e) Represent the following statement in the notation of predicate logic: A traveller visited every country in Europe. (3 marks) (f) Using the sequent calculus prove that the following predicate logic argument is valid: x[F (x) G(x)] (F (a) G(b)) (5 marks)

(g) Explain what is meant by saying that the predicate calculus is semidecidable. (2 marks)

2. (a) Translate the following sentences into propositional logic: i. It is the end of term if tomorrow is Friday ii. On Wednesdays and Fridays Susan goes climbing (1 mark) (1 mark)

27

(b) What does it mean to say that a proof system for a logical language is sound with respect to some formal semantics for that language? (2 marks) (c) Explain by means of truth-tables, why in the truth-functional semantics for propositional logic the formula (P Q) is equivalent to (P Q). (3 marks) (d) Using the rules of the sequent calculus prove the propositonal argument: (P Q) (P Q) (3 marks)

(e) Represent the following statements in the notation of predicate logic: i. Every number is either odd or even ii. No student enjoys every lecture (2 marks) (2 marks)

(f) Using the sequent calculus prove that the following predicate logic argument is valid: R(a), x[R(x) S (x)] x[S (x)] (6 marks)

28