ДМ_Конспект

Таблица 11.1 − Правила дедуктивных выводов логики высказываний

	Правило									Тавтология	Название правила
дедуктивного
	вывода
				A						A ( A B)	Правило введения дизъюнкции
			A B
				A ,						((A) (B)) (A B)	Правило введения конъюнкции
				B
			A B
			A B ,							(A B) A B)	Правило удаления дизъюнкции
			A								(дизъюнктивный силлогизм)
				B
			A B							( A B) A	Правило удаления конъюнкции
				A
		A B								(A B) (B A)	Правило контрапозиции
											импликации
	B A
		A B ,								(A ( A B)) B	Правило отделения
				A							(Modus Ponens)
				B
			B ,							(B (A B)) A	Отрицательная форма правила
		A B									отделения
											(ModusTollens)
			A
		A B ,								((A B) (B C)) (A C	Гипотетический силлогизм
		B C
		A C

11.4 Непротиворечивость, независимость

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

Определение.

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

Непротиворечивое исчисление − это такое исчисление, что, какова бы ни была формула A , никогда формулы A и A не могут быть одновременно выведены из аксиом этого исчисления с помощью указанных в нем правил.

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

Теорема.

Исчисление высказываний непротиворечиво.

121

Рассмотрим свойство независимости системы аксиом исчисления высказываний.

Определение.

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

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

11.5 Различные аксиоматизации исчисления высказываний

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

Пример.

1.Аксиоматизация исчисления высказывания Гилберта и Аккермана

(1938):

а) связки , ;

б) аксиомы:

A A A,

A A B ,

A B B A,

(B C) (A B A C);

в) правило: Modus Ponens (правило отделения).

2. Аксиоматизация исчисления высказывания Россера (1953): а) связки , ;

б) аксиомы:

A A A,

A B A,

(A B) ( (B C) (C A)) ;

в) правило: Modus Ponens (правило отделения).

3. Аксиоматизация исчисления высказывания Клини (1952) а) связки , , , ;

б) аксиомы:

A (B A) ,

(A (B C)) ((A B) (A C)) ,

A B A,

A B B ,

A (B ( A B)), A (A B) ,

B ( A B) ,

122

(A C) ((B C) ((A B) C)) ,

(A B) ((A B) A),A A .

в) правило: Modus Ponens (правило отделения).

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

1. Язык системы S состоит из правильно построенных формул логики высказываний, содержащих операции { , }. Алфавит языка совпадает с

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

2. Аксиомы системы S :

а) A (B A) ;

б) (A (B C)) ((A B) (A C)); в) (B A) ((B A) B).

3. Правила вывода:

а) правило отделения (Modus Ponens); б) правило подстановки.

Достоинством данной формальной системы является лаконичность при сохранении определенной наглядности.

11.6 Некоторые приемы доказательств в исчислении высказываний

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

Теорема о дедукции.

Пусть G − множество формул, A, B − формулы и G, A B . Тогда

G A B .

Эта теорема обосновывает следующий прием: в математических рассуждениях часто какое-то утверждение B доказывают в предположении

некоторого другого утверждения A ,	после чего	заключают, что верно
утверждение «если A то B ».
Вместо прямого логического вывода формулы		B из формулы A часто
оказывается удобным доказать противоречивость формулы A B тем самым
доказав истинность формулы A B .	Такой метод	(прием) доказательства

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

1) (A B) (C C) A B − если из предположения, что A −

верно, а B − неверно, следует два противоречащих друг другу высказываний, то это означает, что из A следует B ;

123

2) B A A B − если из предположения, что B − неверно, следует, что A неверно, то это означает, что из A следует B .

11.7 Контрольные вопросы и задания

1.Что представляет собой исчисление высказываний?

2.Поясните понятия языка, аксиом и правил вывода исчисления высказываний.

3.Приведите примеры аксиом исчисления высказываний.

4.Каким образом строится дедуктивный вывод?

5.Дайте краткую характеристику основных правил дедуктивного вывода.

6.Перечислите правила дедуктивных выводов логики высказываний.

7.В чем состоит полнота и непротиворечивость исчисления высказываний?

8.Дайте определение независимой системы аксиом.

9.Сформулируйте теорему дедукции.

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

ЛЕКЦИЯ 12. ЛОГИКА ПРЕДИКАТОВ (ЛОГИКА ПЕРВОГО ПОРЯДКА).

ПРЕДИКАТЫ. АЛГЕБРА ПРЕДИКАТОВ

12.1 Основные понятия логики предикатов

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

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

терм, квантор.
Определение.
Предикатом называется	функция	P(x1 , x2 ,...,xn ) , переменные которой
принимают значения из некоторого множества M , а сама она принимает два
значения И (истинное) и Л	(ложное),	т.е. P(x , x ,...,x ) : M n {И, Л} (где
		1 2	n
	124

M n M M ... M ).

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

Предикаты становятся высказываниями, когда их переменным присваиваются значения.

Пример.
Предикатами	являются следующие утверждения: P(x) : 3 x 5;
Q(x, y, z) : x2 y2 z2 ;	R(x, y) : x2 y2 0; S(x) : 1 sin( x) 1.

