The specific nature of predicates allows us to introduce operations on them that have no analogues among operations on statements. This refers to two quantifier operations on predicates.

General quantifier

To transform a one-place predicate into a statement, you need to substitute some specific object from the domain of specifying the predicate instead of its variable. There is another way for such a transformation - this is the application of binding operations to the predicate by a general quantifier or an existence quantifier. Each of these operations associates a unary predicate with a certain statement, true or false depending on the original predicate.

Definition. is a rule according to which each unary predicate P(x) defined on the set M is associated with a statement, denoted by , which is true if and only if the predicate P(x) is identically true, and false otherwise, that is

A verbal analogue of the general quantifier " is: “for anyone”, “for everyone”, “for everyone”, etc.

In expression variable X ceases to be a variable in the usual sense of the word, that is, it is impossible to substitute any specific values ​​in its place. They say that the variable X related .

If a unary predicate P(x) given on a finite set M = (a 1,a 2 , …,a n), then the statement equivalent to conjunction P(a 1) P(a 2) … P(an).

Example 59 .

Let X determined on many people M, A P(x)– predicate "x is mortal". Give a verbal formulation of the predicate formula .

Solution.

Expression means "all men are mortal." It does not depend on the variable X, but characterizes all people as a whole, i.e. expresses a judgment regarding all X sets M.

Definition. By the operation of binding by a general quantifier n-ary ( n , new ( , true if and only if the unary predicate defined on the set M 1 is identically true, and false otherwise, that is:

Existence quantifier

Definition. is a rule according to which each unary predicate P(x) defined on the set M is associated with a statement, denoted by , which is false if and only if the predicate P(x) is identically false, and true otherwise, that is

A verbal analogue of the existential quantifier $ is: “exists”, “will be found”, etc.

Similar to the expression , in expression variable X also ceases to be a variable in the usual sense of the word: it is - related variable .

If a unary predicate P(x) given on a finite set M = (a 1,a 2 , …,a n), then the statement equivalent to disjunction P(a 1) P(a 2) … P(an).

Example 60.

Let P(x)– predicate "x is an even number", defined on the set N. Give a verbal formulation to the statement , determine its truth.

Solution.

Original predicate P(x): “x is an even number” is a variable statement: when substituting a specific number instead of a variable X it becomes a simple statement that is true or false, e.g.

when substituting the number 5 - false, when substituting the number 10 - true.

Statement means "in the set of natural numbers N there is an even number." Since many N contains even numbers, then the statement true.

Definition. By the operation of binding with an existence quantifier by variable x 1 is the rule according to which eachn-ary (n 2) predicate P(x 1, x 2, ..., xn), defined on the sets M 1, M 2, ..., Mn , new (n-1)-ary predicate, denoted by , which is for any items , turns into a statement , false if and only if the unary predicate defined on the set M 1 is identically false, and true otherwise, that is:

It was already said above that a variable on which a quantifier is attached is called bound, a variable not bound by a quantifier is called free . An expression on which a quantifier is attached is called scope of the quantifier and all occurrences of a variable with a quantifier in this expression are bound. For multiplace predicates, you can attach different quantifiers to different variables; you cannot attach two quantifiers to the same variable at once.

Example 61.

Let the predicate P(x, y) describes the "x likes y" attitude on a variety of people. Consider all options for attaching quantifiers to both variables. Give a verbal interpretation of the received statements.

Solution.

Let us denote the predicate "x loves y" through LOVES(x, y). Sentences corresponding to various options for attaching quantifiers are illustrated in Fig. 2.3-2.8, where X And at shown on different sets, which is a convention and undertaken only to explain the meaning of sentences (real sets of variables X And at, obviously must match):

- “for any person X there is a person at whom he loves” or “every person loves someone” (Fig. 2.3).

Rice. 2.3. Illustration for the saying “for any person” X there is a person at whom he loves" or "every person loves someone"

The operator with the help of which about k.-l. a separate object is transformed into a statement about a collection (set) of such objects.
In logic, two basic codes are used: the code of generality, “V,” and the code of existence, “E.” In natural language, distant semantic analogues of the community concept are the words “all,” “any,” “everyone”; semantic analogues of K. existence are the words “some”, “exists”. With the help of K data, any attributive statement of the type P(x) that an object x is inherent in P can be transformed into a corresponding quantifier statement of the type VxP(x) and the type ZxP(x). In content, the quantifier formula “VxP(x)” itself reads as “for all x there is P(x)”, and the formula “ExP(x)” - as “for some x there is P(x)”. A statement of the form VxP(x) is true if any x has property P; and is false if at least one x does not have the property P. Similarly, a statement of the form ZxP(x) is true if at least one x has the property P; and false if no x has property P.
Based on the elementary quantifier formulas “VxP(x)”, “ExP(x)” other, more complex quantifier formulas can be constructed. The logical relationships between such formulas are studied in predicate logic. In particular, the formula “ZxP(x)” is logically equivalent to the formula “) VxQUANTITOR| P(x)”, and the formula “VxP(x)” is equivalent to the formula “) Eх) P(x)”, where “)” are negations.
In an implicit form, logics were already used by Aristotle, but in a strict substantive and formal sense they were first introduced into the logic of G. Frege.

