01_-_mnozhestva_otobrazhenia_logika

элементы множества всех людей, а y элемент множества всех натуральных чисел.

Подобным образом высказывательные формы образуют

предложения: “x дружит с y“ и “x имеет рост y и вес z“,	“x
живет в городе y“.

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

Для приведенных примеров высказывательных форм сокращенные записи имеют вид :

Учится(x, y), дружит(x, y), рост-вес(x, y, z), живет (x, y).

Рассмотрим пример высказывательной формы, которая может быть определена для высказывания:

“Занятия физкультурой дают силу студенту Иванову “.

Эта форма может быть записана в виде: Дает(x, y, z). Здесь x обозначение объекта, дающего что -то, т.е. выполняющего действие, y объект или предмет, который дают, а z объект,

получающий y от z.

Примерами применения этой формы являются:

Дает(логика, знания, студент I курса); Дает(сигарета, здоровье, человек).

Здесь первый из приведенных примеров принимает истинностное значение “ t“, а второй “f“.

Пусть P это символическое обозначение высказывательной формы (свойства), связывающей компоненты n-элементных наборов объектов, обозначаемых символами переменных x1 , ... , xn , которые могут принимать значения из множеств A1 , ... , An. Тогда предикату P можно поставить в соответствие функцию, отображающую всякий набор из A1 ... Aп в одно из двух

истинностных значений. Множество A1 ... Aп является областью определения соответствующего отображения.

Кроме того множество наборов значений переменных предиката, при подстановке которых вместо неопределенных

25

объектов формы P получается истинное высказывание, образует отношение на множестве всех таких наборов.

Свойство P называется предикатом, а число входящих в него переменных арностью или размерностью этого предиката.

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

В приведенных примерах предикат Дает имеет арность 3, а предикат Дружит арность 2. Предикаты арности 1 и 2 называются также соответственно унарными и бинарными предикатами.

Общеупотребительные арифметические сравнения могут рассматриваться как бинарные предикаты, которые соответственно можно представлять в виде:

Больше(x, у), Больше-или-равно(x, y); Меньше(x, y), Меньше-или-равно(x, y); Равно(x, y), Не-равно(x, y).

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

Например, Родитель(x, y), Отец(x, y), Брат(x, y),

Родственник(x, y) и другие предикаты.

Пусть некоторое множество наборов вида ( a1,		...	,	an),
где a1, ... , an это элементы множеств A1, ... , An	соответственно.
Поставим ему в соответствие предикат	P(x1 ,	...	,	xn),

принимающий истинностное значение “ t“ только на таких наборах значений своих переменных, которые входят в .

Нетрудно увидеть, что заданное соответствие между подмножествами произведения множеств A1, ... , An и

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

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

представлять одни и те же свойства наборов из A1 ... An и эквиваленты.

26

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

Основные логические связки это: КОНЪЮНКЦИЯ обозначается как &

(эта связка называется также связкой “ И”); ДИЗЪЮНКЦИЯ обозначается как (называется связкой “ ИЛИ”); ИМПЛИКАЦИЯ обозначается как (называется связкой “СЛЕДУЕТ”); ОТРИЦАНИЕ обозначается как (называется связкой “ НЕ”).

Если P1 и P2 два произвольных предиката, то P1 & P2 задает новый предикат, переменными которого являются все различные переменные предикатов P1 и P2 , а истинностные

значения определяются по правилу: P1 & P2 принимает значение “t” на тех и только тех наборах значений своих переменных, на

которых предикаты P1 и P2 являются истинными.

С помощью дизъюнкции образуется предикат, обозначаемый P 1 P 2 , принимающий значение “t” на тех и только тех наборах значений переменных, на которых хотя бы один из предикатов P1 и P2 принимает значение “t”. Соответственно предикат P1 P2 принимает значение “t“ всегда за исключением случая, к огда P1 истинен, а P2 ложен.

Наконец, отрицание это операция, применяемая к произвольному предикату P, которая имеет результатом новый

предикат P, истинный только тогда, когда P ложен. Истинностные значения результата применения л огических

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

P	P
f	t
t	f

27

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

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

	P1		P2		P1 & P2		P1 P2		P1 P2
	f		f		f		f		t
	f		t		f		t		t
	t		f		f		t		f
	t		t		t		t		t

В двух левых столбцах второй таблицы заданы различные

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

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

Содержательно запись P1 P2 понимается как: “Из P1 следует P2 “, что понимается как указание на логическое следование свойства, представляемого предикатом P2 , из свойства, представляемого P1 . При этом результат импликации - истинный только тогда, когда истинное значение P2 “не хуже“ истинного значения P1 . В частности, истинным является следование любого свойства из ложного свойства.

Кроме логических связок к предикатам применяются еще две

специальные операции, называемые кванторами существования и

и .

Пусть P(x1 , ... , xn) некоторый предикат. Тогда применение квантора существован ия по переменной xi этого предиката к P(x1 ,

... , xn) записывается как xi P(x1 , ... , xn). Эта запись

представляет новый предикат B(x1	,..,	xi - 1 , xi + 1 , . . .	,	xn),
переменными которого являются	все	переменные	P	за

исключением xi . Логическое значение пред иката B для любого конкретного набора ( 1 , ... , i 1 , i + 1 , ... , n ) значений

переменных этого предиката определяется по следующему

правилу.	Если существует такое значение	i	переменной xi , для
которого	логическое значение P ( 1 ,...	, i	1 , i , i + 1 ,..., n )

28

