МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Математическая логика

• Название: Математическая логика
• Анкор: МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.doc
• Дата: 05.04.2018
• Размер: 1.08 Mb.
• Имя файла: МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ.doc
• Тип: Документы; #17626
• Категория: Математика
• страница: 3 из 8

Примеры:

1) Р²(х, f¹(а)), Q²(h, g²(a, x), R¹(x), S¹(c) – элементарные предикаторные формулы, где Р² , Q² – двухместные предикаторные константы, а R, S – одноместные, а в скобках находятся термы. Однако выражения Р²(х, f¹(а)), Q²(h, g²(a, x), R¹(x), S¹(c) не являются формулами ЯЛП.

2)Выражение Р²(х, Q¹(а)) – не формула ЯЛП, так как Q¹(а) не является термом.

3. 
   Выражение х Р²(х, f¹(а)) и х Q²(х, f¹(а)) являются формулами ЯЛП согласно пункту 4 индуктивного определения F_n. Однако, выражения  Р²(х, f¹(а)),  Q²(х, f¹(а)), а Р²(х, f¹(а)), а Q²(х, f¹(а)) не являются формулами ЯЛП, так как в первых двух выражениях нет кванторных переменных, а в 3-м и 4-м после кванторов стоит предметная константа, а не предметная переменная. Очевидно, что х g²(x, f¹(a)) и x Q²(b, f¹(а)) не являются формулами ЯЛП навешиваются на высказывательнюю формулу, а не на терм. (Q²(х, f¹(а)) – замкнутая, а не высказывательная формула.)
   

В дальнейшем будем пользоваться терминологией.

1. 
   Предметная переменная формулы называется ее вхождением в формулу.
   
2. 
   В формулах х А(х) и  х А(х) подформула А называется областью действия кванторов  и  по предметной переменной х (А – метаформула).
   
3. 
   Переход от Р(х) к х Р(х) и  х Р(х) – называется связыванием предметной переменной х (навешиванием квантора на переменную х, квантификацией переменной х).
   
4. 
   Переменная, на которую навешивается квантор, называется связанной переменной, несвязанная переменная называется свободной.
   
5. 
   х Р(х) является высказыванием ( замкнутой формулой), а Р(х) – переменной высказывание, то есть незамкнутая формула.
   
6. 
   Одна и та же переменная может быть и свободной и связанной в некоторой формуле.
   

Пример:

В формуле х(у  Р²(х, у) Q²(у, z)) областью действия квантора  по переменной х является подформула у  Р²(х, у) Q²(у, z), а областью действия квантора  по у – подформула  Р²(х, у). В рассматриваемой формуле переменная х имеет два вхождения, у – три, z – одно. Первые вхождения переменных х и у связаны, поскольку они следуют непосредственно за кванторами  и . Второе вхождение х находится в области действия квантора  по х в подформуле у  Р²(х, у) Q²(у, z), а второе вхождение у расположено в подформуле  Р²(х, у). Поэтому вторые вхождения х и у являются связанными. Третье вхождение у и единственное вхождение переменной z в подформуле Q²(у, z) являются свободными.

Следует отметить, что:

1. 
   Сформулированный выше синтаксис ЯЛП называют первопорядковым в том смысле, что в этом языке разрешается квантификация только предметных переменных. Если же разрешить квантификацию введенных в алфавит первопорядкового ЯЛП предметно-функциональных и предикаторных переменных , то говорят о ЯЛП более высокого, чем первый порядка. В этих языках возможна квантификация по предикаторам, то есть выражения типа р(Р(х)), и функторам , то есть f(f(x));
   
2. 
   ЯЛП, не содержащий предметных констант и предметтно-функциональных констант, называется языком чистого исчисления предикатов.
   

Примеры перевода простых высказываний естественного языка и их отрицаний на язык логики предикатов.

а) Высказывания без кванторных слов.

Примеры:

1. 
   Переводом высказывания «Сократ-идеалист» может быть предикатная формула Р¹(а), где предметная константа а соответствует имени Сократ, а одноместная предикаторная константа Р¹- знаку свойства «идеалист».
   
2. 
   Высказывание «Учитель Платона мудр» может быть записано в виде Q¹(f¹(b)), если одноместному предметному функтору «учитель» сопоставить одноместную константу f, знаку свойства «мудр» - одноместную предикатную константу Q¹, имени Платон – предметную константу b. Зная, что «учитель Платона» имеет значение «Сократ», высказывание «Сократ мудр» имеет формальное представление Q¹(а), то есть a=f¹(b).
   
3. 
   Высказывание «Учитель Платона является идеалистом» может быть записано в виде предикатной формулы  Р¹(f(b)) (здесь Р – идеалист, f¹(b)- учитель Платона).
   