Philosophy: Encyclopedic Dictionary. - M.: Gardariki. Edited by A.A. Ivina. 2004 .

(from lat. quantum - how much), a predicate logic operator, applied to formulas containing only one free variable gives (statement). There are K. communities, denoted by the symbol (from English all - everything), and K. existence (from exist - to exist): xP(x) is interpreted (cm. Interpretation) as “for all x the property P holds”, and xP(x) - as “there is an x ​​such that the property?(x)” holds. If (universe) is finite, then xP(x) is equivalent to the conjunction of all formulas P (A), where a is an element of the subject area. Similarly, xP(x) is equivalent to the disjunction of all formulas of the form? (A). If the subject area is infinite, then xP (x) and xP(x) can be interpreted as infinite and disjunction respectively. Introduction to K. in the logic of multiplace predicates (i.e. non-single) causes the undecidability of predicate calculus. Various relationships between the principles of generality and existence and the logical connectives of propositional logic are formalized in predicate calculus.

Philosophical encyclopedic dictionary. - M.: Soviet Encyclopedia. Ch. editor: L. F. Ilyichev, P. N. Fedoseev, S. M. Kovalev, V. G. Panov. 1983 .

(from Lat. quantum - how much) - logical. operator applied to logical. expressions and giving quantities. a characteristic of the domain of objects (and sometimes the domain of predicates), which includes what is obtained as a result of the application of K. How logical The means of propositional logic are not enough to express the forms of general, particular, and individual judgments; in predicate logic, obtained by expanding propositional logic by introducing principles, such judgments are expressible. So, for example, four basic. forms of judgments of traditions. logics “All A are B”, “No A is B”, “Some A are B” and “Some A are not B” can be written down (if we ignore the presupposed requirement of Aristotelian logic for the non-emptiness of A in general judgments) using the symbolism explained below as follows: ∀(x) (A (x) ⊃ B (x)), ∀(x) (A (x) ⊃ B(x)), ∃(x) (A (x ) & B (x)) and ∃ (x) (A (x) & B (x)). Introduction K. allows you to write it down in a formalized logical way. language of expression of nature. languages ​​containing quantities. characteristics of k.-l. subject or predicate areas. In natural In languages, the carriers of such characteristics are the so-called. quantifier words, which include, in particular, quantities. numerals, pronouns “all”, “each”, “some”, verb “exists”, adjectives “any”, “every”, “single”, adverbs “infinitely many”, etc. It turns out that to express all the mentioned quantifier words in a formalism. languages ​​and logic In calculus, the two most commonly used are sufficient. K.: K. generality (or in generality), usually denoted by the symbol ∀ (inverted letter A - the initial letter of the English word “all”, German “alle”, etc.), and K. existence, usually denoted by the symbol ∃ (the inverted letter E is the initial letter of the English word “exist”, German “existieren”, etc.); the signs ∀ and ∃ in the notation of a quan- tity are followed by a letter of a certain alphabet, called a quantifier variable, which is usually considered as part of the notation of a quan- tifier: ∀x, ∀y, ∀F, ∃x, ∃α, etc. For K. generalities the following notations are also used:

for K. existence:

The sign K. is placed before the expression to which K. is applied (the operation of applying K. is often called quantification); this expression is enclosed in parentheses (which are often omitted if this does not lead to ambiguity). The expression ∀x (A (x)) containing the general principle reads as “For all x it is true that A (x)”, or “For every x it is true that A (x)”; The expression ∃x (A(x)) containing the K. of existence is read as “There is x such that A (x)”, or “For some x, A(x) is true.” In both of these cases it is not assumed, generally speaking, that the expression A(x) actually depends on the variable x (it may not contain any variables at all, i.e. it may denote a certain statement; in this case it does not change the meaning of this statement ). However, the main the purpose of K. is statements from an expression that depends on a quantifier variable, or at least a reduction in the number of variables on which this expression, being an open (open) formula (see Closed formula), depends. For example, the expression (y>0&z>0&x=y-z) contains three variables (x, y and z) and becomes a statement (true or false) when k.-l. def. replacing these variables with the names of certain objects from the range of their values. The expression ∃ z(y>0&z>0&x = y-z) depends on only two variables (x and y), and ∃y∃z (y>0&z>0& &x = y –z) - on one x. The last formula expresses, therefore, a certain property (one-place). Finally, the formula ∃х∃у∃z (y>0&z>0&x=y–z) expresses a completely defined statement.

