In the study of propositional forms (predicates), one of the ways of obtaining propositions was indicated: substitution of some value of a variable in P (x) from some set A. For example,

P (x): "x is a prime number". Substituting x = 7, we get the statement

“7 is a prime number”. We will get acquainted with two more logical operations: the hanging of the generality quantifier and the existential quantifier, which allow us to obtain statements from the expression forms.

Let us substitute the word “any” before the expression form P (x): “any x is a prime number”. Received a false statement. Substitute before P (x) the word "some": "some of the numbers x are prime." Got a true saying.

In mathematics, the words “any”, “some” and their synonyms are called quantifiers, which are respectively called the generality quantifier (") and the existence quantifier ($). The generality quantifier is replaced in verbal formulations by the words: any, everything, everyone, everyone, etc. The quantifier of existence in the verbal formulation is replaced by the words: there is at least one, some exists, etc.

Let P (x) be an expression form in M. Notation

("xÎM) P (x)

means: for any element x (from the set M) P (x) holds, which is already a statement. To prove that the statement ("x) P (x) is true, it is necessary to iterate over all the elements a, b, c, etc. from M and make sure that P (a), P (b), P (c) , ... are true, and if it is impossible to iterate over the elements of M, they must prove by reasoning that for any a from M. P (a) is true. To make sure that (x) P (x) is false, it is enough to find only one element aÎM for which P (a) is false.

EXAMPLE... An expression form is given

B (x): "- prime number".

In (1): 2 2 + 1 = 5 - prime number;

In (2): = 17 is a prime number;

In (3): = 257 is a prime number;

In (4): = 65537 is a prime number.

Can we say that ("x) B (x)? This must be proved. Leonard Euler proved that B (5) is false, that is, + 1 = 2 32 + 1 is divisible by 641 and, therefore, (" x) B (x) is false.

EXAMPLE... Consider the statement ("x) C (x), where on N given C (x): "x 3 + 5x divisible by 6".

Obviously, C (1), C (2), C (3), C (4) are true. But if we check even a million values ​​of x, there is always a danger that for the first million of x the statement C (x) will turn out to be false.

You can prove, for example, like this:

x 3 + 5x = x 3 - x + 6x = x (x 2 - 1) + 6x = (x - 1) x (x + 1) + 6x

The expression (x - 1) x (x + 1) is divisible by 3, since at least one of three consecutive natural numbers is divisible by 3; this expression is divisible by 2, since one or two numbers of three consecutive numbers are even. The second term 6x is divisible by 6, therefore the entire sum is divisible by 6, i.e. ("x) C (x) is true."

Let C (x) be some form of expression. Recording

means: there is an element x from the set M for which C (x) holds. ($ x) C (x) is already a statement. If in the set M one can find an element a for which C (a) is true, then the statement ($ x) C (x) is true. If in M ​​there is not a single element a for which C (a) is true, the statement ($ x) C (x) is false.

EXAMPLE... On the set N given C (x): ””. C (1) is false, C (2) is false, C (5) is true. Therefore, ($ x) C (x) is a true statement.

EXAMPLE... On the set N given K (x): "x 2 + 2x + 3 is divided by 7". K (1) = 6, 6 is not divisible by 7; K (2) = 11, 11 is not divisible by 7, etc.

Hypothesis: ($ x) K (x) - false.

Let's prove it. Any natural number by the remainder division theorem can be represented as n = 7q + r, where r< 7.

n 2 + 2n + 3 = (7q + r) 2 + 2 (7q + r) + 3 = 7 (7q 2 + 2qr + 2q) + r 2 + 2r + 3.

So, the number n 2 + 2n + 3 is divisible by 7 if and only if r 2 + 2r + 3 is divisible by 7. The remainder is r Î (0, 1, 2, 3, 4, 5, 6). Let us make sure that r 2 + 2r + 3 is not divisible by 7. Thus, ($ x) K (x) is false.

How to construct a denial of a quantified statement?

In order to construct the negation of a statement with a quantifier, it is necessary to replace the quantifier of generality (") with the quantifier of existence ($) and, conversely, the quantifier of existence with the quantifier of generality, and the sentence after the quantifier, with its negation, i.e.

[("x) P (x) Û ($ x) P (x);

[($ x) P (x) Û ("x) P (x).

For example, let's say two statements are given:

A: “every prime number is odd”;

Q: “every prime number is even”.

Will B be the negation of A? No, since none of the statements are true. In this case

A: “not every prime number is odd, ie there is an even prime number ”is a true statement.

In the future, we consider that a negation of a sentence has been built, if its negation is not simply written down, but the resulting sentence is also transformed to a form where negation signs stand in front of simpler expressions. For example, the negation of a sentence of the form A Ù B will not be considered (A Ù B), but its equivalent: A Ú B.

Let A (x, y) be a two-variable expression form.

Then ("x) A (x, y), ($ x) A (x, y), (" x) A (x, y), ($ x) A (x, y) are also expression forms, but with one variable. In this case, the quantifier is said to bind one variable. To get a statement from the expression form A (x, y), it is necessary to link both variables. For example, ("x) ($ y) A (x, y) is a statement."

For the expression form P (x, y): “x< y”, заданной на Z, consider all cases of obtaining a statement by adding (hanging) quantifiers:

1) ("x) (" y) P (x, y) Û l - “For every x and for every y x< y”;

2) ("y) (" x) (x< y) Û л - “Для всякого у и для всякого х х < y”;

3) ($ x) ($ y) (x< y) Û и - “Существует х и существует у такие, что x < y”;

4) ($ y) ($ x) (x< y) Û и - “Существует х и существует у такие, что x < y”;

5) ("x) ($ y) (x< y) Û и - “Для всякого х существует у такое, что x < y”;

6) ($ y) ("x) (x< y) Û л - “Существует у такое, что для всякого х х < y”;

7) ("y) ($ x) (x< y) Û и - “Для всякого у существует х такое, что x < y”;

8) ($ x) ("y) (x< y) Û л - “Существует x такое, что для всякого y х < y”.

`Note the statements (1) and (2), (3) and (4). The structures of these statements differ only in the sequence of the quantifiers of the same name, but the meaning and truth values ​​of the statements do not change.

Statements (5) and (6), (7) and (8) differ in the order of sequence of opposite quantifiers, which leads to a change in the meaning and, possibly, the truth value of the statement. Statement (7) asserts the presence in Z the smallest number, which is false. (8) asserts the absence of what is true.

Theoretical questions:

1. The concept of a predicate from one, several variables.

2. Examples of one-place and two-place predicates. 3. The area of ​​truth of the predicate.

4. Quantifiers of generality and existence. Free and bound variables. Operations on predicates. What is the area of ​​truth; ; ; ? Give geometric interpretations.

5. Transformation of predicate logic formulas. Definition of identically true and identically false predicate, connection with the area of ​​truth. Basic equivalences.

Exercises

5.1. Specify multiple values ​​of the variables for which the following predicates are true, false:

1.x 2, x Î N; 9. = - x, x Î R;

2.x< 1 , x Î N ; 10. > 0 ,

3. x> 6® x ³ 3, xÎZ; 11.sin x = -, xÎ R;

4.x + 3x +6 = 0, x Î R; 12.cos x =, x ÎR;

5. = 0, xÎR; 13. x ³ y, x, y Î R;

6. | x - 5 |< 2, 14. x + y < 3, x,yÎ N;

7. | 2x + 3 | ³ 2x + 3, x Î R; 15.x (y - 1) = 0, x, yÎR;

8. = x, x Î R; 16.x + y = 4, x, y ÎR.

5.2. Find the domain of truth for the predicates of Exercise 5.1. Draw cases 13-16 on the coordinate plane.

5.3.

1. = 0; 7. | 3x - 2 | > 8;

2. =; 8. | 5x - 3 |< 7;

3. ->; 9. 2 - | x | = 1.7;

4. ; 10. | 3x - 1 | = 3x - 1;

5. < 0 ; 11. | 3x - 1 | = 1 - 3x;

6.> 0; 12. | 2x + 4 | ³ 2x + 4.

5.4. Find the domain of truth of the predicates:

1. ( < x + 1,5) Ù (2x - 8 >3 - 0.5 x);

2. ( - 4 < - 1) Ù ( x + 2 (2x- 1) < 3(x +1);

3. (- + 2x<3x-3) Ù ( - 3(1-x)+2x< );

4. (- + x< 2x - 4)Ù( + 3 (x - 1)< );

5. ((X + 3) (x - 1)< 0) Ù (x + 4x + 6 >x (x - 5);

6. ((X - 6x + 9) (2x - 10)< 0) Ù (6 + x (7 - x) < x +2x(5-x);

7. (1 + £) Ú (- 1< 5x - 5)

8. (-> 2) Ú (- 3x - 1> 2);

9. (+ 6x> + 4) Ú (-> -);

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

4.2. Quantifiers

4.2. Quantifiers

The essential difference between predicate logic and propositional logic is that the former introduces a quantitative characteristic of propositions 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 private and individual ones. But there was no theory about the connection between them. Modern logic considers the quantitative characteristics of statements in the special theory of quantification, which is an integral part of the predicate calculus.

To quantify (quantitatively characterize) statements, this theory introduces two main quantifiers: the generality quantifier, which we will denote by the symbol (x), and the existence quantifier, denoted by the symbol (Ex). They are placed immediately before the statements or formulas to which they refer. When quantifiers have a wider scope, parentheses are placed in front of the corresponding formula.

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

Thus, the judgment: "All material bodies have mass" can be translated into symbolic language as follows:

where x - denotes a material body:

M is the mass;

(x) is a generality quantifier.

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

where the phenomena are denoted through x:

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

(Ex) is an existential quantifier.

With the help of the generality quantifier, it is possible to 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 in the form of the formula:

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

where (x) is the generality quantifier;

T (x) - body temperature;

P (x) - its extension;

Implication sign.

The quantifier of existence refers only to a certain part of objects from a given universe of reasoning. Therefore, for example, it is used to symbolically record statistical laws that assert that a property or relation is relevant only to characterize a certain part of the studied objects.

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

Variables are called related if they are subject to the signs of generality or existence quantifiers. For example, formulas (x) A (x) and (x) (P (x)? Q (x)) contain the variable x. In the first formula, the quantifier of generality stands directly 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 both to an individual predicate and to their combination formed by logical operations negation, conjunction, disjunction, etc.

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

With the help of a combination of quantifiers, it is possible to express rather 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 existential 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 could be expressed "by means of a quantifier of generality: (x) (K (x)? P (x)). But the assertion that anyone who smokes can get cancer would be incorrect, and therefore it is best written in terms of the existential quantifier rather than the generality.

A quantifier of generality is used for statements in which it is asserted that any object from its range of values ​​satisfies a certain predicate A. In science, as already mentioned, the quantifier of generality is used to express statements of a universal nature, which are verbally represented using phrases such as "for everyone", "everyone", "everyone", "any", etc. By negating the quantifier of generality, one can express generally negative statements, which in natural language are introduced by the words "none", "none", "none", etc.

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

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

From the very definition of community and existence quantifiers, 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, everywhere A denotes any formula of the object (subject) language. The meaning of negating quantifiers is obvious: if it is not true that A holds for any x, then there are such x for which A does not hold. It also follows that if: any x is inherent in A, then there is no such x that would not be inherent in -A, which is symbolically represented in the first law of mutual expressibility.

The functional nature of the predicate entails the introduction of another concept - quantifier... (quantum - from Latin "how much") Quantum operations can be viewed as a generalization of conjunction and disjunction operations in the case of finite and infinite regions.

Community quantifier (all, everyone, everyone, any (all - "everyone")). The corresponding verbal expression sounds like this:

"For every x, P (x) is true." The occurrence of a variable in a formula can be concatenated if the variable is located either immediately after the quantifier sign, or in the scope of the quantifier followed by the variable. All other occurrences are free, the transition from P (x) to x (Px) or (Px) is called binding the variable x or quantifying the variable x (or the predicate P) or quantifying the variable x. The variable on which the quantifier is hung is called bound, an unbound quantization variable is called free.

For example, the variable x in the predicate P (x) is called free (x is any of M), in the statement P (x) the variable x is called a bound variable.

The equivalence is valid P (x 1) P (x 2) ... P (x n),

P (x) is a predicate defined on the set M = (x 1, x 2 ... x 4)

Existence quantifier(exist - "to exist"). The verbal expression corresponding to it sounds like this: “There is an x ​​for which P (x) is true”. The statement xР (x) is no longer dependent on x, the variable x is linked by a quantifier.

Equivalence is valid:

xP (x) = P (x 1) P (x 2) ... P (x n), where

P (x) is a predicate defined on the set М = (x 1, x 2… x n).

The quantifier of generality and the quantifier of existence are called dual, sometimes the notation of the quantifier is used! - "there is, and, moreover, only one."

It is clear that the statement xP (x) is true only in the unique case when P (x) is an identically true predicate, and the statement is false only if P (x) is an identically false predicate.

Quantifier operations apply to multiplace predicates as well. Applying a quantifier operation to the predicate P (x, y) with respect to the variable x associates the two-place predicate P (x, y) with a unary predicate xP (x, y) or xP (x, y), which depends on y and does not depend on x.

Quantifier operations on both variables can be applied to a two-place predicate. Then we get eight statements:

1. P (x, y); 2. P (x, y);

3. P (x, y); 4. P (x, y);

5. P (x, y); 6. P (x, y);

7. P (x, y); 8.P (x, y)

Example 3. Consider possible options for quantifying a predicate P (x, y) – “x divided by y”Defined on the set of natural numbers (without zero) N... Give verbal formulations of the received statements and determine their truth.

The operation of hanging quantifiers leads to the following formulas:

Statements “for any two natural numbers, one is divisible by the other” (or 1) all natural numbers are divisible by any natural number; 2) any natural number is a divisor for any natural number) false;

Statements “there are two natural numbers such that the first is divisible by the second” (1. “there is a natural number x that is divisible by some number y”; 2. “there is a natural number y that is a divisor of some natural the numbers x ") are true;

The statement “there is a natural number that is divisible by any natural number” is false;

The statement “for every natural number there is such a natural number that is divisible by the first” (or for every natural number there is a divisible one) is true;

The statement “for every natural number x there is such a natural number y by which it is divisible” (or “for every natural number there is a divisor”) is true;

The statement “there is a natural number that is a divisor of any natural number” is true (such a divisor is one).

In the general case, changing the order of quantifiers changes the meaning of the statement and its logical meaning, i.e. for example, the statements P (x, y) and P (x, y) are different.

Let the predicate P (x, y) mean that x is the mother of y, then P (x, y) means that every person has a mother - a true statement. P (x, y) means that there is a mother of all people. The truth of this statement depends on the set of values ​​that y can take: if it is a set of brothers and sisters, then it is true, otherwise it is false. Thus, the permutation of the quantifiers of universality and existence can change the very meaning and meaning of the expression.

a) replace the initial sign (or) with the opposite

b) put a sign in front of the rest of the predicate

Consider a few sentences with a variable:

- « - prime natural number "; the range of admissible values ​​of this predicate is the set of natural numbers;

- « - even integer "; the range of valid values ​​of this predicate is a set of integers;

- «
- equilateral ";

- «
»

- "student got an estimate »

- « divisible by 3 "

Definition... If a sentence with variables for any change of variables with admissible values ​​turns into a sentence, then such a sentence is called a predicate.

,
,
,
- predicates from one variable (unary predicates). Predicates from two variables:
,
- double predicates. Statements are null predicates.

Community quantifier.

Definition... Symbol is called a generality quantifier.

readable: for anyone , for everybody , for all .

Let be
is a single predicate.

read: for any
- the truth.

Example.

- "All natural numbers are prime" - False statement.

- "All integers are even" - False statement.

- “All students received a grade »Is a single predicate. We put a quantifier on a two-place predicate, and got a one-place predicate. Likewise
-n-ary predicate, then

- (n-1) -place predicate.

- (n-2) -place predicate.

In Russian, the generality quantifier is omitted.

Existence quantifier.

Definition. Symbol is called an existential quantifier.

read: exists , there is , there is .

Expression
, where
- single 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 single predicate.

If we hang 1 quantifier on an n-place predicate, then we get an (n-1) -place predicate, if we hang n quantifiers, we get a zero-place predicate, i.e. utterance.

If quantifiers of the same type are hung, then the order in which the quantifiers are hung is not important. And if different quantifiers are hung on the predicate, then the order in which the quantifiers are hung 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 generality quantifier, this generality quantifier is replaced by an existence quantifier, and the predicate is replaced by its own negation.

De Morgan's law.

When constructing the negation of statements containing an existential quantifier, the existential quantifier must be replaced by a generality quantifier, and the predicate
- its negation. The negation of statements containing several quantifiers is constructed in a similar way: the generality quantifier is replaced by the existence quantifier, the existence quantifier - by the generality quantifier, the predicate is replaced by its own negation.

A.2. Elements of set theory (intuitive set theory). Number sets. Lots of real numbers.

Description of the set: the word set is understood as a collection of objects, which is considered as one whole. Instead of the word "set", they sometimes say "aggregate", "class".

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

Recording
means that is part of the set ... Recording
means that not a member of the set ... We can say about any object whether it is an element of the set or not. Let's write this statement using boolean symbols:

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

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

Definition. Two sets and are called equal if they contain the same elements.

In the logic of predicates, two operations are considered that turn a single predicate into a statement; for this, special words are used that are placed before the predicates. In logic, they are called quantifiers.

There are two types of quantifiers:

1. Quantifier of generality;

2. The quantifier of existence.

1. Community quantifier.

Let there be a predicate P (x) defined on the set M

The symbol is called universal quantifier(community). This is the inverted first letter of the English word All-everything. They read “everyone”, “everyone”, “any”, “everyone”. Variable x in predicate P (x) is called free ( it can be assigned different meanings from M), in utterance same x is called bound the quantifier of universality.

Example # 1: P (x) - "Prime x is odd"

Let's add a quantifier of generality - "Every prime number x is odd" - a false statement.

By expression is meant a statement true when P (x) is true for each element x from the set M and false otherwise. This statement is no longer dependent on x.

2. The quantifier of existence.

Let P (x) - predicate defined on the set M. An expression is understood as utterance which is true if there is an element for which P (x) is true and false otherwise. This statement is no longer dependent on x. The corresponding verbal expression sounds like this: "There is an x ​​for which P (x) is true." The symbol is called existential quantifier. In the statement, the variable x is bound by this quantifier (the quantifier is hung on it).

(Read: "There is such x from M, for which P from x is true")

An expression is understood as a statement that is true if there is an element x ∈ M (at least one) for which P (x) is true, and false otherwise.

Example # 2: P (x) "The number x is a multiple of 5"

Any natural number is a multiple of 5 "

Each natural number is a multiple of 5 "false statements

All natural numbers are multiples of 5 "

There is a natural number divisible by 5

There is a natural number divisible by 5 true statements

At least one natural number is a multiple of 5

Quantifier operations apply to multiplace predicates as well. For example, let a double predicate P (x, y) be given on the set M. Applying a quantifier operation to the predicate P (x, y) with respect to the variable x associates the two-place predicate P (x, y) with a unary predicate (or unary predicate) that depends on the variable y and does not depend on the variable x. Quantifier operations on the variable y can be applied to them, which will already lead to statements of the following types:

To build negatives with quantifiers, you need:

1) replace the quantifier of generality with the quantifier of existence, and the quantifier of existence - with the quantifier of generality;

2) replace the predicate with a negation.

Thus, the following formulas are valid:

Write rejection of a sentence as, and rejection of a sentence as. Obviously, the sentence has the same meaning, and therefore the same truth value as the sentence, and the sentence has the same meaning as. In other words, it is equivalent; is equivalent.

PRI me R No. 3. Construct the negation of the statement "some two-digit numbers are divisible by 12".

Solution. Replace the existential quantifier (expressed by the word "some") with the general quantifier "all" and construct the negation of the sentence after the word "some" by placing the particle "not" in front of the verb. We get the statement "All two-digit numbers are not divisible by 12".

PRI me R No. 4. Formulate the denial of the statement "In every class at least one student did not cope with the test."

Solution. This statement contains a generality quantifier, expressed using the word "each", and an existential quantifier, expressed using the words "at least one". According to the rule of constructing negations of statements with quantifiers, it is necessary to replace the quantifier of generality with the quantifier of existence, and the quantifier of existence - to the quantifier of generality, and remove the particle "not" from the verb. We get: "There is a class in which all students have coped with the test."