Home | | Artificial Intelligence | Propositional and Predicate Logic

# Propositional and Predicate Logic

Logic is concerned with reasoning and the validity of arguments. In general, in logic, we are not concerned with the truth of statements, but rather with their validity.

Propositional and Predicate Logic

Logic is concerned with reasoning and the validity of arguments. In general, in logic, we are not concerned with the truth of statements, but rather with their validity. That is to say, although the following argument is clearly logical, it is not something that we would consider to be true:

All lemons are blue

Mary is a lemon

Therefore, Mary is blue

This set of statements is considered to be valid because the conclusion (Mary is blue) follows logically from the other two statements, which we often call the premises. The reason that validity and truth can be separated in this way is simple: a piece of a reasoning is considered to be valid if its conclusion is true in cases where its premises are also true. Hence, a valid set of statements such as the ones above can give a false conclusion, provided one or more of the premises are also false.

We can say: a piece of reasoning is valid if it leads to a true conclusion in every situation where the premises are true.

Logic is concerned with truth values. The possible truth values are true and false. These can be considered to be the fundamental units of logic, and almost all logic is ultimately concerned with these truth values.

Logic is widely used in computer science, and particularly in Artificial Intelligence. Logic is widely used as a representational method for Artificial Intelligence. Unlike some other representations, logic allows us to easily reason about negatives (such as, ŌĆ£this book is not redŌĆØ) and disjunctions (ŌĆ£orŌĆØŌĆösuch as, ŌĆ£HeŌĆÖs either a soldier or a sailorŌĆØ).

Logic is also often used as a representational method for communicating concepts and theories within the Artificial Intelligence community. In addition, logic is used to represent language in systems that are able to understand and analyze human language.

As we will see, one of the main weaknesses of traditional logic is its inability to deal with uncertainty. Logical statements must be expressed in terms of truth or falsehoodŌĆöit is not possible to reason, in classical logic, about possibilities. We will see different versions of logic such as modal logics that provide some ability to reason about possibilities, and also probabilistic methods and fuzzy logic that provide much more rigorous ways to reason in uncertain situations.

Logical Operators

In reasoning about truth values, we need to use a number of operators, which can be applied to truth values.

We are familiar with several of these operators from everyday language:

I like apples and oranges.

You can have an ice cream or a cake.

If you come from France, then you speak French.

Here we see the four most basic logical operators being used in everyday language. The operators are:

and

or

not

if . . . then . . . (usually called implies)

One important point to note is that or is slightly different from the way we usually use it. In the sentence, ŌĆ£You can have an icecream or a cake,ŌĆØ the mother is usually suggesting to her child that he can only have one of the items, but not both. This is referred to as an exclusive-or in logic because the case where both are allowed is excluded.

The version of or that is used in logic is called inclusive-or and allows the case with both options.

The operators are usually written using the following symbols, although other

symbols are sometimes used, according to the context: and Ōł¦

not ’┐ó

implies ŌåÆ

iff Ōåö

Iff is an abbreviation that is commonly used to mean ŌĆ£if and only if.ŌĆØ

We see later that this is a stronger form of implies that holds true if one thing implies another, and also the second thing implies the first.

For example, ŌĆ£you can have an ice-cream if and only if you eat your dinner.ŌĆØ It may not be immediately apparent why this is different from ŌĆ£you can have an icecream if you eat your dinner.ŌĆØ This is because most mothers really mean iff when they use if in this way.

Translating between English and Logic Notation

To use logic, it is first necessary to convert facts and rules about the real world into logical expressions using the logical operators

Without a reasonable amount of experience at this translation, it can seem quite a

Let us examine some examples. First, we will consider the simple operators, Ōł¦, Ōł©, and

’┐ó.

Sentences that use the word and in English to express more than one concept, all of which is true at once, can be easily translated into logic using the AND operator, Ōł¦.