Dr. examples of formulas containing K.: 1) ∀x(x>0); 2) ∃x(x>0); 3) ∀х (2+2=5); 4) ∃x (2+2=4); 5) ∀x (x = x)& (x+2=y); 6) x ∃y are the parts of the formula to the right of them, and the domain of action of a formula (x = z⊃x ≠ 0). The occurrence of a certain variable in the sign of a formula or in the domain of action of a formula containing this variable , is called a bound occurrence of a variable in a formula. In other cases, the occurrence of a variable is called a free one. The same one can appear in a certain formula in one place in a bound form, and in another. place - in a free place. This is, for example, formula 5): the first three (counting from the left) occurrences of the variable x in it are connected, the last one is free. Sometimes they say that a variable is connected in a given formula if all its occurrences in this formula are connected. In mathematics and logic, any expression containing a free variable can be considered (in an informal approach) as it in the usual sense of the word that it (the expression) depends on various values ​​of this variable; by giving this variable different meanings (i.e., replacing all its free occurrences with the name of a certain object belonging to the range of values ​​of this variable), we obtain different (generally speaking) meanings of this expression, depending on the value of the variable, i.e. . from the constant substituted instead. As for bound variables, the expressions that enclose them do not really depend on them. For example, the expression ∃x(x = 2y), depending on y (which is freely included in it), is equivalent to the expressions ∃z(z = 2y), ∃u(u = 2y), etc. This logical expressions from the associated variables included in them are found in the so-called. the rule for renaming related variables, postulated or deduced in dep. logical calculus (see Variable, Predicate calculus).

The above interpretation of the meaning of K. related to the content of logical. theories. As for the calculations in proper. sense (so-called formal systems), then in them it makes no sense at all to talk about the “meaning” of this or that calculus, which here is simply a certain symbol of calculus. The question of the meaning (meaning) of calculus relates entirely to the area of ​​interpretation of calculus. In application to K. we can talk about at least three interpretations: classical, intuitionistic and constructive, corresponding to various concepts of existence and universality in logic and mathematics (see Intuitionism, Constructive logic). Both in classical and intuitionistic (constructive) predicate calculus, methods of inference in cases where the original or formulas to be proved contain a formula are described by the same so-called predicate calculus. quantification postulates, e.g. Bernays' postulates.

The principles of generality and existence do not exhaust the types of principles used in logic. Extensive principles are the so-called. limited quantum equations of the form ∀xP(x)A(x) or ∃xQ(x)A(x), in which the range of change of the quantifier variable x is “limited” by some special predicate P(x) (or Q(x)). Limited K. are reduced to K. of generality and existence with the help of traces. equivalences: ∀xP(x)A(x) QUANTITOR ∀x(P(x) ⊃A(x)) and ∃xQ(x)A(x) QUANTITOR ∃x(Q(x)&A(x)). The often used K. of uniqueness ∃!xA(x) (“there is a unique x such that A(x)”) is also expressed through the K. of generality and existence, for example. so: xA(x) QUANTITOR ∃xA(x)& ∀y∀z(A(y)&A(z)⊃y=z).

Other types of calculations are also used, which are not covered by the concept of limited calculation. These are “numerical” calculations of the form ∃xnA(x) (“there are exactly n different x such that A(x)”), used in intuitionistic logic of calculation. “quasi-existence” ∃ xA(x), or (“it is not true that there does not exist an x ​​such that A(x)”); with t.zr. classic in the logic of the Q. of “quasi-existence” is no different from the Q. of existence, in intuitionistic logic the sentence ∃xA(x), which says nothing about the existence of an algorithm for finding such x that A(x), really asserts only the “quasi” of such x and K. infinity ∃x∞A(x) (“there are infinitely many x such that A(x)”). Expressions containing the principles of infinity and numerical terms can also be written using the terms of generality and existence. In the extended predicate calculus, coefficients are taken not only by subject variables, but also by predicate variables, i.e. formulas of the form ∃F∀xF(x), ∀Ф∃у(Ф(y)), etc. are considered.

