Predicate logic

The predicate logics (also Quantorenlogiken ) constitute a family of logical systems that allow it to formalize a wide and important in the practice of many sciences and their applications range from arguments and to check their validity. Due to this property, the predicate logic plays an important role in logic and in mathematics, computer science, linguistics, and philosophy.

Gottlob Frege and Charles Sanders Peirce developed independently predicate logic. Frege developed and formalized its system in 1879 published Begriffsschrift. Mature logical systems, such as the traditional term logic, are proper subsets of predicate logic in terms of their expressiveness. They can be completely translated into that.

• 7.1 Types and Extensions
• 7.2 calculi for predicate logic systems

• 9.1 launches
• 9.2 The History

Key terms

Predicate logic is an extension of propositional logic. In SL, composite statements are examined to determine from which simple statements they are composed. For example, the statement " It is raining or the earth is flat " from the two statements " It is raining " and these two statements are not in turn broken down into further sub- statements " The earth is flat. " - Therefore they are atomic or elementary mentioned. In predicate logic, atomic propositions are examined in terms of their internal structure.

A central concept of predicate logic is the predicate. A predicate is a string of words with spaces, which is a true or false statement if in each space with a proper name is used. For example, the phrase " ... is a man" is a predicate, because by inserting a proper name - such as " Socrates " - a declarative sentence, for example, " Socrates is a man," is created. The statement " The earth is flat " can be predicate logic in the proper name "the earth " and the predicate " ... is a disc " disassemble. Based on the definition and the examples it is clear that the term " predicate " in logic, especially in predicate logic is not the same meaning as in traditional grammar, even if both philosophically and historically related. Instead of a proper name, a variable can be used in the predicate are used, whereby the predicate to a set function is: φ (x ) = " x is a man" is a function, which are in the classical predicate logic for the proper names of those individuals, people, the truth value true, and outputs the truth value false for all others.

The second characteristic concept of predicate logic is the quantifier. Quantifiers specify how many individuals of the universe of discourse a set function is carried out. A quantifier binds the variable a set function, so that again results in a sentence. The universal quantifier indicates that a predicate should apply to all individuals. The existential states that a predicate applies to at least one individual. The quantifiers allow statements such as " All men are mortal " or " There are at least a pink elephant ."

Occasionally, additional numerical quantifiers are used, with whom it can be said that a predicate to a certain number of individuals is true. However, these are not absolutely necessary, because they can be on the universal and the existential as well as the identity predicate returns lead.

Predicates

The above definition of a predicate as a sequence of words with clearly defined spaces, which becomes a statement when in each space with a proper name is used, is a purely formal, content- free definition. As regards content predicates can express quite different circumstances, for example terms (eg "_ is a man" ), properties (eg " _ is pink " ) or relations, ie relations between individuals (eg B. "_1 _2 is greater than " or " _1 _2 and _3 is between "). Since the exact nature and the ontological status of concepts, properties and relations are controversial or be viewed from various philosophical trends different, and since the precise definition of concepts, properties and relations is seen different from each other, this formal definition is the application practically advantageous, because it allows to use predicate logic without having to accept certain ontological or metaphysical presuppositions.

The number of different spaces of a predicate is called its arity. Thus a predicate with a space is single-digit, one with two double-digit vacancies etc. Occasionally statements are considered as zero -place predicates, ie as predicates with no spaces. When counting the blank spaces only different vacancies are taken into account.

In formal predicate logic predicates are expressed by predicate letters, usually capital letters from the beginning of the Latin alphabet, for example F_1_2 for a two -place predicate, G_1 for a predicate or H_1_2_3 for a three -place predicate. Often the arguments of a predicate be enclosed in parentheses and separated by commas, so that the examples given as F ( _1, _2 ) or G ( _1 ) and H ( _1, _2, _3 ) would be written.

Proper names and individual constants

In the philosophy of language and linguistics, the topic of proper names is a quite complex. For the treatment under an introductory presentation of predicate logic, it is sufficient to refer to such language expressions as proper names that accurately describe an individual; the word "individual" is understood here in a very general sense and refers to any "thing" ( physical object, number, person, ... ), which can be distinguished in any conceivable manner of other things. Proper names in the sense mentioned actual proper names are generally (eg, " the current Chancellor of Austria " ) (eg, " Gottlob Frege " ) or markings.

The counterpart to the proper names of the natural language are the individual constants of predicate logic; usually selects one lowercase letters from the beginning of the Latin alphabet, eg a, b, c. Unlike natural language proper names each individual constant actually called exactly one individual. This means no implicit metaphysical assumptions, but merely states that only natural-language proper names are expressed by individual constants that actually accurately identify an individual.

Using the vocabulary of predicate letters and individual constants can be evaluated logically atomic sentences like " Socrates is a man " or " Gottlob Frege is the author of, Begriffsschrift ' " already in their inner structure analysis: Translating the proper name " Socrates " with the individual constant a, the proper names " Gottlob Frege " with the individual constant b, the proper name or book title " Begriffsschrift " with the individual constant c and the predicates "_ is a man" and "_1 is the author of _2 " with the predicate letters F_ or G_1_2, then leaves to " Socrates is a man " as Fa and " Gottlob Frege is the author of, Begriffsschrift ' " Gbc express.

Quantifiers

With quantifiers statements can be made about whether a set function on none, some, or all individuals is true of the universe of discourse. In the simplest case, the set function is a predicate. If, in the predicate an individual variable and represents the existential quantifier and the same variable before, it is claimed so that there is at least one individual, the true predicate. So there must be at least one set of the form that the predicate in an individual constant is used, which is true in the relevant universe of discourse. The universal quantifier indicates that a predicate applies to all individuals in the universe of discourse. In classical predicate logic, therefore, all atomic, allquantifizierten statements are true, if the universe of discourse is empty.

The existential quantifier is in a semi- formal language as " there is at least one thing, so ... " or "There's at least one (variable name), is valid for the ... " expressed. In formal language, the characters, or used. The universal quantifier is " For all (variable name ): ... " as in semi- formal language, expressed in a formal language by one of the characters or.

Immediately apparent is the use of quantifiers in predicates, such as " _ is a human being. " The existentially quantified statement would read "There is at least one thing is true for that: it is a man, " in a formal language. Here M_ is the translation of the digit predicate "_ is a man" and is the existential quantifier. The letter x is not an individual constant, but performs the same function in the semi- formal formulation of the word " it " is satisfied: Both mark the blank space referred to by the quantifier. In the example chosen, which appears to be redundant because it contains only one quantifier and only a space and therefore no ambiguity is possible. In the general case, in which a predicate over a space and a set can contain more than one quantifier and more than one predicate, no unambiguous reading would be determined without the use of appropriate " cross reference mark ".

To establish the relationship between a quantifier and the vacancy to which he refers, lowercase letters are usually used by the end of the Latin alphabet, for example, the letters x, y and z; they are known as individual variables. The blank space referred to by a quantifier, or the variable that is used to make this connection is referred to as bound by the quantifier.

It binds in a multi- place predicate a space by a quantifier, the result is a predicate of arity lower by one. The binary predicate L_1_2, "_1 loves _2 ", which expresses the relation of loving, is to be loved by binding of the first blank space with the universal quantifier to single-digit mark, so to speak, to the property of each ( the universal quantifier refers to the first blank space, in which the individual is, of the love runs out ). Is by binding the second space from it, however, the place predicate, so to speak, the ability to love everyone and everything ( the universal quantifier binds the second blank space, ie those in which the individual stands, holding the role of the lover, or ).

Interest are sets of predicates, in which more than one space is bound by a quantifier. The possibility of treating such sentences makes up the vast power of predicate logic, but is also the point at which the system for newcomers is somewhat complicated and intensive discussion and exercise needs. As a small insight into the possibilities of predicate logic are for the simple binary predicate L_1_2, which can be read as above as "_1 _2 loves " all options are enumerated to bind the vacancies by quantifiers:

The matrices illustrate the formulas for the case that five individuals come as lovers and lovers in question. Apart from the sets 6 and 9/10 are examples. The matrix of Theorem 5 is, for example, for " b loves himself "; the " loves c b. " to set 7 /8 for

Important and instructive to, distinguish between sets 1 and 3 is: In both cases, each is loved; In the first case, however, everyone is loved by someone, in the second case, each is loved by one and the same individual.

Consist inferential relationships between some of these sentences - it follows as Theorem 1 of Theorem 3, but not vice versa. (See Hasse diagram )

With three -place predicates formulas can be made as. With the predicate "x wants yz loves. " Means this formula " Somebody wants to love someone all. " Here is a list of all formulas with three -place predicates.

In natural language quantifiers occur on very different formulations. Often, words such as " all, " " none, " "some" or " some " is used, sometimes the quantification is only recognizable from the context - for example, thinks the phrase " men are mortal " is usually the universal statement that all people are mortal.

Some predicate logic equivalences

This chapter provides examples of some frequently used predicate logic equivalences, indicated by the double arrow, dar.

Types of predicate logic

If - as outlined so far - quantifiers bind the vacancies of predicates, then one speaks of first-order logic or order, English: first order logic, abbreviated FOL; it is so to speak the standard system of predicate logic.

An obvious variation of predicate logic is not only to bind the vacancies of predicates, ie, to quantify not only individuals, but also to make existence and universal propositions about predicates. In this way, statements like "There is a predicate that applies: it meets Socrates " and " For every predicate: it applies to Socrates, or it is not true to Socrates to" formalize. In addition to the individual spaces of first-order predicates could have been introduced in this way predicate voids that lead to second-level predicates, for example, just to " _ meets Socrates ". From here it is only a small step to predicates third stage during which vacancies predicates second stage can be used, and in general to a higher level predicates. One speaks in this case, therefore, a higher level of predicate logic, english higher order logic, HOL abbreviated.