For example: ŌĆ£It is raining and it is Tuesday.ŌĆØ might be expressed as: R Ōł¦ T, Where R means ŌĆ£it is rainingŌĆØ and T means ŌĆ£it is Tuesday.ŌĆØ

For example, if it is not necessary to discuss where it is raining, R is probably enough. If we need to write expressions such as ŌĆ£it is raining in New YorkŌĆØ or ŌĆ£it is raining heavilyŌĆØ or even ŌĆ£it rained for 30 minutes on Thursday,ŌĆØ then R will probably not suffice. To express more complex concepts like these, we usually use predicates. Hence, for example, we might translate ŌĆ£it is raining in New YorkŌĆØ as: N(R) We

might equally well choose to write it as: R(N)

This depends on whether we consider the rain to be a property of New York, or vice versa. In other words, when we write N(R), we are saying that a property of the rain is that it is in New York, whereas with R(N) we are saying that a property of New York is that it is raining. Which we use depends on the problem we are solving. It is likely that if we are solving a problem about New York, we would use R(N), whereas if we are solving a problem about the location of various types of weather, we might use N(R).

Let us return nowto the logical operators. The expression ŌĆ£it is raining inNew York, and IŌĆÖmeither getting sick or just very tiredŌĆØcan be expressed as follows: R(N) Ōł¦ (S(I) Ōł© T(I))

Here we have used both the Ōł¦ operator, and the Ōł© operator to express a collection of statements. The statement can be broken down into two sections, which is indicated by the use of parentheses.

The section in the parentheses is S(I) Ōł© T(I), which means ŌĆ£IŌĆÖm either getting sick OR IŌĆÖm very tiredŌĆØ. This expression is ŌĆ£ANDŌĆÖedŌĆØwith the part outside the parentheses, which is R(N).

Finally, the ’┐ó operator is applied exactly as you would expectŌĆöto express negation. For example, It is not raining in New York, might be expressed as ’┐óR(N)

It is important to get the ’┐ó in the right place. For example: ŌĆ£IŌĆÖm either not well or just very tiredŌĆØ would be translated as ’┐óW(I) Ōł© T(I)

The position of the ’┐ó here indicates that it is bound to W(I) and does not play any

role in affecting T(I).

Now let us see how the ŌåÆ operator is used. Often when dealing with logic we are discussing rules, which express concepts such as ŌĆ£if it is raining then I will get wet.ŌĆØ

This sentence might be translated into logic as RŌåÆW(I)

This is read ŌĆ£R implies W(I)ŌĆØ or ŌĆ£IF R THEN W(I)ŌĆØ. By replacing the symbols R and W(I) with their respective English language equivalents, we can see that this sentence can be read as ŌĆ£raining implies IŌĆÖll get wetŌĆØ or ŌĆ£IF itŌĆÖs raining THEN IŌĆÖll get wet.ŌĆØ

Implication can be used to express much more complex concepts than this.

For example, ŌĆ£Whenever he eats sandwiches that have pickles in them, he ends up either asleep at his desk or singing loud songsŌĆØ might be translated as S(y) Ōł¦ E(x, y) Ōł¦ P(y)ŌåÆA(x) Ōł© (S(x, z) Ōł¦ L(z))

Here we have used the following symbol translations:  S(y) means that y is a sandwich. E(x, y) means that x (the man) eats y (the sandwich).

P(y) means that y (the sandwich) has pickles in it.

A(x) means that x ends up asleep at his desk.

S(x, z) means that x (the man) sings z (songs).  L(z) means that z (the songs) are loud.

The important thing to realize is that the choice of variables and predicates is important, but that you can choose any variables and predicates that map well to your problem and that help you to solve the problem.

For example, in the example we have just looked at, we could perfectly well have used instead SŌåÆA Ōł© L where S means ŌĆ£he eats a sandwich which has pickles in it,ŌĆØ A means ŌĆ£he ends up asleep at his desk,ŌĆØ and L means ŌĆ£he sings loud songs.ŌĆØ

