elem_mat_copy

Однако из предикатов можно получать высказывания и другим путем. Для этого вводятся так называемые операции «навешивания кванторов».

Пусть одноместный предикат Р(х) задан на множестве М, тогда под сим-

M		волами (	х			М) Р(х) и (	х М)		Р(х)
	P(x)
		понимаем		высказывание: «Для любого
		х M Р(Х)» и «существует х						М такое,
		что Р(х)».
Слова «для любого х» кратко обозначают символом									х и

называют квантором общности по переменной х. Слова «существует такой х, что ... » обозначают символом х и называют квантором существования.

Высказывание х		М Р (х) считается истинным, если
все элементы множества	М обладают свойством Р и будет лож-

ным, если найдется хотя бы один элемент, который этим свойством не обладает.

Например, [( х R)( |х|>0)]=0, так как для х=0, |х|=0. Ины-

ми словами, квантор общности обобщает логическую операцию «конъюнкция» на бесконечном множестве.

Например, если М = {4, 8, 10}, Р (х) ― «х делится на 2»,

то ( х М)Р(х) Р(4)&Р(8)&Р(10).

Высказывание ( х М)Р(х) считается истинным, если хотя бы один элемент множества М обладает свойством Р и будет ложным, если ни один элемент множества М этим свойством не обладает.

Квантор существования обобщает логическую операцию

«дизъюнкция» на бесконечном множестве.

Если М={а1, а2, ..., аn,...}, то

( х М)Р(х) Р(а1) Р(а2)

... P(an) ...

подчеркнуть,

что

истинность

( х М)Р(х) и

Важно

( х

М)Р(х)

2

2

часто зависит от области определения предиката М.

Например, [(

х

Q)(x = 2)]=0, a [(

х

R) (x

= 2) ]=1.

Пусть

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

пример, от трех переменных: F(х,

у,

z)

(х+y=z). Тогда

( х

)(

y R)(

х М)(х+у=z) будет

истинным высказыванием

21

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

				( х R)( y R) (х+у=z)?
				не зависит от переменных х и у, а зависит
		Это предложение
только от z, то есть является одноместным предикатом F(z).
		Если на n-местный предикат F(х1, х2, ...., хn) навесить
квантор х				или х, то местность предиката уменьшится на 1.
Например:				( x R)(x+y-z=0)			― двухместный предикат;
( x		Для		R)(х+у-z=0) ― одноместный предикат.
		R)( y
		того, чтобы, из n-местного предиката получить выска-

зывание, необходимо на все переменные навесить кванторы, или иначе говорят «связать их кванторами».

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

1.Что называется высказывательной формой (предикатом)?

2.Какие высказывательные формы называют равносильными?

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

4.В чем состоит различие между «свободными» и «связанными» переменными?

5.Одноименные кванторы можно навешивать в любом порядке. Разноименные кванторы переставлять местами нельзя. Почему? Как это объяснить?

Упражнения

1.Установить истинность следующих высказываний: a) ( x Z)(x2 x 2) ;

б) ( x Z)( y Z)(x y 0);

в) ( n N)(n 1);

г) ( x R)(x 0);

д) ( )(( ≥ 3) → ( > 6));

22

же))			(	> 0 &(sin	> 0))	.
	(		)(	)	;
	(		)((	−4 +3 = 0)&(		< 0))

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

a)( x R)(3x2 2x 6 0);

б) ( x R)(x2 4x 3 0 x 3); в) ( x R)( y R)(x y 0).

3.Записать символически следующие высказывания и определения:

а) квадрат любого числа есть число неотрицательное; б) если число больше 7, то квадрат его больше 49;

в) существует такое число х, что для любого числа а выполняется а+х=а; г) определение предела функции в точке;

е) определение непрерывности функции в точке; ж) определение четной функции.

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

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

Законы логики

Известно, что новые знания приобретаются человеком либо опытным путем, либо путем рассуждений. Все рассуждения подчиняются определенным правилам, называемым «законами логики» (тождественно-истинными формулами). Запишем некоторые из них в виде равносильностей формул исчисления высказываний:

1.А А (закон тождества);

2.(А & А) 0 (закон противоречия);

3.А А 1 (закон исключенного третьего);

4.А → В В → А (закон контрапозиции);

5.А & В A В (1-ый закон де Моргана);

23

6.А В А & В (2-ый закон де Моргана);

7.→ & (закон отрицания импликации);

8.(А → В) & (В → С) → (А → С) 1 (закон силлогизма);

9.А & (А→В)→ В 1 (закон заключения).

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

рицание А .

Полезно знать ряд законов, связанных с логикой предика-

тов:

11.

(

)Р(

) (

x

М)

Р(х);

10.

( х

М)

;

12.

(

)Р( )

(Р(хх)

М) A(x) &

);

(

(х)

13.

((

х

M) ()

y(

) →

)

Закон

M) А(х, у)

( y

M) ( x

M) А(х, у).

10 отражает тот факт, что высказывания: «не всякий x обладает свойством Р» и «существует x, не обладающий свойством Р» ― имеют одинаковый смысл.

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

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

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

Например:

1.«Все натуральные числа ― целые; все целые числа ― рациональные. Следовательно, все натуральные числа ― рациональные».

2.«Все квадраты ― ромбы; все ромбы ― параллелограммы. Следовательно, все квадраты параллелограммы».

24

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

Все А есть В, все В есть С: Все А есть С (основанной на законе силлогизма).

Если в эту форму вместо А, В, С подставить другие суждения, то все они будут иметь одинаковую форму. При этом, если посылки будут истинными, то и заключение будет истинно «по форме».

Отыскание и описание подобных правильных схем рассуждений составляет предмет формальной логики ― науки, создателем которой считают греческого философа Аристотеля (384–332 г. до н.э.).

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

1.Правило заключения (Modus Ponens ― M.P.) (основано на законе заключения):

A B; A

B

Почему эта схема надежна? Если предположить, что посылки истинны, то есть [А→В] =1, [А] =1, то из определения импликации следует, что [В] = 1. Это означает, что о чем бы мы ни рассуждали по этой схеме, если мы исходим из истинныхпосылок, тоникогда непридем к ложномузаключению.

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

( x)P(x) Q(x);P(a)

Q(a)

Это правило действует всюду, где приходится применять общие положения в частных случаях.

Например: «Если функция f(x) ― нечетная, то ее график симметричен относительно начала координат. Функция f(x) = х3 ― нечетная, следовательно, ее график симметричен относительно начала координат».

25

Авот схема рассуждения

→;

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

A B; A C

2.

A B &C ;

A& B C

3.

A (B C)

;

A B

4.

B

A

― правило контрапозиции;

A&

C &

B

C

5.

B

― схема доказательства методом от

«противного».

На практике она имеет различные вариации:

а) если

&

, то говорят: «...что противоречит условию»;

б) если

&

, то говорят: «...что противоречит предполо-

жению»;

&

в) если

, то говорят: «... что противоречит ранее до-

&

казанной теореме (или аксиоме)».

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

26

P(1)&( k )(P(k) P(k 1))

nP(n)

иназывается принципом математической индукции.

Вэтой схеме Р(n) ― любой одноместный предикат, заданный на множестве N натуральных чисел и удовлетворяющий условиям:

а) Р(1) ― истинно;

б) ( k N) из истинности P(k) следует истинность Р(k + 1). Тогда Р(n) истинно ( n N).

Условие а) называют базисом индукции. Посылку Р(k) ― индуктивным предположением; утверждение б) ― индуктивным шагом.

Выделим основные шаги доказательства некоторого утверждения Р(n) методом математической индукции.

1.Формулировка утверждения Р(n), n N;

2.Формулировка и проверка истинности базиса индукции (Р(1) ― истинно);

3.Формулировка индуктивного предположения Р(k);

4. Формулировка и доказательство индуктивного шага

Р(k) → Р(k+ 1);

