Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

§1. Предикаты и операции над ними

Введем основное понятие темы.


Определение. Пусть М – непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М.


Рассмотрим примеры. Пусть М есть множество натуральных чисел N. Тогда выражения «x – простое число», «x – четное число», «x – больше 10» являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д. Выражения «x больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x плюс y равно z», «|x-y|£z».

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

Надо отметить, что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение «существует число x такое, что y=2x» на множестве натуральных чисел определяет одноместный предикат. По смыслу этого выражение в нем можно заменять только переменную y. Например, замена y на 6 дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».

Предикат с заменяемыми переменными x1,…,xn будет обычно обозначаться заглавной латинской буквой. После которой в скобках указаны эти переменные. Например, P(x1,x2), Q(x2,x3), R(x1). Среди переменных в скобках могут быть и фиктивные.

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


Определение. Предикат W(x1,…,xn) называется конъюнкцией предикатов U(x1,…,xn) и V(x1,…,xn), заданных на множестве М, если для любых а1,…,аn из М высказывание W(а1,…,аn) есть конъюнкция высказываний U(а1,…,аn) и V(а1,…,аn).


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


В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования. Эти операции рассмотрим вначале на примерах. Пусть дано выражение «существует х такой, что x+y=10». На множестве натуральных чисел это предложение определяет одноместный предикат P(y), так Р(2) и Р(9) – истинные высказывания, Р(11) – ложное. Если обозначить предикат «x+y=10» через S(x,y) (а это предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x,y)». В этом случае говорят, что предикат P(y) получен из предиката S(x,y) навешиванием квантора существования на x и пишут P(y)=($x)S(x,y). Рассмотрим другой пример. Выражение «для всех х справедливо, что y³2» определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y³2» обозначить через T(x,y), то Q(y) можно записать так: «для всех x справедливо T(x,y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x,y) навешиванием квантора общности на х и пишут Q(y)=("x)T(x,y).

После этих примеров нетрудно дать определение в общем виде.


Определение. Пусть P(x1,…,xn) – предикат, заданный на множестве M, y – переменная. Тогда выражение «для всякого y выполняется P(x1,…,xn)» – предикат, полученный из P навешиванием квантора общности на переменную y, а выражение «существует y такой, что выполняется P(x1,…,xn)» – предикат, полученный из P навешиванием квантора существования на переменную y.

Обозначения операций были введены выше.

Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, которые будут ниже, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является (n-1)-местным, если yÏ{ x1,…,xn}, то местность нового предиката равна n.


Если предикат W(x1,…,xn) получен из предикатов U(x1,…,xn) и V(x1,…,xn) с помощью связок, то истинность высказывания W(a1,…,an) определяется таблицами истинности этих связок. Пусть W(x1,…,xn)=("y)U(x1,…,xn,y). Тогда высказывание W(a1,…,an) истинно тогда и только тогда, когда для любого bÎM истинно высказывание U(a1,…,an,b). Если же W(x1,…,xn)=($y)U(x1,…,xn,y), то высказывание W(a1,…,an) истинно в том и только в том случае, когда найдется bÎM, для которого высказывание U(a1,…,an) истинно.

Понятие предиката – весьма широкое понятие. Это видно уже из приведенных выше примеров. Тем не менее мы это еще раз подчеркнем, показав, что n-местная функция может рассматриваться как (n+1)-местный предикат. Действительно, функции y=f(x1,…,xn), заданной на множестве М можно поставить в соответствие выражение «y равно f(x1,…,xn)». Это выражение есть некоторый предикат P(x1,…,xn,y). При этом если элемент b есть значение функции в точке (a1,…,an), то высказывание P(a1,…,an,b) истинно, и обратно. (Подобное «превращение» функции в предикат мы уже делали выше для сложения натуральных чисел.)


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

Во-первых, предикат можно представить отношением следующим образом. Пусть предикат P(x1,…,xn) задан на множестве M. Рассмотрим прямую степень этого множества Mn=MxMx…xM и подмножество Dp множества Mn, определяемое равенством:


Dp={(a1,…,an)ÎMn½высказывание P(a1,…,an) истинно}.


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

Во-вторых, предикат P(x1,…,xn), заданный на M, можно отождествить с функцией fp:Mn®{0,1}, определяемой равенством



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

§2. Формулы логики первого порядка

§3. Интерпретация в логике первого порядка

§4. Равносильность, законы логики первого порядка

§6. Логическое следствие

§7. Нормальные формы

§8. Невыразимость в логике первого порядка

§9. Многосортная логика первого порядка

Задачи

Ответы, указания и решения

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru