Математическая логика и ТА (Рудаков С.А

соответствие изучаемым объектам объект, и t1, t2,...,tn - термы, то f(t1, t2,...,tn) - терм.

Определение формулы:

a) если Р(•,...,•)

п-местный предикат, a t1, t2,...,tn термы, то

P(t1, t2,...,tn) (атомарная) формула;

b)если А и В формулы, то (A&B), (АVВ), (А=>В) формулы;

c)если А формула, то -А формула.

d)если А(х) формула, содержащая переменную х, то

x A(x), x A(x)

- формулы.

В разделе 1.1.3 было введено понятие формулы для высказываний,

которое мы только что расширили для предикатов. Расширение понятия произошло за счет пунктов a) и d). В пункте d) введены кванторы. Знак называется квантором всеобщности, а знак называется квантором существования. Ввел их в логику Ч.С.Пирс , хотя идея квантификации принадлежит Г.Фреге.

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

x A(x, y), x B(x, y)

переменная х связанная, а переменная у свободная.

Ясно, что формула без свободных переменных является выска-

зыванием.

2.1.3 Парадоксы

Многие думают, что парадокс Рассела делает наивную теорию множеств Кантора непригодной. Это абсолютно неверная точка зрения. На самом деле, этот парадокс касается только аксиоматики Фреге, которая содержит следующую аксиому:

31

Рассел заметил, что если взять в этой аксиоме в качестве предикат ,

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

бреет ли сам себя цирюльник, если сам цирюльник бреет всех, кто не бреется сам?

2.1.3 Интерпретации

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

Семантика [гр. semanticos] - 1) смысловая сторона единиц языка -

слов, частей слова, словосочетаний; 2) раздел логики, исследующий от ношения логических знаков и составленных из них выражений (формул)

к понятиям и предметам действительности.

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

M(M).

Формулы наполняются содержанием при интерпретации благодаря тому,

что элементы множества М уже привязаны к конкретной реальности,

знакомы и понятны. Например, в случае, когда М = R, т.е. М является множеством действительных чисел, под формулами мы понимаем сведения из математического анализа. Следовательно, нам становится ясным, когда формула при определенной фиксации своих переменных истинна, когда

ложна.

32

2.1.4 Истинность и выполнимость формул. Модели, общезначимость, логическое следствие

Рассмотрим формулу А(х1, х2,...,хп) и некоторую ее интерпретацию

M(M).

Формула А(х1, х2,...,хп) называется истинной в интерпретации M(M),

если она истинна при любом выборе x1=a1, x2=a2,...,xn=an, где a1, a2,, ...,an

M.

Формула называется выполнимой в интерпретации M(M), если она истинна при некотором выборе переменных x1=a1, x2=a2,...,xn=an, где a1, a2,..., an М.

Пример 1. Пусть M ={a1, a2, ... ,am} - конечное множество и А(х) -

одноместный предикат. Тогда применение квантора всеобщности

( x M ) A(x) A(a1) & A(a2 ) &...& A(am )	(1)
равносильно конъюнкции высказываний. Множество M с условием
истинности формулы (1) дают интерпретацию M(M). Тогда формула А(х)
истинна в интерпретации M(M).
Пусть M ={a1, a2, ... ,am} - конечное множество и А(х) - одноместный
предикат. Тогда применение квантора всеобщности
( x M ) A(x) A(a1)VA(a2 )V...VA(am )	(2)

равносильно дизъюнкции высказываний. Множество M с условием истинности формулы (2) дают интерпретацию M(M). Тогда формула А(х)

выполнима в интерпретации M(M).

Применим к отрицанию формулы (1) закон де Моргана. Получим

( x M ) A(x) ( A(a1 ) & A(a2 ) &...& A(am ) ) ( A(a1 ))V ( A(a2 ))V ...V ( A(am ) ) ( x M )( A(x))

Т.е. доказали что

( x M ) A(x) ( x M )( A(x))

отрицание квантора всеобщности для предиката А(х) есть применение

33

квантора существования к отрицанию А(х).

Аналогично, можно доказать что

( x M )A(x) ( x M ) ( A(x))

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

Интерпретация M(M) называется моделью для совокупности формул A1, A2,...,Ат, если они истинны в M(M). Символически это записывается в виде

M(M)|= A1,A2,...,Ат.

Формула A общезначима, если она истинна в любой интерпретации. Для общезначимой формулы пишем

|= A.

Если формула А общезначима, то формула -А называется логически ложной, или противоречием.

Пусть даны две формулы A(х1, х2,...,хп) и B(х1, х2,...,хп). Формула В является логическим следствием формулы А, если во всякой интерпретации формула В выполнена на каждом наборе переменных x1=a1, x2=a2,...,xn=an, на котором выполнена формула А. Символически для логического следствия используют обозначение

A |= B.

Теорема 1.4. А |= В тогда и только тогда, когда |= (А => В) .

Формулы A(х1, х2,...,хп) и B(х1, х2,...,хп) называются равносильными,

если А |= В и В |= А. Для равносильных формул используется запись: А ≡ В.

2.1.5 Законы логики предикатов

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

равносильные формулы и клаузы:
x (A(x)&B)≡ ( x A(x))& B	(3)
x (A(x)&B)≡ ( x A(x))& B	(4)
x (A(x)VB)≡ ( x A(x))V B	(5)
x (A(x)VB)≡ ( x A(x))V B	(6)
34

( x A(x)=>B)≡ x (A(x)=>B)	(7)
x (A(x)=>B)≡ x A(x) => B	(8)
(B=> x A(x)) ≡ x (B=> A(x))	(9)
(B=> x A(x)) ≡ x (B=> A(x))	(10)
- x A(x)≡ x(-A(x))	(11)
- x A(x)≡ x (-A(x))	(12)
x (A(x)&B(x))≡ ( x A(x))& ( x B(x))	(13)
x (A(x)VB(x))≡ ( x A(x))V ( x B(x))	(14)
x (A(x)&B(x))|= ( x A(x))& ( x B(x))	(15)
( x A(x))V( x B(x))|= x (A(x)VB(x))	(16)

Теорема 1.5. В формулах (7), (8) отсутствует равносильность.

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

Докажем, что левые части в формулах (7), (8) не являются следствиями соответствующих правых частей. Чтобы показать это, возьмем следующую интерпретацию M(M):

M - множество натуральных чисел,

A(x)="x - четное число",

B(x)="x - нечетное число".

Тогда формула ( x M A(x))& ( x M B(x) ) - истинна, а формула

x M (A(x)&B(x)) - ложна.

При этой же интерпретации формула x M (A(x)VB(x)) - истинна, а

формула ( x M A(x))V( x M B(x)) - ложна.

Что и требовалось доказать.

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

x y Р(x, у) ≡ y x Р(x, у) ,	(17)
x у Р(x, у) ≡ у x Р(x, у),	(18)
т.е. одинаковые кванторы при двуместных предикатах можно
переставлять местами. Для перестановки кванторов и	справедлива
35

следующая клауза:
х y Р(х, y) |= y х Р(х, y) .	(19)
Теорема 1.6. В формуле (19) отсутствует равносильность.
Д о к а з а т е л ь с т в о

Докажем, что левая часть в формуле (19) не является следствием правой части. Чтобы показать это, возьмем следующую интерпретацию

M(M):

M1 =" множество шляп",

M2=" множество людей",

M= { M1, M2}

Р(х, y) = «шляпа x пришлась человеку y впору»

Тогда формула

"человека y" "шляпа х" Р(х, y)= «шляпа x пришлась человеку y впору» -

истинна,

а формула

"шляпа х" "человека y" Р(х, y)= «шляпа x пришлась человеку y впору»-

ложна.

	Что и требовалось доказать.
	Истинными являются следующие клаузы:
	Таблица 15 Истинные клаузы
1.	х y Р(х, y) |= х y Р(х, y)
2.	х y Р(х, y) |= х y Р(х, y)
3.	х y Р(х, y) |= х y Р(х, y)
4.	х y Р(х, y) |= х y Р(х, y)
5.	х y Р(х, y) |= х y Р(х, y)
6.	х y Р(х, y) |= y х Р(х, y)
7.	х y Р(х, y) |= х Р(х, х)
8.	х Р(х, х) |= х y Р(х, y)
	36

9.	х y Р(х, y) |= Р(a, b)
10.	Р(a, b) |= х y Р(х, y)
11.	y Р(a, y) |= y х Р(х, y)
12.	y Р(a, y) |= х		y Р(х, y)
13.	х Р(х, b) |= y		х Р(х, y)
14.	х Р(х, b) |= х y Р(х, y)
15.	х y Р(х, y) |= y Р(a, y)
16.	y	х Р(х, y) |= y Р(a, y)
17.	х	y Р(х, y) |=	х Р(х, b)
18.	y х Р(х, y) |= х Р(х, b)

2.1.6 Сколемовские функции и сколемизация формул

Формулу А(х1, х2,...,хп) с помощью формул (3)-(16) можно привести к равносильной формуле в предваренной форме, в которой кванторы , не перемешиваются, а встречаются группами и все «вынесены влево», т.е. либо к виду

x1 x2... xn y1 y2... yn z1 z2... zn B(x1,x2,..., xn,y1,y2,...,yn,z1,z2,..., zn)

либо к виду
u1 u2... un	V1 V2... Vn w1 w2... wn	B(u1,u2,...,un,V1,V2,...,Vn,

w1,w2,...,wn)

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

B(x1,x2,...,xn,z1,z2,..., zn)≡ u (B(x1,x2,...,xn,z1,z2,..., zn)&T(u))

где T(u) — произвольная общезначимая формула.

Раздел не закончен. Далее смотри А.К. Гуц "Математическая логика и теория алгоритмов".

37

2 Неклассические логики

2.1. Нечеткая логика

2.1.1 Высказывания

Упражнения. Нечеткие множества A, B из универсума E=[0,100]

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

Варианты	Функция	Значения	Значения
	принадлежности	аргумента	функции
		0	1
	µA	[0,30]	линейна
1		30	0
		[0,50]	0
	µB	[50,80]	линейна
		[80,100]	1
		[0,20]	1
	µA	[20,40]	линейна
2		[40,100]	0
		[0,60]	0
	µB	[50,70]	линейна
		[70,100]	1
		[0,10]	0
		[10,20]	линейна
3	µA	[20,30]	1
		[30,40]	линейна
		[40,100]	0
		38

		[0,80]	0
	µB	[80,100]	линейна
		100	1
		0	0
		[0,20]	линейна
	µA	[20,40]	1
		[40,50]	линейна
4		[50,100]	0
		[0,80]	0
		[80,90]	линейна
	µB	90	1
		[90,100]	линейна
		100	0
		[0,10]	0
		[10,20]	линейна
	µA	[20,30]	1
5		[30,40]	линейна
		[40,100]	0
		[0,90]	0
	µB	[90,100]	линейна
		100	1
		0	0
		[0,20]	линейна
	µA	20	1
6		[20,40]	линейна
		[40,100]	0
		[0,60]	0
	µB	[60,80]	линейна
		[80,90]	1
		39

		[90,100]	линейна
		100	0

3 Теория алгоритмов

3.1. Алгоритм и вычислимая функция

Алгоритм ‒ это точное предписание, определяющее вычислительный процесс, ведущий к искомому результату (А.А.Марков).

Алгоритм ‒ это процедура П, которая (по А.Н.Колмогорову):

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

2)Расчленена на отдельные простые шаги; каждый шаг состоит в непосредственной обработке возникшего к этому шагу состояния S в

состояние S* = Ωп(S).

3)Непосредственная переработка S в S* = Ωп(S) производится однозначно заданным способом лишь на основании информации о виде заранее ограниченной «активной» части состояния S и затрагивает лишь эту активную часть.

4)Процесс переработки А0 = А в A1 = Ωп(А0), A1 в A2= Ωп(А1), A2 в A3= Ωп(А2) и т.д. продолжается до тех пор, пока либо не произойдет

безрезультатная остановка (или оператор Ωп не определен для возникшего состояния), либо не появится сигнал о получении «решения». При этом не исключается возможность непрекращающегося процесса переработки.

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

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

40