Lit.: Gilbert D. and Ackerman V., Fundamentals of Theoretical Logic, trans. from English, M., 1947, p. 81-108; Tarski A., Introduction to logic and methodology of deductive sciences, trans. from English, M., 1948, about. 36-42, 100-102, 120-23; Kleene S.K., Introduction to Metamathematics, trans. from English, M., 1957, p. 72-80, 130-38; Church A., Introduction to Mathematical Logic, trans. from English, vol. 1, p. 42–48; Kuznetsov A.V., Logical contours of the algorithm, translation from the standardized Russian language into the information-logical language, in: Abstracts of reports at the conference on information processing, machine translation and automatic text reading, M., 1961; Mostowski A., On a generalization of quantifiers, "Fundam. math.", 1957, t. 44, No. 1, p. 12–36; Hailperin T., A theory of restricted quantification, I–II, "J. Symb. Logic", 1957, v. 22, No. 1, p. 19–35, No. 2, p. 113–29.

Yu. Gastev. Moscow.

Philosophical Encyclopedia. In 5 volumes - M.: Soviet Encyclopedia. Edited by F. V. Konstantinov. 1960-1970 .

Synonyms:

See what "QUANTITOR" is in other dictionaries:

Noun, number of synonyms: 1 operator (24) ASIS synonym dictionary. V.N. Trishin. 2013… Synonym dictionary

quantifier- - Telecommunications topics, basic concepts EN quantifier... Technical Translator's Guide

Quantifier is a general name for logical operations that limit the domain of truth of a predicate and create a statement. Most often mentioned: Quantifier of universality (designation: , reads: “for all...”, “for each...” or “every...” ... Wikipedia

A general name for logical operations that use the predicate P(x) to construct a statement that characterizes the domain of truth of the predicate P(x). In mathematics In logic, the quantifier of universality and the quantifier of existence are most commonly used. A statement means... ... Mathematical Encyclopedia

Quantifier- (from Latin quantum how much) a symbol used to denote certain operations of mathematical logic, at the same time a logical operation that gives a quantitative characteristic of the field of objects to which the expression obtained in ... ... The beginnings of modern natural science

In any national language, the connectives “and”, “or”, “if ..., then ...”, “if and only if ...”, etc. are used in ordinary speech. allow you to construct new complex statements from already given statements. The truth or falsity of the statements thus obtained depends on the truth and falsity of the original statements and the corresponding interpretation of connectives as operations on statements. A logical operation can be completely described truth table, indicating what meanings a complex statement takes for all possible meanings of simple statements.

Logical operation is a method of constructing a complex statement from elementary statements, in which the truth value of the complex statement is completely determined by the truth values ​​of the original statements (see the article “ ”).

In the algebra of logic, logical operations and the corresponding logical connectives have special names and are denoted as follows:

Conjunction is a logical operation that associates each two elementary statements with a new statement, which is true if and only if both original statements are true 7 . Logical operation conjunction

Consider two statements: p = “Tomorrow it will be frosty" And q = “It will snow tomorrow" Obviously a new saying p & q = “Tomorrow it will be frosty and tomorrow it will snow” is true only if the statements are true at the same time p And q, namely, that tomorrow there will be frost and snow. Statement p & q will be false in all other cases: it will snow, but there will be a thaw (i.e. there will be no frost); there will be frost, but there will be no snow; there will be no frost, and there will be no snow.

Disjunction- a logical operation that associates each two elementary statements with a new statement, which is false if and only if both initial statements are false, and true when at least one of the two statements forming it is true 8. Logical operation disjunction determined by the following truth table:

Consider two statements: p = “Columbus was in India" And q = “Columbus was in Egypt p q = “Columbus was in India or was in Egypt” is true both if Columbus was in India, but was not in Egypt, and if he was not in India, but was in Egypt, and also if he was in both India and Egypt . But this statement will be false if Columbus was neither in India nor in Egypt.

The conjunction “or” can be used in speech in another, “exclusive” sense. Then it corresponds to another statement - a disjunctive, or strict, disjunction.

Strict, or dividing,disjunction- a logical operation that associates two elementary statements with a new statement that is true only when only one of the statements is true. Logical operation disjunctive clause determined by the following truth table:

Consider two statements: p = “The cat is hunting for mice" And q = “Cat sleeps on the sofa" It is obvious that the new statement pq true only in two cases - when the cat is hunting for mice or when the cat is sleeping peacefully. This statement will be false if the cat does neither one nor the other, i.e. when both events do not occur. But this statement will be false even when it is assumed that both statements will occur simultaneously. Since this cannot happen, the statement is false.

In logic, the connectives “either” and “or” are given different meanings, but in Russian the connective “or” is sometimes used instead of the connective “or”. In these cases, the unambiguity of the definition of the logical operation used is associated with the analysis of the content of the statement. For example, analysis of the statement “ Petya sits on podium A or podium B" replaced by " Petya sits on podium A or B”, then the analysis of the last statement will clearly indicate a logical operation dividing disjunction, because a person cannot be in two different places at the same time.

Implication- a logical operation that associates each two elementary statements with a new statement that is false if and only if condition(premise) - true, and consequence(conclusion) is false. The overwhelming number of dependencies between events can be described using implication. For example, with the statement “ If we go to St. Petersburg during the holidays, we will visit St. Isaac’s Cathedral” We affirm that if we come to St. Petersburg during the holidays, we will definitely visit St. Isaac's Cathedral.

Logical operation implication

An implication will be false only if the premise is true and the conclusion is false, and it will certainly be true if its condition p false. Moreover, for a mathematician this is quite natural. In fact, starting from a false premise, one can obtain both a true and a false statement through correct reasoning.

Let's say 1 = 2, then 2 = 1. Adding these equalities, we get 3 = 3, i.e. from a false premise, through identical transformations, we obtained a true statement.

Implication formed from statements A And IN, can be written using the following sentences: “If A, That IN", "From A should IN”, “A entails IN", "In order to A, it is necessary that IN", "In order to IN, enough to A”.

Equivalence- a logical operation that associates two elementary statements with a new one, which is true if and only if both initial statements are simultaneously true or simultaneously false. Logical operation equivalence is given by the following truth table:

Let us consider the possible meanings of a complex statement that is an equivalence: “ The teacher will give the student a 5 in the quarter if and only if the student receives a 5 on the test.”.

1) The student received 5 in the test and 5 in the quarter, i.e. the teacher fulfilled his promise, therefore the statement is true.

