elem_mat_copy

4.ВОПРОСЫ К ЗАЧЕТУ

1.Высказывания, операции над высказываниями.

2.Формулы, равносильность формул.

3.Предикаты и кванторы.

4.Логические законы. Правила вывода.

5.Теоремы стандартного вида, необходимые и достаточные условия.

6.Методы доказательств (по определению, от противного, метод математической индукции).

7.Множества. Операции над множествами, их свойства (объединение, пересечение, разность, симметрическая разность, декартово произведение множеств).

8.Основные формулы комбинаторики.

9.Бинарные соответствия и их типы.

10.Бинарные отношения, их типы.

11.Операции на множествах.

12.Бинарные операции и их свойства.

5.ПРАКТИКУМ ПО ЭЛЕМЕНТАРНОЙ МАТЕМАТИКЕ

Практическое занятие №1

О предмете и языке математики. Высказывания, операции над ними. Формулы

§1. Элементыматематической логики

Основные умения и навыки, которыми должны овладеть студенты в процессе изучения этой темы:

уметь отличать высказывание от не высказывания;

уметь выявлять логическую структуру сложного предложения;

уметь определять истинность сложного предложения в зависимости от истинности составляющих элементарных высказываний;

11

уметь выяснять, равносильны ли данные формулы исчисления высказываний;

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

уметь переводить предложения естественного языка на символический и обратно;

знать и уметь доказывать наиболее употребительные законы логики;

уметь применять наиболее важные законы логики для переформулировки предложений;

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

владеть наиболее распространенными схемами доказательств утверждений (методом от противного, приведение контрпримера и т.д.);

уметь устанавливать правильность или неправильность предложенного рассуждения, выявляя его логическую схему;

уметь записать предложенную теорему в стандартном виде;

уметь сформулировать для данного предложения ему обратное, противоположное, контрапозиционное;

уметь исходить логические следствия из данных посылок,

необходимые и достаточные условия.

Основные понятия темы: высказывание, предикат.

Высказывания

Под высказыванием понимают повествовательное предложение, о котором имеет смысл говорить, истинно оно или ложно.

Как видим, этому понятию не дается строго математического определения, а дается лишь способ отличать высказывания от «невысказываний». Таким образом, единственное свойство высказывания ― быть истинным или ложным.

Обычно высказывания обозначают большими латинскими буквами: А, В, С и т.д. Если высказывание А ― истинно, то это

12

символически обозначают так: [А] = 1 или [А] = и, если А ― ложно, то [А] = 0 или [А] = л.

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

1.х<5;

2.Если (х<у) и (у<z),то (х<z),где х, у, z R ;

3.Для любого х R найдется y R, такой, что х+у=0;

4.Даздравствует 1Мая!

5.Который час?

6.Треугольник называется равносторонним, если все его стороны равны между собой;

7.В равностороннем треугольнике любая его медиана является биссектрисой и высотой.

Вэтом списке предложения 2, 3, 7 ― истинные высказывания. Предложение 1 станет высказыванием (истинным или ложным), если вместо x подставить конкретное действительное число. Например, [2<5] = 1, [7<5] = 0. Все вопросительные, восклицательные предложения и определения не являются высказываниями. Поэтому предложения 4, 5, 6 ― не высказывания.

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

то, не и т.д.)

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

Так как каждое элементарное высказывание А может иметь только два истинностных значения (1 или 0), то для каждой пары высказываний А, В будет 4 комбинации истинностных значений. Указав для каждой такой комбинации соответствующее истинностное значение их конъюнкции, дизъюнкции, импликации, эквиваленции, отрицания, мы получим таблицу, определяющую эти логические операции:

13

[A]	[B]	[A&B]	[A B]	[A→B]	[A↔B]	[		]
1	1	1	1	1	1	0
1	0	0	1	0	0	0
0	1	0	1	1	0	1
0	0	0	0	1	1	1

Конъюнкция (логическое произведение) обозначается А&В и читается: «А и В», дизъюнкция (логическая сумма), обозначается A B, читается: «А или В»; импликация ― А→В, читается «если А, то В», «из А следует В», «А влечет В»; эквиваленция ― А↔В, читается: «А эквивалентно В», «А тогда и только тогда, когда В»; отрицание ― , читается: «не А».