Пусть x 2 , тогда утверждение P(2) : 3 2 5 является высказыванием, и это высказывание истинно. При x 7 утверждение P(7) : 3 7 5 тоже является

высказыванием, и это высказывание ложно.

Определение.

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

универсом или предметной областью.

Пример.

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

Множество M значений перменных определяется обычно математическим контекстом.

Определение.

Вобщем случае определен некоторый предикат, если:

1)задано некоторое (произвольное) множество, называемое областью определения предиката (предметная область);

2)фиксировано множество {И, Л}, называемое областью значений;

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

Определение.

Предикат с одной переменной называется одноместным предикатом и может обозначаться, например, P(x) , где x − переменная. Предикат, имеющий

две переменные, называется двухместным предикатом и может обозначаться, например, P(x, y) , где x, y − переменные, а предикат, содержащий n

переменных ( n аргументов), называется n -местным предикатом и обозначается P(x1 , x2 ,...,xn ). Высказывания считаются нульместным

предикатом.

Количество аргументов	предиката	P(x1 , x2 ,...,xn ) называется его
порядком.
Пример.
Высказывание « x −	действительное	число» можно представить

одноместным предикатом, « y меньше z » − двуместным предикатом. Если x, y и z замещены конкретными значениями (объектами), то предикат переходит в

125

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

Определение.

Аргументы предиката называются термами. Термы-константы и термы-

переменные называются предметными константами и предметными переменными.

Предикаты обычно обозначаются большими латинскими буквами. Иногда бывает удобно указывать число переменных у предиката путем введения верхнего индекса, например P( n) (x1 , x2 ,...xn ) является n -местным предикатом.

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

Пример.

Представим в виде предиката высказывания: « x делится на 7», « x делится на y », « x − простое число». Выберем в качестве названий предикатов

действия или свойства данных предложений: ДЕЛИТСЯ, ПРОСТОЕ. Тогда заданные высказывания можно записать в виде предикатов следующим образом: ДЕЛИТСЯ( x ,7), ДЕЛИТСЯ( x , y ), ПРОСТОЕ( x ). Здесь первый и

третий предикат являются одноместными и каждый выражает некоторое свойство числа x ; второй предикат – двуместный и выражает бинарное отношение делимости на множестве чисел.

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

индивидуальные символы или константы, которые обычно являются именами объектов, например: Сократ, 13;

символы предметных переменных, в качестве которых обычно выступают буквы латинского алфавита, возможно, с индексами, например:

x, y, b2 ;

функциональные символы – строчные буквы латинского алфавита или осмысленные слова из строчных букв, например: минус( x, y ) –

функциональный символ « x y », отец ( x ) – функциональный символ «отец человека x »;

предикаты – прописные буквы или осмысленные слова из прописных букв, например: P , Q , ДЕЛИТСЯ, БОЛЬШЕ, ПРОСТОЕ.

Пример.

Переведем на естественный язык следующие высказывания логики предикатов: 1) РАВНЯТЬСЯ (x,5) ; 2) ЗНАТЬ(папа(Вася), математика).

Предикат РАВНЯТЬСЯ (x,5) соответствует утверждению « x равняется

5» естественного языка. Здесь 5 – константа, x − предметная переменная.

В высказывании ЗНАТЬ(папа(Вася), математика) функциональный

126

символ «папа( x )» принимает значение из множества людей, соответствующее отношению «быть отцом x ». Поэтому выражение папа(Вася) следует интерпретировать как «Васин папа». Таким образом, предикат ЗНАТЬ (папа(Вася), математика) соответствует предложению «папа у Васи знает математику» естественного языка. Здесь «Вася» и «математика» являются константами, а x − предикатная переменная.

12.2 Операции логики предикатов. Кванторные операции

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

связками (как и в логике высказываний).

Пример.

Пусть P(x) − предикат « x делится на 3», Q(x) − предикат « x делится на 5», тогда выражение P(x) Q(x) означает « x делится на 3 и делится на 5», т.е.

определяет предикат делимости на 15.

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

Определение.

Пусть P(x) − предикат, определенный на множестве M . Высказывание «для всех x M , P(x) истинно» обозначается xP(x) .

Определение.

Символ называется квантором всеобщности (квантором

общности).

Если применяется квантор всеобщности, то говорится, что высказывание истинно для всех x из некоторого множества.

Определение.

Высказывание «существует такой x M , что P(x) истинно» обозначается

xP(x) , где символ называется квантором существования.

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

Пример. Запишем в виде предикатов с кванторами следующие высказывания: «Все студенты сдают экзамены», «Некоторые студенты сдают экзамены на отлично».

Введем предикаты: P − «сдавать экзамены» и Q − «сдавать экзамены на

отлично». Предметная область данных предикатов представляет собой множество студентов. Тогда исходные выражения примут вид: (x)P(x) и (x)Q(x) .

127

Заметим, что имеют место ранги логических связок, учитывая которые кванторы x и x размещаются между связками , , и , ~ .

Применение кванторов к многоместным предикатам уменьшает количество переменных, от которых зависит данный предикат. Например, применение квантора по одной из переменных двухместного предиката превращает его в одноместный.

