Quantifiers of generality and existence. Boolean operations
Predicate (lat. praedicatum- stated, mentioned, said) - any mathematical statement in which there is at least one variable. The predicate is the main object of study of first-order logic.
A predicate is an expression with boolean variables that makes sense for any valid values of these variables.
Expressions: x > 5, x > y are predicates.
Predicate ( n- local, or n-ary) is a function with a set of values (0,1) (or "false" and "true"), defined on the set . Thus, each set of elements of the set M characterized as either "true" or "false".
A predicate can be associated with a mathematical relation: if n-ka belongs to the relation, then the predicate will return 1 on it. In particular, the one-place predicate defines the relation of belonging to some set.
A predicate is one of the elements of logic of the first and higher orders. Starting with second-order logic, formulas can be quantified by predicates.
The predicate is called identically true and write:
if on any set of arguments it takes the value 1.
The predicate is called identically false and write:
if on any set of arguments it evaluates to 0.
The predicate is called doable if it takes the value 1 on at least one set of arguments.
Since predicates take only two values, all operations of Boolean algebra are applicable to them, for example: negation, implication, conjunction, disjunction, etc.
A quantifier is a general name for logical operations that limit the truth region of a predicate. Most often mentioned:
Universal quantifier(designation:, read: “for everyone ...”, “for everyone ...” or “every ...”, “any ...”, “for anyone ...”).
Existence quantifier(designation:, read: “there is ...” or “there is ...”).
Examples
Denote P(x) predicate " x divisible by 5. Using the general quantifier, we can formally write the following statements (of course, false ones):
any natural number is a multiple of 5;
every natural number is a multiple of 5;
all natural numbers are multiples of 5;
in the following way:
.
The following (already true) statements use the existential quantifier:
there are natural numbers that are multiples of 5;
there is a natural number that is a multiple of 5;
at least one natural number is a multiple of 5.
Their formal notation is:
.Introduction to the concept
Let on the set X prime numbers the predicate P(x) is given: "A prime number x is odd." Substitute the word "any" before this predicate. We get a false statement "any prime number x is odd" (this statement is false, since 2 is an even prime number).
Substituting the word “exists” before this predicate P(x), we obtain a true statement “There is a prime number x that is odd” (for example, x=3).
Thus, it is possible to turn a predicate into a proposition by putting before the predicate the words: “everything”, “exists”, etc., which are called quantifiers in logic.
Quantifiers in mathematical logic
The statement means that the range of the variable x included in the predicate truth region P(x).
("For all values of (x) the statement is true").
The statement means that the truth region of the predicate P(x) is non-empty.
("There is (x) for which the statement is true").
Question 31 Graph and its elements. Basic concepts. Incident, multiplicity, loop, adjacency. Graph types. The route in the graph and its length. Route classification. Adjacency matrices of directed and undirected graphs.
In mathematical graph theory and computer science, a graph is a collection of a non-empty set of vertices and a set of pairs of vertices.
Objects are represented as vertices, or nodes of the graph, and connections are represented as arcs, or edges. For different areas of application, the types of graphs can differ in direction, restrictions on the number of connections, and additional data about vertices or edges.
A path (or chain) in a graph is a finite sequence of vertices in which each vertex (except the last one) is connected to the next one in the sequence of vertices by an edge.
A directed path in a digraph is a finite sequence of vertices v i , for which all pairs ( v i,v i+ 1) are (oriented) edges.
A cycle is a path in which the first and last vertices coincide. In this case, the length of the path (or cycle) is the number of its components ribs. Note that if the vertices u and v are the ends of some edge, then according to this definition, subsequence ( u,v,u) is a cycle. To avoid such "degenerate" cases, the following notions are introduced.
A path (or cycle) is called simple if the edges do not repeat in it; elementary if it is simple and the vertices in it do not repeat. It's easy to see that:
Any path connecting two vertices contains an elementary path connecting the same two vertices.
Any simple non-elementary path contains elementary cycle.
Any simple a cycle passing through some vertex (or edge) contains elementary(sub-)cycle passing through the same vertex (or edge).
A loop is an elementary cycle.
Graph or undirected graph G is an ordered pair G: = (V,E
V
E this is a set of pairs (in the case of an undirected graph - unordered) vertices, called edges.
V(and hence E, otherwise it would be a multiset) are usually considered finite sets. Many nice results obtained for finite graphs are wrong (or differ in some way) for infinite graphs. This is because a number of considerations become false in the case of infinite sets.
The vertices and edges of the graph are also called elements of the graph, the number of vertices in the graph | V| - order, number of edges | E| - graph size.
Peaks u and v are called end vertices (or simply ends) of the edge e = {u,v). An edge, in turn, connects these vertices. Two end vertices of the same edge are called neighbors.
Two edges are called adjacent if they have a common terminal vertex.
Two edges are called multiple if the sets of their end vertices are the same.
An edge is called a loop if its endpoints coincide, i.e. e = {v,v}.
degree deg V peaks V call the number of edges incident to it (in this case, the loops are counted twice).
A vertex is called isolated if it is not the end of any edge; hanging (or leaf) if it is the end of exactly one edge.
Directed graph (abbreviated digraph) G is an ordered pair G: = (V,A), for which the following conditions are satisfied:
V is a non-empty set of vertices or nodes,
A it is a set of (ordered) pairs of distinct vertices, called arcs or directed edges.
Arc is an ordered pair of vertices (v, w), where is the top v is called the beginning w- the end of the arc. We can say that the arc leads from the top v to the top w.
Mixed Count
Mixed Count G is a graph in which some edges may be directed and some may be undirected. Written as an ordered triple G: = (V,E,A), where V, E and A defined in the same way as above.
Directed and undirected graphs are special cases of mixed graphs.
Isomorphic graphs(?)
Graph G is called isomorphic to the graph H if there is a bijection f from the set of vertices of the graph G to the set of graph vertices H, which has the following property: if in the graph G there is an edge from the top A to the top B, then in the graph H f(A) to the top f(B) and vice versa - if in the column H there is an edge from the top A to the top B, then in the graph G must be an edge from a vertex f − 1 (A) to the top f − 1 (B). In the case of a directed graph, this bijection must also preserve the orientation of the edge. In the case of a weighted graph, the bijection must also preserve the weight of the edge.
Graph Adjacency Matrix G with a finite number of vertices n(numbered from 1 to n) is a square matrix A size n, in which the value of the element aij equal to the number of edges i th vertex of the graph in j-th peak.
Sometimes, especially in the case of an undirected graph, a loop (an edge from i th vertex to itself) counts as two edges, i.e. the value of the diagonal element a ii in this case is equal to twice the number of loops around i-th vertex.
The adjacency matrix of a simple graph (without loops and multiple edges) is a binary matrix and contains zeros on the main diagonal.
Question 32 Function. Task methods. Classification of functions. Basic elementary functions and their graphs. Composition of functions. elementary functions.
Function - a mathematical concept that reflects the relationship between elements of sets. We can say that a function is a "law" according to which each element of one set (called domain of definition ) is associated with some element of another set (called range ).
The mathematical concept of a function expresses an intuitive idea of how one quantity completely determines the value of another quantity. So the value of the variable x uniquely determines the value of the expression x 2 , and the value of the month uniquely determines the value of the month following it, also any person can be compared to another person - his father. Similarly, some pre-conceived algorithm, given varying input data, produces certain output data.
Ways to set a function
Analytical method
The function of a mathematical object is binary relation that satisfies certain conditions. A function can be defined directly as a set of ordered pairs, for example: there is a function . However, this method is completely unsuitable for functions on infinite sets (which are the usual real functions: power, linear, exponential, logarithmic, etc.).
To set the function, use the expression: . Wherein, x is a variable that runs through the scope of the function definition, and y- range of values. This entry indicates the presence of a functional relationship between the elements of the sets. X and y can range over any set of objects of any nature. It can be numbers, vectors, matrices, apples, rainbow colors. Let's explain with an example:
Let there be a set apple, plane, pear, chair and many man, locomotive, square. We define the function f as follows: (apple, person), (plane, locomotive), (pear, square), (chair, person). If we introduce a variable x running through the set and a variable y running through the set , the indicated function can be specified analytically as: .
Numeric functions can be defined in the same way. For example: where x runs through the set of real numbers defines some function f. It is important to understand that the expression itself is not a function. A function as an object is a set (of ordered pairs). And this expression as an object is the equality of two variables. It defines a function but is not a function.
However, in many branches of mathematics, it is possible to denote by f(x) both the function itself and the analytical expression that defines it. This syntactic convention is extremely convenient and justified.
Numeric functions can also be specified using a graph. Let be a real function of n variables.
Consider some (n+1)-dimensional linear space over the field of real numbers (because the function is real). We choose any basis () in this space. Each point of the function is associated with a vector: . Thus, we will have a set of linear space vectors corresponding to the points of a given function according to the specified rule. The points of the corresponding affine space will form a certain surface.
If we take the Euclidean space of free geometric vectors (directed segments) as a linear space, and the number of arguments of the function f does not exceed 2, the indicated set of points can be visualized in the form of a drawing (graph). If, moreover, the original basis is taken orthonormal, we get the "school" definition of the graph of the function.
For functions of 3 arguments or more, such a representation is not applicable due to the lack of a person's geometric intuition of multidimensional spaces.
However, for such functions, you can come up with a visual semi-geometric representation (for example, each value of the fourth coordinate of a point can be associated with some color on the graph)
proportional values. If variables y and x are directly proportional
y = k x ,
where k- constant value ( proportionality factor).
Schedule direct proportionality- a straight line passing through the origin and forming with the axis X angle whose tangent is k:tan= k(Fig. 8). Therefore, the coefficient of proportionality is also called slope factor. Figure 8 shows three graphs for k = 1/3, k= 1 and k = 3 .
Linear function. If variables y and x connected by the equation of the 1st degree:
Ax + By = C ,
where at least one of the numbers A or B is not equal to zero, then the graph of this functional dependence is straight line. If a C= 0, then it passes through the origin, otherwise it does not. Linear Function Graphs for Various Combinations A,B,C are shown in Fig.9.
Inverse proportion. If variables y and x are inversely proportional, then the functional dependence between them is expressed by the equation:
y = k / x ,
where k- a constant value.
Inverse Proportional Plot - hyperbola(Fig. 10). This curve has two branches. Hyperbolas are obtained when a circular cone is intersected by a plane (for conic sections, see the section "Cone" in the chapter "Stereometry"). As shown in Fig. 10, the product of the coordinates of the points of the hyperbola is a constant value, in our example equal to 1. In the general case, this value is equal to k, which follows from the hyperbola equation: xy=k.
The main characteristics and properties of a hyperbola:
x 0, range: y 0 ;
The function is monotonic (decreasing) at x< 0i at x > 0, but not
monotonic overall due to break point x = 0);
Unbounded function, discontinuous at a point x= 0, odd, non-periodic;
- The function has no zeros.
Quadratic function. This is the function: y = ax 2 + bx + c, where a, b, c- permanent, a b=c= 0 and y = ax 2. Graph of this function square parabola - OY, which is called parabola axis.Dot O top of the parabola.
Quadratic function. This is the function: y = ax 2 + bx + c, where a, b, c- permanent, a 0. In the simplest case, we have: b=c= 0 and y = ax 2. Graph of this function square parabola - curve passing through the origin (Fig. 11). Every parabola has an axis of symmetry OY, which is called parabola axis.Dot O the intersection of a parabola with its axis is called top of the parabola.
Function Graph y = ax 2 + bx + c is also a square parabola of the same type as y = ax 2 , but its vertex lies not at the origin, but at the point with coordinates:
The shape and location of a square parabola in the coordinate system depends entirely on two parameters: the coefficient a at x 2 and discriminant D:D = b 2 – 4ac. These properties follow from the analysis of the roots of the quadratic equation (see the corresponding section in the Algebra chapter). All possible different cases for a square parabola are shown in Fig.12.
Main characteristics and properties of a square parabola:
Function scope: < x+ (i.e. x R), and the area
values: … (Please answer this question yourself!);
The function as a whole is not monotonic, but to the right or left of the vertex
behaves like a monotone;
The function is unbounded, everywhere continuous, even for b = c = 0,
and non-periodic;
- at D< 0 не имеет нулей.
Exponential function. Function y = a x, where a is a positive constant number, called exponential function.Argument x accepts any valid values; as function values are considered only positive numbers, since otherwise we have a multivalued function. Yes, the function y = 81x has at x= 1/4 four different values: y = 3, y = 3, y = 3 i and y = 3 i(Check, please!). But we consider as the value of the function only y= 3. Graphs of the exponential function for a= 2 and a= 1/2 are shown in Fig.17. They pass through the point (0, 1). At a= 1 we have a graph of a straight line parallel to the axis X, i.e. the function turns into a constant value equal to 1. When a> 1, the exponential function increases, and at 0< a < 1 – убывает. Основные характеристики и свойства показательной функции:
Function scope: < x+ (i.e. x R);
range: y> 0 ;
The function is monotonic: it increases with a> 1 and decreases at 0< a < 1;
- The function has no zeros.
Logarithmic function. Function y= log a x, where a- a constant positive number not equal to 1 is called logarithmic. This function is the inverse of the exponential function; its graph (Fig. 18) can be obtained by rotating the graph of the exponential function around the bisector of the 1st coordinate angle.
Main characteristics and properties logarithmic function:
Function scope: x> 0, and the range of values: < y+
(i.e. y R);
This is a monotonic function: it increases as a> 1 and decreases at 0< a < 1;
The function is unbounded, everywhere continuous, non-periodic;
The function has one zero: x = 1.
trigonometric functions. When constructing trigonometric functions, we use radian measure of angles. Then the function y= sin x represented by a graph (Fig. 19). This curve is called sinusoid.
Function Graph y= cos x shown in Fig.20; it is also a sine wave resulting from moving the graph y= sin x along the axis X to the left by 2
From these graphs, the characteristics and properties of these functions are obvious:
Domain: < x+ range of values: 1 y +1;
These functions are periodic: their period is 2;
Limited functions (| y| , everywhere continuous, not monotone, but
having so-called intervals of monotonicity, inside which they
behave like monotonic functions (see graphs in Fig. 19 and Fig. 20);
Functions have an infinite number of zeros (for more details, see the section
"Trigonometric Equations").
Function Graphs y= tan x and y= cot x shown respectively in Fig.21 and Fig.22
It can be seen from the graphs that these functions are: periodic (their period ,
unbounded, generally not monotonic, but have intervals of monotonicity
(what?), discontinuous (what break points do these functions have?). Region
definitions and range of these functions:
Functions y= Arcsin x(fig.23) and y= Arccos x(Fig. 24) multivalued, unlimited; their domain of definition and range of values, respectively: 1 x+1 and < y+ . Since these functions are multivalued,
considered in elementary mathematics, their main values are considered as inverse trigonometric functions: y= arcsin x and y= arccos x; their graphs are highlighted in Fig.23 and Fig.24 with bold lines.
Functions y= arcsin x and y= arccos x have the following characteristics and properties:
Both functions have the same domain of definition: -1 x +1 ;
their ranges: /2 y/2 for y= arcsin x and 0 y for y= arccos x;
(y= arcsin x is an increasing function; y= arccos x- decreasing);
Each function has one zero ( x= 0 for the function y= arcsin x and
x= 1 for the function y= arccos x).
Functions y= Arctan x(fig.25) and y= Arccot x(Fig. 26) - multivalued, unlimited functions; their domain of definition: x+ . Their main meanings y= arctan x and y= arccot x are considered as inverse trigonometric functions; their graphs are highlighted in Fig.25 and Fig.26 with bold branches.
Functions y= arctan x and y= arccot x have the following characteristics and properties:
Both functions have the same scope: x + ;
their ranges: /2<y < /2 для y= arctan x and 0< y < для y= arccos x;
Functions are bounded, non-periodic, continuous and monotonic
(y= arctan x is an increasing function; y= arccot x- decreasing);
Function only y= arctan x has a single zero ( x= 0);
function y= arccot x has no zeros.
Function Composition
If two mappings and are given, where , then the "through mapping" from to given by the formula , , which is called the composition of functions and and denoted by , makes sense.
Fig. 1.30. Through display from to
In addition to the operations considered above, we will use two more new operations related to the peculiarities of the logic of predicates. These operations express statements of generality and existence.
quantifier- some way to attribute the presence of some properties to a whole set of objects: (general quantifier) or simply (), (existence quantifier).
1. General quantifier. Let R (x) be a well-defined predicate that takes the value of AND or L for each element x of some field M. Then by the expression (x) R (x) we mean the statement is true when R (x) is true for each element x of the field M, and false otherwise. This statement no longer depends on x. The corresponding verbal expression would be: "for every x, R(x) is true."
Let now a U(x)-formula of the logic of predicates, which takes on a certain value, if the variable objects and variable predicates included in it are replaced in a completely definite way. The formula I(x) can contain other variables besides x. Then the expression H(x) when replacing all variables of both objects and predicates, except for x, is a specific predicate that depends only on x. And the formula (x) and (x) becomes a well-defined statement. Therefore, this formula is completely determined by setting the values of all variables except x, and, therefore, does not depend on x. The symbol (x) is called general quantifier .
2. Existence quantifier. Let R(x) be some predicate. We associate the formula (x)R(x) with it by defining its value as true if there is an element of the field M for which R(x) is true, and false otherwise. Then if I(x) is a definite formula of predicate logic, then the formula (x)I(x) is also defined and does not depend on the value of x. The sign (x) is called existential quantifier .
The quantifiers (x) and (x) are called dual each other.
We will say that in the formulas (x) and (x) and (x) and (x), the quantifiers (x) and (x) refer to the variable x, or that the variable x is associated with the corresponding quantifier.
An object variable not bound by any quantifier we will call free variables. Thus, we have described all the formulas of predicate logic.
If two formulas I and B, referred to a certain field M, take the same values of I or A for all replacements of predicate variables, statement variables, and free object variables, respectively, by individual predicates defined on M, individual statements, and individual objects from M, then we we shall say that these formulas are equivalent on the field M. (In substitutions of variable predicates, propositions, and objects, we, of course, replace those of them that are denoted in the same way in formulas I and B in the same way).
If two formulas are equivalent on any fields M, then we will simply call them equivalent. Equivalent formulas can be replaced by one another.
The equivalence of formulas makes it possible to bring them in different cases to a more convenient form.
In particular, the following holds: AND → B is equivalent to AND B.
Using this, we can find an equivalent formula for any formula in which only & and - are the only operations of the propositional algebra.
Example: (x)(A(x)→(y)B(y)) is equivalent to (x)(A(x)(y)B(y)).
In addition, for predicate logic there are equivalences associated with quantifiers.
There is a law relating quantifiers to negation. Consider the expression (x) and (x).
The statement "(x)U(x) is false" is equivalent to the statement: "there is an element y for which U(y) is false" or, which is the same, "there is an element y for which U(y) is true." Therefore, the expression (x)U(x) is equivalent to the expression (y)U(y).
Consider the expression (x)U(x) in the same way.
This is the statement "(x) AND (x) is false." But such a statement is tantamount to saying: "for all y I(y) is false" or "for all y I(y) is true." So, (x)U(x) is equivalent to (y)U(y).
We have thus obtained the following rule:
The negation sign can be introduced under the quantifier sign by replacing the quantifier with the dual one.
We have already seen that for every formula there is a formula equivalent to it, which of the propositional algebra operations contains only &, and -.
Using equivalences for each formula, one can find an equivalent one in which the negation signs refer to elementary propositions and elementary predicates.
The predicate calculus is intended for the axiomatic description of the logic of predicates.
Predicate calculus - some axiomatic system designed to model a certain environment and test any hypotheses regarding the properties of this environment using the developed model. Hypotheses at the same time assert the presence or absence of certain properties of some objects and are expressed in the form of a logical formula. The substantiation of the hypothesis is thus reduced to assessing the deducibility and feasibility of the logical formula.
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 main K. are used: K. of generality, "V", and K. of existence, "E". In natural language, the words “all”, “any”, “everyone” are distant semantic analogues of generality K.; semantic analogues of K. existence - the words "some", "exists". With the help of K. data, any attributive statement of the form P(x) that an object x is inherent in P can be transformed into a corresponding quantifier statement of the form VxP(x) and of the form 3xP(x). In terms of content, the quantifier formula "VxP(x)" itself reads as "for all x has P(x)", and the formula "ExP(x)" as "for some x, P(x) takes place". A statement of the form VxP(x) is true if any x has 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 no x has property P.
On the basis of the elementary quantifier formulas "VxP(x)", "ExP(x)" other more complex quantifier formulas can be constructed. Logical relationships between such formulas are studied in the logic of predicates. In particular, the formula "3xP(x)" is logically equivalent to the formula ") VxQUANTOR| P(x)”, and the formula “VxP(x)” is equivalent to the formula “) Ex) P(x)”, where “)” are negations.
In an implicit form, K. were already used by Aristotle, however, in a strict meaningful 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, applying krogo to formulas containing only one free variable gives (statement). Distinguish K. community, denoted by the symbol (from English all - all), and K. existence (from exist - exist): xP(x) is interpreted (cm. Interpretation) as "for all x the property P holds", and xP(x) as "there is x such that the property? (x)" holds. If a (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 many-place predicates (i.e. non-single) causes the undecidability of the predicate calculus. The various relationships between the concepts of generality and existence and the logical connectives of propositional logic are formalized in the predicate calculus.
Philosophical encyclopedic dictionary. - M.: Soviet Encyclopedia. Ch. editors: 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. characterization of the area of objects (and sometimes the area of predicates), to which the resulting application of K. belongs. While logical. the means of propositional logic are not enough to express the forms of general, particular, and individual judgments; in the logic of predicates, obtained by expanding the logic of propositions through the introduction of K., such judgments are expressible. So, for example, four main traditional forms of reasoning. the logics "All A are B", "No A is B", "Some A are B" and "Some A are not B" can be written judgments) using the symbolism explained below as follows: ∀(x) (A (x) ⊃ B (x)), ∀ (x) (A (x) ⊃ B (x)), ) & B (x)) and ∃ (x) (A (x) & B (x)). Introduction K. allows you to write down on a formalized logical. language of expression of natures. languages containing quantity. characteristics of c.-l. subject or predicate areas. In nature. languages, the carriers of such characteristics are the so-called. quantified words, among which are, in particular, quantities. numerals, pronouns "all", "every", "some", the verb "exists", adjectives "any", "any", "single", adverbs "infinitely many", etc. It turns out that for the expression of all the mentioned quantifier words in the formalization. languages and logic. calculus, the two most used are sufficient. K.: K. of the generality (or of the generality), usually denoted by the symbol ∀ (the inverted letter A is 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 designation K. are followed by a letter of a certain alphabet called a quantifier variable, which is usually considered as part of the designation K.: ∀x, ∀y, ∀F, ∃x, ∃α, etc. For K. generality, the following designations 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 K. of generality reads as "For all x it is true that A (x)" or "For each x it is true that A (x)"; the expression ∃x (A(x)) containing the 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 ). However, the main the appointment of K. - 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 proposition (true or false) when c.-l. def. replacing these variables with the names of certain objects from their range of values. The expression ∃z(y>0&z>0&x = y-z) already depends only on two variables (x and y), and ∃y∃z (y>0&z>0& &x = y –z) depends 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 quite a definite. statement.
Dr. examples of formulas containing K.: 1) ∀x(x>0); 2) ∃х(х>0); 3) ∀х (2+2=5); 4) ∃x (2+2=4); 5) ∀x (x = x) & (x+2=y); 6) ∀x∃y (∀z (x = z⊃x ≠ 0) & (x is the action of a c.l.k. ∃y are the parts of the formula to the right of them, and the domain of K. ∀z is the formula (x = z⊃x ≠ 0). In other cases, the occurrence of a variable is called free. place - in a free place.. Such, for example, formula 5): the first three (counting from the left) occurrences of the variable x in it are bound, the last is free. Sometimes a variable is said to be 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 (in an informal approach) as its own in the usual sense of the word that it (the expression) depends on different values of this variable; assigning different values to this variable (i.e., replacing all its free occurrences with the name of a f.l. object belonging to the range of this variable), we obtain different (generally speaking) values of the given expression, depending on the value of the variable, i.e. . from the constant substituted for it. As for bound variables, the expressions that enclose them do not really depend on them. For example, the expression ∃x(x = 2y), which depends on y (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 finds in the so-called. the rule of renaming associated variables, postulated or derived in decomp. logical calculus (see Variable, Predicate calculus).
The above interpretation of the meaning of K. referred to the content of the logical. 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 here is simply a certain symbol of calculus. The question of the meaning (meaning) of calculus belongs entirely to the field of interpretation of calculus. As applied to K., one can speak of at least three interpretations: classical, intuitionistic, and constructive, corresponding to various conceptions 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 derivation in cases where the original formulas or the formulas to be proved contain CVs are described by the same so-called formulas. postulates of quantification, for example. postulates of Bernays.
K. of generality and existence are not exhausted by the types of K. used in logic. Extensive K. represent the so-called. limited Q. of the form ∀xP(x)A(x) or ∃xQ(x)A(x), in which the range of variation of the quantifier variable x is "limited" to a certain special. predicate P(x) (or Q(x)). Limited K. are reduced to K. of generality and existence with the help of the following. equivalences: ∀xP(x)A(x) QUANTIOR∀x(P(x) ⊃A(x)) and ∃xQ(x)A(x) QUANTIOR ∃x(Q(x)&A(x)). The frequently used uniqueness criterion ∃!xA(x) ("there is a unique x such that A(x)") is also expressed in terms of the generality and existence criterion, e.g. so: xA(x) QUANTIOR ∃xA(x)& ∀y∀z(A(y)&A(z)⊃y=z).
Other types of K. are also used, which are not covered by the concept of limited K. Such are the “numerical” K. of the form ∃xnA(x) (“there are exactly n different x such that A(x)”), which is used in the intuitionistic logic of K. "quasi-existence" ∃ xA(x), or ("it is not true that there is no x such that A(x)"); with t. sp. classical the logic of the K. of "quasi-existence" is no different from the K. of existence, while in intuitionistic logic the proposition ∃xA(x), which says nothing about the existence of an algorithm for finding x such that A(x), actually asserts only a "quasi" of such x and K. infinity ∃x∞A(x) ("there are infinitely many x such that A(x)"). Expressions containing infinity and numerical quotients can also be written using generality and existence quotients. In the extended predicate calculus, K. are taken not only by subject, but also by predicate variables, i.e. formulas of the form ∃F∀xF(x), ∀Ф∃у(Ф(y)) and so on are considered.
Lit.: Gilbert D. and Ackerman V., Fundamentals of theoretical logic, trans. from English, M., 1947, p. 81-108; Tarsky A., Introduction to the logic and methodology of deductive sciences, trans. from English, M., 1948, o. 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 standardized Russian into information-logical, in: Abstracts of reports at the conference on information processing, machine translation and automatic reading of the text, 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.
Y. 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:
Exist., 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 Handbook
A quantifier is a general name for logical operations that limit the truth region of a predicate and create a proposition. Most often mentioned: The universal quantifier (designation:, reads: “for all ...”, “for each ...” or “every ...” ... Wikipedia
The general name for logical operations, which, on the basis of the predicate P(x), construct a statement that characterizes the region of truth of the predicate P(x). In mathematical In logic, the universal quantifier and the existential quantifier are most commonly used. A statement means ... ... Mathematical Encyclopedia
quantifier- (from lat. quantum how much) a symbol used to denote certain operations mathematical logic, at the same time a logical operation that gives a quantitative description of the area of \u200b\u200bobjects to which the expression obtained in ... ... Beginnings of modern natural science
The specific nature of predicates allows us to introduce operations on them that have no analogues among operations on statements. We mean two quantifier operations on predicates.
General quantifier
To turn a one-place predicate into a statement, instead of its variable, substitute some specific object from the area where the predicate is specified. There is another way for such a transformation - this is the application of binding operations to the predicate by a general quantifier or an existential quantifier. Each of these operations associates a one-place predicate with some statement, true or false, depending on the original predicate.
Definition. is the rule according to which each one-place 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
Verbal analogue of the general 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, instead of it, it is impossible to substitute any specific values. They say that the variable X bound .
If a one-place predicate P(x) given on a finite set M = (a 1 ,a 2 , …,an), then the statement is equivalent to the conjunction P(a 1) P(a 2) ... P(an).
Example 59 .
Let X defined 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, that is, expresses a judgment regarding all X sets M.
Definition. The binding operation by a general quantifier n-place ( n , new ( , true if and only if the one-place predicate defined on the set M 1 is identically true, and false otherwise, that is:
Existence quantifier
Definition. is the rule according to which each one-place 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
Verbal analogue of the existential quantifier $ is: “exists”, “there is”, etc.
Like the expression , in expression variable X also ceases to be a variable in the usual sense of the word: it is - bound variable .
If a one-place predicate P(x) given on a finite set M = (a 1 ,a 2 , …,an), then the statement is equivalent to the 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 statement to determine its truth.
Solution.
Source Predicate P(x): "x is an even number" is a variable statement: when a specific number is substituted for a variable X it becomes a simple statement that is either true or false, for example,
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 the set N contains even numbers, then the statement true.
Definition. The operation of binding by the existential quantifier variable x 1 is the rule according to which eachn-place (n 2) predicate Р(х 1 , х 2 , …, хn) defined on the sets М 1 , М 2 , …, Мn , new (n-1)-local predicate, denoted , which for any items , turns into a statement , false if and only if the one-place predicate defined on the set M 1 is identically false, and true otherwise, that is:
It has already been said above that the variable on which the quantifier is attached is called bound, the variable not bound by the quantifier is called free . The expression on which the quantifier is attached is called quantifier scope and all occurrences of the variable, on which the quantifier is attached, in this expression are bound. On many-place predicates it is possible to hang different quantifiers on different variables, it is impossible to 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 attaching quantifiers to both variables. Give a verbal interpretation of the received statements.
Solution.
Denote the predicate "x loves y" through LOVES (x, y). The sentences corresponding to different variants of hanging quantifiers are illustrated in fig. 2.3-2.8, where X and at are shown on different sets, which is a convention and is undertaken only to explain the meaning of the 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"
Logic and argumentation: Textbook. allowance for universities. Ruzavin Georgy Ivanovich
4.2. quantifiers
4.2. quantifiers
The essential difference between predicate logic and propositional logic is also 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 a special theory of quantification, which is an integral part of the predicate calculus.
For the quantification (quantification) of statements, this theory introduces two basic 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 when 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 a material body:
M - mass;
(x) is a general quantifier.
Similarly, the statement about the existence of extrasensory phenomena can be expressed through the existential quantifier:
where x denotes the phenomena:
E - the property of extrasensory perception inherent in such phenomena;
(Ex) is the existential quantifier.
Using the general quantifier, one 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) - its extension;
Implication sign.
The existential quantifier refers only to a certain subset of objects from a given universe of reasoning. Therefore, for example, it is used to symbolically record statistical laws that state that a property or relation applies only to the characteristics of a certain part of the objects under study.
The introduction of quantifiers makes it possible, first of all, to turn predicates into definite propositions. Predicates themselves are neither true nor false. They become such if concrete statements are substituted instead of variables, or if they are linked by quantifiers, they are quantified. On this basis, the division of variables into bound and free is introduced.
Bound variables are variables that fall under the action of signs of quantifiers of generality or existence. 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 both to a single predicate and to 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 proposition.
With the help of a combination of quantifiers, quite complex natural language sentences can be expressed in the symbolic language of logic. At the same time, statements dealing with the existence of objects that satisfy certain condition, are introduced using the existential quantifier. For example, the 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 risk 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 is "getting cancer." With certain reservations, the same thing could be expressed by means of the general quantifier: (x) (K(x) ? P(x)). But the statement that anyone who smokes can get cancer would be incorrect, and therefore it is best written using the existential quantifier, not the 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 such phrases as "for everyone", "every", "any", "any", etc. By negating the general quantifier, one can express general negative statements, which in natural language are introduced by the words "none", "none", "no one", etc.
Of course, when translating the statements of a natural language into a symbolic language, certain difficulties are encountered, but the necessary accuracy and unambiguity of the expression of thought is achieved. One cannot, however, think that formal language is richer than 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 natural language expressions as a universal means of expressing thoughts and exchanging them in the process of communication.
Most often, the quantifiers of generality and existence occur together. For example, to express symbolically the statement: "For each real number x there is a number y such that x will be less than y", denote the predicate "be less than" 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 with the help of 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 an object (subject) language. The meaning of the negation of quantifiers is obvious: if it is not true that A holds for any x, then there are x for which A does not hold. It also follows that if: any x is inherent in A, then there is no such x, which would have inherent non-A, which is represented symbolically in the first law of mutual expressibility.