Алгебра логики высказываний Основные понятия
жүктеу/скачать 0.9 Mb.
|
- Бұл бет үшін навигация:
- Объектные константы
- Объектные переменные
- Предикатный символ
- Аксиомы, теоремы, факты и цели
- Переход от естественного языка к языку логики предикатов
- Предваренная нормальная форма
- Исчисление предикатов
Логика предикатовВ алгебре логики высказываний собственно высказывания рассматриваются как неразделимые целые и только лишь с точки зрения их истинности или ложности. Стуктура высказываний или их содержание не рассматриваются. Другим недостатком логики высказываний является ее многословность – даже для описания простых ситуаций требуется значительное количество логических переменных и формул. Главная идея логики предикатов заключается во взаимнооднозначном сопоставлении каждого уникального объекта с индивидуальной объектной константой, обозначаемой именем объекта, а класс однотипных объектов – с объектной переменной, значением которой являются объектные константы. Например, рассмотрим высказывание «7 – простое число». Эту фразу в логике высказываний можно представить с помощью логической переменной, предположим a. Для того, чтобы представить на языке логики другое высказывание «13 – простое число» понадобится другая переменная. Таким образом, для описания простых чисел нам понадобится столько логических переменных, сколько существует простых чисел. На языке логики предикатов эта фраза может быть представлена так: простое_число(7). А весь набор подобных фраз: простое_число(значение). В данном примере простое_число – это предикатный символ, 7 – объектная константа, а значение – объектная переменная. Предикатом называют высказывательную функцию, определенную на множестве наборов значений объектных переменных. Эта функция может принимать только два значения: Истина или Ложь, называемые истинностными значениями. Предикаты могут быть одноместными, если аргумент один, или многоместными – если аргументов несколько. Отношения между объектами среды, также как и в логике высказываний, представляются в виде предложений (формул), состоящих из переменных, констант, связок, скобок, а также функций, предикатов и кванторов. Объектные константыОбъектная константа или просто константа взаимнооднозначно сопоставляется в процессе интерпретации с каким-либо одним объектом и обозначается строкой символов, начинающихся с прописной буквы. Объектные переменныеОбъектные переменные или просто переменные обозначаются строкой, начинающейся со строчной буквы. Областью значений каждой переменной является множество констант, в общем случае бесконечное. ФункцииЕсли некоторый объект в точности соответствует множеству других, то используют функции. Например, если объектами являются двоичные цифры и десятичные цифры, то любому двоичному можно однозначно сопоставить десятичное, и выразить это сопоставление в виде функции преобразование_2_в_10(x, y, z), где x, y, z – двоичные числа, а значение функции – десятичное. Выражение преобразование_2_в_10 называют функциональным символом. Функция в логике предикатов не предполагает обязательного наличия алгоритма вычисления ее значения по аргументам. Она лишь задает с помощью констант и переменных определенное отношение между объектами, соответствующими ее аргументам, и каким-то одним объектом. ТермыКонстанты, переменные и функции являются темами. Как именно выбирать термы для представления знаний – решать разработчику. Рассмотрим, например, среду, состоящую из объектов птицы и крылья. Пусть, также, нам известно, что птицы имеют крылья. Введем константы, обозначающие конкретных птиц: Воробей, Синица, Голубь, и константу Крылья. Введем переменную х, определенную на множестве птиц. Функциональный символ имеет ставит во взаимно однозначное соответствие любой птице объект крылья. Функция имеет (х) задаёт отношение между объектом крылья и какой-либо птицей х. Если х = Воробей, то имеет (Воробей) = Крылья. Функция может и не содержать аргументов, то есть иметь один функциональный символ. Термы, не содержащие аргументов, то есть константы, переменные и функции без аргументов называют элементарными термами. Предикатный символКак и в случае с функцией предикаты начинаются с предикатного символа и следующими за ним в скобках упорядоченного набора переменных или констант, соответствующих объектам, которые находятся в поименованном отношении. С помощью предикатов задаются произвольные отношения между объектами, если аргументов несколько. Если аргумент только один, то предикат описывает свойство объекта, заданного аргументом. Так, например, если два человека Маша и Саша являются братом и сестрой, то это отношение может быть выражено с помощью предиката брат_сестра (Маша, Саша). Предикат может принимать значение Истинно или Ложь. Если предикат Истинен, то отношение имеет место, иначе – не имеет. Отношение между птицами и крыльями также может быть выражено с помощью предиката. Пусть предикат крылья(х) Истинен, если х имеет крылья, тогда при х = Воробей конструкция крылья(Воробей) будет представлять знания о том, что у Воробья есть крылья. АтомыВыражение предикатный_символ (терм, терм, …, терм) называют атомом. Атом представляет предикат. Особо выделяется атом, предикатным символом которого является знак равенства, а аргументами два терма. Этот атом можно было бы представить как равны (терм, терм) или = (терм, терм), но, как правило, его записывают в обычной инфиксной форме терм = терм. Этот атом истинен, когда значения обоих термов совпадают. Атомы без знака отрицания или со знаком отрицания называют литералами. КванторыКогда возникает необходимость выразить какие-либо свойства, общие для целого множества объектов, используют кванторы. В логике предикатов таких кванторов два: , . Квантор общности . Смысл квантора общности совпадает с выражением естественного языка «для всех». То есть, если имеется некоторое знание, применимое для любого объекта определённого типа, то вместо перечисления всех таких объектов можно использовать квантор общности. Например, тот факт, что для успешной учебы студенту необходимо вовремя получать зачеты можно выразить следующим образом: (x) студент(x) вовремя_сдает_зачеты(x) успешно_учится(x). Квантор существования . Если возникает необходимость выразить знание об отдельном объекте из какой-либо совокупности, используют квантор существования. Квантор существования произносится на естественном языке как «существует». Например, на любом факультете университета учится хотя бы один отличник. Эта фраза на языке предикатов выглядит следующим образом: (x) факультет(x) (y) учится(y, x) отличник(y). Взаимосвязь между кванторами. Считают, то квантор связывает переменные, которые записываются за знаком квантора в скобках. Поэтому их называют связанными. Переменные же, которые ни один квантор не связывает, называют свободными. Взаимосвязь между кванторами существования и общности можно легко выразить с помощью связки отрицания и она основана на следующем соображении: если про любой объект из совокупности можно сказать, что он не обладает заданным свойством, то не существует объекта, обладающего этим свойством. Например, очевидно, что «у любой лошади нет крыльев, значит, не существует лошади, у которой есть крылья». Обозначим любую переменную символом х, а любую формулу, содержащую эту переменную – Р(х), тогда справедливы следующие законы: (х) Р(х) (х) Р(х), (х) Р(х) (х) Р(х), (х) Р(х) (х) Р(х), (х) Р(х) (х) Р(х).
РавенствоРавенство является атомом особого типа Терм = Терм или =(Терм, Терм). Равенство означает, что оба терма в атоме соответствуют одному и тому же объекту. Не следует путать предикат равенства с операцией присваивания. В следующей таблице раскрыт смысл равенства для различных термов, где X, Y обозначают константы, x, y – переменные, а F(x) – функция:
Аксиомы, теоремы, факты и целиВ логике высказываний были введены понятия интерпретация, общезначимость, модель и выводимость. Аналогичные понятия есть и в логике предикатов. Аксиомами называют такие формулы, для которых среда является моделью при всех интерпретациях, или формулы, которые истинны при любых значениях входящих в них переменных. Аксиомы, являющиеся литералами (атомы с отрицанием или без), все аргументы которых константы, называют фактами. Аксиомы не являющиеся фактами называют правилами. Основная задача в логике предикатов – вывод на основании истинных фактов и правил целевых формул, называемых теоремами. Переход от естественного языка к языку логики предикатовРассмотрим пример. Предположим, что наши знания о птицах выражены в виде следующих предложений:
Для представления знаний на языке логики предикатов следует выполнить следующие шаги:
Таким образом, на языке логики предикатов эти знания могут быть выражены в виде формул:
В данном примере использованы одноместные предикаты, имеющие по одному аргументу. Но предикаты могут быть также и многоместными, то есть иметь несколько аргументов. В случае многоместных предикатов предикатный символ может рассматриваться как некоторое общее свойство объектов, соответствующих аргументам, либо как отношение, в котором эти объекты находятся. Предваренная нормальная формаФормула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторы, а операция отрицания отнесена к элементарным отрицаниям. Очевидно, что, используя равносильные преобразования, можно каждую формулу логики предикатов привести к нормальной форме. Среди нормальных форм особо важное значение имеет так называемая предваренная нормальная форма. В такой форме кванторы либо отсутствуют, либо они используются после всех операций алгебры логики и записываются перед формулой, то есть эта форма имеет вид: (x1) (x2) … (xn) A(x1, x2, …, xm), n m, где под символом понимается один из кванторов: или .
ПримерыОдной из задач логики предикатов является поиск областей истинности предикатов – множества значений аргументов, на которых предикат принимает истинные значения. Пусть, к примеру, даны предикаты: P(x): «x – четное число» и Q(x): «x кратно 3», определенные на множестве натуральных чисел N. Областями истинности P(x) и Q(x) соответственно являются IP = {2, 4, 6, …, 2n…}, IQ = {3, 6, 9, …, 3n…}. Найдем области истинности для следующих предикатов:
Следующий пример показывает, как с помощью логики предикатов можно отыскать утверждение, противоположное заданному, или, иначе говоря, отрицание заданной формулы. Найдем отрицание формулы (x) (y) R(x, y) L(x, y): ((x) (y) R(x, y) L(x, y)) = (x) ((y) R(x, y) L(x, y)) = = (x) (y) (R(x, y) L(x, y)) = (x) (y) (R(x, y) L(x, y)) = = (x) (y) (R(x, y) L(x, y)).
Считая, что формула A определена на любой области определения проведем равносильные преобразования: A = (x) (P(x) Q(x)) (x) (P(x) (x) Q(x)) = во второй части импликации изменяем квантор в соответствии с законами взаимосвязи между кванторами = (x) (P(x) Q(x)) (x) (P(x) (x) Q(x)) = переносим квантор общности в начало формулы, т.к. квантор одинаково связывает обе части импликации = (x) [(P(x) Q(x)) (P(x) (x) Q(x))] = на основании закона x y = x y = (x) [ (P(x) Q(x)) (P(x) (x) Q(x))] = = (x) [ ( P(x) Q(x)) (P(x) (x) Q(x))] =
= (x) [(P(x) Q(x)) P(x) (x) Q(x)] = = (x) [(P(x) Q(x)) P(x) (x) Q(x)] =
= (x) [(P(x) P(x)) (Q(x) P(x)) (x) Q(x)] = = (x) [(1 (Q(x) P(x))) (x) Q(x)] =
= (x) [Q(x) P(x) (x) Q(x)] = = (x) [Q(x) (x) Q(x) P(x)] = = (x) [(x) (Q(x) Q(x)) P(x)] = наконец, по закону x 1 = 1, имеем = (x) [1 P(x)] = 1. Исчисление предикатовВыше были рассмотрены исчисления логики высказываний, в частности классическое исчисление. Любое логическое исчисление должно включать:
Рассмотрим отличия исчисления предикатов первого порядка от исчислений высказываний. Аксиомы исчисления высказываний преобразуются в аксиомы исчисления предикатов путем замены α α(х), то есть логическая переменная α заменяется предикатом α(х). Кроме того, вводятся две новые аксиомы: (х) α(х) α(у), α (у) (х) α(х). Множество правил вывода включает: Правило Modus Ponens, и правила введения кванторов α ├ α (х) (х), α ├ (х) α (х) .
Введение квантора существования α (А) ├ (х) α(х | А). Здесь α(х) – произвольная формула логики предикатов, имеющая связанную квантором переменную х, α(х | А) – формула α(х), в которой все вхождения переменной х заменены на константу А. жүктеу/скачать 0.9 Mb. Достарыңызбен бөлісу:
|