Английский язык 

Кванторы общности и существования. Логические операции

Рассмотрим несколько предложений с переменной:

- «- простое натуральное число»; область допустимых значений этого предиката – множество натуральных чисел;

- «- чётное целое число»; область допустимых значений этого предиката – множество целых чисел;

- «
- равносторонний»;

- «
»

- «студентполучил оценку»

- «делится нацело на 3»

Определение . Если предложение с переменными при любой за­мене переменных допустимыми значениями превращается в высказы­вание, то такое предложение называется предикатом.

,
,
,
- предикаты от одной переменной (одноместные пре­дикаты). Предикаты от двух переменных:
,
- двухместные предикаты. Высказывания – нульместные предикаты.

Квантор общности.

Определение . Символназывается квантором общности.

читается: для любого, для каждого, для всех.

Пусть
- одноместный предикат.

читается: для любых
- истина.

Пример.

- «Все натуральные числа простые» - Лож­ное высказывание.


- «Все целые числа чётные» - Ложное высказывание.


- «Все студенты получили оценку» - одноместный преди­кат. Навесили квантор на двуместный предикат, получили одномест­ный предикат. Аналогично
-n-местный предикат, то

- (n-1)-местный предикат.

- (n-2)-местный пре­дикат.

В русском языке квантор общности опускается.

Квантор существования.

Определение. Символназывается квантором существования.

читается: существует, есть, найдётся.

Выражение
, где
- одноместный предикат, чита­ется: существует, для которого
истинно.

Пример.

- «существуют простые натуральные числа». (и)


- «существуют целые чётные числа». (и).


- «существует студент, который получил оценку» - од­номестный предикат.

Если на n-местный предикат навесить 1 квантор, то получим (n-1)-ме­стный предикат, если навеситьnкванторов, то получим нульместный предикат, т.е. высказывание.

Если навешивать кванторы одного вида, то порядок навешива­ния кванторов безразличен. А если на предикат навешиваются разные кванторы, то порядок навешивания кванторов менять нельзя.

Построение отрицания высказываний, содержащих кван­торы. Законы Де Моргана.

Закон Де Моргана.

При построении отрицания высказывания, содержащего квантор общности, этот квантор общности заменяется на квантор существования, а предикат заменяется на своё отрицание.

Закон Де Мор­гана.

При построении отрицания высказываний, содержащих квантор существования, нужно квантор существования заменить на квантор общности, а предикат
- его отрицанием. Аналогично строится отри­цание высказываний, содержащих несколько кванторов: квантор общности заменяется на квантор существования, квантор существова­ния - на квантор общности, предикат заменяется своим отрицанием.

П.2. Элементы теорий множеств (интуитивная теория множеств). Числовые множества. Множество действительных чисел.

Описание множества : под словом множество понимается сово­купность объектов, которая рассматривается как одно целое. Вместо слова «множество» иногда говорят «совокупность», «класс».

Определение . Объект, входящий в множество, называется его элементом.

Запись
обозначает, чтоявляется элементом множества. Запись
обозначает, чтоне является элементом множества. Про любой объект можно сказать, является он элементом множества или нет. Запишем это утверждение с помощью логических символов:

Не существует объекта, который одновременно принадлежит множеству и не принадлежит, то есть,

Множество не может содержать одинаковых элементов, т.е. если из множества, содержащего элемент , удалить элемент, то полу­чится множество, не содержащее элемент.

Определение. Два множестваиназываются равными, если они содержат одни те же элементы.

Функциональная природа предиката влечет за собой введение ещё одного понятия – квантора . (quantum – от лат. «сколько») Кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции в случае конечных и бесконечных областей.

Квантор общности (все, всякий, каждый, любой (all – «всякий»)). Соответствующие ему словесное выражение звучит так:

«Для всякого x Р(x) истинно». Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действия квантора, после которого стоит переменная. Все прочие вхождения – свободные, переход от P(x) к x(Px) или (Px) называется связыванием переменной x или навешиванием квантора на переменную x (или на предикат P) или квантификацией переменной х. Переменная, на которую навешивается квантор, называется связанной , несвязанная квантования переменная называется свободной .

