Маркин П.М. Математическая логика

Подождите немного. Документ загружается.

Говорят, что предикат является выполнимым, если R

 и R

М

(т.е. предикат

выполняется хотя бы для одного набора значений аргументов, само соответствие

сюрьективно). В том случае, если область истинности предиката P

, x

,…, x

)

пуста, т.е. R

, то говорят, что предикат является тождественно-ложным

(невыполнимым), а в случае R

М

=Dom P предикат является тождественно-

истинным (общезначимым) – он выполняется для всех наборов аргументов (такой

предикат выражает закон логики)

1) Пример. Для двухместного предиката Р

(х

, х

), где Р

– быть братом на

множестве детей М

= {a,в,c} (где а - Алла, в – Володя, с – Сергей) область

определения Dom Р

(х

, х

) выполняемого предиката, есть область истинности:

={<в, а>, <в,c >, <c, в>, <c, a >} М

;

2) М

= {a,в,c} (где а – Алла, в – Вера, с - - Светлана) имеем невыполнимый

предикат, т.е. Dom Р

(х

, х

)= R

=

3) М

= {a,в,c} (где а – Андрей, в – Володя, с – Сергей) имеем тождественно-

истинный предикат (закон), для которого R

={<а, в>, <a, c >, <в, а >, <в,c >,

<c, a >,<c, в>}

Утверждение 3. Всякой алгебраической операции f: М

M можно поставить в

соответствие (n+1)-местный предикат такой, что P

n+1

, x

,…, x

n+1

) истинен, если и

только если f

, a

,…, a

)= а

n+1

Однако обратное соответствие, т.е. от (n+1)-местного предиката к n-местной

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

n+1

а

n+1

(а

, а

,…, а

n+1

)=  (т.е. предикат был бы ложным).

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

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

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

Пример.

B=J

Dom P

Область истинности

предикатов R

М

)(),(

),(),(

xyxy

yyxx





Пример.

),(),,,(

pzpzyxyx



Пример.

)()(

xxиxx



- высказывания, истинностное значение которых

обусловлено универсумом рассмотрения М.

Примечание.

1) формулы вида х

, x

,…, х

,…, x

) часто называют

экзистенциональной квантификацией формул P

, x

,…, х

,…, x

)

относительно х

, а формулы вида х

, x

,…, х

,…, x

) –

универсальной квантификацией формулы P

, x

,…, х

,…, x

)

относительно х

2) Высказывание хP(х)=u, если предикат Р(х) является тождественно-

истинным, а хP(х)=u, если предикат Р(х) – выполним.

3) Если предметная область М предиката конечна, то его универсальная и

экзистенциональная квантификации являются соответственно

обобщением конъюнкции и дизъюнкции всех формул P(а

) (где а

М),

т.е. имеем равносильности:

).()(...)()()(

),()(...)()()(

aPaPaPaPxxP







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…>|

xF, где >|

, где F –

бескванторная формула, называется предваренной (пренексной)

нормальной формой – П.Н.Ф.

Так ху( P

(x)P

(x, у)) – приведенная П.Н.Ф., а ху( P

(x)P

(x, у)) – П.Н.Ф.,

но не предваренная формуле.

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

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

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

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

меняет истинности высказываний.

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

приведенная форма.

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

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

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

“доказательство”, “оперирование”, “вычисление”.

В математической логике исчисление является частным случаем формальных

(дедуктивных) систем F.S. вида <L, D>, задаваемое правилами синтаксиса

(образования) языковых выражений и правилами построения выводов

(дедуцирования). В том случае, если в исчислении не выделяют аксиомы, то говорят

о натуральных исчислениях.

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

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

предикатов.

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

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

истинных) формул (часто называемых тавтологиями, или законами).

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

Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А

, А

,…, А

(Г

читается как “гамма”)

Ф – теорема; А

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

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

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

,…, А

|Ф, или А

, А

,…, А

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

Пример. Запись А

, А

,…, А

| означает, что множество посылок противоречива.

Пример. |=, 

|= 

, 

| 

– метавысказывания.

Замечание. Специфика отношений |= и | в том, что в отличие от логических связок

(отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах

высказываний, а на пропозициональных формулах.

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

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

конечным или бесконечным множеством аксиом.

Аксиома – формула объектного языка, в рамках которого строится исчисление.

Система аксиом – конечное множество аксиом. Бесконечное множество аксиом

задается перечислением конечного множества схем аксиом. Схема аксиом –

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

определенной структуры.

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

Ниже рассмотрим различные И.В., отличающиеся аксиоматикой. Задание

классического И.В. в Я.Л.В. будем осуществлять с привлечением схем аксиом и

одного вывода.

a) I

A

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

(AB) ((A(BC)) (AC

(AB)

(AB)B

A (B (AB))

A (AB)

B (AB)

(AC) ((BC) ((AB)C))



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

часто называемого правилом отделения:

А,А  В , где А,АВ – тавтология (законы)

Пояснения. 1) Тот факт, что формулы приведенной аксиоматики являются

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

с привлечением истинностных таблиц (это т.н. пассивный метод) или

эквивалентными преобразованиями (это т.н. активный метод). Так (АВА)) 

ИВ=u, т.е. тавтология.

2) Другие аксиоматики, равносильные приведенной и удовлетворяющие

требованиям полноты, независимости и непротиворечивости могут обладать в

каждом конкретном случае теми или иными достоинствами – компактностью,

обозримостью, длительностью выводов.

Так, если использовать только основные связки , то A

I будет представлена

только четырьмя схемами аксиом I

(в этом случае связки являются

производными от основных и аксиомы I

- I

становятся теоремами Ф

-Ф

). Другой

часто используемой аксиоматикой являются следующие схемы аксиом:

б) II

A

(AС)С))

(A))

Эта аксиоматика равносильна предыдущей в том плане, что она порождает тоже

множество тавтологий, а аксиомы A

I выводятся из аксиом A

II (и наоборот).

5) Правило вывода M.p. есть отношение R(Г,Ф) между истинными

формулами-посылками Г и истинной формулой-следствием Ф этих

посылок, т.е. Г |Ф, где Г=А, АВ, Ф=В (другая запись |= А(АВ) В).

Формулировка этого правила следующая “Если большая посылка АВ и

малая посылка А есть тавтологии, то формула-следствие В также есть

тавтология” (Очевидность результата следует в силу операции

импликации в тернарном отношении (А(АВ))В.

Пример. Сделать вывод из высказываний:

- Если на небе кучевые облака, то завтра будет хорошая погода;

- На небе кучевые облака.

Решение. Логические формы приведенных высказываний в объектном Я.Л.В.

следующие: (pr) и р, где р – “на небе кучевые облака”, r – “будет хорошая

погода завтра”. В силу правила М.р., если (pr) и р истинны, то доказуемым

выражением (т.е. выводом) является высказывание r – “будет хорошая погода

завтра”.

6) Используя аксиоматику, правило m.p., можно доказать, а затем и

использовать, производные правила. Эти производные правила

позволяют сократить многократность применения m.p. Среди

производных правил вывода в классическом И.В. выделяют следующие:

- правило дедукции Г,А|  Ф _ , (это означает, что если из Г,А следует Ф, то

Г|АФ

из Г следует АФ);

- правило введение отрицания (или правило доказательства от противного) :

Г,А|  В,  В (иначе Г,А|  В,Г, А|  В ),

Г|А Г|

___

- правило перестановки посылок:

 С) ;

ВАС)

- правило цепного заключения

С)|C

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

В основе исчисления предикатов лежит Я.Л.П. В остальном И.П. является

расширением И.В. Аксиоматико-дедуктивную систему И.П. J

=< L(J

), D(J

) >

получим, добавив к рассмотренным выше схемам аксиом И.В. (имея, конечно, в виду

переход к Я.Л.П.) следующие две классические схемы кванторных аксиом И.П., а к

правилу Modus Ponens – два метаправила вывода:

(*) |=хП(х)П(у) - аксиома универсальной конкретизации.

(**) |=П(у)хП(х) – аксиома экзистенциональной конкретизации.

Эти аксиомы могут быть переписаны в виде:

хП(х) |П(у); П(у) |хП(х).

F

(x)

хF

(x) - правило универсального обобщения, где F

не содержит свободной

переменной х. ( очевидно, что если |= F

F

(x), то |= F

хF

(x)

 F

(x)

хF

F

(x) - правило экзистенциональной конкретизации, где F

не содержит

свободной переменной х.

Пояснения.

1) Схемы аксиом (*) и (**) являются обобщением теорем логики