2) The student did not get a 5 on the test, and the teacher did not give him a 5 in the quarter, i.e. the teacher kept his promise, the statement is true.

3) The student did not receive a 5 on the test, but the teacher gave him a 5 in the quarter, i.e. the teacher did not keep his promise, the statement is false.

4) The student received a 5 on the test, but the teacher did not give him a 5 in the quarter, i.e. the teacher did not keep his promise, the statement is false.

Note that in mathematical theorems equivalence is expressed by the connective “necessary and sufficient.”

The operations discussed above were double (binary), i.e. were performed on two operands (statements). In the algebra of logic, the one-place (unary) operation is defined and widely used negation.

Negation- a logical operation that associates each elementary statement with a new statement, the meaning of which is opposite to the original one. Logical operation negation is given by the following truth table:

In Russian, the connective “it is not true that...” is used to construct a negation. Although the connective “it is not true that …” does not connect any two statements into one, it is interpreted by logicians as a logical operation, since, when placed in front of an arbitrary statement, it forms a new one from it.

By negating the statement “I have a computer at home” there will be a statement “It’s not true that I have a computer at home” or, which is the same in Russian, “I don’t have a computer at home”. By negating the statement “I don't know Chinese” there will be a statement “It’s not true that I don’t know Chinese” or, which is the same thing in Russian, “I know Chinese”.

Quantifiers

In mathematical logic, along with logical operations, quantifiers are also used. Quantifier(from lat. quantum- how many) is a logical operation that gives a quantitative characteristic of the area of ​​objects to which the expression obtained as a result of its application relates.

In ordinary language, words like All, every, some, any, any, endlessly a lot of, exists, available, the only one, some, final number, as well as all cardinal numbers. In formalized languages, an integral part of which is the predicate calculus, two types of quantifiers are sufficient to express all such characteristics: general quantifier And existence quantifier.