Отметим, что в русском языке один и тот же союз может употребляться в различных смыслах. Например, «или» ― в разделительном смысле и неразделительном, а в логике только в неразделительном. Использование логических операций строго в определенном смысле позволяет в математическом языке избавиться от неопределенности естественного языка, неоднозначности определений. Однако, как в естественном, так и в математическом языках, конъюнктивная, дизъюнктивная и т.п. связи могут быть выражены различными способами. Например:

1.« ...Чиновник ― человек небогатый, но приличный».

2.«Мал золотник, да дорог».

3.«Последовательность ограничена, а предела не имеет».

4.«Функция непрерывна, однако не дифференцируема».

5.«Из дифференцируемости функций в точке хо следует ее непрерывность в этой точке».

6.«Для того, чтобы функция была дифференцируема в точке хо, необходимо, чтобы она была непрерывна в точке хо» и

т.п.

Рассмотрим два сложных предложения:

1.Если 9 делится на 2 и 3, то 8 делится на 5.

2.Если человек работает в вузе и преподает математику, то он имеет высшее образование.

14

Логическая структура этих сложных предложений одинакова. Если обозначить простые предложения буквами, а логические операции соответствующими символами, то каждое предложение можно заменить формулой (А&В)→C. Эта формула выражает

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

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

Например, для формулы (А&В)→C таблица истинности имеет вид:

[A]	[B]	[С]	[A&B]	[А&В→C]
1	1	1	1	1
1	1	0	1	0
1	0	0	0	1
0	0	0	0	1
0	1	1	0	1
0	0	1	0	1
0	1	0	0	1
1	0	1	0	1

Как видим, формула имеет ложное значение только при одном наборе значений истинности высказывательных переменных, а при всех остальных наборах ― истинное значение.

Упражнения

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

а) Функция у = x3 монотонно возрастает на множестве R действительных чисел; б) Функция у = х2 ― нечетная функция;

в) х2 + у 2 >0 для любого х;

15

г) существует такое действительное число, что 2х + 5=19; д) любые три отрезка могут быть сторонами треугольника;

ж) х + у = у + х.

2.Выделить структуру следующих высказываний и определить их истинностные значения:

а) диагонали ромба взаимно перпендикулярны и делят углы пополам; б) если сумма цифр числа делится на 3, то и само число делится на 3;

в) натуральное число не может быть одновременно простым и составным; г) касательная, проведенная к окружности, перпендикулярна к

радиусу, проведенномув точкукасания.

3.Построить таблицы истинности

для следующих формул

исчисления высказываний:

&

A;

б) A

;

а)

(A B)

B

(B &C)

в) (A B) &

B;

&

B

г)

;

д)

→

&

;

е)

↔

&

→

.

Практическое занятие №2

Равносильность формул. Виды формул

Среди формул логики высказываний есть такие, которые при всех наборах высказывательных переменных принимают значение 1 (истина). Такие формулы называются тавтологиями или

логическими законами. Это, например, формулы A А,

А&(А→В)→В, (А→В)↔(В→ ) и т.д. Они играют особую роль, ибо выражают логическую структуру таких высказываний, которые истинны в силу только этой своей структуры.

16

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

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

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

Отношение равносильности обозначается знаком . Из определения следует, что равносильные формулы имеют одинаковые таблицы истинности, поэтому проверка равносильности двух формул сводится к составлению их таблиц истинности и анализа этих таблиц.

Выясним для примера, будут ли равносильными следующие фор-

мулы:

1) A&(B C) и (A&B) (A&C) 2)(А→В)&С и А→(В&С)?

Для этого составимтаблицыистинностиэтихформулисравним

их:

[A	[B	[С	[A&(B C)]		[(А&В) (A&C)]	[(A→B)&C]	[А→(В&C)]
1	1	1	1		1	1	1
1	1	0	1		1	0	0
1	0	1	1		1	0	0
0	1	1	0		0	1	1
1	0	0	0		0	0	0
0	1	1	0		0	1	1
0	0	1	0		0	1	1
0	0	0	0		0	0	1

17

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

довательности: , &, , →, ↔, если скобки в данной формуле не расставлены.

Упражнения

1.Доказать равносильность формул:

а) A (B C) и A& B C;

б) A (B &C) и (A B) & (A C);

в) (A B) C и (A& B) B;