равно "t", то B на наборе ( 1	, ... , i 1 , i +	1 , ... , n ) является
истинным.
Если такого значения переменной x i		не существует ,	то
значение B на наборе ( 1 , ... , i 1 , i + 1		, ... , n ) является
ложным.
Квантор всеобщности
Применение квантора	всеобщности	переменной xi	к

предикату P(x1 , ... , xn) записывается как: xi P(x1 , ... , xn). Эта запись представляет новый предикат B(x1 , ... , xi -1 , xi + 1 , …, xn).

Истинностное		значение	B	для		каждого		конкретного			набора
( 1 , ... ,	i 1	, i + 1 , ... , n		)		значений		переменных			этого
предиката определяется по следующему правилу.
Если для		каждого	значения			i	переменной		xi	логическое
значение предиката P ( 1			,... , i 1			, i , i + 1 ,..., n )				равно "t", то
предикат B на наборе ( 1 ,				... ,		i	1 , i + 1 , ... , n ) является
истинным.	В	противном		случае			п редикат		B	на	наборе
( 1 , ... ,	i 1	, i + 1 , ... , n )			принимает значение "f".

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

Например, если P(x) одноместный предикат, то: x P(x),

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

значение. Т. е. x P(x) принимает значение "t" только тогда, когда P(x) принимает значение " t" хотя бы для одного значения переменной x.

Аналогично, предикат x P(x) принимает значение " t" только тогда, когда предикат P(x) является истинным.

Вкачестве примера рассмотрим двухмес тный предикат

РОДСТВЕННИК(x, y), истинный только для пар людей, являющихся родственниками.

29

Предикат x РОДСТВЕННИК(x, y) является истинным только для тех людей, которые имеют хотя бы одного родственника.

Аналогично, x РОДСТВЕННИК(x, y) предикат, истинный лишь для таких людей, для которых каждый человек является родственником. Нетрудно убедиться, что истинностным значением этого предиката всегда является ложь.

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

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

1. Запись всякого предиката является формулой.

2. Если A и B формулы, то следующие записи являются формулами:

(A & B), (A B), (A B), ¬(A), ( x A), ( x A).

3. Никакие другие записи не являются формулами.

При этом для формул ( x A) и ( x A) не требуется, чтобы переменная x имела свободные вхождения в A.

Логические связк и и кванторы сопоставляются с значениями

приоритетов: 1) , ; 2) ¬; 3) &; 4) , . Это позволяет упрощать записи в формулах за счет опускания избыточных скобок.

1.3.4. ДОКАЗУЕМОСТЬ И ВЫВОДИМОСТЬ

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

30

Соответствующая этому закону формула имеет вид :

Находиться(газ, x) увеличиваться(температура, газ)

являться(x, замкнутый сосуд)

увеличиваться(давление, газ).

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

В конкретных областях деятельности обычно применяют частично формализованные представления закономерностей и конкретных данных.

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

Всякий вывод осуществляется по определенным правилам. Такие правила носят характер схем, содержащих условия на структуру формул или соотношений, к которым применяется правило. Описания правил вывода удобно представлять

выражениями вида:	A 1 ... A n	. Здесь A1 , ... , An шаблоны посылок
	A n 1

правила вывода, а An+1 шаблон заключения или следствия.

К наиболее часто используемым правилам вывода относятся:

1)	правило modus ponens			A	A B		;
					B
2)	правило modus tollens		A			B A		;
					B
3)	правило обобщения			A		.
			x A

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

31

A, являющееся

Например, правило modus ponens утверждает, что если имеют место или справедливы соотношения, представляемые формулами A и A B, то справедливо и соотношение, выраженное формулой B. По таблице истинности для импликации,

если A и A B являются		истинными, то	B также	истинная
формула.
Логический	вывод	представляет	собой	цепочку

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

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

Метод следствий использует правило modus ponens и состоит в порождении всевозможных следствий из исходных соотношений до тех пор, пока не будет получе но заключение, являющееся решением задачи.

Метод рассуждений от противного использует правило modus tollens и основан на получении противоречия. К совокупности начальных истинных соотношений, добавляется отрицание утверждения цели задачи. Это соответству ет предположению о справедливости свойства, противоположного доказываемому свойству. Такое действие называется предположением о противном. Вывод, получаемый с помощью правила modus tollens, представляет собой цепочку отрицаний. Если в такой цепочке появляется соотношение

отрицанием некоторого начального соотношения A, то такая ситуация квалифицируется как противоречие, а предположение о противном как неверное.

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

32

1.3.5. СТРУКТУРА УТВЕРЖДЕНИЙ И ДОКАЗАТЕЛЬСТВ ТЕОРЕМ

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

1. ”Если A, то B“. Такое утверждение называется достаточными условиями, когда в предположении истинности

соотношений, представляемых A, следует истинность соотношений B. Говорят, что условия A являются достаточными для B.

Доказательство	такого	утверждения	использует
соотношения, входящие	в A,	и, возможно, другие	известные

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

2. “A тогда и только тогда, когда B“. Такое утверждение называется критерием. В этом утверждении A называется

необходимыми условиями, а B достаточными условиями. Оно эквивалентно двум утверждениям приведенного ранее вида: ”Если

A, то B“ и ”Если B, то A“. Поэтому доказательство критерия состоит из двух частей. Доказательство первого из приведенных утверждений называется доказательством необходимости, а второго доказательством достаточности.

Если в произвольном критерии переставить правое и левое соотношения, то наименования таких соотношений как необходимого и достаточного также поменяются. Доказательство необходимости исходного критерия превратится в доказательство достаточности нового критерия. Аналогично, доказательство достаточности исходного критерия превращается в доказательство необходимости для нового критерия.

33