Quantifiers allow from a specific expressive form (see “ Statements. Boolean values") to obtain an expressive form with a smaller number of parameters, in particular, to obtain a statement 9 from a one-place expressive form.

General quantifier allows from a given statement form with a single free variable x get a statement using the link “For everyone x…”. The result of applying the general quantifier to the propositional form A( x) denote x A( x). Statement x A( x) will be true if and only if, upon substitution into A( x) instead of a free variable x of any object from the range of possible values, a true statement is always obtained. Statement x A( x) can be read as follows: “For any x A( x)”, “A( x) for arbitrary x", "For all x true A( x)", "Every x has property A( x)" and so on.

The existential quantifier allows from a given expressive form with a single free variable x get a statement using the connective “There is such x, What …". The result of applying the general quantifier to the propositional form A( x) denote x A( x). Statement
x A( x) is true if and only if, in the range of possible values ​​of the variable x there is an object such that when substituting its name instead of the occurrence of a free variable x in A( x) turns out to be a true statement. Statement x A( x) can be read as follows: “For some x A( x)”, “For suitable x true A( x)", "Exists x, for which A( x)”, “At least for one x true A( x)" and so on.

Quantifiers play for formalized languages ​​of mathematical logic the same role that so-called “quantitative” (“quantifier”) words play for natural language - they determine the scope of applicability of a given statement (or expressive form).

When constructing a negation to a statement containing a quantifier, the following rule applies: the particle “not” is added to the predicate, the general quantifier is replaced by a uniqueness quantifier, and vice versa. Let's look at an example. The negation of the statement “All 11th grade boys are excellent students” is the statement “It is not true that all 11th grade boys are excellent students” or “Some 11th grade boys are not excellent students.”

In computer science, quantifiers are used in logical programming languages ​​(see “ Programming languages”) and database query languages.

The ability to construct complex statements is required when working with databases, when constructing an Internet search query, when constructing algorithms and writing programs in any algorithmic language. Moreover, this skill can be classified as a general school skill, because it is associated with the construction of complex inferences (reasoning, drawing conclusions). This skill is based on knowledge of basic logical operations and the ability to determine the truth of complex statements.

Schoolchildren are introduced to the logical operations disjunction, conjunction and negation in basic school. The concept of a truth table is also introduced there. Most likely, familiarity with these concepts arises in programming languages, but they can also be used in spreadsheets - there logical operations are implemented through the corresponding functions OR, AND, NOT.

More complex logical operations can be covered in high school. Problems using implication are found in each of the published versions of the Unified State Exam in computer science. For example: for what number X true statement (( X > 3) (X < 3)) –> (X < 1)? (Demo version of the Unified State Exam, 2007)

When studying the operation of implication, students should pay attention to the fact that most mathematical theorems are implications. However, those implications in which premises (conditions) and conclusions (consequences) are sentences without mutual (essentially) connection cannot play a more or less important role in science. They are completely fruitless proposals, because... do not lead to deeper conclusions. Indeed, in mathematics, not a single theorem is an implication in which the condition and conclusion are not related in content. In addition to the connective “if,... then...”, in mathematical theorems the implications are formulations of only necessary or only sufficient conditions.

The tasks of creating sufficient and necessary conditions for schoolchildren turn out to be difficult. When developing this skill, three points should be especially noted:

a) the form “necessary and sufficient” used in mathematical statements corresponds to the connective “if and only then” (equivalence);

b) the connective “in order to…( A), it is necessary that...( B)” is realized by direct implication A B. (In order for a quadratic equation to have a solution, the discriminant must be non-negative);

c) a sufficient condition is realized by the inverse implication B ® A and can be expressed in Russian, for example, like this: “in order for... (A), it is enough that... (B).”

In high school (grades 10–11), it is useful for students to develop the ability to construct a negation of a statement in Russian. This skill is necessary, for example, to prove theorems using the “by contradiction” method. Constructing a negation even for simple statements is not always easy. For example, to the statement There are red ones in the parking lot“Zhiguli” the following sentences will not be negative:

1) Those in the parking lot are not red “Zhiguli”;

2) There's a white one in the parking lot “Mercedes”;

3) Reds“Zhiguli” are not parked.

The negation of this statement would be “There are no red Zhigulis in the parking lot.” This can be explained to schoolchildren this way: the negation of a sentence must completely exclude the truth of the original statement. If there is a white Mercedes in the parking lot, then nothing prevents the red Zhiguli from parking too.

You can read about the algorithm for constructing a negation of a complex statement in the book “Mathematical Foundations of Computer Science” by E. Andreeva, L. Bosova, I. Falina.

Until now, the study of quantifiers has not been traditional for school computer science courses. However, now they are included in the standard of the specialized school. The easiest way is to demonstrate the role of quantifiers in constructing the same negations of statements in Russian, both mathematical and arbitrary. The rule for replacing a general quantifier with an existential quantifier and vice versa can be easily justified using De Morgan’s laws (see. “Boolean expressions”).

6 From Latin words idem- the same and potens- strong; literally equivalent.

7 This definition easily extends to the case n statements ( n > 2, n- natural number).

