Математическая логика

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

Документы

Содержание Квантификация предикатов. Эквивалентные преобразования кванторных формул. 2) Законы коммутативности одноименных кванторов. 3) Законы пронесения и вынесения кванторов (эквивалентности предваренных приведенных формул) Классические логические исчисления. Классическое и.в. Теория алгоритмов.

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

• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Программы кандидатского экзамена по специальности 01. 01. 06 "Математическая логика,, 50.44kb.
• Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Н. В. Папуловская Математическая логика Методическое пособие, 786.38kb.
• Уакиев Валериан Савирович рекомендуемая литература, 334.04kb.
• Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
• Логика компьютера, 210.22kb.
• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.

Пояснения:

1. Выражение Рⁿ(а₁, а₂…а_n), где а₁, а₂…а_n М являются предметными константами, есть высказывание, а выражение Рⁿ(х₁, х₂…х_n) есть логическая (двоичная) переменная (при этом х₁, х₂…х_n – нелогические переменные).
   
2. Поскольку предикаты могут принимать два значения (интерпретируются как переменные высказывания), то из них можно образовывать сложные формулы логики высказываний (сам предикат Рⁿ(х₁, х₂…х_n), являющийся элементарной формулой, рассматривается в сложной формуле как логическая переменная).
   

Утверждения:

1. Всякий предикат Рⁿ(х₁, х₂…х_n) определяет отношение R Мⁿ такое, что а₁, а₂…а_nR, если и только если Рⁿ(а₁, а₂…а_n)=U. При этом R задает область истинности предиката Рⁿ(х₁, х₂…х_n) .
   
2. Каждому n-местному отношению R Мⁿ соответствует предикат Рⁿ(х₁, х₂…х_n) такой, что Рⁿ(а₁, а₂…а_n)=U, если и только если а₁, а₂…а_nR.
   

Эти утверждения можно проиллюстрировать графически бинарным функциональным соответствием q= Мⁿ, B, P, с помощью которого возникает высказывание , если в качестве значений х_i ( i = 1…n)



B=J_mP

Dom P

Область истинности предикатов R_u Мⁿ

Мⁿ

u

л

Говорят, что предикат является выполнимым, если R_u  и R_u Мⁿ (т.е. предикат выполняется хотя бы для одного набора значений аргументов, само соответствие сюрьективно). В том случае, если область истинности предиката Pⁿ(x₁, x₂,…, x_n) пуста, т.е. R_u , то говорят, что предикат является тождественно-ложным (невыполнимым), а в случае R_u Мⁿ=Dom P предикат является тождественно-истинным (общезначимым) – он выполняется для всех наборов аргументов (такой предикат выражает закон логики)

1. Пример. Для двухместного предиката Р²(х₁, х₂), где Р² – быть братом на множестве детей М₁ = {a,в,c} (где а - Алла, в – Володя, с – Сергей) область определения Dom Р²(х₁, х₂) выполняемого предиката, есть область истинности:
   

R_u ={<в, а>, <в,c >, , } М² ;

2. М₂ = {a,в,c} (где а – Алла, в – Вера, с - - Светлана) имеем невыполнимый предикат, т.е. Dom Р²(х₁, х₂)= R_u =
   
3. М₂ = {a,в,c} (где а – Андрей, в – Володя, с – Сергей) имеем тождественно-истинный предикат (закон), для которого R_u ={<а, в>, , <в, а >, <в,c >, ,}
   

Утверждение 3. Всякой алгебраической операции f: Мⁿ M можно поставить в соответствие (n+1)-местный предикат такой, что Pⁿ⁺¹(x₁, x₂,…, x_n+1) истинен, если и только если fⁿ(a₁, a₂,…, a_n)= а_n+1

Однако обратное соответствие, т.е. от (n+1)-местного предиката к n-местной функции возможно не всегда, а только при условии, чтобы для любого а¹_n+1а_n+1 Pⁿ⁺¹(а₁, а₂,…, а¹_n+1 )=  (т.е. предикат был бы ложным).

семьи М, то в случае:


КВАНТИФИКАЦИЯ ПРЕДИКАТОВ.

Навешивание квантора на предикат уменьшает в нем число свободных переменных и превращает его предикат от меньшего числа переменных.

Пример.




Пример.



Пример.

- высказывания, истинностное значение которых обусловлено универсумом рассмотрения М.

Примечание.

1. формулы вида х_i Pⁿ(x₁, x₂,…, х_i,…, x_n) часто называют экзистенциональной квантификацией формул Pⁿ(x₁, x₂,…, х_i,…, x_n) относительно х_i, а формулы вида х_i Pⁿ(x₁, x₂,…, х_i,…, x_n) – универсальной квантификацией формулы Pⁿ(x₁, x₂,…, х_i,…, x_n) относительно х_i.
   
2. Высказывание хP(х)=u, если предикат Р(х) является тождественно-истинным, а хP(х)=u, если предикат Р(х) – выполним.
   
3. Если предметная область М предиката конечна, то его универсальная и экзистенциональная квантификации являются соответственно обобщением конъюнкции и дизъюнкции всех формул P(а_i) (где а_i М), т.е. имеем равносильности:
   

