Consider a few sentences with a variable:
-
« 
- simple 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.
read: for anyone 
, for each 
, 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, got a single 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 of quantifying is irrelevant. 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 quantifier of generality, this quantifier of generality is replaced by the quantifier of existence, and the predicate is replaced by its 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 similarly constructed: 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.
The specific nature of predicates allows one to introduce operations on them that have no analogues among operations on statements. This refers to two quantifier operations on predicates.
Community quantifier
To turn a one-place predicate into a statement, you need to substitute some specific subject from the domain of the predicate instead of its variable. There is one more way for such a transformation - it is applying to the predicate the bind operations with the generality quantifier or the existential quantifier. Each of these operations associates with a unary predicate some statement, true or false, depending on the original predicate.
Definition. is the 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 generality quantifier " is: "for anyone", "for everyone", "for everyone", etc.
In the expression variable x already ceases to be a variable in the usual sense of the word, that is, it is impossible to substitute any concrete values for it. They say that the variable x bound .
If a single predicate P (x) set on 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 be x defined on a lot of people M, but P (x)- predicate "X is mortal"... Give a verbal formulation of the predicate formula .
Decision.
Expression means "all people are mortal." It does not depend on the variable x, but characterizes all people in general, that is, expresses a judgment regarding all x multitudes M.
Definition. The generality quantifier binding operation n-bed ( n, a new ( 
, true if and only if the unary predicate defined on the set М 1 is identically true, and false otherwise, that is:
Existence quantifier
Definition. is called 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", "there is", etc.
Like an expression , in expression variable x also ceases to be a variable in the usual sense of the word: it is - bound variable .
If a single 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 be P (x)- predicate "X is an even number" defined on the set N... Give verbal wording to the statement , determine its truth.
Decision.
Original predicate P (x): "x is an even number" is a variable statement: when substituting a specific number instead of a variable x it turns into a simple statement that is true or false, for example,
when substituting the number 5 - false, when substituting the number 10 - true.
Utterance means “in the set of natural numbers N there is an even number. " Since the set N contains even numbers, then the statement true.
Definition. The bind operation with the existential quantifier variable x 1 is called a rule according to which eachn-bed (n 2) predicate P (x 1, x 2, ..., xn) defined on the sets М 1, М 2, ..., Мn, a new (n-1) -local predicate, denoted 
which is for any items 
, turns into a statement 
, false if and only if the unary predicate defined on the set М 1 is identically false, and true otherwise, that is:
It has already been said above that the variable on which the quantifier is hung is called bound, the variable unbound by the quantifier is called free ... The expression on which the quantifier is hung is called the scope of the quantifier and all occurrences of the quantified variable in this expression are bound. On multiplace predicates, you can hang different quantifiers on different variables, you cannot hang two quantifiers on the same variable at once.
Example 61.
Let the predicate P (x, y) describes the relationship "x loves y" on a set of people. Consider all options for quantifying both variables. Give a verbal interpretation of the received statements.
Decision.
We denote the predicate "X loves y" through LOVES (x, y)... The sentences corresponding to the various quantifier hanging options are illustrated in Fig. 2.3-2.8, where x and at are shown on different sets, which is a convention and was undertaken only to explain the meaning of sentences (real sets of variables x and at obviously should match):
- “for any person x there is a man at whom he loves "or" every person loves someone "(Fig. 2.3).
Fig. 2.3. Illustration for the saying “for any person x there is a man 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 the totality (set) of such objects.
In logic, two basic K are used: K of community, "V", and K of existence, "E". In natural language, the remote semantic analogs of the community are the words "all", "any", "everyone"; semantic analogs of K. existence - the words "some", "exists." With the help of K.'s data, any attributive statement of the form P (x) that the object x is inherent in P can be transformed into the corresponding quantifier statement of the form VxP (x) and the form ZxP (x). Informally, the quantifier formula "VxP (x)" itself reads as "for all x has P (x)", and the formula "EhP (x)" - as "for some x has P (x)". A statement of the form VxP (x) is true if any x possesses the property P; and false if at least one x does not have property P. Similarly, a statement of the form 3xP (x) is true if at least one x has property P; and false if none of x has property P.
On the basis of the elementary quantifier formulas "VxP (x)", "EhR (x)", other, more complex quantifier formulas can be constructed. Logical relationships between such formulas are studied in predicate logic. In particular, the formula "ЗхР (х)" is logically equivalent to the formula ") VxQUANTOR | P (x) ", and the formula" VхР (х) "is equivalent to the formula") Eh) P (x) ", where") "is negation.
In an implicit form, K. were already used by Aristotle, but in a strict content 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), operator of predicate logic, application of which to formulas containing only one free variable gives (utterance)... Distinguish K. community, denoted by the symbol (from English all - all), 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) takes place”. If a (universe) is finite, then xP (x) is equivalent to the conjunction of all formulas P (but), where a is an element of the subject area. Similarly, xP (x) is equivalent to a disjunction of all formulas of the form? (but)... 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) determines the undecidability of the predicate calculus. Various relationships between the theory of generality and existence and the logical connectives of propositional logic are formalized in the predicate calculus.
Philosophical encyclopedic Dictionary... - M .: Soviet encyclopedia. Ch. edition: L. F. Ilyichev, P. N. Fedoseev, S. M. Kovalev, V. G. Panov. 1983 .
(from Latin quantum - how much) - logical. operator applied to boolean. expressions and giving quantities. the characteristic of the area of objects (and sometimes the area of predicates), to which the result obtained as a result of the application of K. belongs. How logical. the means of the logic of statements are not enough to express the forms of general, particular and individual judgments, in the logic of predicates obtained by expanding the logic of statements due to the introduction of K., such judgments are expressible. So, for example, four mains. forms of judgments tradition. the logics "All A are B", "None A is B", "Some A are B" and "Some A are not B" can be written (if we abstract from the requirement of the non-emptiness of A in general judgments) using the symbols 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 in a formalized logical. language of expression of natures. language containing the number. characteristics K.-L. subject or predicate areas. In natures. languages, carriers of such characteristics are the so-called. quantifier words, which include, in particular, quantities. numerals, pronouns "all", "every", "some", the verb "exists", adjectives "any", "every", "unique", adverbs "infinitely many", etc. It turns out that for the expression of all the mentioned quantifier words in the formalism. languages and logical. two calculations are enough to use the most. К .: To. Community (or in general), usually denoted by the symbol ∀ (inverted letter A is the initial letter of the English word "all", German "alle", etc.), and K. is the essence, usually denoted by the symbol ∃ (inverted letter E - the initial letter of the English word "exist", German "existieren", etc.); the signs ∀ and ∃ in the designation of K. are followed by a letter of a certain alphabet, called a quantifier variable, which is usually considered as part of the designation of K.: ∀х, ∀у, ∀F, ∃х, ∃α, etc. For K. the community also use the designations:
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 K. of generality reads as "For all x it is true that A (x)", or "For each x, A (x) is true"; the expression ∃x (A (x)) containing K. of existence reads as "There is x such that A (x)", or "For some x, A (x) is true". In both 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 can denote a certain statement; in this case, it does not change the meaning of this statement ). However, DOS. the purpose of K. is statements from an expression that depends on a quantifier variable, or at least a decrease 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 meanings. The expression ∃ z (y> 0 & z> 0 & x = y-z) already 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, thus, a certain property (single). Finally, the formula ∃х∃у∃z (y> 0 & z> 0 & x = y – z) expresses quite definite. utterance.
Dr. examples of formulas containing K .: 1) ∀x (x> 0); 2) ∃x (x> 0); 3) ∀x (2 + 2 = 5); 4) ∃x (2 + 2 = 4); 5) ∀x (x = x) & (x + 2 = y); 6) ∀х∃у (∀z (x = z⊃x ≠ 0) & (x is the action of a K.-L. K., called the area of action of this K. Thus, in formula 6) the domains of action of K. ∀x and ∃y are the parts of the formula standing to the right of them, and the area of action of K. ∀z is the formula (x = z≠x хождение 0). Occurrence of a c.-l. variable in the sign of K. or in the scope of K. containing this variable , is called a connected entry of a variable into a formula.In other cases, an entry of a variable is called a separate entry. This is, for example, formula 5): the first three (counting from the left) occurrences of the variable x in it are bound, the last one is free. It is sometimes said that a variable is bound in a given formula if all its occurrences in that formula are bound. In mathematics and logic, any expression containing a free variable can be considered (with an informal approach) as it in the usual sense of the word, that it (expression) depends on different values of this variable; by assigning different values to this variable (i.e., replacing all its free occurrences with the name of an object belonging to the range of values of this variable), we obtain different (generally speaking) values of this expression, depending on the value of the variable, i.e. ... from the constant substituted for it. As for bound variables, their enclosing expressions are not really dependent on them. For example, the expression ∃x (x = 2y), depending on y (included in it freely), is equivalent to the expressions ∃z (z = 2y), ∃u (u = 2y), etc. This is logical. expressions from the associated variables included in them finds in the so-called. the rule for renaming related variables, postulated or displayed in decomp. logical. calculi (see Variable, Predicate calculus).
The above interpretation of the meaning of K. was related to the content of logic. theories. As for the calculus in own. sense (the so-called formal systems), then in them it does not make sense at all to talk about the "meaning" of this or that K., which is here just a certain symbol of calculus. The question of the meaning (sense) of calculus belongs entirely to the field of calculus interpretation. As applied to K., one can speak of 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 the classical and in the intuitionistic (constructive) predicate calculus, the methods of inference in cases where the initial or provable formulas contain K. are described by the same so-called. postulates of quantification, for example. Bernays' postulates.
K. commonality and existence are not exhausted by the types of K. that are used in logic. bounded quantifiers of the form ∀xP (x) A (x) or ∃xQ (x) A (x), in which the range of variation of the quantifier variable x is "bounded" by a certain special. predicate P (x) (or Q (x)). Restricted K. are reduced to K. community and existence with the help of a trace. equivalences: ∀xP (x) A (x) QUANTOR x (P (x) ⊃A (x)) and ∃xQ (x) A (x) QUANTOR ∃x (Q (x) & A (x)). The frequently 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) QUANTOR ∃xA (x) & ∀y∀z (A (y) & A (z) ⊃y = z).
Other types of K., which are not covered by the concept of bounded K., are also useful. Such are the "numerical" K. of the form ∃хnА (x) ("there are exactly n different x such that A (x)"), used in the intuitionistic logic of K. "quasi-existence" ∃ xA (x), or ("it is not true that there is no such x that A (x)"); with t. sp. classic logic K. "quasi-existence" does not differ in any way from K. existence, in intuitionistic logic the sentence ∃xA (x), which does not say anything about the existence of an algorithm for finding such x such that A (x), really only asserts a "quasi" such x and K. infinity ∃x∞A (x) ("there are infinitely many such x such that A (x)"). Expressions containing K. of infinity and numerical K. can also be written using K. generality and existence. In the extended predicate calculus, C. 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; A. Tarsky, Introduction to the logic and methodology of deductive sciences, trans. from English, M., 1948, about. 36-42,100-102,120-23; Klini S.K., Introduction to metamathematics, trans. from English, M., 1957, p. 72-80, 130-38; Church Α., Introduction to Mathematical Logic, trans. from English, v. 1, p. 42-48; Kuznetsov A.V., Logical contours of an algorithm, translation from standardized Russian into information-logical, in collection: Abstracts of reports at a conference on information processing, machine translation and automatic reading of text, Moscow, 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 "QUANTOR" is in other dictionaries:
Noun., Number of synonyms: 1 operator (24) ASIS synonym dictionary. V.N. Trishin. 2013 ... Synonym dictionary
quantifier- - Telecommunication topics, basic concepts EN quantifier ... Technical translator's guide
Quantor is a common name for logical operations that limit the range of truth of any predicate and create a statement. Most often mentioned: Quantifier of universality (designation:, reads: "for all ...", "for everyone ..." or "everyone ..." ... Wikipedia
The general name for logical operations, which, according to the predicate P (x), construct a statement characterizing the region of truth of the predicate P (x). In mathematical. the quantifier of universality and the quantifier of existence are most commonly used in logic. Statement means, ... Encyclopedia of Mathematics
Quantor- (from Latin quantum how much) a symbol used to denote some operations of mathematical logic, at the same time a logical operation that gives a quantitative characteristic of the area of objects to which the expression obtained in ... The beginnings of modern natural science
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 will exist, 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) - 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 out 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) takes place. ($ 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 there is not a single element a in M 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. By the remainder division theorem, any natural number 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 assume 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 be considered not (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) Ú (-> -);
Issues addressed1. Quantifiers.
2. The quantifier of universality.
3. The quantifier of existence.
4. The concept of a predicate logic formula. Formula value
logic of predicates.
5. Equivalent formulas of predicate logic.
Quantifier concept
Quantor - (from Latin quantum - how much), logicalquantifying operation
the area of objects to which the expression belongs,
obtained as a result of its application.
In ordinary language, carriers of such characteristics
are words like "all", "each", "some",
"exists",
"available",
"any",
"any",
"single", "several", "infinitely many",
"finite number", as well as all quantitative
numerals.
Operations for a predicate
For predicates, two new definitions are introduced.compared with the statement logic of the operation:
generality quantifier
existential quantifier
Community quantifier
Let P (x) be a unary predicate defined onsubject set M.
A universal statement corresponding to
predicate P (x), is called the statement:
“Each element of the set M satisfies
predicate P (x) "
or
"For every x the predicate is satisfied"
This statement is denoted - (x) P (x)
The statement (x) P (x) is considered true if
the predicate P (x) is identically true, and false -
otherwise.
Community quantifier
The symbol x is called a quantifiervariable x, it is read like this:
"For all x"
"For each x"
"For any x"
community of
Expression (x) P (x) reads: "for all x, P (x)", or
"For each x, P (x)".
For example, x (x = x) is a true universal
statement, and x (x> 2) is a false universal
utterance.
finite set (a1, a2, ... am), then:
P (x) P (a1) P (a2) ... P (am)
Community quantifier
Thus, the generality quantifiercan be understood as operator
conjunction by quantifiable
variable.
Existence quantifier
Existentialutterance,
appropriate
predicate
P (x),
called
the statement “there is an element of the set M,
satisfying
predicate
Р (x) ",
which
denoted by x P (x) and is considered true if
the predicate P (x) is satisfiable, but false otherwise
case.
The symbol x is called an existential quantifier, and
expression x in which this quantifier precedes
variable x, read like this:
"There is an x such that ..."
"For some x, ..."
Existence quantifier
EGx (x> 2) is a true existential statement
x (x = x + 1) is a false existential statement.
If P (x) is a unary predicate defined on
finite set (a1, a2, ... am), then
P (x) P (a1) P (a2) ... P (am)
Existence quantifier
Thus, the quantifierexistence can be understood as
disjunction operator
quantifiable variable.
10. Examples
Examples of formula entries and their verbal expressions:x (x 2 1 (x 1) (x 1)) For all x, the predicate ...
x (x 0)
inequality...
x (x 0)
For all x, it is true ... ..
y (5 y 5)
There is a y such that 5 + y = 5
y (y 2 y 1 0)
For all y, the predicate
y (y 2 y 1 0)
There is y that….
x (x x)
For some x, it is true
3
2
11. Formulas of predicate logic
The following symbology is available in predicate logic:The symbols p, q, r, ... are utterance variables that take
two values: 1 - true, 0 - false.
Subject variables - x, y, z, ..., which run through
values from some set M;
x0, y0, z0 are subject constants, i.e., the values of subject
variables.
P (·), Q (·), F (·),… - unary predicate variables;
Q (·, ·,…, ·), R (·, ·,…, ·) are n-ary predicate variables.
P0 (·), Q0 (·, ·,…, ·) are symbols of constant predicates.
Logical operation symbols:,.
Symbols for quantifier operations: x, x.
Additional symbols: brackets, commas.
12. Formulas of predicate logic
A subject variable is called free if itdoes not immediately follow the quantifier and is not included in
the scope of the quantifier on that variable, all others
variables,
incoming
in
formula,
are called
related.
y z (P (x, y) P (y, z))
The formula for predicate logic is:
Each predicate letter and predicate letter with
subject variables following it in parentheses.
Expressions of the form F G, F G, G, F G, F G, (y) F,
(y) G, where F and G are predicate logic formulas, the variable
M.
13. Formulas of predicate logic
Each utterance is as variable asconstant, is a formula (elementary).
and
If F (·, ·, ..., ·) is an n-place predicate variable
or a constant predicate, and x1, x2, ..., xn are subject
variables or subject constants (not
are necessarily all distinct), then F (x1, x2, ..., xn) is
formula. Such a formula is called elementary, in
her subject variables are free, not
bound quantifiers.
14. Formulas of predicate logic
If A and B are formulas, moreover, such that the samesubject variable is not in one of them
connected, and in the other - free, then the words A B,
A B, A B are formulas. In these formulas, those
variables that were in the original formulas
are free are free, and those that were
related, are related.
If A is a formula, then A is a formula, and the character
subject variables in the transition from formula A to
formula A does not change.
15. Formulas of predicate logic
If A (x) is a formula in which the subjectvariable x enters freely, then the words xA (x) and
xA (x) are formulas, moreover, the subject
the variable is included in them connected.
Any word other than those named
formulas in the previous paragraphs is not
formula.
16. Formulas of predicate logic
For example, if P (x) and Q (x, y) are single anddouble predicates, and q, r are variables
statements, then the formulas will be, expressions:
q, P (x), P (x) Q (x, y), xP (x) xQ (x, y), (Q (x, y) q) r
0
Not a formula, for example, the word: xQ (x, y) P (x)
Here the condition of item 3 is violated, since the formula
xQ (x, y) the variable x appears connected, and the formula
P (x) variable x enters freely.
It is clear from the definition of the predicate logic formula that
every propositional algebra formula is
formula of predicate logic.
17. Interpretation of the predicate formula
An interpretation of the predicate calculus formulais called the concretization of sets, of which
object variables take values and
concretization
relations
and
the respective
truth sets for each predicate letter.
18. Formulas of predicate calculus
identicallytrue for
any
interpretation,
those.
generally valid
identically
false
at
any
interpretation,
those.
contradictory
feasible
(formulas,
truth
which depends
from
interpretation)
19. The value of the predicate logic formula
As an example, consider the formulay z (P (x, y) P (y, z))
In the formula, the double predicate P (x, y) is defined on
set MхM, where M = (0,1,2, ..., n, ...), i.e. MхM = NхN.
The formula includes a variable predicate P (x, y), subject
variables x, y, z, two of which y and z are related by quantifiers,
and x is free.
Let's take
per
specific
value
predicate
P (x, y)
fixed predicate P0 (x, y): “x
Then, for y values less than x0 = 5, the predicate P0 (x0, y)
takes the value “false”, and the implication P (x, y) P (y, z) for
of all z M takes on the value "true", i.e. utterance
has the meaning "true".
20. Equivalent formulas of predicate logic
Definition 1.equivalent on the domain M if they take
the same logical values for all values included in
them variables assigned to the area M.
Definition 2.
The two predicate logic formulas A and B are called
equivalent if they are equivalent in any area.
21. Equivalent formulas of predicate logic
Let A (x) and B (x) be variable predicates, and C be a variablea statement (or a formula that does not contain x). Then have
place the following equivalences:
22. Equivalent formulas of predicate logic
ExampleThe predicate Mother (x, y) means that x is the mother of y.
Then y x Mother (x, y) means that each person has
mother is a true statement.
x y Mother (x, y) means that there is a mother of all people, that
is another statement, the truth of which depends on
sets of values that can take y: if it is
many brothers and sisters, then it is true, and otherwise
case it is false.
Thus, the permutation of the universal quantifiers and
existence can change the meaning and meaning of an expression.
23. Laws of logical operations (generally valid formulas of predicate logic)
24. Exercise
Find the negation of the following formulas25. Exercise
andThe exercise
Prove equivalence
x (A (x) B (x)) xA (x) xB (x)
Let the predicates A (x) and B (x) be identically false. Then there will be
false and predicate A (x) B (x)
x (A (x) B (x))
In this case, statements will be false
xA (x) xB (x)
Let at least one of the predicates (for example, A (x)) not
identically false. Then it will not be identically false and
predicate A (x) B (x)
In this case, the statements xA (x) x (A (x) B (x))
Hence, the original formulas will also be true
Therefore: x (A (x) B (x)) xA (x) xB (x)
26.
On my ownFor a more detailed study of the material
we read on our own:
TEXTBOOK: "Mathematical logic and theory
algorithms ",
author Igoshin V.I.
Pages 157-164
Pages 165-178
Pages 178-183
27.
HomeworkProve equivalence
C xA (x) x (C A (x))
Prove that the formula is valid
A V (P (x) Q (x)) xP (x) xQ (x)
Prove that the formula is inconsistent
A x ((F (x) F (x)) (F (x) F (x)))
