Алгебра логики высказываний

Вид материала

Документы

Содержание Логика предикатов Объектные константы Объектные переменные Предикатный символ Аксиомы, теоремы, факты и цели Переход от естественного языка к языку логики предикатов Предваренная нормальная форма Исчисление предикатов

Подобный материал:

• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.
• Лекция Логические основы компьютеров , 369.25kb.
• Алгебра логики. Определение формы сложных высказываний, построение таблиц истинности, 132.48kb.
• Функции алгебры логики, 47.25kb.
• Алгебра логики и логические основы компьютера Алгебра логики (булева алгебра), 39.45kb.
• Программа дисциплины Математическая логика Семестр, 13.41kb.
• Логика высказываний. Основные понятия и определения. Логические функции одной и двух, 6.36kb.
• Основы математической логики. Алгебра логики (булева алгебра), 59.39kb.
• Программа курса «Математическая логика и теория алгоритмов», 37.76kb.
• 1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции., 38.38kb.

Логика предикатов

В алгебре логики высказываний собственно высказывания рассматриваются как неразделимые целые и только лишь с точки зрения их истинности или ложности. Стуктура высказываний или их содержание не рассматриваются. Другим недостатком логики высказываний является ее многословность – даже для описания простых ситуаций требуется значительное количество логических переменных и формул.


Главная идея логики предикатов заключается во взаимнооднозначном сопоставлении каждого уникального объекта с индивидуальной объектной константой, обозначаемой именем объекта, а класс однотипных объектов – с объектной переменной, значением которой являются объектные константы.


Например, рассмотрим высказывание «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) – функция:

X = Y	Истинно, если константы именуют один и тот же объект
x = Y	Истинно, если значение переменной равно константе
x = y	Истинно, если значения переменных совпадают
X = F(Y)	Истинно, если значение функции совпадает с константой
X = F(y)
x = F(Y)	Истинно, если значение функции совпадает со значением переменной
x = F(y)

Аксиомы, теоремы, факты и цели

В логике высказываний были введены понятия интерпретация, общезначимость, модель и выводимость. Аналогичные понятия есть и в логике предикатов. Аксиомами называют такие формулы, для которых среда является моделью при всех интерпретациях, или формулы, которые истинны при любых значениях входящих в них переменных. Аксиомы, являющиеся литералами (атомы с отрицанием или без), все аргументы которых константы, называют фактами. Аксиомы не являющиеся фактами называют правилами. Основная задача в логике предикатов – вывод на основании истинных фактов и правил целевых формул, называемых теоремами.

Переход от естественного языка к языку логики предикатов

Рассмотрим пример. Предположим, что наши знания о птицах выражены в виде следующих предложений:

• Если существо имеет крылья, то это существо – птица.
  

• Если существо летает и несет яйца, то это существо – птица.
  

Для представления знаний на языке логики предикатов следует выполнить следующие шаги:

1. Выявить, что во фразе является объектом, который необходимо сопоставить с константой или переменной. Если речь идет о конкретном объекте, то вводится константа, если же упоминается целый класс объектов, то используют переменную.
   
2. Определить свойства объектов. Сопоставить свойствам предикатные символы.
   
3. С помощью логических связок сформировать формулы констант, переменных и предикатов, соответствующих объектам и их свойствам.
   

Таким образом, на языке логики предикатов эти знания могут быть выражены в виде формул:

• имеет_крылья(существо)  птица(существо)
  
• летает(существо)  несет_яйца(существо)  птица(существо)
  

В данном примере использованы одноместные предикаты, имеющие по одному аргументу. Но предикаты могут быть также и многоместными, то есть иметь несколько аргументов. В случае многоместных предикатов предикатный символ может рассматриваться как некоторое общее свойство объектов, соответствующих аргументам, либо как отношение, в котором эти объекты находятся.

Предваренная нормальная форма

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


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

(x₁) (x₂) … (x_n) A(x₁, x₂, …, x_m), n  m,

где под символом  понимается один из кванторов:  или .


Существует теорема утверждающая, что любая формула логики предикатов может быть приведена к предваренной нормальной форме.

Примеры

Одной из задач логики предикатов является поиск областей истинности предикатов – множества значений аргументов, на которых предикат принимает истинные значения. Пусть, к примеру, даны предикаты: P(x): «x – четное число» и Q(x): «x кратно 3», определенные на множестве натуральных чисел N. Областями истинности P(x) и Q(x) соответственно являются I_P = {2, 4, 6, …, 2n…}, I_Q = {3, 6, 9, …, 3n…}. Найдем области истинности для следующих предикатов:

1. P(x)  Q(x): множеством истинности конъюнкции будет пересечение множеств истинности конъюнктов – I_PQ = I_P  I_Q = {6, 12, …, 6n…}
   
2. P(x)  Q(x): множеством истинности дизъюнкции будет объединение множеств истинности дизъюнктов – I_PQ = I_P  I_Q = {2, 3, 4, 6, …, 2n , 3n…}
   
3. P(x): множеством истинности отрицания будет исключение множества истинности предиката из множества его определения – I_P = N \ I_P = {1, 3, 5, …, 2n - 1,…}
   
4. P(x)  Q(x): множеством истинности импликации (логического следствия) будет объединение множества истинности отрицания первого дизъюнкта и множества истинности второго дизъюнкта (так как a  b =  a  b) – I_PQ = I_P  I_Q = {1, 3, 5, …, 2n - 1,…}  {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 = (x) (P(x)  Q(x))   (x) (P(x)  (x) Q(x)).

Считая, что формула 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   x = 1

= (x) [(P(x)   P(x))  (Q(x)   P(x))  (x)  Q(x)] =

= (x) [(1  (Q(x)   P(x)))  (x)  Q(x)] =

на основании закона x  1 = 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,

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

α   ├ α   (х) (х),

α   ├  (х) α (х)  .


Существуют также и неклассические исчисления предикатов первого порядка. Они могут строиться на дополнении множества аксиом специфическими для данной предметной области общезначимыми формулами. Также могу использоваться следующие правила вывода:

Исключение квантора общности  (х) α(х) ├ α(х | А),

Исключение квантора существования  (х) α (х) ├ α(х | А),

Введение квантора существования α (А) ├  (х) α(х | А).

Здесь α(х) – произвольная формула логики предикатов, имеющая связанную квантором переменную х, α(х | А) – формула α(х), в которой все вхождения переменной х заменены на константу А.