The choice of granularity is important, but there is no right or wrong way to make this choice. In this simpler logical expression, we have chosen to express a simple relationship between three variables, which makes sense if those variables are all that we care aboutŌĆöin other words, we donŌĆÖt need to know anything else about the sandwich, or the songs, or the man, and the facts we examine are simply whether or not he eats a sandwich with pickles, sleeps at his desk, and sings loud songs.

The first translation we gave is more appropriate if we need to examine these concepts in more detail and reason more deeply about the entities involved.

Note that we have thus far tended to use single letters to represent logical variables. It is also perfectly acceptable to use longer variable names, and thus to write expressions such as the following:

Fish (x) Ōł¦ living (x) ŌåÆhas_scales (x)

This kind of notation is obviously more useful when writing logical expressions that are intended to be read by humans but when manipulated by a computer do not add any value.

Truth Tables

We can use variables to represent possible truth values, in much the same way that variables are used in algebra to represent possible numerical values.

We can then apply logical operators to these variables and can reason about the way in which they behave.

It is usual to represent the behavior of these logical operators using truth tables.

A truth table shows the possible values that can be generated by applying an operator to truth values.

Not

First of all, we will look at the truth table for not, ’┐ó.

Not is a unary operator, which means it is applied only to one variable.

Its behavior is very simple:

true is equal to false

false is equal to true

If variable A has value true, then ’┐óA has value false.

If variable B has value false, then ’┐óB has value true.

├ś These can be represented by a truth table, And

Now, let us examine the truth table for our first binary operatorŌĆöone which acts on two variables: Ōł¦ is also called the conjunctive operator.

A Ōł¦ B is the conjunction of A and B.

You can see that the only entry in the truth table for which A Ōł¦ B is true is the

one where A is true and B is true. If A is false, or if B is false, then A Ōł¦ B is false. If both A and B are false, then A Ōł¦ B is also false.

What do A and B mean? They can represent any statement, or proposition, that can take on a truth value.

For example, A might represent ŌĆ£ItŌĆÖs sunny,ŌĆØ and B might represent ŌĆ£ItŌĆÖs warm outside.ŌĆØ In this case, A Ōł¦ B would mean ŌĆ£It is sunny and itŌĆÖs warm outside,ŌĆØ which clearly is true only if the two component parts are true (i.e., if it is true that it is sunny and it is true that it is warm outside).

Or

The truth table for the or operator, Ōł© Ōł© is also called the disjunctive operator.

A Ōł© B is the disjunction of A and B.

Clearly A Ōł© B is true for any situation except when both A and B are false.

If A is true, or if B is true, or if both A and B are true, A Ōł© B is true.

This table represents the inclusive-or operator.

A table to represent exclusive-or would have false in the final row. In other