Например, переменная x в предикате Р(x) называется свободной (x – любое из М), в высказывании Р(x) переменную x называют связанной переменной.

Справедлива равносильность P(x 1)P(x 2)…P(x n),

P(x) – предикат, определенный на множестве М={х 1 ,х 2 ...х 4 }

Квантор существования (exist – «существовать»). Словесное выражение, соответствующее ему, звучит так: “Существует x, при котором Р(x) истинно”. Высказывание xР(x) уже не зависит от x, переменная x связана квантором .

Справедлива равносильность:

xP(x) = P(x 1)P(x 2)…P(x n), где

P(x) - предикат, определенный на множестве М={x 1 ,x 2 …x n }.

Квантор общности и квантор существования называют двойственными, иногда используется обозначение квантора ! – «существует, и притом, только один».

Ясно, что высказывание xP(x) истинно только в том единственном случае, когда Р(x) - тождественно истинный предикат, а высказывание ложно только тогда, когда Р(x) - тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат xP(x,y) или xP(x,y), зависящий от у и не зависящий от х.

К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь высказываний:

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)

Пример 3. Рассмотреть возможные варианты навешивания кванторов на предикат P(x,y) – “x делится на y ”, определенный на множестве натуральных чисел (без нуля) N . Дать словесные формулировки полученных высказываний и определить их истинность.

Операция навешивания кванторов приводит к следующим формулам:



Высказывания “для любых двух натуральных чисел имеет место делимость одного на другое” (или 1) все натуральные числа делятся на любое натуральное число; 2) любое натуральное число является делителем для любого натурального числа) ложные;

Высказывания “существуют такие два натуральных числа, что первое делится на второе” (1. «существует такое натуральное число x, которое делится на какое-то число y»; 2. «существует такое натуральное число y, которое является делителем какого-то натурального числа x») истинны;

Высказывание “существует натуральное число, которое делится на любое натуральное”, ложное;

Высказывание “для всякого натурального числа найдется такое натуральное, которое делится на первое” (или для всякого натурального числа найдется свое делимое), истинное;

Высказывание “для всякого натурального x существует такое натуральное число y, на которое оно делится” (или «для всякого натурального числа найдется свой делитель»), истинное;

Высказывание “существует натуральное число, которое является делителем всякого натурального числа”, истинное (таким делителем является единица).

В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логическое значение, т.е. например, высказывания P(x,y) и P(x,y) различны.

Пусть предикат P(x,y) означает, что x является матерью для y, тогда P(x,y) означает, что у каждого человека есть мать – истинное утверждение. P(x,y) означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, в противном случае оно ложно. Таким образом, перестановка кванторов всеобщности и существования может изменить сам смысл и значение выражения.

а) заменить начальный знак (или ) на противоположный

б) поставить знак перед остальной частью предиката

При изучении высказывательных форм (предикатов) был указан один из способов получения высказываний: подстановка какого-нибудь значения переменной в Р(х) из некоторого множества А. Например,

Р(х):” х - простое число”. Подставив х = 7, получим высказывание

“ 7 - простое число”. Мы познакомимся ещё с двумя логическими операциями: навешивание квантора общности и квантора существования, которые позволяют получить из высказывательных форм высказывания.

Подставим перед высказывательной формой Р(х) слово “любое”: “ любое х - простое число”. Получили ложное высказывание. Подставим перед Р(х) слово “некоторые”: “ некоторые числа х - простые”. Получили истинное высказывание.

