Predicate calculation

Predicate calculation . In predicate calculations, there are simpler elements to form atomic expressions, unlike a simple proposition where its value is true or false according to an interpretation.

Table of Contents

Summary

[ hide ]

1 Definition
2 The universal quantifier
3 The existential quantifier
4 Alphabet of the calculation of predicates
5 Terms and formulas for the calculation of predicates
6 Interpretation of formulas of the calculation of predicates
7 External links
8 Sources

Definition

In the calculation of predicates the truth value depends on the components that make up the predicate. For example: Pedro is the father of Idalia is an expression in the calculation of predicates, which in general could be: x is the father of y, or simply p (x, y).

In other words, we have here an open proposition that depends on two variables, and that of course the value of truth depends on the values that are given to the variables, because for example: Frank is the father of Lisbeth and can have a value of truth different from the previous one.

In general, it can be said that a predicate can have one or more variables and that the variables can take values from a specific set called DOMAIN. Thus, for example, the two expressions mentioned above are of the form p (x, y) where the predicate p represents “is the father of” and the domain is the set of people.

Predicate Calculation allows you to broaden the spectrum of PropositionalCalculus , working with formulas of various types in addition to Boolean.

While propositional logic has expressive limitations that do not allow describing the internal structure of propositions, predicate logic has a much more expressive language that makes it possible to resolve those limitations.

In propositional logic the propositional representation of the judgment “If Ana studies, approves” is made up of two atoms “Ana studies”, represented as p and “Ana approves”, represented as q, but the propositional variables p and q do not reflect the link between the propositions they represent, (both refer to Ana).

In the language of the calculation of predicates, atoms have a relational representation, being able to represent “Ana studies” as Est (ana), where Est (x) is the unitary relation (of an argument) that expresses that individual x studies, of a similarly “Ana approves” can be represented as Apr (ana), being Apr (x) the relation that expresses that the individual x approves, thus Est (ana) and Apr (ana) expressly express that both propositions refer to properties different (study and pass) of the same object (Ana).

Therefore , Predicate calculus can be defined as a formal system , structured for the study of inference in formal languages with quantifiers that only reach variables of individuals, and with predicates and functions whose arguments are constants or variables of individuals.

The construction of formulas in this calculation forces to define new expressions called predicates.

A predicate is an application of a boolean function whose arguments can be of different types, that is, a predicate can be a function of type Z → B.

Function names (equal, minor) are called predicate symbols. The notation x <y is also used to express the minor predicate (x, y). For example, the following expression x <y ∧ x = z ⇒ q (x, z + x) contains three predicates, x <y, x = z and q (x, x + z).

The arguments of the predicates are in this case, variables of type other than B or also expressions of these types.

The arguments of a predicate are called terms, for example in the formula above the terms in the predicates are x, y, z and z + x.

The universal quantifier

The conjunction ᴧ is associative, commutative and has a true neutral element. Therefore it can be considered a valid operation to define the quantized expression.

( ᴧ x: R: P)
The symbol Ɐ , which is read “for everything”, is known as the universal quantizer and the previous expression is called universal quantification and it is read “for all x that satisfies R, P is satisfied”.
The sentence “all singers make intensive use of the voice”, presents a variable, since “singers” does not refer to any particular element so it can only be represented by one variable, however it constitutes a proposition because it can be assign a truth value.

This is due to the fact that the variable is universally quantified by “all”, which means that the property “make intensive use of the voice” is fulfilled by all the elements of the universe (set of all singers).

The universal quantifier ( ∀ ) is the operation that allows the representation of this type of propositions in the calculation of predicates, leaving the previous example as follows:

∀ (x) UseIntVoz (x)

> It can be seen that x, according to what was stated in the previous section, is free in UsoIntVoz (x), but the same does not occur in ∀ (x) UsoIntVoz (x) because when quantifying a variable, it stops being free.

Some examples of the use of this quantifier are the following:

a) All dogs bark.
b) Each man must think for his own head.

It is possible to define this new operator from another already known one, the conjunction ( ᴧ ), because if a1, a2, a3 … are the elements of the universe in which the variable x takes values, then:

