elem_mat_copy

2.( x) (В(х) → А(х)) ― обратная теорема;

3.( x) (А(х) → В(х)) ― противоположная теорема;

4.( x) (В(х) → А(х)) ― обратная к противоположной теорема.

Заметим, что 1 и 4, 2 и 3 теоремы образуют в паре закон контрапозиции, поэтому логически эквивалентны. На практике, как правило, обычно доказывают прямую и (или) обратную теорему.

Если истинна теорема ( x) ( А(х) → В(х)), то В(х) является логическим следствием посылки А(х). В этом случае говорят, что В(х) следует из А(х) и понимают это так, что всегда, когда истинно А(х) будет истинным и В(х) (множество истинности предиката А(х) содержится во множестве истинности предиката В(х) и записывается так: А(х) В(х).

Таким образом, доказать теорему стандартного вида ― это означает установить отношение следования между условием и заключением. Если верна теорема ( x) ( А(х) → В(х)), то А(х) называют достаточным условием для В(х), а В(х) ― необходимым условием для А(х).

Если наряду с прямой теоремой будет верна и обратная теорема ( x) (В(х) → А(х)), то В(х) становится необходимым и достаточным условием для А(х). Если в формулировке теоремы есть словосочетание «тогда и только тогда», «необходимо и достаточно», то это «сигнал» того, что придется доказывать прямую и обратную теорему.

Например, теорема: «Параллелограмм является ромбом тогда и только тогда, когда его диагонали перпендикулярны» имеет структуру (А(х) ↔ В(х)).

1.Необходимость В(х) (доказательство прямой теоремы): «Если параллелограмм ― ромб, то его диагонали перпендикулярны».

2.Достаточность В(х) (доказательство обратной теоремы): «Если диагонали параллелограмма перпендикулярны, то он является ромбом».

31

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

Вопросы для самоконтроля

1.В чем суть метода доказательства от противного?

2.Что называют необходимым условием, достаточным, необходимым и достаточным?

Упражнения

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

а) если натуральное число оканчивается двумя нулями, то оно кратно4;

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

в) в параллелограмме противоположные углы равны.

2.Проверьте правильность следующих рассуждений:

а) Все люди красивы, а все красивые существа смертны;

следовательно, все люди смертны; б) Всякая последовательность, имеющая предел, ограни-

чена, а последовательность +(−1) не имеет предела: следовательно, она не ограничена.

3.Определите истинностное значение следующих высказываний:

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

ходимои достаточно, чтобы он имел два острых угла; в) для того, чтобы число делилось на 5, необходимо и доста-

точно, чтобы оно оканчивалось нулем; г) для того, чтобы сумма двух целых чисел делилась на 3,

необходимо и достаточно, чтобы каждое слагаемое делилось на 3.

32

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

Самостоятельная работа по теме «Элементы математической логики»

1.Определите истинностное значение высказываний: а) 7 ― простое число и 9 ― простое число; б) число 2 ― четное или это число простое;

в) число 144 делится на 2 и на 3, но не делится на 5;

г) если число 18 делится на 2 и не делится на 3, то 18 не де-

лится на 6.

> 3) → (

> 7)).;

2.

ед)) ( )((

( )((|

| ≤ 1)&(

> 1))

Докажите равносильность формул:

ба))

( →

) →

и

→

;

.

и

3.

(С → ) →

(

→ )&

Запишите без знака отрицания:

да))

<

;

б)

≤

;

;

в)

≥

;

г)

>

;

е)

( )( )( > ) .

;

4.а)

( )( )( = )

Доказать, что

:

+1) = ( +1)

б)