высказываний, учитывая, что на конечном универсуме |M|=k:

хР(х)а

 а

 а



хР(х)а

 а

 а

.

Прочтение предикатной аксиомы(*) может быть следующим: “Если предикат П(х)

выполняется для всех х, то он выполняется и для а” ; аналогично, (**) может

быть прочитана так: “Если предикат П(а) выполним для а, то существует х,

для которого выполняется предикат П(х)”.

2) Трактовка предикатных схем (*) и (**) в смысле дедуктивной выводимости, т.е.

хП(х)|П(а) и П(а) |хП(х) означает, что используется правило -исключения

и правило -введения.

3) Смысл двух дополнительно введенных правил вывода соответственно

следующий: “Если формула F

(x) есть следствие посылок F

, ни одна из которых

не содержит свободной переменной х, то из них выводимо высказывание

хF

(x)”. Если формула F

есть следствие посылок, имеющих свободные

вхождения переменной х, то если существует х, обладающий свойством F

, то

есть и свойство F

4) Для удобства приведения формальных доказательств в И.П. помимо трех

основных правил вывода используют и производные правила (доказуемые в

выбранной аксиоматике с помощью трех основных правил вывода).

Примеры доказательств в И.В.

Пример1. Доказать правило дедукции, т.е. если А

, А

,…, А

| Ф , то |= А

( А

(…

( А

Ф)…))

Дадим алгебраическое доказательство этой теоремы.

Поскольку Г|Ф тогда и только тогда, когда |=ГФ, то имеем:

___________ __ __ __ __ __

 А

…А

 Ф = А

, А

,…, А

Ф = А

А

… А

 Ф = А

А

… (А

Ф)=

__ __

А

… (А

m-1

(А

Ф))=…=А

( А

(…( А

Ф)…))

Пример2. Доказать выполнимость правила введения отрицания Г,А|  В,  В в A

Г|А

Доказательство.

По теореме дедукции из того, что из Г,А|В,В имеем:

а) Г|АВ

б) Г|АВ

а) шаги доказательства для случая Г|АВ следующие:

1) (АВ)

2) 

3) ((А

4) 

5) 

Итак, Г|А при |= АВ

Аналогично,

б) шаги доказательства для случая Г|АВ следующие:

1) (

2) ((А

3) ((А

4) 

т.е. Г|А и |= (т.к. любая теорема – тавтология)

Пример 3. Доказать правило транзитивности (цепного заключения) (АВ), (ВС) |

АС

Доказательство.

1) (АС))С)

2) А(ВС)=u, т.к. ВС=u

3) АС

Итак, АВ, ВС|АС. Очевидно, т.к. АС выводимо из АВ и ВС, то |= (АВ)

(ВС)(АС) и |=(АВ)  ((ВС)(АС))

Пример 4. Доказать выводимость формулы (PQ) (RS) из посылок (P Q) (( P

Q) (RQ)), (PQ), (RQ) (RS)

Доказательство.

Согласно m.p. из (P Q) (( P Q) (RQ)) и (PQ) имеем (P Q) (RQ).

Согласно цепного правила из (P Q) (RQ) и (RQ)(RS) имеем выводимость

формулы (PQ) (RS).

Пример 5. Доказать правило резолюции СА, СВ|АВ

Доказательство.

Т.к. (СА)( СВ) (АВ) есть тавтология, то выводимость АВ доказана.

Примеры доказательств в И.П.

Пример. Обосновать правильность на языке логики предикатов силлогизм:

“Все люди – смертны ”

“ Сократ – человек ”

“Сократ – смертен ”

Обоснование.

Логическая форма силлогизма следующая

х(P(х) Q(x))

P(с)

Q(x)

Где P, Q – соответственно предикаторные буквы, имеющие интерпретацию

“человек” и “смертен” ;

С – интерпретация предметной переменной х – “Сократ”.

Строим формальный вывод по шагам

1) в первую предикаторную аксиому (*) метапеременную формулу П(х)

формулу Я.Л.П. P(x) Q(x), т.е. имеем х(P(х) Q(x)) (P(с) Q(с))

2) используя правило Modus Ponens к первому шагу и первой посылки

заданного силлогизма, имеем (P(с) Q(с));

3) Применив повторно правило m.p. ко второму шагу и 2-ой посылке

силлогизма, получаем Q(с).