В математике слова “любые”, “некоторые” и их синонимы называются кванторами, которые соответственно называются квантор общности (") и квантор существования ($). Квантор общности заменяется в словесных формулировках словами: любой, все, каждый, всякий и т.д. Квантор существования в словесной формулировке заменяется словами: существует, хотя бы один, какой-нибудь найдётся и т.д.

Пусть Р(х) - высказывательная форма на М. Запись

("хÎМ) Р(х)

означает: для любого элемента х (из множества М) имеет место Р(х), что уже представляет собой высказывание. Чтобы доказать, что высказывание ("х)Р(х) - истинно, надо перебрать все элементы а, b, с и т.д. из М и убедиться, что Р(а), Р(b), Р(с),... истинны, и, если невозможно перебрать элементы М, должны доказать с помощью рассуждений, что для любого а из М высказывание Р(а) истинно. Чтобы убедиться, что ("х)Р(х) ложно, достаточно найти лишь один элемент аÎМ, для которого Р(а) ложно.

ПРИМЕР . Дана высказывательная форма

В(х):” - простое число”.

В(1): 2 2 + 1 = 5 - простое число;

В(2): = 17 - простое число;

В(3): = 257 - простое число;

В(4): = 65537 - простое число.

Можно ли сказать, что ("х)В(х) ? Это необходимо доказывать. Леонард Эйлер доказал, что В(5) - ложно, т.е. + 1 = 2 32 + 1 делится на 641 и, следовательно, ("х)В(х) - ложно.

ПРИМЕР . Рассмотрим высказывание ("х)С(х), где на N задано С(х): “х 3 + 5х делится на 6”.

Очевидно, С(1), С(2), С(3), С(4) истинны. Но если мы проверим даже миллион значений х всегда есть опасность, что для миллион первого значения х утверждение С(х) окажется ложным.

Доказать можно, например, так:

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

Выражение (х - 1)х(х + 1) делится на 3, так как из трех последовательных натуральных чисел по крайней мере одно делится на 3; это выражение делится и на 2, так как из трех последовательных чисел одно или два числа чётны. Второе слагаемое 6х делится на 6, следовательно и вся сумма делится на 6, т.е. ("х)С(х) - истинно.

Пусть С(х) некоторая высказывательная форма. Запись

означает: существует элемент х из множества М, для которого имеет место С(х). ($х)С(х) уже высказывание. Если во множестве М можно найти элемент а, для которого С(а) истинно, то высказывание($х)С(х) - истинно. Если же в М нет ни одного элемента а, для которого С(а) истинно, высказывание ($х)С(х) - ложно.

ПРИМЕР . На множествеN задано С(х):” ”. С(1) - ложно, С(2) - ложно, С(5) - истинно. Следовательно, ($х)С(х) - истинное высказывание.

ПРИМЕР . На множестве N задано К(х):” х 2 + 2х + 3 делится на 7”. К(1) = 6, 6 не делится на 7; К(2) = 11, 11 не делится на 7 и т.д.

Гипотеза: ($х)К(х) - ложно.

Докажем это. Любое натуральное число по теореме о делении с остатком можно представить в виде n = 7q + r, где r < 7.

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

Итак, число n 2 + 2n + 3 делится на 7 тогда и только тогда, когда r 2 + 2r + 3 делится на 7. Остаток r Î { 0, 1, 2, 3, 4, 5, 6 }. Методом перебора убедимся, что r 2 + 2r + 3 не делится на 7. Итак, ($х)К(х) - ложно.

Как построить отрицание высказывания с квантором?

Для того чтобы построить отрицание высказывания с квантором, нужно заменить квантор общности (") на квантор существования ($) и, наоборот, квантор существования на квантор общности, а предложение, стоящее после квантора, на его отрицание, т.е.

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

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

Например, пусть даны два высказывания:

А: “каждое простое число нечётно”;

В: “ каждое простое число чётно”.

Будет ли В отрицанием высказывания А? Нет, так как ни одно из высказываний не является истинным. В данном случае

А: “не каждое простое число нечётно, т.е. существует чётное простое число” - истинное высказывание.

В дальнейшем считаем, что построено отрицание предложения, если не просто записано его отрицание, но и полученное предложение преобразовано к виду, где знаки отрицания стоят перед более простыми выражениями. Например, отрицанием предложения вида А Ù В будем считать не (А Ù В), а ему равносильное: А Ú В.

Пусть А(х,у) - высказывательная форма с двумя переменными.

Тогда ("х)А(х,у), ($х)А(х,у), ("х)А(х,у), ($х)А(х,у) тоже высказывательные формы но уже с одной переменной. В этом случае говорят, что квантор связывает одну переменную. Чтобы получить из высказывательной формы А(х,у) высказывание необходимо связать обе переменные. Например, ("х)($у)А(х,у) - высказывание.

Для высказывательной формы Р(х,у): “ x < y”, заданной на Z , рассмотрим все случаи получения высказывания путем добавления (навешивания) кванторов:

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

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

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

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

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

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

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

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

` Обратите внимание на высказывания (1) и (2), (3) и (4). Структуры этих высказываний отличаются лишь порядком следования одноименных кванторов, но при этом не меняются смысл и значения истинности высказываний.

Высказывания (5) и (6), (7) и (8) отличаются порядком следования разноимённых кванторов, что приводит к изменению смысла и, возможно, значения истинности высказывания. Высказывание (7) утверждает о наличии в Z наименьшего числа, что ложно. (8) утверждает об отсутствии такого, что истинно.

Теоретические вопросы:

1. Понятие предиката от одного, нескольких переменных.

2. Примеры одноместных и двуместных предикатов. 3. Область истинности предиката.

4. Кванторы общности и существования. Свободные и связанные переменные. Операции над предикатами. Какова область истинности ; ; ; ? Дать геометрические интерпретации.

5. Преобразование формул логики предикатов. Определение тождественно истинного и тождественно ложного предиката, связь с областью истинности. Основные равносильности.

Упражнения

5.1. Укажите несколько значений переменных, при которых следующие предикаты истинны, ложны:

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

2. х < 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. Найдите область истинности предикатов упражнения 5.1. Случаи 13 - 16 изобразите на координатной плоскости.

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. Найдите область истинности предикатов:

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) Ú ( - > - );

Специфическая природа предикатов позволяет ввести над ними такие операции, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами.

Квантор общности

Для превращения одноместного предиката в высказывание нужно вместо его переменной подставить какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения – это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.

Определение. называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае, то есть

Словесным аналогом квантору общности " является: «для любого», «для каждого», «для всякого» и т.п.

В выражении переменная х уже перестает быть переменной в обычном смысле этого слова, то есть вместо нее невозможно подставить какие бы то ни было конкретные значения. Говорят, что переменная х связанная .

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно конъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 59 .

Пусть х определен на множестве людей М , а Р(х) – предикат «х – смертен» . Дать словесную формулировку предикатной формулы .

Решение.

Выражение означает «все люди смертны». Оно не зависит от переменной х , а характеризует всех людей в целом, т. е. выражает суждение относительно всех х множества М .

Определение. Операцией связывания квантором общности n-местному ( n , сопоставляется новый ( , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно истинен, и ложное в противном случае, то есть:

Квантор существования

Определение. называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое ложно в том и только в том случае, когда предикат Р(х) тождественно ложен, и истинно в противном случае, то есть

Словесным аналогом квантору существования $ является: «существует», «найдется» и т.п.

Подобно выражению , в выражении переменная х также перестает быть переменной в обычном смысле этого слова: это — связанная переменная .

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно дизъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 60.

Пусть Р(х) – предикат «х – четное число» , определенный на множестве N . Дать словесную формулировку высказыванию , определить его истинность.

Решение.

Исходный предикат Р(х): «х – четное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например,

при подстановке числа 5 – ложным, при подстановке числа 10 – истинным.


Высказывание означает «во множестве натуральных чисел N существует четное число». Поскольку множество N содержит четные числа, то высказывание истинно.

Определение. Операцией связывания квантором существования по переменной х 1 называется правило, по которому каждому n-местному (n 2) предикату Р(х 1 , х 2 , …, х n), определенному на множествах М 1 , М 2 , …, М n , сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов , превращается в высказывание , ложное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно ложен, и истинное в противном случае, то есть:

Выше уже было сказано, что переменная, на которую навешен квантор, называется связанной, несвязанная квантором переменная называется свободной . Выражение, на которое навешивается квантор, называется областью действия квантора и все вхождения переменной, на которую навешен квантор, в это выражение являются связанными. На многоместные предикаты можно на разные переменные навешивать различные кванторы, нельзя на одну и ту же переменную навешивать сразу два квантора.

Пример 61.

Пусть предикат Р(х, у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение.

Обозначим предикат «х любит у» через ЛЮБИТ(х, у) . Предложения, соответствующие различным вариантам навешивания кванторов, проиллюстрированы на рис. 2.3-2.8, где х и у показаны на разных множествах, что является условностью и предпринято только для объяснения смысла предложений (реальные множества переменных х и у , очевидно, должны совпадать):

— «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит» (рис. 2.3).

Рис. 2.3. Иллюстрация к высказыванию «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит»

Предика́т (лат. praedicatum - заявленное, упомянутое, сказанное) - любое математическое высказывание, в котором есть, по меньшей мере, одна переменная. Предикат является основным объектом изучения логики первого порядка.

Предикат – выражение с логическими переменными, имеющие смысл при любых допустимых значениях этих пременных.

Выражения: х > 5, x > y – предикаты.

Предика́т (n -местный, или n -арный) - это функция с множеством значений {0,1} (или «ложь» и «истина»), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».

Предикат можно связать с математическим отношением: если n -ка принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.

Предикат - один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам.

Предикат называют тождественно-истинным и пишут:

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым , если хотя бы на одном наборе аргументов он принимает значение 1.

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д

Ква́нтор - общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают:

Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).

Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).

Примеры

Обозначим P (x ) предикат «x делится на 5». Используя квантор общности, можно формально записать следующие высказывания (конечно, ложные):

любое натуральное число кратно 5;

каждое натуральное число кратно 5;

все натуральные числа кратны 5;

следующим образом:

.

Следующие (уже истинные) высказывания используют квантор существования:

существуют натуральные числа, кратные 5;

найдётся натуральное число, кратное 5;

хотя бы одно натуральное число кратно 5.

Их формальная запись:

.Введение в понятие

Пусть на множестве Х простых чисел задан предикат Р(х): «Простое число х - нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число х нечётно» (это высказывание ложно, так как 2 - простое чётное число).

Подставив перед данным предикатом Р(х) слово «существует», получим истинное выказывание «Существует простое число х, являющееся нечётным» (например, х=3).

Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова: «все», «существует», и др., называемые в логике кванторами.

Кванторы в математической логике

Высказывание означает, что область значений переменной x включена в область истинности предиката P (x ).

(«При всех значениях (x) утверждение верно»).

Высказывание означает, что область истинности предиката P (x ) непуста.

(«Существует (x) при котором утверждение верно»).

Вопрос31 Граф и его элементы. Основные понятия. Инцидентность, кратность, петля, смежность. Типы графов. Маршрут в графе и его длина. Классификация маршрутов. Матрицы смежности ориентированного и неориентированного графов.

В математической теории графов и информатике граф - это совокупность непустого множества вершин и множества пар вершин.

Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Ориентированным путём в орграфе называют конечную последовательность вершин v i , для которой все пары (v i ,v i + 1) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер . Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u ,v ,u ) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.

Всякий простой неэлементарный путь содержит элементарный цикл .

Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).

Петля - элементарный цикл.

Граф или неориентированный граф G - это упорядоченная пара G : = (V ,E

V

E это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

V (а значит и E , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов . Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | - порядком, число рёбер | E | - размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u ,v }. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v ,v }.

Степенью deg V вершины V называют количество инцидентных ей рёбер(при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) G - это упорядоченная пара G : = (V ,A ), для которой выполнены следующие условия:

V это непустое множество вершин или узлов,

A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга - это упорядоченная пара вершин (v, w) , где вершину v называют началом, а w - концом дуги. Можно сказать, что дуга ведёт от вершины v к вершине w .

Смешанный граф

Смешанный граф G - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G : = (V ,E ,A ), где V , E и A определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы(?)

Граф G называется изоморфным графу H , если существует биекция f из множества вершин графа G в множество вершин графа H , обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B , то в графе H f (A ) в вершину f (B ) и наоборот - если в графе H есть ребро из вершины A в вершину B , то в графе G должно быть ребро из вершины f − 1 (A ) в вершину f − 1 (B ). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n ) - это квадратная матрица A размера n , в которой значение элемента a ij равно числу рёбер из i -й вершины графа в j -ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a ii в этом случае равно удвоенному числу петель вокруг i -й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Вопрос32 Функция. Способы задания. Классификация функций. Основные элементарные функции и их графики. Композиция функций. Элементарные функции.

Функция - математическое понятие, отражающее связь между элементами множеств. Можно сказать, что функция это «закон», по которому каждому элементу одного множества (называемому областью определения ) ставится в соответствие некоторый элемент другого множества (называемого областью значений ).

Математическое понятие функции выражает интуитивное представление о том, как одна величина полностью определяет значение другой величины. Так значение переменной x однозначно определяет значение выражения x 2 , а значение месяца однозначно определяет значение следующего за ним месяца, также любому человеку можно сопоставить другого человека - его отца. Аналогично, некоторый задуманный заранее алгоритм по варьируемым входным данным выдаёт определённые выходные данные.

Способы задания функции

Аналитический способ

Функция математический объект представляет собой бинарное отношение, удовлетворяющее определенным условиям. Функцию можно задать непосредственно как множество упорядоченных пар, например: есть функция . Однако, этот способ совершенно непригоден для функций на бесконечных множествах (каковыми являются привычные вещественные функции: степенная, линейная, показательная, логарифмическая и т. п.).

Для задания функции пользуются выражением: . При этом, x есть переменная, пробегающая область определения функции, а y - область значений. Эта запись говорит о наличии функциональной зависимости между элементами множеств. х и y могут пробегать любые множества объектов любой природы. Это могут быть числа, векторы, матрицы, яблоки, цвета радуги. Поясним на примере:

Пусть имеется множество яблоко, самолет, груша, стул и множество человек, паровоз, квадрат . Зададим функцию f следующим образом: (яблоко,человек), (самолет,паровоз), (груша,квадрат), (стул,человек) . Если ввести переменную x, пробегающую множество и переменную y, пробегающую множество , указанную функцию можно задать аналитически, как: .

Аналогично можно задавать числовые функции. Например: где х пробегает множество вещественных чисел задает некоторую функцию f. Важно понимать, что само выражение не является функцией. Функция как объект представляет собой множество (упорядоченных пар). А данное выражение как объект есть равенство двух переменных. Оно задает функцию, но не является ею.

Однако, во многих разделах математики, можно обозначать через f(x) как саму функцию, так и аналитическое выражение, ее задающее. Это синтаксическое соглашение является крайне удобным и оправданным.

Графический способ

Числовые функции можно также задавать с помощью графика. Пусть - вещественная функция n переменных.

Рассмотрим некоторое (n+1)-мерное линейное пространство над полем вещественных чисел (так как функция вещественная). Выберем в этом пространстве любой базис (). Каждой точке функции сопоставим вектор: . Таким образом, мы будем иметь множество векторов линейного пространства, соответствующих точкам данной функции по указанному правилу. Точки соответствующего аффинного пространства будут образовывать некоторую поверхность.

Если в качестве линейного пространства взять евклидово пространство свободных геометрических векторов (направленных отрезков), а число аргументов функции f не превосходит 2, указанное множество точек можно изобразить наглядно в виде чертежа (графика). Если сверх того исходный базис взять ортонормированным, получим "школьное" определение графика функции.

Для функций 3 аргументов и более такое представление не применимо ввиду отсутствия у человека геометрической интуиции многомерных пространств.

Однако, и для таких функций можно придумать наглядное полугеометрическое представление (например каждому значению четвертой координаты точки сопоставить некоторый цвет на графике)

Пропорциональные величины. Если переменные y и x прямо пропорциональны

y = k x ,

где k - постоянная величина ( коэффициент пропорциональности ).

График прямой пропорциональности – прямая линия, проходящая через начало координат и образующая с осью X угол , тангенс которого равен k : tan = k (рис.8). Поэтому, коэффициент пропорциональности называется также угловым коэффициентом . На рис.8 показаны три графика для k = 1/3, k = 1 и k = 3 .

Линейная функция. Если переменные y и x связаны уравнением 1-ой степени:

A x + B y = C ,

где по крайней мере одно из чисел A или B не равно нулю, то графиком этой функциональной зависимости является прямая линия . Если C = 0, то она проходит через начало координат, в противном случае - нет. Графики линейных функций для различных комбинаций A , B , C показаны на рис.9.

Обратная пропорциональность. Если переменные y и x обратно пропорциональны , то функциональная зависимость между ними выражается уравнением:

y = k / x ,

где k - постоянная величина.

График обратной пропорциональности – гипербола (рис.10). У этой кривой две ветви. Гиперболы получаются при пересечении кругового конуса плоскостью (о конических сечениях см. раздел «Конус» в главе «Стереометрия»). Как показано на рис.10, произведение координат точек гиперболы есть величина постоянная, в нашем примере равная 1. В общем случае эта величина равна k , что следует из уравнения гиперболы: xy = k .

Основные характеристики и свойства гиперболы:

x 0, область значений: y 0 ;

Функция монотонная (убывающая) при x < 0и при x > 0, но не

монотонная в целом из-за точки разрыва x = 0);

Функция неограниченная, разрывная в точке x = 0, нечётная, непериодическая;

- нулей функция не имеет.

Квадратичная функция. Это функция: y = ax 2 + bx + c , где a, b, c - постоянные, a b = c = 0 и y = ax 2 . График этой функции квадратная парабола - OY , которая называется осью параболы .Точка O вершиной параболы .

Квадратичная функция. Это функция: y = ax 2 + bx + c , где a, b, c - постоянные, a 0. В простейшем случае имеем: b = c = 0 и y = ax 2 . График этой функции квадратная парабола - кривая, проходящая через начало координат (рис.11). Каждая парабола имеет ось симметрии OY , которая называется осью параболы .Точка O пересечения параболы с её осью называется вершиной параболы .

График функции y = ax 2 + bx + c - тоже квадратная парабола того же вида, что и y = ax 2 , но её вершина лежит не в начале координат, а в точке с координатами:

Форма и расположение квадратной параболы в системе координат полностью зависит от двух параметров: коэффициента a при x 2 и дискриминанта D : D = b 2 – 4ac . Эти свойства следуют из анализа корней квадратного уравнения (см. соответствующий раздел в главе «Алгебра»). Все возможные различные случаи для квадратной параболы показаны на рис.12.

Основные характеристики и свойства квадратной параболы:

Область определения функции:  < x + (т.e. x R ), а область

значений: … (ответьте, пожалуйста, на этот вопрос сами!);

Функция в целом не монотонна, но справа или слева от вершины

ведёт себя, как монотонная;

Функция неограниченная, всюду непрерывная, чётная при b = c = 0,

и непериодическая;

- при D < 0 не имеет нулей.

Показательная функция. Функция y = a x , где a - положительное постоянное число, называется показательной функцией .Аргумент x принимает любые действительные значения ; в качестве значений функции рассматриваются только положительные числа , так как иначе мы имеем многозначную функцию. Так, функция y = 81 x имеет при x = 1/4 четыре различных значения: y = 3, y = 3, y = 3 i и y = 3 i (проверьте, пожалуйста!). Но мы рассматриваем в качестве значения функции только y = 3. Графики показательной функции для a = 2 и a = 1/2 представлены на рис.17. Они проходят через точку (0, 1). При a = 1 мы имеем график прямой линии, параллельной оси Х , т.e. функция превращается в постоянную величину, равную 1. При a > 1 показательная функция возрастает, a при 0 < a < 1 – убывает. Основные характеристики и свойства показательной функции:

Область определения функции:  < x + (т.e. x R );

область значений: y > 0 ;

Функция монотонна: возрастает при a > 1 и убывает при 0 < a < 1;

- нулей функция не имеет.

Логарифмическая функция. Функция y = log a x , где a – постоянное положительное число,не равное 1, называется логарифмической . Эта функция является обратной к показательной функции; её график (рис.18) может быть получен поворотом графика показательной функции вокруг биссектрисы 1-го координатного угла.

Основные характеристики и свойства логарифмической функции:

Область определения функции: x > 0,а область значений:  < y +

(т.e. y R );

Это монотонная функция: она возрастает при a > 1 и убывает при 0 < a < 1;

Функция неограниченная, всюду непрерывная, непериодическая;

У функции есть один ноль: x = 1.

Тригонометрические функции. При построении тригонометрических функций мы используем радианную меру измерения углов.Тогда функция y = sin x представляется графиком (рис.19). Эта кривая называется синусоидой .

График функции y = cos x представлен на рис.20; это также синусоида, полученная в результате перемещения графика y = sin x вдоль оси Х влево на 2

Из этих графиков очевидны характеристики и свойства этих функций:

Область определения:  < x + область значений: 1 y +1;

Эти функции периодические: их период 2 ;

Функции ограниченные (| y | , всюду непрерывные, не монотонные, но

имеющие так называемые интервалы монотонности , внутри которых они

ведут себя, как монотонные функции (см. графики рис.19 и рис.20);

Функции имеют бесчисленное множество нулей (подробнее см. раздел

«Тригонометрические уравнения»).

Графики функций y = tan x и y = cot x показаны соответственно на рис.21 и рис.22

Из графиков видно, что эти функции: периодические (их период ,

неограниченные, в целом не монотонные, но имеют интервалы монотонности

(какие?), разрывные (какие точки разрыва имеют эти функции?). Область

определения и область значений этих функций:

Функции y = Arcsin x (рис.23) и y = Arccos x (рис.24)многозначные, неограниченные; их область определения и область значений соответственно: 1 x +1 и  < y + . Поскольку эти функции многозначные, не

рассматриваемые в элементарной математике, в качестве обратных тригонометрических функций рассматриваются их главные значения: y = arcsin x и y = arccos x ; их графики выделены на рис.23 и рис.24 жирными линиями.

Функции y = arcsin x и y = arccos x обладают следующими характеристиками и свойствами:

У обеих функций одна и та же область определения: 1 x +1 ;

их области значений:  /2 y /2 для y = arcsin x и 0 y для y = arccos x ;

(y = arcsin x – возрастающая функция; y = arccos x – убывающая);

Каждая функция имеет по одному нулю (x = 0 у функции y = arcsin x и

x = 1 у функции y = arccos x ).

Функции y = Arctan x (рис.25) и y = Arccot x (рис.26)- многозначные, неограниченные функции; их область определения:  x + . Их главные значения y = arctan x и y = arccot x рассматриваются в качестве обратных тригонометрических функций; их графики выделены на рис.25 и рис.26 жирными ветвями.

Функции y = arctan x и y = arccot x имеют следующие характеристики и свойства:

У обеих функций одна и та же область определения:  x + ;

их области значений:  /2< y < /2 для y = arctan x и 0 < y < для y = arccos x ;

Функции ограниченные, непериодические, непрерывные и монотонные

(y = arctan x – возрастающая функция; y = arccot x – убывающая);

Только функция y = arctan x имеет единственный ноль (x = 0);

функция y = arccot x нулей не имеет.

Композиция функций

Если даны два отображения и , где , то имеет смысл "сквозное отображение" из в , заданное формулой , , которое называется композицией функций и и обозначается .

Рис.1.30.Сквозное отображение из в