Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Основы логики предикатов и логического вывода
Предикаты Логика высказываний оперирует с атомами. Атомы являются абстракциями простейших повествовательных предложений, которые могут быть истинными или ложными. Атом рассматривается как неделимое целое, его структура не анализируется. Таким образом, аппарат, подходы и результаты логики высказываний могут быть применены только к очень узкому классу ситуаций - самых простых рассуждений на естественном языке. В естественном языке встречаются и более сложные повествовательные предложения, истинность которых может меняться при изменении объектов, о которых идет речь, хотя структура предложений не меняется. Например, предложение “Джон любит Мэри” может быть истинным, а предложение “Джон любит Мэгги” ложным. В логике такие предложения, истинность которых зависит от параметров, абстрагируют с помощью предикатов. Например, предикат Любит(х,у) на паре <Джон, Мэри> может принимать значение истина, а на паре <Джон, Мэгги> - ложь. На латыни слово “ предикат ” (praedicatum) означает “ сказуемое ”, т.е. то, что в элементарном суждении утверждается о субъекте этого суждения, т.е. свойства этого оюъекта. Например, высказывание “ Собака имеет хвост” истинно, “ Лошадь имеет хвост” истинно, а “ Человек имеет хвост” ложно. Поэтому заменив субъект в суждении переменной x, получим некую форму “ х имеет хвост”, которая является функцией от х и принимает значения истинно для одних субъектах-аргументах этой функции и ложно для других. Формализация подобной высказывательной формы и называется предикатом, т.е. функцией, принимающей истинностные значения (истина либо ложь) и определенной на произвольной области изменения своей переменной; n-местный предикат является естественным обобщением функции одной переменной. Определение 2.7. n-местным предикатом Р(х1,...,хn) называется функция Р: М n®{ True, False }, определенная на наборах длины n элементов некоторого множества М и принимающая значения в области истинностных значений (рис.2.3, а). ÿ Множество М называется предметной областью предиката, а х1,...,хn - предметными переменными. Пусть М - множество натуральных чисел и n = 2. Двуместный предикат Р(х,у): х³у+3 истинен на парах <25,1> и <15,12> и ложен на паре <1,1>. Поскольку предикат каждому элементу множества М n ставит в соответствие True или False, то можно считать, что предикат выделяет на М n некоторое подмножество, на котором он истинен (рис.2.3, б). Таким образом, предикат на М может характеризовать (задавать) некоторое подмножество элементов М, а именно тех, на которых он истинен.
Предикаты могут быть связаны логическими связками, например, Р(х,у) ÚØQ(х,у). Рассмотрим формулу РÞQ. Она принимает истинное значение на тех аргументах, на которых предикат Р ложен или же предикат Q истинен. Очевидно также, что если на каждом элементе множества М n, на котором предикат Р истинен, предикат Q тоже истинен, формула РÞQ общезначима. Таким образом, формула РÞQ общезначима тогда и только тогда, когда множество истинности предиката Р является подмножеством множества истинности предиката Q, или, что то же, предикат P сильнее предиката Q, как это показано на рис.2.3, в). Рис.2.3. Графическое представление предикатов
В качестве аргументов предикатов можно использовать и функции, принимающие значения из предметной области. Например, функция Отец(х) пусть абстрагирует предложение естественного языка “ Отец человека по имени х ”. Тогда Любит(Отец(Отец(х)),у) - тоже предикат, он будет принимать истинное значение на паре <Мэри, Джон>, если дедушка Мэри действительно любит Джона. Итак, в отличие от логики высказываний, в которой структура простейших утверждений не анализируется (они там называются атомами), в логике предикатов атомный предикат имеет структуру. Определение 2.8. Термом будем называть переменную или константу предметной области М, или функцию, принимающую значения в предметной области. Атомный предикат - это n-местная функция F(t1,...,tn), принимающая значение в множестве { True, False }, где ti - термы. ÿ Введем понятие формулы - комбинации простейших утверждений. Определение 2.9. Правильно построенные формулы (ППФ) логики предикатов - это комбинация атомных предикатов и констант с логическими связками. Они определяются рекурсивно над множеством атомных предикатов с помощью символов операций (связок) Ø, Þ, скобок и одной дополнительной связки ", которая читается “ для всех ”. Рекурсивно ППФ определяются так:
1. Логические константы True, False есть формулы. 2. Атомный предикат есть формула. 3. Если Р - формула, то Ø(Р) тоже формула. 4. Если Р, Q - формулы, то (PÞQ) - тоже формула. 5. Если Р - формула, то ("х)Р тоже формула. 6. Никаких других формул в логике предикатов нет. Фактически, добавлением в логике предикатов по сравнению с логикой высказываний является то, что предикаты обычно не имеют фиксированного истинностного значения, их истинность различна для разных значениях их аргументов. В качестве единственной новой логической связки в логике предикатов используется связка ". В логике предикатов для сокращения формул используются записи: PÚQ для (ØP)ÞQ, P&Q для Ø(Ø(P)Ú(ØQ)), PÛQ для (PÞQ)&(QÞP), ($х)Р для Ø(("х)ØP). ÿ Новые логические связки " - “ для всех ” и $ - “ существует ” называются кванторами: " - “квантор всеобщности” и $ - “квантор существования”. Формула ("х)Р(х) читается так: “Для всех х выполняется Р(х)”. Очевидно, что это уже не предикат, это константа True либо False, в зависимости от того, действительно ли для каждого элемента х предметной области высказывание Р(х) истинно. Аналогично, логической константой является ($х)Р(х), что читается так: “Существует такое х, что для него выполняется Р(х)”. Для конечной предметной области значения этих связок очевидны. Пусть на М ={x1,x2,...,xn} определен произвольный предикат Р(х). Тогда очевидно: ("х)Р(х) = Р(х1)&Р(х2)&...&Р(хn)=&хÎ М Р(х); ($х)Р(х) = Р(х1)ÚР(х2)Ú...ÚР(хn) =ÚхÎ М Р(х). Пример 2.9. Пусть Р(х) - предикат, определенный на множестве всех людей и означающий “ х является студентом”. Тогда ("х) Р(х) ложно, а ($х) Р(х) истинно. Формула ("х) Любит(х, Отец(Отец(Джон))) истинна, если все любят дедушку Джона, а формула ($х) [Р(х) ÞØ Любит(Отец(Джон), х)] истинна, если отец Джона не любит хотя бы одного студента. Далее, если R(x,y) - предикат, определенный на множестве всех семейных людей и означающий “х и у - супруги”, то ("х)($y)R(х,y) ¹ ($y)("х)R(х,y). Первая формула истинна, вторая - ложна. ÿ Свободные и связанные переменные. Область действия переменной, указанной в кванторе, если она не очевидна, определяется скобками, например: G(x,z) = ("t)[Р(t,z)Ú("u)($y)Q(t,y,u)]Þ("r)R(x,r). Переменная связана, если она находится в области действия квантора. Связанные переменные можно заменять, если это не приводит к изменению смысла формулы. Например, предыдущая формула эквивалентна такой: G(x,z) = ("х)[Р(х,z)Ú("z)($y)Q(x,y,z)]Þ("z)R(x,z). Интерпретации. Формула логики предикатов является только схемой высказывания. Формула имеет определенный смысл, т.е. обозначает некоторое высказывание естественного языка, если существует какая-либо ее интерпретация. Интерпретировать формулу - это значит связать с ней непустое множество М (конкретизировать предметную область), а также указать соответствие: - каждой предметной константе конкретный элемент из М; - каждой n-местной функциональной букве в формуле конкретную n-местную функцию на М; - каждой n-местной предикатной букве в формуле конкретное отношение между n элементами области интерпретации М. На каждой интерпретации формула логики предикатов должна принять конкретное значение, True или False.
Рассмотрим, например, элементарную формулу G(f(a,b),g(a,b)) и следующую ее интерпретацию: - М - множество действительных чисел; - а, b - числа 2 и 3 соответственно; - f - функция сложения аргументов; - g - функция умножения аргументов; - G - отношение " не меньше ". При такой интерпретации приведенная формула обозначает высказывание: " сумма 2+3 не меньше произведения 2*3 ", что неверно. Следовательно, G(f(a,b),g(a,b)) на этой интерпретации равна False. На измененной интерпретации, когда в качестве а и b мы выберем 2 и 1, G(f(a,b),g(a,b))= True. Две формулы логики предикатов эквивалентны, если они принимают одинаковые истинностные значения на всех возможных интерпретациях. В отличие от логики высказываний, значения формул логики предикатов уже нельзя определить на основе таблиц истинности на всех возможных интерпретациях: предметная область может быть бесконечной. Единственный способ определить эквивалентность формул - использовать аналитические преобразования на основе установленных эквивалентностей. Это и составляет основную трудность и качественное отличие этой модели от логики высказываний. Эквивалентности логики предикатов. (а) Комбинация кванторов: 1. ("х)("y)P(х,y) = ("y)("х)P(х,y); 2. ($х)($y)P(х,y) = ($y)($х)P(х,y); 3. ("х)($y)P(х,y) ¹ ($y)("х)P(х,y). Свойства (а) 1 и 2 аналогичны свойствам коммутативности дизъюнкции и конъюнкции. Свойство 3 доказано в примере 2.9. Оно говорит о том, что перестановка местами кванторов существования и общности меняет смысл высказывания, а в общем случае, конечно, и значение его истинности. (б) Комбинация кванторов и отрицаний: 1. Ø("х)P(х) = ($х)ØP(х); 2. Ø($х)P(х) = ("х)ØP(х). Свойства (б) непосредственно следуют из определения квантора $. Это аналог теорем де Моргана. Пример 2.10. Афоризм Козьмы Пруткова “Нет столь великой вещи, которую не превзошла бы величиною еще большая …” ([П82]) формально в виде предиката может быть записан так: Ø($ х Ø$ уР (у,х)), где х и у принимают значения в множестве всех вещей, а утверждение Р(а, b) означает “ Вещь а превосходит величиной вещь b ”. Этот предикат эквивалентен такому: (" х $ уР (у,х)), что дает эквивалентную формулировку этого афоризма, менее замысловатую: “ Для любой вещи всегда найдется большая ”. ÿ (в) Расширение области действия кванторов (Q не зависит от х): 1. ("х)P(х)ÚQ = ("х)[P(х)ÚQ]; 2. ($х)P(х)ÚQ = ($х)[P(х)ÚQ]; 3. ("х)P(х)&Q = ("х)[P(х)&Q];
4. ($х)P(х)&Q = ($х)[P(х)&Q]. Эти свойства являются следствием свойств коммутативности и дистрибутивности дизъюнкции и конъюнкции. (г) Расширение области действия кванторов (Q зависит от х): 1. ($х)P(х)Ú($х)Q(x) = ($х)[P(х)ÚQ(x)]; 2. ("х)P(х)&("х)Q(x) = ("х)[P(х)&Q(x)]; 3. ($х)[P(х)&Q(x)] Þ ($х)P(х)&($х)Q(x); 4. ("х)P(х)Ú("х)Q(x) Þ ("х)[P(х)ÚQ(x)]. Свойства (г) 2 и 4 являются следствием свойств 1 и 3 и выводятся с применением теоремы де Моргана. Свойство 1 иллюстрируется следующим высказыванием, обе части которого эквивалентны: “ Среди нас есть английский шпион, или же среди нас - японский шпион. Да, в наши ряды затесался английский или японский шпион. ”. Свойство 2 иллюстрирует следующее высказывание, обе части которого, очевидно, тоже эквивалентны: “ Все - летчики, и все - герои. Каждый - и летчик, и герой ”. Высказывание: “ Есть у нас комсомолки, спортсменки, красавицы ” более сильное, чем высказывание: “ Есть у нас комсомолки, есть и спортсменки, есть и красавицы ”, потому что второе не обязательно означает, что перечисленными качествами: “ быть комсомолкой, спортсменкой и красавицей ” обладает одно лицо (свойство 3). В математике часто используются предикаты, различные переменные которых определены на разных множествах значений. Кванторы существования и всеобщности для таких переменных могут сопровождаться указанием того множества значений, на котором переменная определена. Определение 2.10. Ограниченным предикатом называется предикат, определенный не на всей предметной области, а на множестве объектов, удовлетворяющих дополнительному условию. Простейшие примеры ограниченных предикатов - ("хÎХ)Р(х) и ($хÎХ)Р(х), что имеет смысл: “ для всех х, принадлежащих множеству Х, справедливо Р(х) ” и “ существует такое х, принадлежащее множеству Х, для которого справедливо Р(х) ”. Очевидно, что предикат ("хÎХ)Р(х) эквивалентен ("х) (хÎХ)ÞР(х) и ($хÎХ)Р(х) эквивалентен ($х)(хÎХ)&Р(х). Более общо, иногда удобно записывать предикаты относительно объектов, удовлетворяющих дополнительному условию, например: ("х: R(x))Р(х) и ($х: R(x))Р(х). Первое из них читается: “ для любого х, удовлетворяющего условию R(x), справедливо Р(х) ”, а второе: “ существует х, удовлетворяющее условию R(x), для которого справедливо Р(х) ”. Эти ограниченные предикаты эквивалентно можно представить: ("х: R(x))Р(х) º ("х) R(x)ÞР(х) и ($х: R(x))Р(х) º ($х) R(x)&Р(х). ÿ. Теорема 2.7. Для ограниченных предикатов выполняются законы де Моргана: Ø("хÎХ)Р(х) = ($хÎХ)ØР(х); Доказательство этой теоремы остается в качестве упражнения (задача 2.23). ÿ Пример 2.11. Формальным выражением того факта, что массив х1, х2,..., хn упорядочен по возрастанию, является предикат ("iÎ{1,...,n-1}) хi£хi+1, что словесно звучит так: “Любой последующий элемент массива не больше предыдущего элемента”. Выразим формально отрицание этого факта, т.е. утверждение, что этот массив не упорядочен по возрастанию:
Ø("iÎ{1,...,n-1}) хi£хi+1 º ($iÎ{1,...,n-1})Ø(хi£хi+1) º ($iÎ{1,...,n-1})хi>хi+1. Таким образом, противоположное утверждение звучит так: “Существует пара соседних элементов массива, из которых последующий меньше предыдущего”. ÿ Пример 2.12. Определение достижимого состояния конечного автомата записывается так: “ Состояние s конечного автомата является достижимым тогда и только тогда, когда существует такая входная цепочка, что под ее воздействием автомат переходит в это состояние из начального состояния s0 ”. В виде предиката это записывается короче: Достижимо (s)Û($aÎX*)d*(s0,a)=s. Исходя из этого определения, определим понятие недостижимого состояния конечного автомата. В виде предиката это записывается так: Недостижимо (s)ÛØ[($aÎX*)d*(s0,a)=s]. Отсюда: Недостижимо (s) Û("aÎX*) Ø[d*(s0,a)=s] или, что то же: Недостижимо (s)Û("aÎX*)d*(s0,a)¹s. В словесной формулировке: “ Состояние s конечного автомата недостижимо тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние из начального состояния s0 ”. ÿ Пример 2.13. Существует теорема p»k+1q Û ("хÎХ) [d(p,х)»k d(q,х) & l(p,х) = l(q,х)] (здесь p»kq обозначает утверждение “состояние p k-эквивалентно состоянию q”, а Øp»kq обозначает утверждение “состояния p и q k-различимы ”. Доказательство необходимости состоит в том, что нужно показать p»k+1q Þ ("хÎХ) [d(p,х)»k d(q,х) & l(p,х) = l(q,х)]. Доказательство этого более простого утверждения проводится от противного, т.е. доказывается его контрапозиция: ($хÎХ)[Ød(p,х)»kd(q,х)Úl(p,х)¹l(q,х)]ÞØp»k+1q. Из свойств предикатов легко показывается, что эта формула эквивалентна конъюнкции двух утверждений: ($хÎХ)[Ød(p,х)»kd(q,х)]ÞØp»k+1q и ($хÎХ)[l(p,х)¹l(q,х)]ÞØp»k+1q. Словами это можно сказать так: “Если существует такой элемент х из Х, что состояния d(p,х) и d(q,х) k-различимы, то р и q являются k+1- различимыми” и: “Если существует такой элемент х из Х, что l(p,х) не равно l(q,х), то состояния р и q являются k+1- различимыми”. ÿ
|
|||||||||
Последнее изменение этой страницы: 2016-08-16; просмотров: 130; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.224.73.125 (0.042 с.) |