1∙4+2∙7+ + (3

, где

.

неравенство Бернулли:

(1+ )

≥ 1+

> −1

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

Множества, способы задания множеств. Теоретико-множественные операции. Теоретико-множественные тождества

§2. Множества и элементы комбинаторики

Основные знания, умения и навыки, которыми должны овла-

деть студенты в процессе изучения этой темы:

понимать смысл неопределяемого понятия «множество».

33

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

уметь доказывать теоретико-множественные тождества;

знать и понимать смысл основных комбинаторных конструкций (перестановки, размещения, сочетания);

уметь решать задачи комбинаторики.

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

Множества

Понятия «множество», «соответствие», «отношение» относятся к числу неопределяемых математических понятий. Поэтому для понятия множества дается описательное определение, содержание и смысл которого раскрываются при изучении теории множеств. Множество ― это набор, совокупность каких-либо объектов, называемых его элементами, обладающих некоторым общим для них характеристическим свойством. В качестве примеров можно привести множество действительных чисел, множество решений заданного алгебраического уравнения, множество прямых, проходящих через заданную точку. В принципе никаких ограничений на природу элементов, их количество и свойства не налагается, так что допустимо рассмотрение таких множеств, как множество налогоплательщиков, множество процентных ставок и т.п.

Понятие «множество» вводится для обозначения совокупности объектов (предметов), объединенных в одно целое либо путем перечисления, либо путем задания характеристического свойства Р(х) (одноместного предиката). Записывается множество так: X = {х │ Р (х)} и читается ― «множество тех х, для которых имеет место свойство Р».

Элементы, составляющие множество, обычно обозначаются малыми латинскими буквами, а само множество ― большой латинской буквой. Знак используется для обозначения принадлежности элемента множеству. Запись x A означает, что элемент x принадлежит множеству A. Если некоторый объект x не являет-

34

ся элементом множества A, пишут x A. Например, если A ― это множество четных чисел, то 2 A, а 1 A.

П р и м е р 1: Запись Х = { х | х2 + 5х + 6=0} означает, что X состоит из корней квадратного уравнения х2 + 5х + 6 = 0, решив его, множество X можно задать перечислением: X={-2, -3}.

О п р е д е л е н и е 1: Множество В называют подмножеством множества А, если ( ) → ( ).

B A

В этом случае пишут:		и читают «В ― подмножест-
во А», или «В включено в А»	или «В содержится в А».

С количественной точки зрения, множества бывают конечные и бесконечные. Конечное множество содержит определенное количество элементов, которое можно сосчитать. Если же любое число, каково бы велико оно ни было, оказывается недостаточным, чтобы сосчитать элементы множества, то оно называется бесконечным. Конечное множество может содержать один элемент и даже ни одного элемента. Множество, не содержащее ни одного элемента, называют пустым и обозначают Ø. Принято

считать, чтоØ		А, где А― любое множество, а также, что					.
Количество элементов множества А обозначают					|.	Если
множество А конечно и содержит n элементов, то пишут|:						| =.	.
Тот факт, чтомножество Абесконечно, записывают так:					|
Множество, которое содержит в себе все			мыслимые мно-
				|	| = ∞

жества, называют универсальным и обозначают буквой U.

За м е ч а н и е: следует четко различать обозначения

и ,а также понятия: элемент множества и подмножество, состоящее из одного элемента.

Например: если А = {a , b, с}, то записи а А и {а} А ― правильны, а записи а А и {a} А ― неправильны.

Оп р е д е л е н и е 2: (А = В) (А В)&(B A).

35

Для придания наглядности различным рассуждениям, связанным с множествами, используют диаграммы Эйлера-Венна.

Данный рисунок иллюстрирует тот очевидный факт, что если (А В)& (В С) → (А С).

A B С

Дадим определения основным теоретико-множественным операциям:

Пересечением множеств A и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат обоим этим множествам. Пишут: A∩B. Множество A∩B может быть задано с помощью характеристического свойства: A∩B {х│х А & х В}. Изобразим A∩B с помощью диаграммы Эйлера-Венна:

A B

Объединением множеств A и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из этих множеств. Записывают: A B. Зададим множество A B с помощью характеристического свойства: A B {х│х А х В}. Изобразим A B с помощью диаграммы Эйлера-Венна:

A B

36

Разностью множеств A и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат A и не принадлежат B. Записывают: A\B. С помощью характеристического свойства: A\B {х│х А & х В}. Изобразим диаграмму Эйлера-Венна для множества A\B:

A

B

Дополнением множества A называют разность универсально-

го множества U и множества A. Обозначение:

U или CA. С по-

мощью характеристического

свойства:

U

{х│х А}. Про-

Эйлера-Венна:

иллюстрируем множество U на диаграмме

U

A

Симметрической разностью (обозначение: A∆B) мно-

жеств A и B называется объединение множеств A\B и B\A, т.е. A∆B (A\B) (B\A). На диаграмме Эйлера-Венна:

A B

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

37

ских операций (например, вместо конъюнкции двух одноместных предикатов (свойств) можно рассматривать соответствующую операцию пересечения множеств их истинности).

Из определения теоретико-множественных операций следу-

ет, что:	(		),, то(				)(		)	;
Если
Если	(			то			)&(		;
Если				,)то	(				)
Если		(	U\, то)		(	.	)(		)( )
				(		)

Принято теоретико-множественные операции выполнять в следующем порядке:

	,		,	, \, ∆.
З а д а ч а: Доказать	тождество:
			∩					.
			о
				всех теоретико-множественных
Д о к а з а т е л ь с т в ∩ =

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

∩

&(

∩

).

Покажем, что

.

По определению

подмножества, это включение будет вы-

∩

полняться, если

(

∩

)

Пусть

.

∩

( ∩

)

(

.

) ( ) (

) ( )

∩

Теперь покажем, что

∩ .

Для этого возьмем произвольный элемент y из множества

.( ) ( )

:

( ∩ ) ∩ ∩

. Это

∩

&

∩

∩

=

Из того, что

=				доказательство может быть проиллюстрировано на
диаграммах Эйлера-Венна:
			38

U

A B

∩

U

A B

Упражнения

1. Доказать:

а) А \ (В С) = (А \ В) \С; б) А\ (В \С) = (А \ В) (А С);

в) (А В) \ С = (А \ С) (В \ С); г) (А В) (А \В) = А;

е) А \ B =А\(В А);

ж) А (В \С) = (А В) \С; и) (А\В) \С =(А\С) \(В \С); к) (А\В) = А (В А);

л) (А В С)=А (В С). 2. Решить систему:

A X B

A X C , гдеB A C .

39

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

Элементы комбинаторики. Перестановки, размещения, сочетания

Пусть даны два произвольных множества A и B.

О п р е д е л е н и е 1. Декартовым (прямым) произведени-

ем множеств А и В называют множество, состоящее из всех упорядоченных пар вида , , где и .

Символически это множество записывают так:

× { , | , }

Пр и м е р 1: Если А={1, 2, 3}, а В={0, 4}, то

×= { 1,0 , 1,4 , 2,0 , 2,4 , 3,0 , 3,4 };

×= { 0,1 , 0,2 , 0,3 , 4,1 , 4,2 , 4,3 }.

ВидимП,	что в общем случае			×	≠ ×	.
	р и м е р 2:	= {				.
			|0 ≤		≤ 2},	= { |0 ≤ ≤ 3}

y

3

2

×

1

0

1

2

x

П р и м е р 3: R R = R2 ― плоскость (двумерное пространство); R R R = R3 ― трехмерное пространство.

З а м е ч а н и е: Если			, а		, то			.
Прямое произведение|		можно определить и для нескольких
		| =		| | =		|	× | = ∙
множеств	:			|
	д е л е н и е 2.							.
О п р е× × …× {		, ,…,				,
×	× …×						= 1,2,…, }

40