4. 
   Высказывание «Сократ достоин Платона» может быть формализовано предметной формулой R²(a, b), где R – двухместный предикаторный символ «достоин», а индивидные константы a и b соответствуют именам Сократ и Платон. Очевидно, что в приведенной интерпретации выражение ЯЛП: R²(b, а) есть высказывание «Платон достоин Сократа», R²(а, а) – «Сократ достоин сам себя», R²(b, f¹(b)) – «Платон достоин своего учителя»,  R²(f¹(а), f¹b)) – «Учитель Сократа не достоин учителя Платона»
   
5. 
   Высказывание о наличии трехместного отношения между тремя объектами «Сократ достоин Платона больше, чем своего учителя» в ЯЛП имеет вид S³ (а, b, f¹(а)) , где S³ – трехместная предикаторная константа, соответствующая отношению «…достоин…больше, чем…». Очевидно, формальное выражение  S³ (а, b, f¹(а)) может быть переведено как отрицание вышеприведенного высказывание.
   

б) Высказывания с кванторными словами.

Примеры:

1. 
   Высказывательная форма «х является выдающимся» Р¹(х) становится высказыванием х Р¹(х), если использовать кванторное слово «кто-то», то есть «Кто-то является выдающимся» (здесь Р¹ – предикаторная константа «выдающийся»). Очевидно, что предикаторная формула х  Р¹(х) может быть переведены нка русский язык как «кто-то не является выдающимся» или аналогичная формула х Р¹(х) – «неверно, что все являются выдающимися».
   
2. 
   Естественное высказывание «Кто-то достоин Сократа» переводится формулой х Р²(х, а), а формула х Р²(а, х) соответствует выражению «Сократ достоин кого-нибудь». Формула х Р²(х, х) переводится как «Кто-то не достоин самого себя».
   
3. 
   Высказыванию «Все являются талантливыми» соответствует формула х S¹(х), а высказывание «всякий достоин Сократа» - х Р²(х, а).
   
4. 
   Высказывание «Никто не достоин учителя Платона» и «учитель Платона не достоин никого» можно соответственно записать предикатными формулами вида: х  Р²(х, f¹(b)) и х  Р²(f¹(b), х).
   
5. 
   Высказывание «Каждый достоин кого-нибудь» соответствует формуле х у Р²(х, у).
   
6. 
   Формуле х у Р²(х, у) можно сопоставить естественно-языковое выражение «Кто-то кого-то не достоин».
   
7. 
   Формулу х у S³(х, а, у) можно интерпретировать фразой «Кто-то достоин Сократа больше, чем кого-либо»
   

в) Простые высказывания, выражаемые сложными формулами.

Примеры:

1. 
   Высказывание «Некоторый идеалист мудр» может быть переведено на ЯЛП посредством формулы х (Р¹(х)Q¹(х))( буквальный смысл- «существует объект х, который является идеалистом Р , а является мудрым Q). Очевидно, что предикатная формула  х (Р¹(х)Q¹(х)) имеет буквальный смысл «Для всякого человека х верно, что если он идеалист Р, то он мудр Q» .
   
2. 
   Формулы х (Р¹(х)Q(х)) х (Р¹(х)Q(х)) могт быть переведены как «Некоторый идеалист не мудр» и «Ни один идеалист не мудр».
   
3. 
   Простое высказывание «Некоторый идеалист достоин Платона» переводится на ЯЛП формулой х (Р¹(х)  R²(x,b)), а формула х (Р¹(х) R²(b, х)) переводится на естественный язык так: «Существует такой человек, что если он является идеалистом, то Платон достоин его». Переводом же высказывания «Каждый идеалист достоин Платона» является формулой вида х (Р¹(х) R²(х, b)).
   
4. 
   Великая теорема Ферма: «Для любого nN не существует х, у, z N, удовлетворяющих равенству хⁿ⁺²+yⁿ⁺²=zⁿ⁺²», на ЯЛП есть формула x y z (P¹(x),P¹(y),P¹(z) R⁴(x,y,z,n)), где P¹ – одноместная предикаторная константа «быть натуральным числом», а R⁴- одноместная предикаторная константа, соответствующая равенству хⁿ⁺²+yⁿ⁺²=zⁿ⁺².
   

СЕМАНТИКА ЯЛП.

Напомним, что семантикой формализованного языка называется совокупность правил приписывания значений выражениям этого языка. Именно в этом случае говорят об интерполяции нелогических символов языка (логические символы – логические операторы – имеют заданную при построении языка интерпретацию). Суть данной поцедуры – указать, объекты каких типов могут быть сопоставлены в качестве значений дискрептивным константам и предметным переменным. Совокупность таких объектов называется областью интерпретации, или универсумом рассмотрения (рассуждения) М. Приписывание значений дискретивным константам в ЯЛП осуществляют с помощью семантической функции J (называемой часто интерпретационной функцией).