4. Равносильные выражения
   

хР(х)=хР(х),

 хР(х)=хР(х), т.е. взаимовыразимость кванторов означает, что один квантор определяет сокращенную запись другим. Именно поэтому в логике предикатов первого уровня достаточно только один из кванторов.

Эквивалентные преобразования кванторных формул.

1. Закон отрицания кванторов:
   

хР(х)  хР(х),

 хР(х)  хР(х).

Эти эквивалентности являются обобщением законов де-Моргана.

Пример. Пусть Р – сдал экзамен, а М – студент учебной группы. Тогда высказывание хР(х) ( “не все студенты группы сдали экзамен”) эквивалентно высказыванию хР(х) (“существуют студенты группы, которые не сдали экзамен”)

2) Законы коммутативности одноименных кванторов.

ху Р(х, у)  ухР(х,у),

ху Р(х, у)  ух Р(х, у).

Однако, для разноименных кванторов действительна импликация:

ху Р(х, у)  у х Р(х, у).

3) Законы пронесения и вынесения кванторов (эквивалентности предваренных приведенных формул):

• х(Р(х)Z)  хP(x) )Z  ZхР(х),
  

х(Р(х)Z)  хP(x) )Z  ZхР(х),

х(Р(х)Z)  хP(x) )Z  ZхР(х),

х(Р(х)Z)  хP(x) )Z  ZхР(х).

Пример. х(F(x)Q(y))  H(x)  Q(y))  х(Q(y)(H(x)F(x))  Q(y)х(H(x) )F(x))

• х(P₁(x)P₂(x)) хP₁(x)х P₂(x),
  

х(P₁(x)P₂(x))  хP₁(x)х P₂(x),

Это т.н. законы дистрибутивности квантора  относительно операции  и  относительно .

Для квантора  относительно  и  относительно  действительны соотношения (верно лишь в одну сторону):

(хP₁(x)хP₂(x))  х(P₁(x)P₂(x)),

х(P₁(x)P₂(x))  хP₁(x)х P₂(x).

Примечание.

1) Предикатная формула, построенная только с привлечением булевых логических операций  и кванторов ,  так, что логическая операция  (обращение) встречается лишь перед символами предикатов, называются приведенной формой. Так, х P₁(x)х P₂(x, у) – приведенная формула, а формулы хР(х)хQ(x,y),

хР(х)хQ(x,y) – не приведенные формулы (т.к. “”

2. Предикатная формула вида >|₁x >|₂x…>|_nxF, где >|_i, где F – бескванторная формула, называется предваренной (пренексной) нормальной формой – П.Н.Ф.
   

Так ху( P₁(x)P₂(x, у)) – приведенная П.Н.Ф., а ху( P₁(x)P₂(x, у)) – П.Н.Ф., но не предваренная формуле.

4)Законы переименования связанных переменных:

хР(х) уР(у),

хР(х) уР(у).

Эти равносильности означают, что переименование связанных переменных не меняет истинности высказываний.

Утверждения. 1) Для любой предикатной формулы существует равносильная ей приведенная форма.

2)Для любой предикатной формулы существует эквивалентная ей П.Н.Ф.

КЛАССИЧЕСКИЕ ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ.

Понятие “исчисление” является экспликацией интуитивных понятий “вывод”, “доказательство”, “оперирование”, “вычисление”.

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

Ниже будем изучать классические исчисления высказываний (И.В.) и предикатов (И.П.) как гомоморфные отображения (модели) логики высказываний и логики предикатов.

Цель классических И.В. и И.П.

Целью И.В. и И.П. является описание кланов всех общезначимых (тождественно-истинных) формул (часто называемых тавтологиями, или законами).

Метасимволика И.В. и И.П.

Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А₁, А₂,…, А_n (Г читается как “гамма”)

Ф – теорема; А_i – метаформула; R(J) – множество правил вывода в исчислении;

| - символ отношения дедуктивного вывода.

Пример. Запись Г|Ф ( из гипотез Г дедуктивно выводима формула Ф) означает А₁, А₂,…, А_n |Ф, или А₁, А₂,…, А_n

Ф

Пример. Запись |А означает, что А доказуема.

Пример. Запись А₁, А₂,…, А_n | означает, что множество посылок противоречива.

Пример. |=, ₁ |= ₂, ₁ | ₂ – метавысказывания.

Замечание. Специфика отношений |= и | в том, что в отличие от логических связок (отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах высказываний, а на пропозициональных формулах.

Построение логических исчислений.

Построение (задание) исчислений качественно отличаются видом аксиоматики – конечным или бесконечным множеством аксиом.

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

КЛАССИЧЕСКОЕ И.В.

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

a) I₁ A

I₂ (AB)((A)

I₃ (AB) ((A(BC)) (AC

I₄ (AB)

I₅ (AB)B

I₆ A (B (AB))

I₇ A (AB)

I₈ B (AB)

I₉ (AC) ((BC) ((AB)C))

I₁₀ 

Правило вывода для этой аксиоматики – правило модус-поненс (Modus ponens, m.p.), часто называемого правилом отделения:

ТЕОРИЯ АЛГОРИТМОВ.


Вводные положения.