∀ (x) A (x) ⇔ A (a1) ᴧ A (a2) ᴧ A (a3) ᴧ …

This equivalence evidences that for a value ai of the universe, A (ai) is false so that ∀ (x) A (x) is false as well.

Finally, it remains to specify that if the universe in which the variable x takes values is empty, it is established that ∀ (x) A (x) is true.

The existential quantifier

The disjunction ⅴ is symmetric, associative, and its neutral element is false. Therefore it can be considered a valid operation to define the quantized expression
( ⅴ x: R: P)

This expression is usually written like this:

( ∃ x: R: P)

The symbol ∃ , which is read “exists”, is known as the existential quantifier and the previous expression is called existential quantification and it is read “there exists x in the range R that satisfies P”.

The sentence “someone has arrived” is a proposition with a variable, but this is not universally quantified. This type of propositions present existential quantification, which is expressed by: “someone”, “some”, “a”, etc.

In this case, it is stated that the property “having arrived” is fulfilled by at least one of the elements of the universe (set of all people).

The existential quantifier ( ∃ ) is the operation that allows us to represent this type of propositions in the calculation of predicates, leaving the previous example as follows:

∃ (x) Has Arrived (x)

Some examples of the use of this quantifier are the following:

c) There are men who have given their lives for freedom.
d) A student was late.

This operator, like ∀ (), can be defined from another already known, in this case the disjunction ( v ), because if a1, a2, a3 … are the elements of the universe in which the variable x takes values , then:
∃ (x) A (x) ⇔ A (a1) v A (a2) v A (a3) v …

This equivalence evidences that for a value ai of the universe, A (ai) is true for ∃ (x) A (x) to be true as well.

In case the universe in which the variable x takes values is empty, it is established that ∃ (x) A (x) is false.

Predicate Calculus Alphabet

Like propositional calculus, predicate calculus has an alphabet , some of whose symbols have already been discussed.

This alphabet has, first of all, symbols of individual constants, which will be denoted as combinations of letters and numbers, always starting with a lowercase letter. If only one letter is used, it will be one of the first in the Latin alphabet (a, b, c, d, e, …).

The symbols of individual variables that will be denoted by the last letters of the Latin alphabet (u, v, w, x, y, z) are also part of this alphabet.

Other components of the alphabet are the symbols of functions that will be lowercase letters of the Latin alphabet, or combinations of letters and numbers (with lowercase initials), preferably f, g and h will be used.

Also included in the alphabet are relationship symbols, which will be combinations of letters and numbers, always beginning with a capital letter.

The symbols of the universal quantifier ∀ () and existential ∃ () seen previously, obviously also make up this alphabet.
Finally, the symbols for propositional constants, propositional operations, and grouping, seen in the alphabet of propositional calculus, make up this alphabet as well.

Terms and formulas for the calculation of predicates

Like propositional calculus, predicate calculus defines the concept of a formula, but also establishes a fundamental expression called a term and is defined according to the following rules:

Every constant and every variable is a term.
If t1, t2, …, tn are terms and f is a symbol of n-ary function, then f (t1, t2, …, tn) is a term.
Every term is the result of applying a finite number of times of the two previous rules.

Knowing the definition of a term, it is possible to establish the concept of a formula for the calculation of predicates, which is based on that of the elementary formula or atom:

definition. If t1, t2, …, tn are terms and R is an n-ary relation symbol, then R (t1, t2, …, tn) is an elementary formula or atom.

Some examples of elemental formulas or atoms are as follows:

a) R (a, x).
b) Friend (luis, juan).
c) Brother (x, y).
d) Large (x).
e) Father (x, y).
f) Mother (x, y).
g) Parents (x, y, z).

Obviously, an atom will represent an elementary proposition, but to represent non-elementary propositions, an atomic formula is not enough, so the concept of formula is defined as follows:

Every elemental formula is a formula.
If A is a formula, then ¬A is a formula.
If A and B are formulas, then [A vB], [A ᴧB], [A ⇒ B] and [A ⇔ B] are formulas.
If A is a formula where x occurs free, then ∀(x) A and ∃(x) A are formulas.
Every formula is the result only of the application of a finite number of times of rules 1, 2, 3 and 4.

Some examples of formulas are as follows:

a) Parents (x, y, z).
e) Parents (x, y, z) ⇔ Father (x, z) ᴧMother (y, z).
b) Parents (Luis, Ana, Jose).
f) Father (luis, jose) ᴧMother (ana, jose).
g) ∀(x) ∀(y) ∀ (z) [Parents (x, y, z) ⇔ Father (x, z) ᴧ Mother (y, z)].

Interpreting formulas from the calculation of predicates

In propositional calculus, one interpretation of a formula is an assignment of values to the variables involved, determining all the interpretations of a formula is not difficult since each variable only takes values at {0, 1}.

In the calculation of predicates this becomes much more complex, since the variables take values in various universes and the quantifiers appear that make it necessary to analyze the interpretation of formulas from another perspective, being necessary to establish:

A set U, which will be the domain of values of each free variable and to which all the constants will belong.
A function with domain in Un and codomain in Ufor each symbol of function n-aria.
A relation defined in Un for each n-ary relation symbol.

Thus, it is determined that a formula A has an interpretation in U if all the symbols of constants, n-ary functions and n-ary relations that occur in A are interpreted, respectively, in elements, n-ary functions and n- relations. arias in U .

Having established the above, to determine the truth value of a formula, given an interpretation, the procedure is as follows:

If A is an atomic formula of the form R (a1, …, an), then A is true in Uif and only if <a1, …, an> belongs to R
If A is the formula ¬B, then A is true in Uif and only if B is false in U .
If A is the formula B vC, then A true in Uiff at least one of the formulas B or C is true in U .
If A is the formula B ᴧC, then A is true in Uiff the formulas B and C are true in U .
If A is the formula B ⇒C, then A is true in Uif and only if B is false less in U or C is true in U .
If A is the formula B ⇔C, then A is true in Uiff both formulas B ⇒ C and C ⇒ B are true in U .
If A is the formula ∀(x) B (x), then A is true in Uif and only if B (x) is true in U for any value of x does U belong .
If A is the formula ∃(x) B (x), then A is true in Uiff B (x) is true in U for at least one value of the x belongs to U .

The following example illustrates the interpretation of formulas in the calculation of predicates.
Let interpretation I be defined by:

U = {1, 2, 3, 4},
R = {<1,1>, <1,2>, <1,3>, <1,4>, <2,3>},

f = {<1,2>, <2,3>, <3,4>, <4,1>}

a = 1, b = 2

Let be the formulas for the calculation of predicates:

a) ∀(x) R (x, f (x))
b) ∃(x) R (x, f (x))
c) ∀(x) R (a, x)
d) ∃(x) R (b, x)
e) ∀(x) [ ∃ (y) R (x, y) ⇒ R (x, 3)]

Determine the value of the formulas above:

a) ∀(x) R (x, f (x)).

In this case the formula is false for I, since R (3, f (3)), is R (3, 4) and <3,4> does not belong to R.

b) ∃(x) R (x, f (x)). This formula is true for I, since it suffices that a value of x makes R (x, f (x)) true and this occurs with x = 1.
c) ∀(x) R (a, x). Since a = 1, the veracity of this formula depends on R (1, x) being true for all values of x, which in effect occurs, then being true.
d) ∃(x) R (b, x). Since b = 2 and for x = 3 we have R (2, 3), which is true, so the formula is also true.
e) ∀∃ (y) R (x, y) ⇒ R (x, 3)]. This formula is true because they are:

∃ (y) R (1, y) ⇒ R (1, 3)
∃ (y) R (2, y) ⇒ R (2, 3)

∃ (y) R (3, y) ⇒ R (3, 3)

∃ (y) R (4, y) ⇒ R (4, 3)

The first is, because the right part of the implication is. The same goes for the second one. The third and fourth are true because their implicants are false (no pair of R has 3 or 4 as the first element).