Дискретная математика & математическая логика

0,2;

1, ?;

2,?;

1.

3,?;

*,?;λ,?;

Ветвление по значению первого символа – для начала укажем путь по значению «0»

2. R,3; это сдвиг вправо к следующей ячейке

0,?;

1, 4;

2,?;

3. Ветвление по значению второго символа

3,?;

*,?;λ,?;

4.R,5; это сдвиг вправо к следующей ячейке

0, ?;

1, ?;

2, ?;

5.Ветвление по значению третьего символа

3,6;*,?;

λ, ?;

6. R,7; это сдвиг вправо к следующей ячейке

7.*, 8; запись * после последовательности 013

8. HLT; стоп.

Теперь указываем все возвраты и переход по λ. Все λ отправим к команде 7.

251

Первую петлю организуем так: в ячейке 8 выполним сдвиг вправо и возврат к первой команде:

9. R,1.

Остальные возвраты выполним путём адресации к анализу первого символа.

Вся программа получится такая:

0,2;

1, 9;

2,9;

1. Ветвление по значению первого символа

3,9;

*,9;λ,7;

2.R,3; это сдвиг вправо к следующей ячейке

0,9;

1, 4;

2,9;

3.Ветвление по значению второго символа

3,9;*,9;λ,7;

4. R,5; это сдвиг вправо к следующей ячейке

0,9;

1, 9;

2,9; 5. Ветвление по значению третьего символа

3,6;

*,9;λ,7;

6.R,7; это сдвиг вправо к следующей ячейке

7.*, 8; запись * после последовательности 013

8.HLT; стоп.

9.R,1

252

11.ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ

11.1.Математическая логика. Доказательство правильности программ

Каждая программа рассматривается как теорема [5]: если исходные данные удовлетворяют некоторым условиям, то после выполнения данной программы для её результатов будут справедливы некоторые другие условия.

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

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

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

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

4.После того как достигнута заключительная точка, программа завершена.

Пример. Пусть имеется ящик с деталями разного веса. С помощью чашечных весов (без гирь) необходимо определить самую тяжёлуюдеталь.

Алгоритм с тремя контрольными точками может быть записан следующим образом:

1.Самая тяжёлая деталь – в ящике.

Начало цикла: пока в ящике больше одной детали (n > 1). Действие Z1. Положить любые две детали на чашки весов.

2.Самая тяжёлая деталь – в ящике или на весах.

Взвешивание – какая деталь тяжелее? х = 1? Действие Z2. Лёгкую деталь отложить.

253

Действие Z3. Тяжёлую деталь вернуть в ящик. Конец цикла.

3. В ящике ровно одна деталь – самая тяжёлая. Действие Z4. Взять самую тяжёлую деталь из ящика. Схема алгоритма имеет вид (рис. 11.1):

Рис. 11.1. Схема алгоритма определения самой тяжёлой детали

А. В начальный момент утверждение 1 верно: самая тяжёлая деталь в ящике (даже если она всего одна).

В. Если утверждение 1 верно, то при входе в цикл верно и утверждение 2: в промежутке между этими двумя точками детали «уходили» только на весы.

С. Если верно утверждение 2, то при следующем проходе цикла верно и 1.

Если в точке 2 самая тяжёлая деталь находилась в ящике, она тамиосталась. Между точками 2 и1 изящиканичегоневынималось.

Если же в точке 2 самая тяжёлая деталь была на весах, то она будет возвращена в ящик.

254

D. Если верно утверждение 1, то при выходе из цикла верно и утверждение 3.

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

вие цикла: в ящике не больше одной детали.

Следовательно, в ящике ровно одна деталь и в соответствии с утверждением 1 она самая тяжёлая.

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

11.2.Особенности построения модифицированного дерева опровержения с предположением,

содержащим квантор общности

При отрицании предположения возникают кванторы существования, что приводит к введению функций Сколема. В этом случае трудности заключаются в интерпретации вводимых функций Сколема [15].

Пример. Каждый является ребёнком своего родителя. Если х ребёнок у, то у – родитель х. Требуется найти родителя произвольного х:

xF (x, f (x)), x[F (x, y→ ) P(x, y)].

где f – функция «родительства»; F(x, y) – предикат «хребёнок у»; P(y, x) – предикат «у– родительх».

Предположение «у каждого х есть родитель у» имеет вид

