Scribd
Upload
31 views8 pages

Understanding Predicate Calculus

Predicate calculus, also known as predicate logic, provides a formal system for statements involving variables. It uses predicates and quantifiers to represent statements like "x is greater than 10" or "for all x, P(x)". The key aspects covered in the document include: - Using predicates like P(x) and quantifiers like ∀x and ∃x to represent statements. - The difference between bound and free variables. - Negating quantified statements using rules like ~∀xP(x) = ∃x~P(x). - Valid formulas and equivalences over a universe of discourse. - Inference rules like Universal Specification and Existential Generalization

Uploaded by

Khushi Hanuman
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views8 pages

Understanding Predicate Calculus

Predicate calculus, also known as predicate logic, provides a formal system for statements involving variables. It uses predicates and quantifiers to represent statements like "x is greater than 10" or "for all x, P(x)". The key aspects covered in the document include: - Using predicates like P(x) and quantifiers like ∀x and ∃x to represent statements. - The difference between bound and free variables. - Negating quantified statements using rules like ~∀xP(x) = ∃x~P(x). - Valid formulas and equivalences over a universe of discourse. - Inference rules like Universal Specification and Existential Generalization

Uploaded by

Khushi Hanuman
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

PREDICATE CALCULUS OR PREDICATE LOGIC

09/08/2023

Introduction:
1. In mathematics and computer programs, we encounter statements involving
variables such as “x > 10”, “x = y + 5” and “x + y = z”. These statements are
neither true nor false, when the values of the variables are not specified.

2. The statement “x is greater than 10” has 2 parts. The first part, the variable x, is
the subject of the statement. The second part “is greater than 10”, which refers to
a property that the subject can have, is called the predicate.

3. Notation:

Denote “x is greater than 10” by the notation P(x), where P denotes the
predicate “is greater than 10” and x is the variable.
P(x) is called the propositional function at x.

Once a value has been assigned to the variable x, the statement P(x) becomes a
proposition and has a truth value.

For example, P(x)=x>10 the truth values of


P(15)=15 > 10 is T
P(5)=5 > 10 is F .

4. NOTE:
The statements “x = y + 5” and “x + y = z” will be denoted by P(x, y)
and P(x, y, z) respectively.

5. Defn:The logic based on the analysis of predicates in any


statement is called predicate logic or predicate calculus.

Domain or Universe of discourse:


UOD or Domain of a predicate variable is the collection of all possible
values that the variable may take.

(ie):Many mathematical statements assert that a property is true for all values of a
variable in a particular domain, called the universe of discourse. Such a statement is
expressed using a universal quantification. The universal quantification
of P(x) is the statement.
QUANTIFIERS

1. UNIVERSAL QUANTIFIER
2. EXISTENTIAL QUANTIFIER

UNIVERSAL QUANTIFIER EXISTENTIAL QUANTIFIER


P(x) is true for all values of x in the There exists at least one x (or an x) such
universe of discourse that P(x) is true

Notation: (x)P(x) or ∀xP(x) Notation: ∃ xP(x).


Read: “ for all x, P(x)” or “ for every x, Read: “ For some x, P(x) ”
P(x)”

The symbol ∀ is called the universal The symbol ∃ is called the existential
quantifier quantifier

Eg:If P(x) = x2 <10 , where the universe Eg: When P(x) = x2 > 10 , where the
consists of the positive integers 1, universe of discourse consists of the
2, 3 and 4, then ∀ x P(x) = P(1) Ʌ P(2) Ʌ positive integers not exceeding 4, then the
P(3) Ʌ P(4) . truth value of ∃ xP(x) is T,
the truth value of ∀x P(x) = T Ʌ T Ʌ T Ʌ F since P(1) v P(2) v P(3) v P(4) is true as
= F. P(4) is true

NEGATION OF A QUANTIFIED EXPRESSION:

Let P(x) is the statement “x has studied computer programming” .

∀xP(x)= every student (in the class) has studied computer programming

The negation of this statement is “There is a student in the class who has not studied
computer programming”.
Symbolically: ∃ P(x).

Thus , ~ ∀(x)P(x) = ∃ (x)~P(x).

Similarly, ∃ xP(x) means that “there is a student in the class who has studied
computer programming . The negation of this statement is “Every student in
this class has not studied computer programming”, which is denoted by
∀ x ~P(x).

Thus, ~ ∃ (x)P(x) =∀(x)~P(x).

FREE AND BOUND VARIABLES

(1) Bound variable: When a quantifier is used on a variable x or when we have to