Квантор общности можно истолковывать как обобщение конъюнкции, а квантор существования – как обобщение дизъюнкции, т.е. если область определения M предиката P конечна, например, M {a1 ,a2 ,...,an }, то

высказывание xP(x) эквивалентно P(a1 ) P(a2 ) ... P(an ) , а высказывание

xP(x) − дизъюнкции P(a1 ) P(a2 ) ... P(an ) .

Пример.

Пусть задан предикат P(x) , который означает « x − нечетное число» и определен на области M {a,b, c}.

Высказывание P(x) означает: « a − нечетное число», и b − нечетное число и c − нечетное число», а высказывание P(x) означает то же, что и

дизъюнкция « a − нечетное число, или b − нечетное число, или c нечетное число»

12.3 Формулы и их интерпретация в логике предикатов

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

Алфавит логики предикатов в общем случае содержит следующие символы:

1)символы предметных переменных: x1 , x2 ,...,xn ,...;

2) символы предикатов:	P(t ) , P(t ) ,...,P(t ) ,..., где t 0,1, 2,...;
	1 2	n

3)логические символы: , , , , ~ ;

4)символы кванторов: , ;

5)скобки и запятую: ),( .

Определение.

Если P n -местный предикат и t1 ,t2 ,...,tn термы, то P(t1 ,t2 ,...,tn )

называется атомом или элементарной формулой логики предикатов.

Пример.

Атомами являются: ДЕЛИТСЯ( x ,13), ДЕЛИТСЯ( x , y ), БОЛЬШЕ

(плюс( x ,1), x ), РАВНЯТЬСЯ( x ,1), СДАВАТЬ(студенты, сессия).

Определение.

Правильно построенными формулами логики предикатов называются

128

формулы, которые можно рекурсивно определить следующим образом:

1.	Атом является формулой.
2.	Если P и Q − формулы, то (P), (P Q), (P Q), (P Q), (P ~ Q)
также являются формулами.
3.	Если P − формула, а x − свободная переменная, то (x)P и (x)P

тоже формулы.

4. Никаких формул, кроме порожденных указанными выше правилами, не существует.

Введем понятие свободного и связанного вхождения переменной в формулу.

Определение.

В выражениях ( )P(x) и ( )P(x) формула P(x) , на которую

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

Следует заметить, что формула P может и не иметь вхождений переменной x . В таком случае считается, что формулы P и (x)P одинаковые.

Определение.

Вхождение переменной x в формулу P(x) называется связанным, если x

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

Пример.

Определим вхождение переменных в следующие формулы: а) A12 (x, y) ; б)

A12 (x, y) xA11 (x) , в) x(A12 (x, y) xA11 (x)) .

Единственное вхождение переменной x в формулу а) является свободным. Первое вхождение переменной x в формулу б) свободное, а второе и третье − связанные. Все вхождения переменной x в формулу в) связанные.

Определение.

Переход от P(x) к xP(x) или xP(x) называется связыванием

переменной x , а сама переменная x в этом случае – связанной. Переменная, не связанная никаким квантором, называется свободной.

Смысл связанных и свободных переменных в предикатных выражениях различен. Свободная переменная − это обычная переменная, которая может принимать различные значения из M ; выражение P(x) – переменное

высказывание, зависящее от значения x . Выражение (x)P не зависит от

переменной x и при фиксированных P и M имеет вполне определенное значение. Это в частности означает, что переименование связанной переменной, т.е. переход от (x)P(x) к (y)P( y) , не меняет истинности

129

выражения.

Определение. Формула называется замкнутой, если она не имеет свободных переменных.

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

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

Пример. (x)(z)Q(x, y, z) не является высказыванием, так как переменная y не связана никаким квантором.

Формулы имеют смысл только тогда, когда существует какая-либо интерпретация символов, входящих в эти формулы.

Определение.

Интерпретация формулы F логики предикатов состоит из элементов непустой предметной области D , значений всех констант, функциональных символов и предикатов, встречающихся в F . Указанные значения задаются следующим образом:

1.Каждой константе ставится в соответствие некоторый элемент из D .

2.Каждому n -местному функциональному символу ставится в

соответствие отображение из Dn в D . Здесь Dn (x , x ,...,x ) , где
1 2	n

x1 , x2 ,...,xn D .

3. Каждому n -местному предикату ставится в соответствие отображение из Dn в {И, Л}.

Для каждой интерпретации на области D формула может получать истинностное значение И или Л согласно следующим правилам:

1.Если заданы значения формул F и G , то истинностные значения формул ( F ), ( F G ), ( F G ),( F G ),( F ~ G ) получаются с помощью таблиц истинности соответствующих логических операций.

2.Формула (x)F получает значение И, если F получает значение И

для каждого x из D , в противном случае она получает значение Л.

3.Формула (x)F получает значение И, если F получает значение И

хотя бы для одного x из D , в противном случае она получает значение Л.

4. Формула, содержащая свободные переменные, не может получать

истинностные значения.
Пример. Пусть задан предикат P(x) x2 5. Формула	xP(x) не

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

130