Пару М, J , задающую допустимую в классической логике предикатов интерпретацию дискретивных констант, называют моделью. Формально моделью называется кортеж М, J  такой, что М, а J –интерпретирующая функция, удовлетворяющая условиям: J(k)М, J ⁿ : Mⁿ M, J Пⁿ  Mⁿ (здесь k, , П –соответственно произвольная предметная константа, предметно-функциональная константа, предикатная константа). Очевидно, что значениями термов являются предметы (индивиды) из области инте5рпритации М, а возможными значениями формул – объекты «истина, не ложь» (это означает, что термы являются аналогами простых и сложных имен, а формулы – аналогами высказываний естественного языка), то есть ): J(Ф ⁿ (t₁…t_n)М (J(ⁿ): Mⁿ M – алгебраическая операция), Пⁿ(t₁…t_n): MⁿМ, л ( то есть J(П ⁿ (t₁…t_n)М, хотя J(П ⁿ) М). При этом значения термов и формул обусловлены выбором конкретной модели М, J  и конкретного приписывания элементов М предметным переменным.

Примеры:

1) Пусть область интерпретации есть множество целых положительных чисел ( то есть М=Z^t ), а интерпретационная функция J сопоставляется предметной константе а число 5М, одноместной предметно-функциональной константе f – операция возведения в квадрат, двухместный предметно-функциональной константе g – операции сложения. Положим, что предметной переменной х приписывается значение 3М. В этом случае значениями нижеприведенных термов в указанной модели < z^t,J>, при х=3 будут:

• 
  для терма а, очевидно, 5
  
• 
  для терма х, очевидно, 3
  
• 
  для терма f¹(а) имеем 5² равно 25.
  
• 
  для терма g² (x,a), имеем 3+5=8
  
• 
  для терма f ¹(g² (x,a ))=(3+5)² =64
  
• 
  для терма g² (f(a),x)=5²+3=28
  

2) Для элементарных предикатных свойств Q²(f¹(a),x) и Р¹(g² (x,a)) определить принимаемые ими значения в модель < z^t,J>, если J(Q²) – множество пар таких чисел: где первая конпонента больше второй, J(Р¹) множество четных чисел, а х=3, а=5, f², gt

Решение:

Для первой формулы имеем:

<5²,3 >=<25,3 > J(Q²), то есть  Q²(f¹(a),x)=U при х=3, а=5.

Для второй формулы имеем:

(3+5)=8  J(Р¹), то есть  Р¹(g² (x,a))=U при х=3, а=5.

Очевидно, что в случае х f(a), когда х=26 имеем 25, 26 J(Q²) и 25+ 26 J(Р¹), то есть  Q²(f¹(a),x)=л при х25,  Р¹(g² (x,a))=л при х четном.
3) При условии примера 2 определить значение формул

Q²(f(a),x)  Р¹(g² (x,a)),  Q²(f(a),x)  Р¹(g² (x,a)), Q²(f(a),x)  Р¹(g² (x,a)).

Решение:

Для первой формулы имеем:

 Q²(f(a),x)  Р¹(g² (x,a))=U при х=3, а=5.

Для второй формулы имеем:

  Q²(f(a),x)  Р¹(g² (x,a))=Л при х=з.

Для третьей формулы имеем:

 Q²(f(a),x)  Р¹(g² (x,a))=U при х=3.
4) Замкнутая формула х Р¹(х) не содержит свободных переменных и ее значения в модели < z^t,J> при J(Р¹)  х z^t: х=2n, nN  есть «U», то есть х Р¹(х)= U при х=2n. Аналогично, если J(Q²)х: х=k, l, kl, имеем у Q²(х, у)=л при k=1.
5) Формула х Р¹(f¹(х)) в модели N, J при f², J(Р¹)  х: х=2n, nN  будет логична при хN\ J(Р¹), то есть х Р¹(f¹(х))=л при х- нечетное. Аналогично, формула Q²(g²(х, а), у) в модели N, J при J(Q²)х: х=k, l, kl, g t , а=2, у=1 имеет значение «U», то есть х Q²(g²(х, а), у)= U при хN.

КЛАССИЧЕСКАЯ ЛОГИКА ПРЕДИКАТОВ.
Логика предикатов, подобно логике высказываний, строится на базе формализованного языка, выделяя в множестве предикатных формул понятия закона логики предикатов и отношения логического следования к логической эквиваленции.
а) Отношение логического следования.

Из множество формул Г логически следует формула В (то есть Г=В), если и только если не существует модели М, J и приписывания значений предметным переменным, при которых каждая формула из Г принимает значение «U», формула В- значение «Л».

Пример:

Р(а), Q(a) =x(Р(х)Q(х)). Действительно, если предположить, что это не так, то из истинных высказываний Р(а) и Q(a) высказывание x(Р(х)Q(х)) должно быть логичным. Однако, Р(х)=U при х=а и Q(х) =U при х=а и, следовательно, Р(х)Q(х)=U при х=а. Налицо противоречие, свидетельствующее о неверности допущения. Итак, из формул Р(х), Q(х) следует формула x(Р(х)Q(х)).

Замечание:

Наличие отношения логического следования между приведенными формулами свидетельствует о правильности всех умозаключений, логические формы которых имеют вид:

Р(х), Q(х)

x(Р(х)Q(х)).

Итак, правильным, в частности, является естественное умозаключение:

• 
  Студентка Наташа трудолюбива.
  
• 
  Наташа успешно учится по специальности.
  
• 
  Некоторые трудолюбивые студенты успешно учатся по специальности.
  

Однако, следующие умозаключения являются неправильными:

• 
  Существует трудолюбивый студент.
  
• 
  Существует студент, успешно осваивающий специальность.
  
• 
  Некоторые трудолюбивые студенты успешно осваивают специальность.
  

Действительно, логическая форма заданного умозаключения имеет вид:

Р(х), Q(х)

x(Р(х)Q(х))

Покажем, что между посылками и заключением в этом случае отсутствует следование. Положим, что универсумом рассмотрения является множество животных М, а предикаторным константам Р и Q соответствуют «быть медведем» и «быть лисой». Поскольку все формулы рассматриваемого умозаключения замкнуты, то приписывание значения переменной х произвольно. В модели М, J формулы Р(х), Q(х) истинны, поскольку существуют животные, которые соответственно есть медведи и есть лисы. Однако формула x(Р(х)Q(х)) есть ложь, так как не существует таких животных в универсуме М, которые одновременно являются и медведем и лисой. Именно это и означает, что Р(х), Q(х) x(Р(х)Q(х)).
б)Законы классической логики предикатов.

Формула А является общезначимой(тождественно истинной), если и только если А принимает значения «U» в каждой модели М, J и при любом приписывании значений предметным переменным. Законы классической логики предикатов выражаются общезначимыми формулами ЯЛП.

Утверждение «Формула ЯЛП – общезначима» символически записывается так: А.

Пример:

1. 
   В ЯЛП закон исключенного третьего может быть записан эквивалентными формулами xР(х)xР(х) xР(х)xР(х).
   
2. 
   =(x(Р(х) x(Р(х) ) читается так: «Если для любого х присуще свойство Р, то существует х, обладающий свойством Р. Очевидно, что (x(Р(х)x(Р(х) ) является законом.
   

Примечания:

1. 
   Как и в логике высказываний, существует связь между отношением логического следования и законом классической логики предикатов., то есть А₁, А₂…А_n= В тогда и только тогда, когда = (А₁(А₂…(А_n)…) (что равносильно = ((А₁А₂…А_n)В).
   
2. 
   В классической логике предикатов нет, в отличие от логики высказываний, общей процедуры (алгоритма) для решения вопроса о том, имеет ли место отношения логического следования Г=В (или в частном случае А=В) и является ли ГВ законом. В этом плане логика предикатов является неразрешимой относительно универсальной общезначимости формул.
   
3. 
   Поскольку логика предикатов является неразрешимой теорией, то особое значение приобретает формализация понятий логического закона и логического следования посредством построения логических исчислений именно в тех случаях, когда семантический анализ не позволяет выявить логическое следование и логический закон на множестве предикатных формул, это позволяет сделать исчисление (тго есть это осуществляется синтаксическим образом).
   
4. 
   Для логики высказываний исчисление, вообще говоря, как эффективная процедура не является необходимым. Оно нужно как часть логического исчисления для формул ЯЛП.
   
5. 
   Важное в практических применениях узкое исчисление предикатов (то есть одноместных, сингулярных) – разрешимо. То есть если предикат Р(х) является теоремой, то есть и алгоритм его разрешения.
   

АЛГЕБРА ЛОГИКИ ПРЕДИКАТОВ.

Алгебра логики предикатов (алгебра кванторной логики, алгебра неоднородных логических функций) – раздел математической логики, изучающий операции над высказываниями субъектно-предикатной структуры, то есть _n=F_n, U, Л²U, Л, , , где F_n- множество предикатных формул вида Рⁿ(х₁, х₂…х_n)

с нелогическими переменными х_i (выражение Рⁿ(х₁, х₂…х_n) понимается, как переменная, высказывание, истинность которого определяется подстановкой предметных констант вместо предметных переменных.

Выражение отношений посредством многоместных предикатов.

Неоднородная логическая функция Рⁿ(х₁, х₂…х_n): МⁿВ есть n-местный предикат, где Рⁿ n-местная предикаторная константа, М универсум (область) рассмотрения предикатов, В=U, Л - двоичное множество истинных значений высказывания.