assign a value to this variable to get a proposition, the occurrence of the variable
is said to be bound or the variable is said to be a bound variable.
(2) An occurrence of a variable that is not bound by a quantifier or that is set equal to
a particular value is said to be free.
(3) The part of the logical expression or predicate formula to which a quantifier is
applied is called the scope of the quantifier.
Examples:

VALID FORMULAS AND EQUIVALENCES

Let A and B be any two predicate formulas defined over a common universe of
discourse E. When each of the variables appearing in A and B is replaced by
any element (object name) of the universe E, if the resulting statements have
the same truth values, then A and B are said to be equivalent to each other over
E and denoted as A ≡ B or A ↔ B over E.
INFERENCE THEORY OF PREDICATE CALCULUS

1. Three basic rules Rule P, Rule T and Rule CP of inference used in statement
calculus can also be used in predicate calculus.

2. The indirect method can also be used in predicate calculus.

3. We need some additional rules for predicate calculus such as


➢ Rule US
➢ Rule ES
(Used to eliminate quantifiers (∀ 𝑎𝑛𝑑 ∃) )
➢ Rule UG
➢ Rule EG
(Used to include quantifiers (∀ 𝑎𝑛𝑑 ∃) )

Note:
• US stands for Universal Specification
• UG stands for Universal Generalization
• ES stands for Existential Specification
• EG stands for Existential Generalization
Problem 1:
Let us consider the following argument.

All humans are Mortal


Socrates is a human
Therefore Socrates is a mortal.
Let us use the notations,
H(x) : x is a human
M(x): x is a mortal
s: Socrates
\
Problem 3:

Show, by indirect method of proof, that

Exercise:
Show that the conclusion

follows from the premises

Common questions

Powered by AI

The indirect method of proof involves assuming the negation of the conclusion and deriving a contradiction. For instance, proving 'All humans are mortal, Socrates is human, therefore Socrates is mortal,' indirectly assumes Socrates is not mortal, and considering all humans are mortal, creates a contradiction. This contradiction validates the original conclusion under the assumption of valid premises .

Two predicate formulas are considered equivalent over a universe of discourse if, when each variable in both formulas is replaced by any element of the universe, the resultant statements have identical truth values. This implies that both formulas express the same logical content under every interpretation allowed by the domain .

The negation of a universally quantified expression ∀P(x) results in an existential quantification of the negation, expressed as ∃~P(x). Conversely, the negation of an existentially quantified expression ∃P(x) leads to a universal quantification of the negation, noted as ∀~P(x).

The scope of a quantifier in a logical expression refers to the part of the formula where the quantifier applies. It determines how the variables within that scope behave and are interpreted. Misidentifying the scope can change the meaning and truth value of the logical expression, making it crucial for the correct interpretation of predicates .

In predicate logic, a bound variable is one that has a quantifier applied to it, or it has been assigned a value to become a part of a proposition. In contrast, a free variable is one that is not enclosed by a quantifier or has been set to a specific value .

The domain of discourse determines the set of all possible values for the variable in a quantified statement, influencing the truth value. For example, if P(x) is true for all x within the domain, the universal quantification ∀xP(x) is true only if every individual truth evaluation within the domain is true. Conversely, an existential quantification ∃xP(x) is true if at least one individual truth evaluation is true within the domain .

A predicate function encapsulates a property that applies to a variable, such as 'x is greater than 10'. Here, P(x) denotes the predicate function where 'is greater than 10' is the predicate, and 'x' is the subject. When a specific value is applied to 'x', P(x) becomes a proposition with a definite truth value .

Universal quantification (∀xP(x)) asserts that a property P holds for every element within a domain, which is inherently stronger because it implies an absolute truth across all instances. Conversely, existential quantification (∃xP(x)) requires the property to hold for only one instance, making it less restrictive and more flexible in its truth conditions .

The notation for a universal quantifier, expressed as ∀xP(x), is read as "for all x, P(x)" or "for every x, P(x)". It indicates that the predicate P applies universally across the domain. The existential quantifier, denoted as ∃xP(x), is read as "there exists an x such that P(x)". It signals that there is at least one instance within the domain where the predicate P holds true .

Predicate calculus extends the rules of inference from statement calculus—such as Rule P, Rule T, and Rule CP—by incorporating quantifiers. Predicate calculus introduces additional rules like Universal Specification (US), Existential Specification (ES), Universal Generalization (UG), and Existential Generalization (EG). These rules handle the inclusion and elimination of universal and existential quantifiers, allowing for more comprehensive logical deductions within the richer framework of predicate logic .

You might also like