The formally simplest extension of first-order predicate logic, however, is the addition of agents for the treatment of identity. The resulting system is called predicate logic of first stage with identity. Whilst it is identity in the predicate logic to define a higher level, that is, without language extension handle, but the aim is to work as long and as much as possible on the first step, because there is for this simple and above all complete calculi, d h calculi in which all valid in this system formulas and arguments can be derived. That is no longer true for the predicate logic of a higher level, ie it is not possible for the higher level to derive a single calculus all valid arguments.

Conversely, one can restrict predicate logic of first stage, by limiting, for example, on predicates. The resultant from this restriction logical system, the monadic predicate logic, has the advantage to be decidable; This means that there are mechanical methods ( algorithms ), which may determine, for each formula and for each argument of the monadic predicate logic in finite time if it, or whether it is valid or not. For some applications, monadic predicate logic is sufficient; Moreover, the entire traditional term logic, namely syllogistic, expressed in monadic predicate logic.

Parallel to the already themed distinction predicate logic systems according to their level or order there is classical and non classical forms. From classical predicate logic or generally of classical logic is called if and only if the following two conditions are met:

• The system treated is bivalent, that is, every statement takes exactly one of exactly two truth values, mostly true and false at (principle of bivalence ); and
• The truth value of statements, which are composed by propositional connectives, is by the truth values ​​of compound statements uniquely determined ( extensionality ).

If he deviates from at least one of these principles, the result is not classical predicate logic. Of course, it is also within the non-classical predicate logic possible to limit themselves to one-place predicates ( non-classical monadic predicate logic) to quantify over individuals ( non-classical predicate logic of first stage ), the system to expand identity ( non-classical predicate logic of first stage with identity) or the quantification of predicates extending ( non-classical predicate logic higher level ). A commonly used non- classical predicate logic system is the modal predicate logic (see modal logic ).

Semantics of Predicate Logic

For each predicate logic system a formal semantics can be placed. For this purpose, an interpretation function to define a function in the mathematical sense, the circumference and the atomic sentences assigns the predicates of formal predicate logic language a truth value. First, a universe of discourse is defined, which is the set of distinct objects ( "individuals" ), on which the interpretable predicate logic statements are to refer. Then the individual language elements are interpreted as follows for the classical predicate logic:

• B () = true ( here is a predicate logic statement ) when B () = false; otherwise, B () is = false. In other words, the negation of a false statement is true, the negation of a true statement is false.
• B () = true ( are here in predicate logic statements ) when B () = B () = true; otherwise, B () is = false. In other words, a conjunction is only true if both conjuncts are true; otherwise it is false.
• Analogous definitions are set up for all the other connectives.
• B (), where a single digit predicate letter and an individual constant is, returns the truth value " true" if the interpretation of an element of interpretation is, in other words, when the fall of named individuals under the predicate. Otherwise, B () returns the truth value "false".
• B (), where a digit predicate letter and to individual constants, returns the truth value " true" if the tuple is an element of interpretation of the predicate letters. Otherwise, B () returns the truth value "false".
• B (), where an individual variable, and a predicate in whose (single or multiple-occurring ) space is entered, returns the truth value " true" if B () the truth value " true " returns - regardless of which individual stands. It is an individual constant that does not occur in and is the expression that arises in every occurrence of the individual variable when replaced by the individual constant. otherwise, B () is = false. In other words, B () is exactly true when actually applies to all the individuals of the universe of discourse.
• B (), where an individual variable, and a predicate in whose (single or multiple-occurring ) space is entered, returns the truth value " true" if, when applies to at least one individual from the universe of discourse, that is if it is possible is a not occurring in individual constant an individual from the universe of discourse assign such that B () the truth value " true " returns.

Alternatives

Before the flowering of propositional logic and predicate logic, the term logic dominated in the form developed by Aristotle syllogistic and building upon it relatively moderate extensions. Two developed in the 1960s in the tradition of the term logic systems are referred to by their representatives as the predicate logic equally powerful ( Freytag ) or even superior ( summer ), but have in the professional world with little response found ( see Article term logic).

The laws of predicate logic are valid only if the range of the investigated individuals is not empty, that is, if there is any at least one individual ( of whatever kind ). A modification of predicate logic, which is not subject to this existence condition is the free logic ( engl. free logic).

Application

Predicate logics are of central importance for various foundations of mathematics.

There are also some concrete applications in computer science: It plays a role in the design and programming of expert systems and artificial intelligence. Logic programming languages ​​based on to share - often limited - forms of predicate logic. A form of knowledge representation can be done with a collection of expressions in predicate logic.

The relational calculus, one of the theoretical foundations of database query languages ​​such as SQL, also uses the predicate logic as a means of expression.

In linguistics, specifically the formal semantics of the predicate logic for the representation of meaning are applied.