Описание всех лабораторных работ (1006390), страница 3

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

Текст из файла (страница 3)

В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования. Эти операции рассмотрим вначале на примерах. Пусть дано выражение «существует х такой, что 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-х² » определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y-х² » обозначить через T(x,y), то Q(y) можно записать так: «для всех x справедливо T(x,y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x,y) навешиванием квантора общности на х и пишут Q(y)=(x)T(x,y).

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

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

Если предикат W(x₁,…,x_n) получен из предикатов U(x₁,…,x_n) и V(x₁,…,x_n) с помощью связок, то истинность высказывания W(a₁,…,a_n) определяется таблицами истинности этих связок. Пусть W(x₁,…,x_n)=(y)U(x₁,…,x_n,y). Тогда высказывание W(a₁,…,a_n) истинно тогда и только тогда, когда для любого bM истинно высказывание U(a₁,…,a_n,b). Если же W(x₁,…,x_n)=(y)U(x₁,…,x_n,y), то высказывание W(a₁,…,a_n) истинно в том и только в том случае, когда найдется bM, для которого высказывание U(a₁,…,a_n) истинно.

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

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

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

D_p={(a₁,…,a_n)Mⁿвысказывание P(a₁,…,a_n) истинно}.

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

Во-вторых, предикат P(x₁,…,x_n), заданный на M, можно отождествить с функцией f_p:Mⁿ{0,1}, определяемой равенством

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

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

Будем исходить из следующих трех множеств: F,R,V. Элементы множества F – символы (или имена) функций, элементы R – символы (или имена) предикатов, элементы множества V – переменные. Будем считать, что каждому символу функции и предиката поставлено в соответствие натуральное число или ноль – местность (т.е. число аргументов) этого символа. Допускаются нульместные символы функций, которые называются константами, и нульместные символы предикатов (последние будут играть роль атомарных формул логики высказываний). Объединение F и R будем называть сигнатурой. Сигнатуру заранее фиксировать не будем, она будет определяться содержанием решаемой задачи. Множество V предполагается бесконечным, для обозначения его элементов будут использоваться, как правило, буквы x,y,z,u,y,w с индексами и без них.

В примерах, приведенных выше, мы видели, что для записи предикатов использовались арифметические выражения: 2x, x+y, – x². Аналогом арифметического выражения в логике служит понятие терма.

Определение. Термом называется

1) переменная и константа;

2) выражение вида f(t₁,…,t_n), где t₁,…,t_n – термы, а f – n-местный функциональный символ.

Можно сказать, что терм – выражение, полученное из переменных и констант с помощью символов функций.

Определение. Атомарной формулой называется выражение вида r(t₁,…,t_n), где t₁,…,t_n – термы, r – символ n-местного предиката.

Примерами атомарных формул являются выражения xy²+1, |x-y|z, x делит нацело y-3.

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

1) атомарная формула,

2) выражения вида (F)&(G), (F₁)(G), (F), (F)(G),(F)(G), (v)(F), (v)(F), где F и G – формулы логики предикатов, v – переменная.

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

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

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

Например, в формуле

F=t(x)&(y)[s(x,y)(x)(r(x,y)t(y))]

Первое и второе вхождение переменной x свободны, третье и четвертое связаны. Все вхождения переменной y связаны.

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

Формула F из предыдущего примера имеет одну свободную переменную x.

Если x₁,…,x_n – все свободные переменные формулы F, то эту формулу будем обозначать через F(x₁,…,x_n). Это обозначение будем применять и в том случае, когда не все переменные из x₁,…,x_n являются свободными в F.

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

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

Определение. Интерпретацией на непустом множестве М называется функция, заданная на сигнатуре FR, которая

1) константе ставит в соответствие элемент из М;

2) символу n-местной функции ставит в соответствие некоторую n-местную функцию, определенную на множестве М;

3) символу n-местного предиката ставит в соответствие n-местный предикат, заданный на М.

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

Приведем примеры. Пусть сигнатура состоит из символа одноместного предиката P и двухместного предиката D, M={2,3,6,9,12,15} и

F=(P(x)&(_y)(P(y)D(x,y))

Поставим в соответствие (проинтерпретируем) P(x) предикат «x – простое число», D(x,y) – предикат «x меньше или равно y». Тогда формула F получит в соответствие предикат «x=2». На этом же множестве можно рассмотреть и другую интерпретацию: P(x) ставится в соответствие «x – нечетное число», D(x,y) – предикат «x делит y». В таком случае, формула F получает в соответствие предикат «x=3». Если  – интерпретация, то предикат, соответствующий формуле F будем обозначать через (F).

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

П(х): «х – первокурсник»,

С(х): «х – спортсмен»,

Л(х): «х – любитель подледного лова»,

З(x,y): «х знаком с y».

Тогда рассуждение запишется в виде следующей последовательности формул.

Н₁=(x)[П(х)(y)(C(y)&З(x,y))],

H₂=(x)(y)[П(x)&Л(y)З(x,y)],

H₃=(x)(C(x)Л(x))

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

Определение. Формулы F(x₁,…,x_n) и G(x₁,…,x_n) называются равносильными, если для любой интерпретации  с областью М высказывания (F)(a₁,…,a_n) и (G)(a₁,…,a_n) при любых a₁,…,a_n из М одновременно истинны или одновременно ложны.

Пусть F(x)=(y)P(x,y), G(x)=(y)P(x,y), где Р – символ двухместного предиката. Докажем, что формулы F(x) и G(x) равносильны. Возьмем интерпретацию  с областью М. Пусть высказывание (F)(a) истинно для aM. Истинность этого высказывания означает, что не для всякого yM высказывание (P)(a,y) истинно. Следовательно, найдется bM, для которого высказывание (P)(a,b) ложно. Если высказывание (P)(a,b), ложно, то высказывание (P)(a,b) истинно. Отсюда следует, что найдется yM такой, для которого высказывание (P)(a,y) истинно. Это означает истинность высказывания (G)(a). Итак, мы доказали, что если высказывание (F)(a) истинно, то высказывание (G)(a) тоже истинно. Обратная импликация доказывается аналогично. Значения истинности высказываний (F)(a) и (G)(a) при любом aM совпадают. Следовательно, формулы F(x) и G(x) равносильны.

Определение. Формула F(x₁,…,x_n) называется тождественно истинной, если для любой интерпретации  с областью М высказывание (F)(a₁,…,a_n) при любых a₁,…,a_n из М является истинным.

Приведем список основных равносильностей – законов логики предикатов. Прежде всего, законы алгебры логики изученные в курсе «Дискретная математика» работают и если вместо высказываний использовать предикаты. Дополним список законами, специфичными для логики предикатов:

22) (x)(F(x)&G(x) равносильна (x)(F(x)&(x)G(x),

23) (x)(F(x)G(x) равносильна (x)F(x)(x)G(x),

24) (x)(y)F(x,y) равносильна (y)(x)F(x,y),

25) (x)(y)F(x,y) равносильна (y)(x)F(x,y),

26) (x)F(x) равносильна (x)F(x),

27) (x)F(x) равносильна (x)F(x).

Законы 22, 23 утверждают, что квантор общности можно переносить через конъюнкцию, а квантор существования через – дизъюнкцию. Естественно поставить вопрос, можно ли квантор существования переносить через конъюнкцию, а квантор общности – через дизъюнкцию. Другими словами, будут ли равносильны следующие пары формул

(x)(F(x)G(x) и (x)(F(x)(x)G(x)

(x)(F(x)&G(x) и (x)(F(x)& (x )G(x) ?

Характеристики

Список файлов лабораторной работы