8 This definition, like the previous one, applies to the case n statements ( n > 2, n- natural number).

9 Uspensky V.A., Vereshchagin N.K., Plisko V.E. Introductory course of mathematical logic. M.: Fizmatlit, 2002.

Logic and argumentation: Textbook. manual for universities. Ruzavin Georgy Ivanovich

4.2. Quantifiers

4.2. Quantifiers

A significant difference between predicate logic and propositional logic is also that the former introduces a quantitative characteristic of statements or, as they say in logic, quantifies them. Already in traditional logic, judgments were classified not only by quality, but also by quantity, i.e. general judgments differed from particular and individual ones. But there was no theory about the connection between them. Modern logic considers the quantitative characteristics of statements in a special theory of quantification, which is an integral part of predicate calculus.

For the quantification (quantitative characteristics) of statements, this theory introduces two main quantifiers: the general quantifier, which we will denote by the symbol (x), and the existential quantifier, denoted by the symbol (Ex). They are placed immediately before the statements or formulas to which they refer. In the case where quantifiers have a wider scope, parentheses are placed before the corresponding formula.

The general quantifier shows that the predicate denoted by a certain symbol belongs to all objects of a given class or universe of reasoning.

Thus, the proposition: “All material bodies have mass” can be translated into symbolic language as follows:

where x - denotes the material body:

M - mass;

(x) is a general quantifier.

Similarly, a statement about the existence of extrasensory phenomena can be expressed through an existence quantifier:

where x denotes phenomena:

E - the property of extrasensory perception inherent in such phenomena;

(Ex) is an existential quantifier.

Using the generality quantifier, you can express empirical and theoretical laws, generalizations about the connection between phenomena, universal hypotheses and other general statements. For example, the law of thermal expansion of bodies can be symbolically represented as a formula:

(x) (T(x) ? P(x)),

where (x) is the general quantifier;

T(x) - body temperature;

P(x) is its extension;

Sign of implication.

The existential quantifier refers only to a certain part of objects from a given universe of reasoning. Therefore, for example, it is used to symbolically write statistical laws that state that a property or relation applies only to characterize a certain part of the objects being studied.

The introduction of quantifiers makes it possible, first of all, to transform predicates into definite statements. Predicates themselves are neither true nor false. They become such if concrete statements are either substituted for variables, or, if they are connected by quantifiers, they are quantified. On this basis, a division of variables into bound and free is introduced.

Variables that fall under the influence of the signs of quantifiers of generality or existence are called bound. For example, the formulas (x) A (x) and (x) (P (x) ? Q (x)) contain the variable x. In the first formula, the general quantifier stands immediately before the predicate A(x), in the second, the quantifier extends its action to the variables included in the previous and subsequent terms of the implication. Similarly, the existential quantifier can refer to both a separate predicate and their combination, formed using the logical operations of negation, conjunction, disjunction, etc.

A free variable is not subject to quantifier signs, so it characterizes a predicate or propositional function, not a statement.

Using a combination of quantifiers, one can express quite complex natural language sentences in the symbolic language of logic. In this case, statements where we are talking about the existence of objects that satisfy a certain condition are introduced using the existence quantifier. For example, a statement about the existence of radioactive elements is written using the formula:

where R denotes the property of radioactivity.

The statement that there is a danger for a smoker to get cancer can be expressed as follows: (Ex) (K(x) ? P(x)), where K denotes the property of “being a smoker”, and P - “getting cancer”. With certain reservations, the same thing could be expressed” by means of a general quantifier: (x) (K(x) ? P(x)). But the statement that anyone who smokes can get cancer would be incorrect, and so it is best written using an existence quantifier rather than a generality quantifier.

The general quantifier is used for statements that state that a certain predicate A is satisfied by any object in its range of values. In science, as already mentioned, the general quantifier is used to express statements of a universal nature, which are verbally represented using phrases such as “for everyone,” “each,” “any,” “any,” etc. By negating the quantifier of generality, one can express generally negative statements, which in natural language are introduced by the words “none”, “not one”, “nobody”, etc.

Of course, when translating natural language statements into symbolic language, certain difficulties are encountered, but the necessary accuracy and unambiguous expression of thought is achieved. However, one cannot think that formal language is richer than natural language, in which not just the meaning is expressed, but also its different shades. Therefore, we can only talk about a more accurate representation of natural language expressions as a universal means of expressing thoughts and exchanging them in the process of communication.

Most often, generality and existence quantifiers appear together. For example, to express symbolically the statement: “For every real number x, there is a number y such that x will be less than y,” we denote the predicate “to be less” by the symbol<, известным из математики, и тогда утверждение можно представить формулой: (х) (Еу) < (х, у). Или в более привычной форме: (х) (Еу) (х < у). Это утверждение является истинным высказыванием, поскольку для любого действительного числа х всегда существует другое действительное число, которое будет больше него. Но если мы переставим в нем кванторы, т.е. запишем его в форме: (Еу) (х) (х < у), тогда высказывание станет ложным, ибо в переводе на обычный язык оно означает, что существует число у, которое будет больше любого действительного числа, т.е. существует наибольшее действительное число.

From the very definition of the quantifiers of generality and existence it immediately follows that there is a certain connection between them, which is usually expressed using the following laws.

1. Laws of permutation of quantifiers:

(x) (y) A ~ (y) (x) A;

(Ex) (Ey) A ~ (Ey) (Ex) A;

(Ex) (y) A ~ (y) (Ex) A;

2. Laws of negation of quantifiers:

¬ (x) A ~ (Ex) ¬ A;

¬ (Ex) A ~ (x) ¬ A;

3. Laws of mutual expressibility of quantifiers:

(x) A ~ ¬ (Ex) ¬ A;

(Ex) A ~ ¬ (x) ¬ A.

Here, A denotes any formula of an object (subject) language. The meaning of the negation of quantifiers is obvious: if it is not true that for any x A holds, then there are x for which A does not hold. It also follows that if any x has A, then there is no x that has not-A, which is symbolically represented in the first law of interexpressibility.

Let's look at a few sentences with a variable:

- « - a simple natural number"; the range of permissible values ​​of this predicate is the set of natural numbers;

- « - even integer”; the range of permissible values ​​of this predicate is the set of integers;

- «
- equilateral";

- «
»

- "student received an assessment »

- « is divisible by 3"

Definition. If a sentence with variables, with any replacement of variables with admissible values, turns into a statement, then such a sentence is called a predicate.

,
,
,
- predicates from one variable (single-place predicates). Predicates from two variables:
,
- two-place predicates. Propositions are null-place predicates.

General quantifier.

Definition. Symbol is called a general quantifier.

read: for anyone , for each , for all .

Let
- unary predicate.

read: for anyone
- true.

Example.

- “All natural numbers are prime” - False statement.

- “All integers are even” - False statement.

- “All students received an assessment " is a one-place predicate. We put a quantifier on a two-place predicate and got a one-place predicate. Likewise
-n-ary predicate, then

- (n-1)-local predicate.

- (n-2)-place predicate.

In Russian, the general quantifier is omitted.

Existence quantifier.

Definition. Symbol called an existence quantifier.

read: exists , There is , there will be .

Expression
, Where
- one-place predicate, read: exists , for which
true.

Example.

- “there are prime natural numbers.” (And)

- “there are even integers.” (And).

- “there is a student who received a grade " is a one-place predicate.

If we add 1 quantifier to an n-ary predicate, we get an (n-1)-ary predicate; if we add n quantifiers, we get a zero-place predicate, i.e. statement.

If we assign quantifiers of the same type, then the order in which the quantifiers are assigned does not matter. And if different quantifiers are assigned to a predicate, then the order in which the quantifiers are assigned cannot be changed.

Construction of the negation of statements containing quantifiers. De Morgan's laws.

De Morgan's Law.

When constructing the negation of a statement containing a general quantifier, this general quantifier is replaced by an existence quantifier, and the predicate is replaced by its negation.

De Morgan's Law.

When constructing the negation of statements containing an existential quantifier, it is necessary to replace the existential quantifier with a general quantifier, and the predicate
- his denial. The negation of statements containing several quantifiers is constructed in a similar way: the general quantifier is replaced by an existence quantifier, the existence quantifier is replaced by a general quantifier, the predicate is replaced by its negation.

P.2. Elements of set theories (intuitive set theory). Numerical sets. The set of real numbers.

Description of the set: The word set refers to a collection of objects that is considered as one whole. Instead of the word “set” they sometimes say “collection”, “class”.

Definition. An object included in a set is called its element.

Record
means that is an element of the set . Record
means that is not an element of the set . You can say about any object whether it is an element of a set or not. Let's write this statement using logical symbols:

There is no object that simultaneously belongs to a set and does not belong, that is,

A set cannot contain identical elements, i.e. if from a set containing an element , remove element , then we get a set that does not contain the element .

Definition. Two sets And are said to be equal if they contain the same elements.