Васильева М.Е. КЛ_М_Ч1

40

Графически введенные операции можно изобразить следующим образом. Все, что заштриховано, есть множество X Y.

То, что заштриховано дважды, есть множество X Y.

Х	Y	Х	Y
	Рисунок 5.2		Рисунок 5.3

Заштриховано множество Х / Y. Незаштрихованная часть прямоугольника, есть Х .

Х	Y	Х
	Рисунок 5.4	Рисунок 5.5

Приведенные выше графические изображения операций над множе-

ствами принято называть диаграммами ЭйлераВенна.

Пример 5.1 Рассмотрим множества А = {-2, -1, 0, 1, 3, 4, 5} и

B = { -1, 0, 1, 2, 4, 7}. Найти А B ,

A B и A/ B.

Решение. A B { -2, -1, 0, 1, 2, 3, 4, 5, 7}

A B={ -1, 0, 1, 4}

A/ B={-2, 3, 5}.

Свойства операций над множествами

1.

X Y Y X

2. X Y Z X Y Z

3. X X

X U U

5. X

U

6. X Y Y X

4.

X

7.

X Y Z X Y Z

8. X

9. X X

X U X

12.

X

10.

11.

X

U

U

X Y

13.

14.

X

Y

15. X Y Х Y

16.

X \ X

17.

X \ X

X Y

18. \ X

19.

X Y Z X Z

Y Z

20.

Z X Z Y Z

Понять свойства операций или даже установить новые можно, пользу-

ясь диаграммами Венна.
Например, для свойства 7 получаем:
X Y Z заштрихованы дважды		X (Y Z) заштрихованы дважды
Х	Y	Х	Y
	Z		Z

Рисунок 5.6

Рисунок 5.7

41

Очевидно, множества, заштрихованные дважды, на рисунке 5.6 и рисунке 5.7 одинаковы. Поэтому равенство 7 действительно имеет место.

Для свойства 14 имеем:

X Y заштриховано		X	Y		заштриховано дважды

Рисунок 5.8

Рисунок 5.9

Очевидно, множество, заштрихованное на рисунке 5.8, и множество, заштрихованное на рисунке 5.9 дважды, одинаковы. Следовательно, равенство 14 имеет место.

5.3 Язык логики высказываний

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

Рассмотрим примеры.

1)Ю.Гагарин – первый космонавт.

2)Париж – столица Англии.

3)Число 6 делится на 2 и на 3.

4)Карась не рыба.

5)Если юноша окончил среднюю школу, то он получает аттестат зрелости. Высказывания 1), 3), 5) истинны, а высказывания 2) и 4) ложны.

Очевидно, предложение "Как Вы себя чувствуете?" не является высказыванием.

Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. (Это высказывания 1) и 2)). Высказывания, которые получаются из элементарных с помощью грамматических связок "не", "и", "или", "если…, то…", "тогда и только тогда", принято называть сложными или составными.

Алфавит языка логики высказываний составляют следующие символы:

1.x, y, z, a, b,c … - переменные (элементарные высказывания).

2.¬, &, v, , ~ - логические константы (связки), имеющие свои соб-

ственные названия, а именно: ¬ - отрицание, & - конъюнкция, v – дизъюнкция, - импликация, ~ - эквиваленция.

3.Скобки – ( ).

"Высказывания" или "предложения" на этом языке называются формулами

иобразуются по следующим правилам:

1.Любая переменная является формулой (формулы обозначают А, В,

С, …)

42

2.Если А и В формулы, то формулами также будут выражения ¬А, А&В, АvВ, А В, А~В.

3.Ничто иное не является формулой.

Валгебре логики все высказывания рассматриваются только с точки зрения их логического значения. Считается, что каждое высказывание либо истинно (будем обозначать буквой "И" или цифрой "1"), либо ложно (будем обозначать "Л" или "0"). Если высказывание Х истинно, то будем писать Х=1, а если Х ложно, то Х=0.

5.4 Таблицы истинности для логических связок

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

Обозначение: ¬А, А читается "не А", "не верно, что А"

А		А
1		0
0		1

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

Обозначение: (А&В), (А^В), ( А В) читается А и В

А	В	А&В
1	1	1
1	0	0
0	1	0
0	0	0

Например А& А - всегда ложно.

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

Обозначение: (АvВ), ( А В) читается "А или В".

А	В	АvВ
1	1	1
1	0	1
0	1	1
0	0	0

Высказывание Аv А- всегда истинно.

Слабая дизъюнкция

43

А	В	АvВ
1	1	0
0	1	1
1	0	1
0	0	0

АvВ – истинно, когда только одно высказывание истинно.

Определение Импликацией двух высказываний А, В, называется высказывание, которое считается ложным, если А истинно, а В ложно. Обозначение: (А В), ( А В), (А В) читается "если А то В".

А - называется антецедентом, В - консеквентом. А В А В

1	1	1
1	0	0
0	1	1
0	0	1

