Predicate Logic
Predicate Logic
A predicate is a statement that contains variables (predicate variables) and that may be true or false depending on the values of these predicate variables. Predicates are the propositions containing variables and represent properties or relations among objects. A predicate is an expression of one or more than one variable defined in some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable of the predicate. Predicate logic dealt quite satisfactorily with modifiers like there exists …, all …, among . . . and only. It is also known as the First-order logic.
Consider the declarative sentence:
“Every student is younger than some instructor”
We could identify this assertion with a propositional atom p, in propositional logic. However, it does not reflect the finer logical structure of this sentence. This statement is about being a student, being an instructor and being younger than somebody else. We would like to have a mechanism for expressing all these properties together with their logical relationships and dependencies. For that purpose, we use predicates. For example, we could write S(andy) to say that Andy is a student and I(Paul) to denote that Paul is an instructor. Likewise, Y (andy, paul) could mean that Andy is younger than Paul. This S, I and Y symbols are called predicates.
There is a concept of variables e.g. x, y, z. We employ it in the sense that variables can be thought of like place holders for concrete values (like a student). We can now specify the meanings of S, I and Y more formally, using variables.
S(x) denotes “x is a student.”
I(x) denote “x is an instructor.”
Y (x, y) denote “x is younger than y.”
The names of the variables are not important, we use them consistently. We can state the intended meaning of S by writing
S(y): y is a student.
or, equivalently, by writing
S(z) : z is a student.
The availability of variables is still not sufficient, we need to convey the meaning of ‘Every’ and ‘Some’ in the sentence, ‘Every student x is younger than some instructor y’. Here we need to introduce quantifiers ∀ (read as: ‘for all’) called Universal Quantifier and ∃ (read as: ‘there exists’ or ‘for some’) called Existential Quantifier, which always come with a variable, as ∀x (‘for all x’) or ∃z (‘there exists z’, or ‘there is some z’).
Universal quantifier
A universal quantifier states that the statements within its scope are true for every value of the specific variable written with it. ∀xP(x) is read as, for every value of x, P(x) is true.
Example − “Man is mortal” can be transformed into the predicate logic as ∀xM(x) where M(x) is the predicate which denotes x is mortal and the universe of discourse is all men.
Existential quantifier
Existential quantifier states that the statements within its scope are true for some values of the specific variable written with it. ∃xP(x) is read as for some values of x, P(x) is true.
Example − “Some people are dishonest” can be transformed into the predicate logic as ∃xD(x) where D(x) is the predicate which denotes x is dishonest and the universe of discourse is some people.
The variables of predicates are quantified by quantifiers. These quantifiers may be nested If we use a quantifier that appears within the scope of another quantifier.
Example − “All rabbits are faster than all tortoises.”
R={rabbits}, T={tortoises}
C(x, y): Rabbit x is faster than tortoise y
∀x R (∀y T, C(x, y)).
Now we can write the sentence “Every student x is younger than some instructor y.” in an entirely symbolic way as:
∀x (S(x) → (∃y (I(y) ∧ Y (x, y))))
Its re-translation results in “For every x, if x is a student, then there is some y which is an instructor such that x is younger than y.” which shows that this encoding is rather a paraphrase of the original sentence.
Different predicates may have a different number of arguments. The predicates that have just one argument are called unary predicates. The predicates that have two arguments are called binary predicates. Predicates with any finite number of arguments are also possible in predicate logic.
Example − “Not all birds can fly.”
We choose the unary predicates B and F
B(x) : x is a bird
F(x) : x can fly.
Now the sentence ‘Not all birds can fly’ can be coded as:
¬(∀x (B(x) → F(x)))
Saying as: ‘It is not the case that all things which are birds can fly.’ we could code this alternatively as:
∃x (B(x) ∧ ¬F(x))
Saying as: ‘There is some x which is a bird and cannot fly.’
To get a feel for what kind of reasoning must predicate logic be able to support, let us consider the following argument:
“No books are gaseous. Dictionaries are books. Therefore, no dictionary is gaseous.”
We choose predicates B, G, and D.
B(x) : x is a book.
G(x) : x is gaseous.
D(x) : x is a dictionary.
It’s encoding in predicate logic is as:
¬∃x (B(x) ∧ G(x)), ∀x (D(x) → B(x)) ⊢ ¬∃x (D(x) ∧ G(x))
Predicate logic extends propositional logic not only with quantifiers but also with one more concept, that of function symbols. Consider a declarative sentence:
“Every child is younger than its mother.”
We could express this sentence using predicates as:
∀x ∀y (C(x) ∧ M(y, x) → Y (x, y))
Where,
C(x): that x is a child.
M(x, y): x is y’s mother.
Y (x, y): x is younger than y.
The function symbols of predicate logic give us a way of avoiding this ugly encoding, for they allow us to represent y’s mother more directly. We simply write m(y) to mean y’s mother, Instead of writing M(x, y) to mean that x is y’s mother. Here the symbol m is a function symbol: it takes one argument (returns the mother of that argument). Using m, the above sentence has simpler encodings than it had using M:
∀x (C(x) → Y (x, m(x)))
One can always do by using a predicate symbol (without function symbols). However, it is usually neater and more compact encodings to use function symbols whenever possible. Function symbols can be used only in the situations in which we want to denote a single object. The different function symbols may take different numbers of arguments. Functions that take zero arguments are called constants: ‘a’ and ‘p’ are constants for Andy and Paul, respectively.