5.Вывод: ( n N) Р(n) ― истинно.

Пр и м е р: доказать тождество:

12 +32 +52 +...+(2n -l)2 = n(2n 1)(2n 1) 3 .

Д о к а з а т е л ь с т в о:

Обозначим через Sn = 12 + 32 + ... + (2n ― 1)2.

Тогда утверждение

Sn n(2n 1)(2n 1) 3

обозначим через Р(n).

Формулировка и проверка базиса индукции:

27

б)	(1)	«	=	∙ ∙	= 1 (1 = 1)			», т.е. [P(1)]=1;
а)
	Индуктивное предположение:
		[P(k)]=1 « =				(	)(	)	».

Формулировка и доказательство индуктивного шага:

а) из истинности Р(k) следует истинность Р(k+1), т.е. нужно доказать, что из того, что

Sk

=

k(2k 1)(2k 1)

3

будет следовать, что

Sk 1

=

(k 1)(2(k 1) 1)(2(k 1) 1)

(k 1)(2k 1)(2k 3)

.

3

3

б) Действительно,

S

=

k(2k 1)(2k 1)

(2k 1)2

(2k 1)[k(2k 1) 3(2k 1)]

k 1

3

3

(2k 1)(2k2 k 6k 3) (2k 1)(2k 5k 3) (2k 1)(k 1)(2k 3)

3

3

3

,

т.е. Р(k+1) ― истинно.

Вывод: согласно принципа математической индукции,n N Р(n) ― истинно.

Упражнения

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

а) & → ;

б) → ↔ & ;

28

гв)) →	↔		→
				.;
&(	→	) →

2.Переформулируйте следующие предложения с помощью законов логики:

а) неверно, что число 9 ― четное или простое; б) неверно, что 7 делится на 3 и на 4;

в) неверно, что 2 ― нечетное число и 3 делится на 4; г) не всякое уравнение имеет действительный корень; д) не всякое простое число нечетно;

е) не существует числа x, такого, что x+1=x.

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

а) любое натуральное число четно; б) среди положительных действительных чисел не суще-

ствует наименьшего.

4.Доказать методом математической индукции:

1 2 2 3 ... n(n 1) n(n 1)(n 2)

а) 3 ;

		1						1		...					1						n
б) 1 3							3 5					(2n 1)(2n 1)								2n 1;
в)																				( )			;
		∙ ∙	2+ ∙					∙	2+ + (				)(		)(	)2
														2				= n((n 1)()( n 2))
	2 1				3 2					... n(n 1)					(n 1)n
г)																					1 3 4		;

д)	|sin2			|2	≤ ...sin		2
							;			n 1
		1		1		1
е) 2										n
				3		n
зж)) (			+(		+1). +(				+2) ) 9;
	(		+11		) 6				29

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

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

Теорема ― высказывание, истинность которого устанавливается при помощи рассуждения (доказательства), проводимого на основе законов логики.

Математические теоремы чаще всего носят общий характер, то есть доказывается, что все элементы некоторого множества обладают общим свойством или свойствами. Например. «Во всяком параллелограмме диагонали в точке пересечения делятся пополам». Логическая структура этой теоремы имеет вид: x M P(x).

Это наиболее общая форма записи теорем. Однако часто предикат Р(х) имеет вид импликации А(х) → В(х), поэтому обычно теорема записывается в виде: ( x M )(A(x) → B(x)), который называют стандартным видом.

( x M) называют разъяснительной частью этой теоремы, А(х) ― условием теоремы, В(х) ― заключением теоремы.

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

Формулировка заключения теоремы начинается после частицы «то».

Например, «Пусть ABCD ― произвольный четырехугольник. Тогда, если ABCD ― ромб, то диагонали ABCD ― перпендикулярны».

Следует заметить, что разъяснительная часть теоремы часто отсутствует, когда понятно, элементы какого множества рассматриваются в теореме.

С любой данной теоремой стандартного вида можно соотнести еще четыре утверждения:

1.( x) ( А(х) → В(х)) ― прямая теорема;

30