Исчисление высказываний

Лекция 3 Исчисление высказываний Исчисление высказываний и исчисление предикатов – это прежде всего языки. Используя их слова, фразы и предложения, мы можем представлять свойства и отношения в окружающем мире и рассуждать о них. Символы исчисления высказываний -Символы исчисления высказываний – это символы высказываний P, Q, R, S, …, -Значения истинности true (истина), false (ложь) -Логические связки , , , , Символы высказываний составляют высказывания или утверждения относительно некоторого мира. Они могут быть как истинны, так и ложны, например, «автомобиль красный» или «вода мокрая». В исчислении высказываний предложения формируются из элементарных символов согласно следующим правилам. Предложения исчисления высказываний Предложения Пример Каждый логический символ и символ истинности являются предложением true, P, Q и R Отрицание предложения есть предложение P, false Конъюнкция (логическое умножение), или операция И, двух предложений есть предложение P P Дизъюнкция (логическое сложение), или операция ИЛИ, двух предложений есть предложение P P Импликация (включение) одного предложения в другое есть предложение PQ Эквивалентность двух предложений есть предложение PQR В выражениях вида PQ элементы P и Q называются конъюнктами. В выражениях вида PQ элементы P и Q называются дизъюнктами. В импликации PQ, P – предпосылка (антецедент), а Q – заключение (консеквент). В предложениях исчисления высказываний скобки () и [] используют для группировки символов в подвыражения и, таким образом, дают возможность управлять порядком их оценки и присваивания значений. Например, (PQ)R отличается от P(QR). Выражение является предложением, когда оно может быть сформулировано в виде некоторой последовательности допустимых символов, например: ((PQ)R)PQR является правильно построенным предложением, поскольку: P, Q, и R – высказывания и поэтому предложения; PQ – конъюнкция двух предложений, поэтому является предложением; (PQ)R – импликация одного предложения в другое, т.е. предложение; P и Q – отрицания предложений, являющиеся предложениями; PQ – дизъюнкция двух предложений, поэтому является предложением; PQR – дизъюнкция двух предложений, т.е. предложение; ((PQ)R)PQR – эквивалентность двух предложений, являющаяся предложением. Получили предложение, которое было построено путём применения ряда правил. Семантика предложений Семантика предложений представляет собой значение этих предложений. Символ предложения соответствует утверждению относительно мироздания. Например, P может обозначать высказывание «идёт дождь», а Q – высказывание «я живу в коричневом доме». Предложение, давая некоторое описание мира, может быть как истинным, так и ложным. Присвоение значения истинности логическим предложениям называется интерпретацией. Формально интерпретация – это отображение логических символов на множество {T, F}(true – истина, false – ложь). Например, если P обозначает высказывание «идёт дождь», а Q – «я на работе», то набор высказываний {P, Q} имеет четыре различных варианта в таблице истинности {T, F}. Семантика исчисления высказываний Интерпретация набора высказываний – это присвоение значения истинности, T или F, каждому символу. Символу true всегда присваивается T, а символу false – F. Отрицание: высказывание P есть F, если P имеет значение T. И высказывание P есть T, если P имеет значение F. Конъюнкция: высказывание имеет значение T, только если оба конъюнкта имеют значение T, иначе выражение имеет значение F. Дизъюнкция: высказывание имеет значение F, только если оба дизъюнкта имеют значение F, иначе выражение имеет значение T. Импликация: высказывание имеет значение F только тогда, когда предпосылка (символ перед импликацией) есть T, и значение истинности следствия (символ после импликации) есть F, иначе выражение имеет значение T. Эквивалентность: высказывание имеет значение T только тогда, когда оба выражения имеют одинаковое значение истинности, иначе выражение имеет значение F. Значения истинности сложных выражений часто описываются таблицами истинности. Таблица истинности содержит все возможные варианты значения истинности для элементарных суждений, составляющих большие выражения, и задаёт значение истинности выражениям для каждой возможной интерпретации данного выражения. Например, таблица истиности для PQ даёт значения истинности выражения для каждого возможного значения операнда. Выражение PQ истинно только тогда, когда и P, и Q имеют значение T. Закон контрапозиции импликации: PQ(QP) Закон Моргана: (PQ)(PQ) и (PQ)(PQ) Законы коммутативности: (PQ)(QP) и (PQ)(QP) Ассоциативный закон: ((PQ)R)(P(QR)) Ассоциативный закон: ((PQ)R)(P(QR)) Дистрибутивный закон: P(QR)(PQ)(PR) Дистрибутивный закон: P(QR)(PQ)(PR) Эти тождества могут быть использованы для приведения выражения исчисления высказываний к синтаксически различным, но логически эквивалентным формам. Пример таблицы истинности: P Q P PQ PQ (PQ)(PQ) T T F T T T T F F F F T F T T T T T F F T T T T Исчисление предикатов В исчислении высказываний каждый элементарный символ (P, Q и т.д.) обозначает высказывание некоторой сложности. При этом не существует способа получить доступ к компонентам отдельного суждения. Исчисление предикатов предоставляет эту возможность. Например, вместо того, чтобы разрешить единственный символ высказывания P, обозначив всё предложение «во вторник шёл дождь», мы можем создать предикат погода, который описывает отношения между датой и погодой: погода(вторник, дождь). Посредством правил вывода можно изменять выражения исчислений предикатов, непосредственно обращаясь к их компонентам и выводя новые предложения. Кроме того, исчисление предикатов позволяет включать в выражения переменные. Переменные помогают создавать обобщённые утверждения относительно классов логических объектов. Например, можно заявить, что для всех значений X, где X – день недели, утверждение погода(X, дождь) есть истина; т.е. каждый день идёт дождь. Синтаксис предикатов Алфавит исчисления предикатов состоит из следующих элементов. 1. Набор букв английского алфавита как верхнего, так и нижнего регистра. 2. Набор цифр – 0, 1, …, 9 3. Символ подчёркивания _. Символы в исчислении предикатов начинаются с буквы, за которой следует последовательность перечисленных выше знаков. Пример допустимых знаков в алфавите исчисления предикатов. a R 6 9 p _ z Пример недопустимых знаков в алфавите исчисления предикатов. # % @ / & “ “ Пример допустимых символов исчисления предикатов. George fire3 tom_and_jerry bill XXXX friends_of Пример строк, содержащих неразрешённые знаки. 3jack “no blanks allowed” ab%cd ***71 duck!!! Символы (или идентификаторы) используются для обозначения объектов, свойств или отношений в области рассуждения. Символы исчисления предикатов могут представлять переменные, константы, функции или предикаты. Константами называют определенные объекты или свойства из области рассуждения. Исчисление предикатов также допускает существование функций для объектов из некоторой области рассмотрения. Функции обозначают отображение одного или нескольких элементов множества (называемого областью определения функции) в однозначно определяемый элемент другого множества (множества значений функции). Каждый функциональный символ связан с арностью, указывающей на количество параметров этой функциональной зависимости. Так, например, символ father мог бы обозначать функцию арности 1, которая позволяет определить отца, а plus мог бы быть функцией арности 2, которая отображает два числа в их арифметическую сумму. Примеры функциональных выражений. f(X, Y) father(david) price(bananas) Каждое функциональное выражение обозначает отображение аргументов в единственный объект множества значений, называемый значением функции. Например, если father – это унарная функция, то father(david) является функциональным выражением, значением которого может быть, например, george. Если plus – это функция арности 2, определенная на множестве целых чисел, то plus(2,3) является функциональным выражением, значением которого является целое число 5. Замена функции её значением называется её оцениванием. К символам исчисления предикатов относятся 1. Символы истинности true и false. 2. Символы констант 3. Символы переменных 4. Функциональные символы Функциональное выражение состоит из функциональной константы арности n, за которой следуют n термов , , …, , заключенных в круглые скобки и отделенных друг от друга запятыми. Термом исчисления предикатов обозначают объекты и свойства из области определения данной задачи. Примеры термов: cat times(2, 3) X blue mother(jane) kate Предикат указывает на отношение между несколькими объектами (в том числе и между нулевым числом объектов). Количество объектов определяет арность предиката. Атомарное высказывание – самая примитивная единица языка исчислений предикатов, является предикатом арности n, за которым следует n термов, заключённых в круглые скобки и разделённых запятыми. Примеры атомарных высказываний: likes(george, kate) friends(father_of(david), father_of(andrew)) символами предикатов в этих выражениях являются likes и friends Можно комбинировать атомарные предложения и формировать предложения в исчислении предикатов, использую логические операторы. , , , , Исчисление предикатов первого порядка включает два символа: кванторы переменных , . Они ограничивают значение предложения, содержащего переменную. Квантор всеобщности означает, что предложение истинно для всех значений переменной. Пример: X likes(X, ice_cream) означает следующее. Выражение истинно для всех значений X в области определения X. Квантор существования указывает, что предложение истинно по крайней мере для одного значения в области определения. Пример: Y friends(Y, peter) означает следующее. Выражение истинно, если имеется по крайней мере один объект Y, который является другом Питера. Предложения исчисления предикатов: 1. Если s – предложение, то его отрицание s тоже является предложением 2. Если s1 и s2 – предложения, то их конъюнкция s1s2 тоже является предложением 3. Если s1 и s2 – предложения, то их дизъюнкция s1s2 тоже является предложением 4. Если s1 и s2 – предложения, то их импликация s1s2 тоже является предложением 5. Если s1 и s2 – предложения, то их эквивалентность s1s2 тоже является предложением 6. Если X – переменная и s предложение, то X s есть предложение 7. Если X – переменная и s предложение, то X s есть предложение Пример использования исчисления предикатов. Рассмотрим модель простого мира. Рассматриваемая область определения – набор семейных отношений в библейской генеалогии. mother(eve, abel) mother(eve, cain) father(adam, abel) father(adam, cain) XY father(X, Y)mother(X, Y)parent(X, Y) XYZ parent(X, Y)parent(X, Z)sibling(Y, Z) В примере для определения набора отношений родителей и детей использованы предикаты mother и father. В терминах этих предикатов импликация даёт общее определение других отношений, в том числе родительских и братских. Семантика исчисления предикатов Семантика исчисления предикатов обеспечивает основу для определения значений истинности корректно построенных выражений. Истинность выражений зависит от соответствия констант, переменных, предикатов и функций объектам и отношениям в области определения. Из истинности отношений в области определения следует истинность соответствующих выражений. Пример: Информация относительно некоторого человека Джорджа и его друзей Кейт и Сьюзи может быть выражении так. friends(george, susie) friends(george, kate) Если Джордж друг Сьюзи и Кейт, то каждое из этих выражений будет иметь значение истинности T. Если Джордж – друг Сьюзи, но не Кейт, то первое выражение будет иметь значение истинности T, а второе – значение истинности F. Чтобы использовать исчисление предикатов для решения задач, объекты и отношения в интерпретируемой области определения описываются с помощью набора корректных выражений. Термы и предикаты этих выражений обозначают объекты и отношения в области определения. Так формируется база данных выражений исчисления предикатов, каждое из которых, имея значение истинности T, описывает «состояние мира». Описание Джорджа и его друзей – это простой пример такой базы данных. Другой пример – мир блоков, описанный в лекции 1. Определим интерпретацию в области определения Пусть область определения D – некоторое непустое множество Интерпретация на D – это связывание логических объектов их D с каждой константой, переменной, предикатом и функциональным символом в выражении исчисления предикатов на основе следующих правил. 1. Каждой константе ставится в соответствие элемент из D. 2. Каждой переменной ставится в соответствие непустое подмножество из D; оно является областью допустимых значений для этой переменной 3. Каждая функция f арности m определяется для m параметров из D и задает отображение из D в D. 4. Каждый предикат p арности n определяется для n параметров из D и задает отображение из D в {T, F}. Значение истинности выражений исчисления предикатов Пусть существует выражение E и интерпретация I для E на непустой области определения D. Значение истинности для E определяется так. 1. Значение константы – это элемент из D, которому соответствует данная константа в интерпретации I. 2. Значение переменной – это множество элементов из D, которые соответствуют данной переменной в интерпретации I. 3. Значение функционального выражения – это такой элемент из D, который получается в результате оценивания функции для значений параметров, соответствующих интерпретации. 4. Значение символа истинности true – это T, а false – F. 5. Значение атомарного предложения равно либо T, либо F, и определяется интерпретацией I. 6. Значение отрицания предложения равно T, если значение предложения равно F; и значение отрицания предложения равно F, если значение предложения равно T. 7. Значение конъюнкции двух предложений равно T, если оба предложения принимают значение T, иначе оно равно F. 8. Значение истинности выражений, использующих операции , , и , определяется значениями их операндов. Для переменной X и предложения S, содержащего X, выполняются следующие соотношения. 9. Значение выражения X S равно T, если S равно T для всех значений X из I, иначе оно равно F. 10. Значение X S равно T, если в интерпретации существует значение X, для которого S равно T; иначе оно равно F. В исчислении предикатов переменная может быть замещена любыми допустимыми константами. Таким образом, переменная является шаблоном для подстановки. В исчислении предикатов переменные должны быть связаны одним из двух кванторов: универсальности или существования. Переменная считается свободной, если она не связана квантором универсальности или существования. Выражение считается замкнутым, если все его переменные связаны кванторами. В исчислении предикатов все переменные должны быть связаны кванторами. Для обозначения квантора всеобщности применяется символ . Для указания области действия квантора, т.е. выделения имен переменных, на которые распространяется действие квантора, часто используются круглые скобки. Пример: X(p(X)q(Y)r(X)) Отсюда ясно, что переменная X связана квантором всеобщности в p(X) и в r(X). Квантор всеобщности усложняет вычисление значения истинности предложения, потому что для определения истинности выражения необходимо проверить все возможные значения переменной. Пример: X likes(george, X), где переменная X задана на множестве всех людей, необходимо проверить все возможные значения X. Если область определения интерпретации бесконечна, исчерпывающая проверка всех подстановок переменной, связанной квантором всеобщности, в вычислительном отношении невозможна, так как алгоритм никогда не остановится. Из-за этой проблемы исчисление предикатов считают неразрешимым. Переменные также могут быть связаны квантором существования. В этом случае выражение с переменной считается истинным, если оно истинно по крайней мере для одного значения из области определения переменной. Квантор существования обозначается . Область действия квантора существования также задается круглыми скобками, в которых все вхождения переменной считаются связанными этим квантором. Анализ истинности выражения, содержащего переменную, связанную квантором существования, может оказаться не проще, чем оценивание выражений, содержащих переменные под квантором всеобщности. Предположим, необходимо определить истинность выражения. Для этого можно подставлять в него различные значения каждой переменной, пока не будет найдено такое, которое делает выражение истинным. Если область определения переменной бесконечна, и выражение ложно при всех подстановках значений, алгоритм никогда не завершится. Приведём несколько примеров взаимосвязи между операцией отрицания и кванторами всеобщности и существования. X p(X)Xp(X) X p(X)Xp(X) X p(X)Y p(Y) X q(X)Yq(Y) X (p(X)q(X))X p(X)Y q(Y) X (p(X)q(X))Xp(X)Y q(Y) На определенном нами языке переменные, связанные квантором всеобщности и квантором существования, могут ссылаться только на объекты из рассматриваемой области определения. Имена предикатов и имена функций не могут быть замещены именами переменных, стоящих под знаком квантора. Этот язык называется исчислением предикатов первого порядка. Исчисление предикатов первого порядка Исчисление предикатов первого порядка позволяет связывать знаком квантора переменные, соответствующие объектам из предметной области, но не предикаты или функции. Пример: (likes)likes(george, kate) Данная запись не является правильно построенным выражением в исчислении предикатов первого порядка. Существуют исчисления предикатов высших порядков, в которых такие выражения поддаются интерпретации. Примеры предложений, представленных исчислением предикатов: Если в понедельник не будет дождя, Том пойдёт в горы weather(rain, monday)go(tom, mountains) Эмма – это доберман-пинчер и хорошая собака gooddog(emma)isa(emma, doberman) Все баскетболисты – высокие X (basketball_player(X)tall(X)) Некоторые люди любят анчоусы X (person(X)likes(X, anchovies)) Никто не любит налоги X likes(X, taxes)