UNIT-IV
The Propositional calculus: The Prepositional Calculus : Introduction – Syntax of the
Prepositional Calculus – Truth-Assignments – Validity and Satisfiability – Equivalence and
Normal Forms – resolution in Prepositional Calculus.
The Predicate calculus: Syntax of the Predicate Calculate Calculus – Structures and
Satisfiability – Equivalence – Un-solvability and NP-Completeness.
A proposition (or a statement) is classified as a declarative sentence to which only
one of the truth values. i.e. true or false. can be assigned. When a proposition is
true, we say that its truth value is T. When it is false, we say that its truth value is
F.
Consider. for example. the following sentences in English:
1. New Delhi is the capital of India.
2. The square of 4 is 16.
3. The square of 5 is 27.
4. Every college will have a computer by 2010 A.D.
S. Mathematical logic is a difficult subject.
6. Chennai is a beautiful city.
7. Bring me coffee.
8. No. thank you.
9. This statement is false.
The sentences 1-3 are propositions.
The sentences 1 and 2 have the truth value
T. The sentence 3 has the truth value F.
Although we cannot know the truth
value of 4 at present. we definitely know that it is true or false, but not both.
So the sentence 4 is a proposition.
For the same reason, the sentences 5 and 6 are propositions.
To sentences 7 and 8, we cannot assign truth values as they are not
declarative sentences.
The sentence 9 looks like a proposition.
However, if we assign the truth value T to sentence 9, then the sentence
asserts that it is false. If we assign the truth value F to sentence 9, then the
sentence asserts that it is true.
Thus the sentence 9 has either both the truth values (ornone of the two truth
values),
Therefore, the sentence 9 is not a proposition,
We use capital letters to denote propositions,
We now define the following connectives. There are five basic
connectives.
(i) Negation (NOT)
(ii) Conjunction (AND)
(iii) Disjunction (OR)
(iv) Implication (IF THEN ,:~/
(v) If and Only If.
Translate the following sentences into propositional forms:
(a) If it is not raining and I have the time. then I will go to a movie.
(b) It is raining and I will not go to a movie..
(c) It is not raining. ./
(d) I will not go to a movie.
(e) I will go to a movie only if it is not raining.
Solution
Let P be the proposition 'It is raining'.
Let Q be the proposition 'I have the time'.
Let R be the proposition '1 will go to a movie'.
Solution
(a) I will go to a movie if and only if it is not raining and I have thetime.
(b) I will go to a movie if and only if I have the time.
(c) It is not the case that I have the time or I will go to a movie.
(d) I will go to a movie, only if it is not raining or I have the time.
A wff is not a proposition, but if we substitute a proposition in place of a
propositional variable, we get a Proposition.
A tautology or a universally true formula is a well-formed formula whose truth
Xvalue is T for all possible assignments of truth values to the propositional
variables.
For example.
LOGICAL IDENTITIES
NORMAL FORMS:
To Obtain DNF:
Construction to obtain the princip disjunctive normal form of a given
formula:
Step 4 Repeat step 3 until all the elementary products are reduced to sum of
minterms. Use the idempotent laws to avoid repetition of minterms.
Rules of inference for propositional calculus (statement calculus)
Resolution in Prepositional Logic:
Basis of Resolution:
Winter V summer
~Winter V cold
Resolving above two clauses, the resolvent : summer V cold.
Winter and ~winter resolvent is nil, which is a contradiction. Resolution stops and the above
statements are not true at the same time.
The theoretical basis of the resolution procedure in predicate logic is “ Herbrand ’s
theorem”:
To show that a set of clauses S is unsatisfiable, it is necessary to consider only
interpretations over a particular set, called the Herbrand universe of S
A set of clauses S is unsatisfiable if and only if a finite subset of ground instances of S
is unsatisfiable.
Resolution in Prepositional Logic:
In Propositional logic the procedure for producing a proof by resolution of proposition P
with respect to a set of axioms F is as follows:
1. Convert all the propositions of F to clause form.
2. Negate P and covert the result to clause form. Add it to the set of clauses obtained in step1.
3. Repeat until either a contradiction is found or no progress can be made:
(a) Select two clauses. Call these the parent clauses
(b) Resolve them together. The resulting clause, called resolvent, will be the disjunction of all
the literals of both parent clauses with the exception: If there are any pair of literals L and ~L
such that one parent clause contains L and other contains ~L, the cancel each other.
(c) If the resolvent is the empty clause, then a contradiction has been found, If it is not, then
add it to the set of clauses available to the procedure.
Example:
Given axioms: P , (P ∩ Q)R, (S V T)Q, T and prove R is true
Clause form : 1. P 2. ~P V ~Q V R 3. ~S V Q 4. ~T V Q 5. T Add 6. ~R to it
Now take: ~R ~Q V R
(2)
~Q ~T V Q
(4)
~T T
(5)
NIL
NIL Indicates Contradiction. It is due to assumption ~R is true. Therefore R is true.
PREDICATE CALCULUS
Consider two propositions 'Ram is a student', and 'Sam is a student. As
propositions, there is no relation between them, but we know they have something
in common. Both Ram and Sam share the property of being a student. We can
replace the both propositions by a single statement x is a student'. By replacing x
by Ram or Sam (or any other name), we get many propositions. The common
feature expressed by 'is a student' is called a predicate.
Sentences involving predicate describing the property of objects are denoted
by P(x), where P denotes the predicate and x is a variable denoting any object.
For example P(x) can denote 'x is a student'. In this sentence, x is a variable and P
denotes the predicate ‘is a student'. The sentence 'x is the father of y’ also
involves a predicate 'is the father of’. Here the predicate describes the relation
between two persons. We can write this sentence as F(x, y), Similarly, 2x + 3y =
4z can be described by S(x,y,z).
Representing Simple Facts in Logic:
Prepositional Logic:
It is raining RAINING
It is sunny SUNNY
It is Windy WINDY
If it is raining then it is not sunny.
RAINING ~ SUNNY (~ NOT OPERAOR)
Limitations of Propositional Logic:
Socrates is a man. SOCRATESMAN (a)
Plato is a man. PLATOMAN (b)
All men are mortal MORTALMAN
The fact MORTALMAN is not giving the fact “All men are mortal” instead it gives Mortal is a man as per
(a) and (b) above. Here propositional calculus fails to represent the fact; we use the First Order
Predicate Logic to represent this fact. This representation is First order
predicate logic.
Represent the following facts using Predicate logic and then answer the question was Marcus loyal to
Caesar?
Given Fact Equivalent Predicate Logic Representation
1. Marcus was a man Man(Marcus).
2. Marcus was a Pompeian Pompeian(Marcus)
3. All Pompeians were Romans x: Pompeian(x) Roman(x)
4. Caesar was a ruler ruler(Caesar)
5. All Romans were either loyal to Caesar or x:Roman(x)loyalto(x, Caesar) V hate(x, Caesar)
hated him
6. Everyone is loyal to someone loyalto(x,y)
7. People only try to assassinate rules they x: y:Person(x)∩ruler(y) ∩
are not loyal to tryassassinate(x,y)~loyalto(x,y)
8. Marcus tried to assassinate Caesar tryassassinate(Marcus, Caesar)
~loyalto(Marcus, Caesar)
Person(Marcus)∩ruler(Caesar)∩tryassassinate(Marcus, Caesar)
Person(Marcus)∩ruler(Caesar)
Person(Marcus)
Here the fact Person (Marcus) was not given in the set of facts. We have only a fact
man(Marcus) is available. So the fact All men are people is added then : man(x)person(x)
ALGORITHM TO CONVERT THE WELL-FORMED FORMULAE (wff) i.e. facts in predicate logic form
TO CONJUNCTIVE NORMAL FORM(CNF):
1. Eliminate , using ab is equivalent to ~a V b
2. Reduce the scope of each ~ to a single term.
~(~a) = a,
~(a V b) = ~a ∩ ~b,
~(a∩b) = ~a V ~b,
~ x:P(x) = x: ~P(x)
~ x:P(x) = x: ~P(x)
3. Standardize variables so that each quantifier binds a unique variable.
Would be converted to
4. Move all the quantifiers to the left of the formula without changing their relative order.
At this point, the formula is in Prenex normal form.
5. Eliminate Existential quantifiers.
y:Presidet(y) can be transformed into the formula President(S1) where S1 is a function
with no arguments that satisfies President.
y:father-of(y,x) changes to
These functions are called Skolem functions. Functions with no arguments are called
Skolem constants.
6. Drop the prefix. All variables are universally quantified.
7. Convert the matrix into conjunction of disjuncts.
8. Create a separate clause corresponding to each conjunct.
9. Standardize apart the apart the variables in the set of clauses generated in step 8.