Итак, х(P(х) Q(x))(P(с) Q(с)), х(P(х) Q(x)), P(с) | Q(c)

Пример. Доказать правило переименования свободных переменных в A

II, т.е. F(x) ~

F(y)

Доказательство.

1) | F(x) (по условию)

2) F(x)(Ф F(x)) (

)(

IIAиIIA



, где |=Ф – любая тавтология, не

содержащая свободного вхождения х)

3) Ф F(x) (m.p. 2, 1)

Пример. Доказать правило переименования связанных переменных.

Доказательство.

А)Покажем, что |хF(x) ~ |уF(y)

1) |хF(x) (по условию)

2) хF(x)F(y) (предикатная аксиома (*))

3) хF(x)уF(y) (правило универсального обобщения)

4) уF(y) (m.p. 3,1)

б) Покажем, что |хF(x) ~ |уF(y)

1) |уF(у) (по условию)

2) F(y)  хF(x) (предикатная аксиома (**))

3) уF(y) хF(x) (правило экзистенциональной конкретизации)

4) хF(х) (m.p. 3,1)

МЕТАТЕОРИЯ ЛОГИЧЕСКИХ ИСЧИСЛЕНИЙ (МЕТАЛОГИКА).

Металогика – раздел логики, в котором изучаются логические исчисления и

формализованные логические теории. Одним из основных объектов металогики

является отношение логического следования и отношение дедуктивной

выводимости. При этом отношение логического следования, так же, как и

отношение импликации, единственно для любых логических исчислений, а

отношение дедуктивной выводимости варьируется в зависимости от правил вывода

и аксиом, принятых в том или ином конкретном логическом исчислении.

Отношение |=, |,  различны и в то же время тесно взаимосвязаны. Связь между

дедуктивной выводимостью и импликацией выражает теорема дедукции.

Большинство логических исчислений строится таким образом, что в них теорема

дедукции либо постулируется, либо доказывается с помощью специальных

металогических средств. Связь между отношением логического следования и

заданным в некотором логическом исчислении отношением дедуктивной

выводимости отражает принцип адекватности: логическое исчисление обеспечивает

адекватную дедуктивную формализацию некоторой содержательной теории лишь в

том случае, если любая общезначимая пропозициональная формула данного

исчисления доказуема в нем и, наоборот, любая доказуемая в данном исчислении

формула является общезначимой формулой (т.е. если совокупность всех

общезначимых формул совпадает с совокупностью всех доказуемых формул).

Принцип адекватности выражает общезначимая метаформула: |=((|=)( |)). В

этом принципе объединены два важных металогических требования: треьование

полноты и требование непротиворечивости лолического исчисления.

Если в логическом исчислении истинны все метавысказывания вида “Если |, то |

= ”, то исчисление семантически непротиворечиво (формальная, т.е. дедуктивная

непротиворечивость исчисления к тому же предполагает, что в нем не существует

формулы вида , такой, что | и |). Наоборот, если истинны все

метавысказывания вида “Если |=, то |”, то исчисление является семантически

полным (в узком, т.е. синтаксическом смысле, исчисление полно, если к системе его

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

недоказуемую в этом исчислении формулу).

Пример. Классическое И.В. непротиворечиво, семантически полно и разрешимо.

Пример. Классическое И.П. непротиворечиво, семантически полно, но неразрешимо(

хотя исчисление одноместных предикатов – разрешимо) .

Напоминание.

1) Проблема разрешимости является алгоритмической проблемой,

требующей построения алгоритма решения всех ее задач (для любой

формулы некоторой теории построить доказательство, доказать, что она

не теорема). Если такой алгоритм существует (не существует), то

проблема разрешения называется разрешимой (неразрешимой).

2) Формула вида Ф некоторого исчисления является независимой

относительно логического следования, если ни сама Ф, ни Ф не являются

логическим следствием остальных общезначимых формул (в конечном

счете аксиом) исчисления. Правило вывода исчисления называется

независимым, если существует теорема Ф, которая не может быть

выведена из аксиом данного исчисления без использования этого

правила.

Независимость системы аксиом и правил вывода логического исчисления

свидетельствует о том, что данное исчисление не содержит избыточных средств

формализации соответствующей содержательной теории.

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

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

Теория алгоритмов - раздел математической логики, в котором изучаются

теоретические возможности эффективных процедур вычисления

(алгоритмов) и их приложения.