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

Атомы

 

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

Кванторы

 

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

 

Квантор общности ". Смысл квантора общности совпадает с выражением естественного языка «для всех». То есть, если имеется некоторое знание, применимое для любого объекта определённого типа, то вместо перечисления всех таких объектов можно использовать квантор общности. Например, тот факт, что для успешной учебы студенту необходимо вовремя получать зачеты можно выразить следующим образом:

" (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. С помощью логических связок сформировать формулы констант, переменных и предикатов, соответствующих объектам и их свойствам.

 

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

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

 

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

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

 

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

 

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

s(x₁) s(x₂) … s(x_n) A(x₁, x₂, …, x_m), n £ m,

где под символом s понимается один из кванторов: " или $.

 

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

Примеры

 

Одной из задач логики предикатов является поиск областей истинности предикатов – множества значений аргументов, на которых предикат принимает  истинные значения. Пусть, к примеру, даны предикаты: 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,

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

α ® b ├ α ® " (х) b(х),

α ® b ├ $ (х) α (х) ® b.

 

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

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

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

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

 

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