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 ∧

             or ∨

             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 daunting task in some cases.

· 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.