дг))

→

( → ) и

( → );

→

( &

и

е)

(

)и

( &

;)

→ ) →

→

2.Доказать, что нижеприведенные формулы являются тавтологиями:

а) → ;

б) ( & ) → ;

в) → ( ).

Практическое занятие №3

Предикаты и кванторы

Предикаты

Даже самые элементарные разделы математики (например, уравнения и неравенства) не могут быть полностью описаны лишь средствами исчисления высказываний. Это связано с тем, что в этой теории высказывание ― нерасчленяемый объект, не обладающий никакими свойствами, кроме как быть истинным или

18

ложным. Дальнейшим развитием теории высказываний является теория предикатов. Логика предикатов начинается с анализа структуры элементарных высказываний. Высказывание расчленяется на терм и предикат. Терм ― это объект, о котором говорится в высказывании, а предикат ― это свойство, которым этот объект обладает или отношение, в котором он находится с другими объектами. Например: «2 ― четное число», «2» ― терм, «быть четным числом» ― предикат, или «3<5», «3», «5» ― термы, «меньше» ― предикат. Эти свойства и отношения определяют функцию, аргументы которой принимают значения из некоторого множества М, а областью значений является множество {0, 1}. В данном случае «х<у», «х ― четное число». Если вместо х и у подставлять любые числа из множества R, то будем получать либо истинные, либо ложные высказывания.

О п р е д е л е н и е: Функция F (х1, х2, ..., хn), определенная на множестве М и принимающая значения из множества {0, 1}, называется n-местным предикатом (n-местной высказывательной формой).

Таким образом, например, F(х) ― это одноместный предикат или одноместная высказывателъная форма, которая становится высказыванием, если вместо переменной х подставить

любое значение из некоторого множества М. Так, например,

если F(x) = х2 + х ― 2 = 0 и М = R, то для х=2 F(2) =22 + 2–

– 2 = 4 ≠ 0, [F(2)] = 0, т.е. получили ложное высказывание; если х = 1, то F(1) = 12+1-2 = 0, [F(l)] = 1, то есть получили истинное высказывание.

Любое высказывание является нуль-местным предикатом и обозначается F0.

Итак, в логике предикатов рассматривают символы трех видов, связанные с множеством М и множеством {0, 1}:

а) предметные постоянные а, b, с, ..., d M;

б) предметные переменные х, у, z, ..., принимающие значения из множества М;

в) переменные высказывания А, В, С, …, принимающие значения из множества {0,1}.

19

						Если на множестве М
						задан n-местный предикат
		A		B
						F (х1, х2, ...., хn), то множе-
						ство М разбивается на два
M			F (х1, х2, ...., хn)
						множества: М=А В, на од-
						ном из множеств предикат
						принимает истинное значе-
						ние, на другом ― ложное.

Первое множество А называется множеством истинности предиката.

Например, множеством истинности любого уравнения или неравенства (например, F(х, у)=х2+у2-5=0) является множество его решений.

На множестве предикатов (высказывательных форм) можно определить отношение равносильности.

О п р е д е л е н и е: Два предиката F(х1, х2, ...., хn) и P(х1, х2, ...., хn) от одних и тех же переменных называются равносильными, если они имеют одно и то же множество истинно-

сти. Обозначение: F (х1, х2, ...., хn) P (х1, х2, ...., хn). Например, (х + 5 = 7) (х = 2), (х2 + 1 ≥ 0) (х R).

Отношение равносильности на множестве предикатов является отношением эквивалентности, так как оно определяется через отношение равенства множеств их истинности, а отношение равенства есть отношение эквивалентности на любом множестве.

С помощью логических операций (&, , ...) из данных высказывательных форм можно строить более сложные высказывательные формы.

Например, Р( х, у) & Q (х: у) → В (х, у) С (х).

Из определения предиката (высказывательной формы), ясно, как получить высказывание ― для этого нужно вместо переменных подставить некоторые значения из множества М. Например, подставив вместо х, у, z действительные числа 3, 4, 5 в предикат х2+y2=z2, получим «9+16=25» ― истинное высказывание. Если подставить числа 1, 0, 2, то получим «1=4» ― ложное высказывание.

20