x yP(y, x).

Отрицание предположения будет таким:

x y P(y, x).

При введении функции Сколема в стандартной бескванторной форме получим

255

P(y, a).

Тогда множество дизъюнктов имеет вид

F (x, f (x)), F (x, y) P(x, y), P(y, a).

Дерево опровержения имеет вид (рис. 11.2):

Рис. 11.2. Дерево опровержения

Опровержение достигнуто. Умозаключение верно.

Для модифицированного дерева доказательства получим – рис. 11.3:

F (x, f (x)),F (x, y) P(x, y),P(y, a) P(y, a):

Рис. 11.3. Модифицированное дерево опровержения

256

В корне получается трудноинтерпретируемое утверждение P(f (a), a), содержащее функцию Сколема f (a). Отрицание предпо-

ложения P(y, a) означает, чтонекоторыйиндивиднеимеетродителя. Поэтому P(f (a), a) интерпретируется так: независимо от ин-

дивида а, у которого не должно быть родителей, как оказалось P(f (a), a) , т.е. для любого а родителем является f (a).

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

11.3. Многозначные переключательные функции и их функциональная полнота

Функция, принимающая значение из множества M = {0,1, ..., k −1} , аргументы которой принимают значения из это-

го же множества, называется переключательной функцией (ПФ) или функцией k-значной логики [5].

Примером могут быть функции сложения и умножения по модулю k.

Число различных k-значных ПФ n переменных равно k k n . Так, трехзначных ПФ двух переменных 19 683. Все они образуют множество Pk .

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

ном из них, и это верно для любого k.

С.В. Яблонский нашел все предполные классы для k = 3 – их оказалось 27.

257

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

Примеры функционально полных систем:

max(x1 , x2 ) ±1(modk ),

min(x1 , x2 ) ±1(modk),

max(x1 , x2 ), x +1(modk).

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

Представим систему, включающую в себя константы и следующие функции:

1)x1 x2= min(x1 , x2 ) – конъюнкция;

2)x1 x2= max(x1 , x2 ) – дизъюнкция;

3)константы 0,1, 2, ..., k −1.

	Одноместные функции имеют вид xдj						j , где δj –			показатель
значения переменной:			xдj	j = 0,	если дj ≠ x j ; иначе xдj				j	= k −1, дj =
= {0,1,..., k −1}.
	Рассмотрим некоторую трехзначную ПФ:
						х2
	х1		0			1				2
	0		0			0				0
	1		2			0				1
	2		0			1				0

Получим СДНФ

1	0		1	2	2	1		.
f ( x1 , x2 ) = 2 x1 x2			1x1	x	1x x		2
				2		1

258

На наборе 10 получаем

f (1, 0) = 2 1 1 1 0 0 1 0 =0 2.

На наборе 10 получаем

1	0		1	2	2	1
f ( x1 , x2 ) = 2 2	2	1	2	0 1 2		0= 2.

На наборе 00 получаем

1	0		1	2	2	1
f ( x1 , x2 ) = 2 0	2	1	0	0 1 0		0= 0.

На наборе 21 получаем

1	0			1	2	2	1
f ( x1 , x2 ) = 2 0	0		1	0	0 1 2		2= 1.
На наборе 12 получаем
1	0			1	2	2	1
f ( x1 , x2 ) = 2 2	0		1	2	2 1 2		0= 1.

Существуют методы минимизации такой СДНФ, однако они не всегда так эффективны, как в двоичном случае.

Многозначные ПФ можно с успехом моделировать совокупностью двоичных. Например, вышеприведенная троичная функция на основе памяти – ПЗУ:

x1,1	x1,2	x2,1	x2,2	f1 ( x1, x2 )		f1 ( x1, x2 )
	Адреса				Данные
0	1	0	0	1		0
0	1	1	0	0		1
1	0	0	1	0		1

Остальные адреса заполняются нулями.

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

259

11.4. Реляционная алгебра и реляционное исчисление

Эдгар Франк «Тед» Кодд (1923–2003) – рис. 11.4 – британский ученый, работы которого заложили основы теории реляционных баз данных. Работая в компании IBM, он создал реляционную модель данных. Он также внес существенный вклад в другие области информатики [5].

Рис. 11.4. Эдгар Франк «Тед» Кодд

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

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

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

260