Из ложного высказывания следует, что угодно, а так же истинное высказывание следует из чего угодно.

Определение Эквиваленцией (эквивалентностью) – двух высказываний А

иВ называется новое высказывание, которое считается истинным, когда оба высказывания либо одновременно истинны, либо одновременно ложно

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

Обозначение: (А~В), ( А В), (А В) читается "А тогда и только тогда, когда А", "Для того, чтобы А необходимо и достаточно, чтобы В".

А	В	А~В
1	1	1
1	0	0
0	1	0
0	0	1

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

В связи с этими формулы

(x&y)v z и x (yv(x & y))

могут быть записаны так:

x & y v z и x y v x &y

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

44

Например, логическим значением формулы x &y v z в случае, если х=1, у=0, z=0 будет истинна, то есть x &y v z =1 (т.к. х & у =0

x &y =1 1 v z =1).

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

щью таблицы истинности.

Например, для формулы х v y x& у таблица имеет вид:

х	у	х						у		х v y			х & у				х	v y х &	у
1	1	0				0				1			0			0
1	0	0				1				0			1			1
0	1	1				0				1			0			0
0	0	1				1				1			0			0

В место переменных х,у последовательно подставляем значения: (1,1), (1,0), (0,1), (0,0). Приведем вычисления для первой пары значений:

х v y х & у

1 v 1 1&1

0v 1 1&0

1 0

0

5.5 Равносильные формулы алгебры логики

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

Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.

Например, равносильны формулы:

xx ,

хv х x ,

(x& х) v y у.

Определение. Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тождественно истинны формулы x vx , x (y x) .

Определение. Формула А называется тождественно ложной, если она принимает значение 0 при всех входящих в нее переменных.

Например, тождественно ложна формула x &x .

Важнейшие равносильности алгебры логики можно разбить на три группы.

45

I. Основные равносильности:

1.x & x x

- законы идемпотентности

2.x v x x

3. x & 1 x

4. x v 1 1

5. x & 0 0

6. x v 0 x

7. x & х 0 – закон противоречия.

8. x v х 1 – закон исключенного третьего. 9. х x – закон снятия двойного отрицания.

10.х &(x v y) x

- законы поглощения.

11.х v (y & x) x

II.Равносильности, выражающие одни логические операции через другие:

1.x y x y & y x

2.x y x v y

3.x & y x v y

4.x v y x & y

5.x & y х v y

6.x v y x & y

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

III.Равносильности, выражающие основные законы алгебры логики:

1.x & y y & x - коммутативность конъюнкции

2.x v y y v x - коммутативность дизъюнкции

3.x & y &z x & y &z - ассоциативность конъюнкции

4.x v y v z x v y v z - ассоциативность дизъюнкции

5.x & y v x x & y v x & z - дистрибутивность конъюнк-

ции относительно дизъюнкции.

6. x v y & z x v y & x v z - дистрибутивность дизъюнк-

ции относительно конъюнкции.

Используя равносильности I, II, III групп можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

Формула А считается проще равносильной В, если она содержит меньше букв, меньше логических операций.

Рассмотрим ряд примеров.

46

Пример 5.2. Упростить формулу x v y x v y &y . Решение. Запишем цепочку равносильных формул:

x v y x v y &y x v y v x v y &y x v y v x v y & y x v y & y y

2.2 1.9 1.2 1.2

Подробнее:

2.2

1. x v y x v y x v y v x v y x y x v y

3.2 1.2

2. x v y v x v y x v x v y v y x v y

3.x v y & y y1.10

Пример5.3. Доказать равносильность x ~ y x & y v x & y.

Решение.

2.1

2.2

3.6

x ~ y

x y & y x

v y &

v x

x

y

3.6

1.7

1.6

&

v

& x v y &

v y & x

&

v0 v0 v y & x

x

y

x

y

x

y

x & y v y & x .

1.Доказать, что формула A x y x тождественно истинная.1.6

2.1

2.1

A x y x x

v x

v

v x

v

v x

y

x

y

x

y

3.4

1.8

1.4

x

v x v

y

1 v

y

1.

3.4

5.6 Контрольные вопросы и задания

1Что понимают под «множеством»?

2Какие операции можно выполнять над множествами?

3Что понимают под объединением, пересечением, разностью множеств?

4Что понимают под дополнением множества?

5Какое множество будет разностью множеств Z и N , объединением множеств Z и N , пересечением множеств Z и N , где N – множество натуральных чисел, Z - множество целых чисел

6Дайте определения конъюнкции, дизъюнкции, импликации и отрицания

7Составьте таблицу истинности для формулы x v y x & y v x y

8 Упростите формулу x & y x

x xo

47

Лекция № 6

ТЕМА: ФУНКЦИЯ. ПРЕДЕЛ ФУНКЦИИ. БЕСКОНЕЧНО БОЛЬШИЕ И БЕСКОНЕЧНО МАЛЫЕ ВЕЛИЧИНЫ. ТЕОРЕМЫ О ПРЕДЕЛАХ