words, while A Ōł© B is true if A and B are both true, A EOR B (A exclusive-or

is false if A and B are both true.

You may also notice a pleasing symmetry between the truth tables for Ōł¦ and Ōł©. This will become useful later, as will a number of other symmetrical relationships.

Implies

The truth table for implies (ŌåÆ) is a little less intuitive. This form of implication is also known as material implication

In the statement AŌåÆB, A is the antecedent, and B is the consequent. The bottom two lines of the table should be obvious. If A is true and B is true, then A ŌåÆ B seems to be a reasonable thing to believe.

For example, if A means ŌĆ£you live in FranceŌĆØ and B means ŌĆ£You speak French,ŌĆØ then AŌåÆB corresponds to the statement ŌĆ£if you live in France, then you speak French.ŌĆØ

Clearly, this statement is true (AŌåÆB is true) if I live in France and I speak French (A is true and B is true).

Similarly, if I live in France, but I donŌĆÖt speak French (A is true, but B is false), then it is clear that AŌåÆB is not true.

The situations where A is false are a little less clear. If I do not live in France (A is not true), then the truth table tells us that regardless of whether I speak French or not (the value of B), the statement AŌåÆB is true. AŌåÆB is usually read as ŌĆ£A implies BŌĆØ but can also be read as ŌĆ£If A then BŌĆØ or ŌĆ£If A is true then B is true.ŌĆØ

Hence, if A is false, the statement is not really saying anything about the value of B, so B is free to take on any value (as long as it is true or false, of course!).

All of the following statements are valid:

52 = 25 ŌåÆ4 = 4 (true ŌåÆtrue)

9 _ 9 = 123 ŌåÆ8 > 3 (false ŌåÆtrue)

52 = 25 ŌåÆ0 = 2 (false ŌåÆfalse)

In fact, in the second and third examples, the consequent could be given any meaning, and the statement would still be true. For example, the following statement is valid:

52 = 25 ŌåÆLogic is weird

Notice that when looking at simple logical statements like these, there does not need to be any real-world relationship between the antecedent and the consequent.

For logic to be useful, though, we tend to want the relationships being expressed to be meaningful as well as being logically true.

Iff

├ś The truth table for iff (if and only if {Ōåö}) is as follows: It can be seen that A Ōåö B is true as long as A and B have the same value.

In other words, if one is true and the other false, then A Ōåö B is false. Otherwise, if A and B have the same value, AŌåö B is true.

Complex Truth Tables

Truth tables are not limited to showing the values for single operators.

For example, a truth table can be used to display the possible values for A Ōł¦ (B Ōł©C). Note that for two variables, the truth table has four lines, and for three variables, it has

eight. In general, a truth table for n variables will have 2n lines.

The use of brackets in this expression is important. A Ōł¦ (B Ōł© C) is not the same as (A Ōł¦ B) Ōł© C.

To avoid ambiguity, the logical operators are assigned precedence, as with mathematical operators.

The order of precedence that is used is as follows: ’┐ó, Ōł¦, Ōł©,ŌåÆ,Ōåö

Hence, in a statement such as ’┐óA Ōł© ’┐óB Ōł¦ C, the ’┐ó operator has the greatest

precedence, meaning that it is most closely tied to its symbols. Ōł¦ has a greater precedence than Ōł©, which means that the sentence above can be expressed as (’┐óA) Ōł© ((’┐óB) Ōł¦ C)

Similarly, when we write ’┐óA Ōł© B this is the same as (’┐óA) Ōł© B rather than ’┐ó(A Ōł© B)

In general, it is a good idea to use brackets whenever an expression might otherwise be ambiguous.

Tautology

Consider the following truth table: This truth table has a property that we have not seen before: the value of the expression AŌł©’┐óA is true regardless of the value of A.

An expression like this that is always true is called a tautology. If A is a tautology, we write: |=A

A logical expression that is a tautology is often described as being valid.

A valid expression is defined as being one that is true under any interpretation.

In other words, no matter what meanings and values we assign to the variables in a valid expression, it will still be true.

For example, the following sentences are all valid:

If wibble is true, then wibble is true.

Either wibble is true, or wibble is not true.

In the language of logic, we can replace wibble with the symbol A, in which case these two statements can be rewritten as

AŌåÆA

If an expression is false in any interpretation, it is described as being contradictory. The following expressions are contradictory:

Ōł¦ ’┐óA

Equivalence

Consider the following two expressions: A Ōł¦ B

B Ōł¦ A

It should be fairly clear that these two expressions will always have the same value for a given pair of values for A and B.

In otherwords, we say that the first expression is logically equivalent to the second

expression.

We write this as A Ōł¦ B _ B Ōł¦ A. This means that the Ōł¦ operator is commutative.

Note that this is not the same as implication: A Ōł¦ BŌåÆB Ōł¦ A, although this second statement is also true.

The difference is that if for two expressions e1 and e2: e1 _ e2, then e1 will always have the same value as e2 for a given set of variables.

On the other hand, as we have seen, e1ŌåÆe2 is true if e1 is false and e2 is true. There are a number of logical equivalences that are extremely useful.

The following is a list of a few of the most common:

A Ōł¦ A _ A

A Ōł¦ (B Ōł¦ C) _ (A Ōł¦ B) Ōł¦ C (Ōł¦ is associative)

A Ōł¦ (B Ōł© C) _ (A Ōł¦ B) Ōł© (A Ōł¦ C) (Ōł¦ is distributive over Ōł© )

A Ōł¦ (A Ōł© B) _ A

A Ōł© (A Ōł¦ B) _ A

A Ōł¦ true _ A

A Ōł¦ false _ false

All of these equivalences can be proved by drawing up the truth tables for each side of the equivalence and seeing if the two tables are the same.

The following is a very important equivalence: AŌåÆB _ ’┐óA Ōł© B

We do not need to use the ŌåÆ symbol at allŌĆöwe can replace it with a combination of ’┐ó and Ōł© .

Similarly, the following equivalences mean we do not need to use Ōł¦ orŌåö:

A Ōł¦ B _ ’┐ó(’┐óA Ōł© ’┐óB)

In fact, any binary logical operator can be expressed using ’┐ó and Ōł© . This is a fact

that is employed in electronic circuits, where nor gates, based on an operator called nor, are used. Nor is represented by Ōåō, and is defined as follows:

A Ōåō B _ ’┐ó(A Ōł© B)

Finally, the following equivalences are known as DeMorganŌĆÖs Laws:

A Ōł¦ B _ ’┐ó(’┐óA Ōł© ’┐óB)

A Ōł© B _ ’┐ó(’┐óA Ōł¦ ’┐óB)

By using these and other equivalences, logical expressions can be simplified.

For example, (C Ōł¦ D) Ōł© ((C Ōł¦ D) Ōł¦ E) can be simplified using the following rule: A Ōł© (A Ōł¦ B) _ A hence, (C Ōł¦ D) Ōł© ((C Ōł¦ D) Ōł¦ E) _ C Ōł¦ D

In this way, it is possible to eliminate subexpressions that do not contribute to the overall value of the expression.

Propositional Logic

There are a number of possible systems of logic.

The system we have been examining so far is called propositional logic.

The language that is used to express propositional logic is called the propositional calculus.

A logical system can be defined in terms of its syntax (the alphabet of symbols and how they can be combined), its semantics (what the symbols mean), and a set of rules of deduction that enable us to derive one expression from a set of other expressions and thus make arguments and proofs.

Syntax

We have already examined the syntax of propositional calculus. The alphabet of symbols, _ is defined as follows

= {true, false, ’┐ó,ŌåÆ, (, ), Ōł¦, Ōł© ,Ōåö, p1, p2, p3, . . . , pn, . . . }

Here we have used set notation to define the possible values that are contained within the alphabet Ōłæ.

Note that we allow an infinite number of proposition letters, or propositional symbols, p1, p2, p3, . . . , and so on.

More usually, we will represent these by capital letters P, Q, R, and so on,

If we need to represent a very large number of them, we will use the subscript notation (e.g., p1).

An expression is referred to as a well-formed formula (often abbreviated as wff) or a sentence if it is constructed correctly, according to the rules of the syntax of propositional calculus, which are defined as follows.

In these rules, we use A, B, C to represent sentences. In other words, we define a sentence recursively, in terms of other sentences.

The following are wellformed sentences:

P,Q,R. . .

true, false

(A)

’┐óA

A Ōł¦ B

AŌåÆB

AŌåö B

Hence, we can see that the following is an example of a wff: P Ōł¦ Q Ōł© (B Ōł¦ ’┐óC)ŌåÆA Ōł¦ B Ōł© D Ōł¦ (’┐óE)

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Propositional and Predicate Logic |