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 A↔ B

·         Hence, we can see that the following is an example of a wff: P ∧ Q ∨ (B ∧ ￢C)→A ∧ B ∨ D ∧ (￢E)

 

Semantics

·          The semantics of the operators of propositional calculus can be defined interms of truth tables.

·          The meaning of P ∧ Q is defined as “true when P is true and Q is also true.”

·          The meaning of symbols such as P and Q is arbitrary and could be ignored altogether if we were reasoning about pure logic.

·          In other words, reasoning about sentences such as P ∨ Q∧ ￢R is possible without considering what P, Q, and R mean.

·          Because we are using logic as a representational method for artificial intelligence, however, it is often the case that when using propositional logic, the meanings of these symbols are very important.

·         The beauty of this representation is that it is possible for a computer to reason about them in a very general way, without needing to know much about the real world.

·         In other words, if we tell a computer, “I like ice cream, and I like chocolate,” it might represent this statement as A ∧ B, which it could then use to reason

            with, and, as we will see, it can use this to make deductions.

 

Predicate Calculus

 Syntax

·         Predicate calculus allows us to reason about properties of objects and relationships between objects.

·         In propositional calculus, we could express the English statement “I like cheese” by A. This enables us to create constructs such as ￢A, which means “I do not like cheese,” but it does not allow us to extract any information about the cheese, or me, or other things that I like.

·         In predicate calculus, we use predicates to express properties of objects. So the sentence “I like cheese” might be expressed as L(me, cheese) where L is a predicate that represents the idea of “liking.” Note that as well as expressing a property of me, this statement also expresses a relationship between me and cheese. This can be useful, as we will see, in describing environments for robots and other agents.

·          For example, a simple agent may be concerned with the location of various blocks, and a statement about the world might be T(A,B), which could mean:

Block A is on top of Block B.

·          It is also possible to make more general statements using the predicate calculus.

 

 

Functions

·         In much the same way that functions can be used in mathematics, we can express an object that relates to another object in a specific way using functions.

·         For example, to represent the statement “my mother likes cheese,” we might use L(m(me),cheese)

·         Here the function m(x) means the mother of x. Functions can take more than one argument, and in general a function with n arguments is represented as

f(x1, x2, x3, . . . , xn)

 

First-Order Predicate Logic

·         The type of predicate calculus that we have been referring to is also called firstorder predicate logic (FOPL).

·         A first-order logic is one in which the quantifiers and can be applied to objects or terms, but not to predicates or functions.

·         So we can define the syntax of FOPL as follows. First,we define a term:

·         A constant is a term.

·         A variable is a term. f(x1, x2, x3, . . . , xn) is a term if x1, x2, x3, . . . , xn are all terms.

·         Anything that does not meet the above description cannot be a term.

·         For example, the following is not a term: x P(x). This kind of construction we call a sentence or a well-formed formula (wff), which is defined as follows.

·         In these definitions, P is a predicate, x1, x2, x3, . . . , xn are terms, and A,B are wff ’s. The following are the acceptable forms for wff ’s:

P(x1, x2, x3, . . . , xn) ￢A A ∧ B A ∨ B A→B  A↔ B (x)A (x)A

·         An atomic formula is a wff of the form P(x1, x2, x3, . . . , xn).

·         Higher order logics exist in which quantifiers can be applied to predicates and functions, and where the following expression is an example of a wff:

(P)( x)P(x)

 

Soundness

·         We have seen that a logical system such as propositional logic consists of a syntax, a semantics, and a set of rules of deduction.

·         A logical system also has a set of fundamental truths, which are known as axioms.

·         The axioms are the basic rules that are known to be true and from which all other theorems within the system can be proved.

·         An axiom of propositional logic, for example, is A→(B→A)

·         A theorem of a logical system is a statement that can be proved by applying the rules of deduction to the axioms in the system.

·         If A is a theorem, then we write ├ A

·         A logical system is described as being sound if every theorem is logically valid, or a tautology.

·         It can be proved by induction that both propositional logic and FOPL are sound.

 

Completeness

·         A logical system is complete if every tautology is a theorem—in other words, if every valid statement in the logic can be proved by applying the rules of deduction

                to the axioms. Both propositional logic and FOPL are complete.

 

Decidability

·         A logical system is decidable if it is possible to produce an algorithm that will determine whether any wff is a theorem. In other words, if a logical system is decidable, then a computer can be used to determine whether logical expressions in that system are valid or not.

·         We can prove that propositional logic is decidable by using the fact that it is complete.

·          We can prove that a wff A is a theorem by showing that it is a tautology. To show if a wff is a tautology, we simply need to draw up a truth table for that wff and

·         show that all the lines have true as the result. This can clearly be done algorithmically because we know that a truth table for n values has 2n lines and is therefore finite, for a finite number of variables.

·          FOPL, on the other hand, is not decidable. This is due to the fact that it is not possible to develop an algorithm that will determine whether an arbitrary wff in

              FOPL is logically valid.

 

Monotonicity

·         A logical system is described as being monotonic if a valid proof in the system cannot be made invalid by adding additional premises or assumptions.

·         In other words, if we find that we can prove a conclusion C by applying rules of deduction to a premise B with assumptions A, then adding additional assumptions

A￢and B￢will not stop us from being able to deduce C.

·         Monotonicity of a logical system can be expressed as follows: If we can prove {A, B} ├ C, then we can also prove: {A, B, A_, B_} ├ C.

·         In other words, even adding contradictory assumptions does not stop us from making the proof in a monotonic system.

·         In fact, it turns out that adding contradictory assumptions allows us to prove anything, including invalid conclusions. This makes sense if we recall the line in

          the truth table for →, which shows that false → true. By adding a contradictory assumption, we make our assumptions false and can thus prove any conclusion.