6.1Понятие функции

6.2Понятие предела функции. Геометрическая интерпретация понятия предела функции

6.3Понятие бесконечно малой величины и её свойства

6.4Основная теорема теории пределов

6.5Свойства пределов

6.6Контрольные вопросы и задания

6.1 Понятие функции

Определение. Функция это закон (или правило), по которому каждому элементу x множества X ( x X ) ставится в соответствие единственный элемент y множества Y ( y Y ).

Обозначают функцию следующим образом y f (x) или f : X Y .

Переменная х называется при этом аргументом или независимой перемен-

ной, а у - функцией или зависимой переменной.

Множество X называют областью определения функции f и обозначается D (f).

Множество Y называют множеством значений функции f и обозначается Е (f).

При рассмотрении какого-нибудь частного значения функции y = f

(x), т.е. значения, которое она принимает при заданном численном значении х=хо пишут f (xo) или y

Определение. Пусть задана функция у=f(х) с областью определения D и множеством значений Е. Если каждому значению y Е соответствует единственное значение х D, то определена функция х= (у) с областью определения Е и множеством значений D. Такая функция (у) называется обратной к функции f(х) и записывается следующим образом: х= (у)=f 1 (у).

Замечание. Из определения следует: f( (y)) = y, (f(x)) = x.Чтобы найти функцию х= (у), обратную к функции у=f(х), достаточно решить уравнение f(х)= y относительно х (если это возможно).

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

Переменную х называют независимой переменной, u – промежуточной, y – зависимой переменной (функцией).

48

6.2Понятие предела функции. Геометрическая интерпретация понятия предела функции

Пусть дана функция y f (x) . Значение аргумента x a входит в об-

ласть определения функции вместе с некоторой окрестностью. Определение. Число b является пределом функции y f (x) при x a , ес-

ли по любому сколь угодно малому положительному найдется , такое, что |f(x) – b| < , как только |x – a| < . Тот факт, что число b является пределом функции y f (x) при x a обозначается следующим образом:

b lim f (x) .

x a

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

b lim f (x) 0	( ) , такое что		f (x) b		, как только		x a
x a

Геометрическая интерпретация понятия предела функции

Пусть на числовой оси задана точка b. -окрестностью точки b называется интервал (b , b ) (рисунок 6.1).

b

b

x

(

)

b

Рисунок 6.1

Аналогично, -окрестностью точки а на числовой прямой являет-

ся интервал (a , a ) .

Известно,

что неравенство

f (x) b

можно преобразовать следу-

ющим образом:

f (x) b b f (x) b .

Последнее неравенство означает,

что f (x)

принадлежит интервалу

(b , b ) или -окрестности точки b.

Из неравенства

x a

следует, что a x a , т.е. что x принад-

лежит -окрестности точки а.

Определение. Число b называется

y

пределом

функции y f (x) при

b (

y f (x)

x a , если по любому, сколь

угодно малому,

положительному

b )

найдется ,

зависящее

от ,

такое, что как только аргумент x

x

попадает

в -окрестность

точки

(

)

а, значение функции f (x)

попа-

a

а

a

дает в -окрестность точки b.

Рисунок 6.2

49

6.3 Понятие бесконечно малой величины и её свойства

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

Замечание. Сравнивая данное определение с определением предела функ-

ции, замечаем, что (x) - бесконечно малая величина тогда и только тогда,

когда lim (x) 0.

x a

Коротко:

lim (x) 0 ( ( 0) ( ) , что

(x)

, как только

x a

).

(6.1)

x a

при x a ,

Определение. Функция f (x)

называется ограниченной

если

найдутся такие числа c 0 и

0, что

f (x)

c, как только

x a

.

Замечание. Любая функция,

имеющая предел при x a ограничена, что

вытекает из определения предела функции.

6.4 Бесконечно большие величины и их связь с бесконечно малыми

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

Например, величина 1x - бесконечно большая величина при x 0.

Бесконечно большую величину обозначают (x) , а предел бесконечно большой величины - , причем если функция M(x) сохраняет свой

знак в окрестности точки x a, то limM (x) или limM (x) .
x a	x a
Теорема 6.1 Пусть M(x) - бесконечно большая величина при x a , тогда

1
функция (x) M (x)	будет бесконечно малой величиной при	x a .

Замечание. Другими словами, величина, обратная бесконечно большой, есть величина бесконечно малая.

Теорема 6.2 Если (x) - бесконечно малая величина при x a , не обращающаяся в нуль в некоторой окрестности точки а за исключением может быть

	самой точки x a, то M (x)	1	есть величина бесконечно большая при x a .
		(x)

Замечание. Другими словами, величина, обратная бесконечно малой, есть величина бесконечно большая.

Свойства бесконечно малых функций, с учетом их связи с бесконечно большими, можно свести в таблицу 6.1.