Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | 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 ∧

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.

**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 2^{n} 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

∨
￢A

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

∧
￢A

(A ∨ ￢A)→(A ∧ ￢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 ∧ A _ A

A ∧ (B ∧ C) _ (A ∧ B) ∧ C (∧ is associative)

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

A ∨ true _
true

A ∨ false _
A

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)

A↔ B _ ￢(￢(￢A ∨ B) ∨ ￢ (￢B ∨ A))

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

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

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.