Оглавление:
Главная страница djvu-student.narod.ru
Электрический привод
Математическая логика
Биология
Бжд
История
Психология
Литература
Экономика
Химия
Информатика
Юриспруденция
Высшая математика
Школьная математика
Сопротивление материалов
Теоретическая механика
Теоретические основы электротехники
Физика
Программы, бесплатный софт
Обратная связь
Наша кнопка


Скачать эту страницу
в формате PDF, 168 КБ

Математическая логика, учебник

Учебник, часть 3

3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

Математическая логика основана на понятии простого высказывания. Простое высказывание – это утверждение, про которое можно сказать, истинно оно или ложно при данных условиях. Из простых высказываний с помощью логических операций строятся составные высказывания, которые далее будут называться просто высказываниями. Сохраняющее эти операции сопоставление каждому высказыванию одного из значений «истина» или «ложь», обозначаемых соответственно 1 или 0, называется интерпретацией исчисления высказываний.

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

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

3.1. Исчисление высказываний L

Алфавитом называется произвольное множество. Его элементы называются символами. Произвольная конечная последовательность символов называется словом. Слово может быть пустым.

Исчисление высказываний L определяется следующим образом:

Его алфавит состоит из символов , называемых логическими, и из символов, принадлежащих произвольному множеству Р, называемых нелогическими символами или буквами.

Синтаксис исчисления L определяется с помощью наименьшего подмножества S множества слов, такого, что

  1. Р S;

  2. Если AS и BS , то AS и (AB) S.

Элементы множества S называются (пропозициональными) формулами. Таким образом, формулами называются слова, определяемые по индукции с помощью правил 1 – 2 из логических и нелогических символов. Предполагая, что приоритет унарной

операции выше, чем приоритет импликации, в некоторых случаях символы скобок в формуле опускаются.

Аксиомами исчисления L называются формулы:

(A1) A(BA),

(A2) (A (BC)) ((AB) (AC)),

(A3) (BA) ((BA) B).

Здесь A, B, C – произвольные формулы. Поэтому в действительности мы имеем бесконечное множество аксиом, в каждой из групп A1, A2 и A3.

Правилом вывода Modus Ponens называется множество троек формул (A,AB,B), которое позволяет паре формул (A,AB) поставить в соответствие формулу B, называющуюся непосредственным следствием этих формул. Правило вывода Modus Ponens обозначается через MP и записывается, как

MP

Формула A называется выводимой в исчислении L из формул X1, X2, …, Xk, если существует последовательность формул: A1, A2, A3, …, An, такая, что для каждого формула Ai является либо аксиомой исчисления L, либо элементом множества {X1, …, Xk} , либо непосредственным следствием формул Ap и Aq, при некоторых
1 p, q i-1. В этом случае последовательность: A1, A2, A3, …, An называется выводом формулы A. Для обозначения выводимости формулы A в исчислении L из формул X1, …, Xk применяется запись:

X1, X2, …, Xk L A .

Если для вывода формулы A достаточно аксиом, то А называется теоремой теории L, а выводимость из пустого множества формул записывается, как

L А .

Лемма. Имеет место теорема L АА.

Доказательство. Построим вывод формулы АА из аксиом (А1) – (А3) следующим образом:

А1 будет аксиомой (А2) для формул А, B = (АА), С = А;

А2 будет аксиомой (А1) для формул А, В = (АА);

получим:

А1=(А ((АА) А)) ((АА)) А)),

А2((АА) А).

Применяя правило вывода MP , будем иметь непосредственное следствие формул A2 и A1:

А3=(АА)) А).

Следующая формула получается из аксиомы (А1) подстановкой В = А:

А4А).

Применяя правило вывода MP, получим:

А5 = АА.

Последовательность формул: A1, A2, A3, А4, А5 = (АА) является искомым выводом формулы АА.

3.2. Теорема о дедукции

Пусть Г – множество формул. Запись Г L А означает, что существует конечная последовательность формул Xi Г, , такая, что X1, X2, …,Xn L A. Вместо Г{X} L А будем писать Г, X L А. Легко видеть, что из Г LВ) следует существование вывода Г, А L В. Верно и обратное утверждение:

Теорема (о дедукции). Пусть Г – множество формул исчисления L; А и В – формулы, и пусть

Г, А L В.

Тогда Г LВ). В частности, при пустом Г, из выводимости А L В вытекает теорема: L АВ.

Доказательство. Пусть В1, В2, …, Вn = В – вывод формулы B из формул, принадлежащих множеству Г{A}. Докажем с помощью индукции по i, что Г LВi), а затем применим это к i = n, чтобы получить Г LВ). При i = 1 имеем В1 Г, либо В1 = А, либо В1 – аксиома. Если В1 Г, либо В1 – аксиома, тогда получаем с помощью аксиомы (А1) формулу В1В1). Применение MP к В1 и В1 (AВ1) дает вывод для АВ1 из Г. Если же В1 = А, то имеем: LВ1) по доказанной лемме о том, что верна теорема L АА.

Докажем теперь: Г L Вi) при i > 1, предполагая, что выводимость
Г L Вк) уже доказана для всех k < i.

Для Вi имеем 4 возможности: Вi Г; Вi – аксиома; Вi = А; Вi непосредственно следует из Вj и Вm, при некоторых j, m i-1. В первых трёх случаях Г L АВi доказывается так же, как при i = 1. В четвёртом случае формула Вm равна формуле (ВjВi), и согласно предположению индукции имеем:

Г LВj) и Г LjВi)),

ибо (ВjВi)=Вm. По аксиоме (А2) верно

L jВi)) ((АВj) Вi)).

Применение

MP

приводит к выводу Г L Вj) Вi). Из этого вывода и вывода Г
L Вj) с помощью Modus Ponens получаем:

Г L Вi).

Таким образом, Г L Вi), для всех i = 1,…,n. В частности, при i = n, получаем:

Г LВ),

что и требовалось доказать.

3.3. Интерпретации исчисления высказываний

Семантика исчисления L определяется с помощью произвольной функции е:S{0,1}=I, удовлетворяющей для всех А,ВS соотношениям и е(АВ)=е(А) е(В).

Функция е называется интерпретацией исчисления L.

Лемма 1 (об интерпретации исчисления L). Для каждой функции f: РI, заданной на множестве букв исчисления L, существует единственная интерпретация еf: SI исчисления L, ограничение которой на Р равно f, в том смысле, что
еf(p) = f(p), для всех p P.

Доказательство. Пусть S0 = P, Sn+1 = Sn{A: ASn}{(AB):A,BSn}. Утверждение леммы доказывается по индукции. Положим ef(A)=f(A) для AS0. Предполагая, что ef уже определена на Sn, продолжим её на Sn+1 следующим образом: Если А=В, для некоторого ВSn, то положим ef(A) =; аналогично, в случае A=(BC) при некоторых В, СSn, положим ef(BC) = ef(B) ef(C). В результате получаем функцию , ограничение которой на Р равно f.

Формула А исчисления L называется тавтологией, если е(А)=1, для любой интерпретации е:SI исчисления L.

Теорема (о полноте). Формула А исчисления высказываний L является тавтологией тогда и только тогда, когда она является теоремой исчисления L.

Доказательство. Если формула А является теоремой исчисления L, то, поскольку аксиомы являются тавтологиями и применение MP к тавтологиям Р и РQ даёт тавтологию, мы можем заключить, что А – тавтология. Это доказывает, что каждая теорема является тавтологией. Для доказательства обратного утверждения нам понадобится следующая лемма.

Лемма 2. Пусть формула А содержит переменные а1, а2, …, аn, и пусть задана некоторая функция f: { а12,…,аn }I={0,1}. Тогда L А’, где и А’ обозначают следующие формулы:

Здесь ef обозначает интерпретацию исчисления L для случая, когда Р={ а12,…,аn}, по лемме об интерпретации ef определяется функцией f единственным образом.

Доказательство леммы проведем по индукции, по количеству логических связок и в формуле А. В случае, когда А = а – переменная, имеем: а L а и а Lа.

Пусть А = В. Если ef(B) = 1, то ef(A) = 0 и А’ = А = В. По предположению индукции L В. Пользуясь теоремой L ВВ, получаем: L В = А’. Если же ef(B) = 0, то ef(A) = 1 и А’ = А= В. По предположению индукции: L В и В =А’.

Рассмотрим случай А = (ВС). По предположению индукции:

L В и L С.

Если ef(B) = 0, то независимо от значения ef(C) имеем: ef(A)=1 и В’ = В, А’ = А. Но L В. С помощью теоремы L ВС), получаем: L ВС.

Если ef(B) = 1 , то возможны 2 случая: – ef(C) = 1 или ef(C) = 0. В случае ef(C) = 1 имеем: ef(A) = 1 и С’ = С, А’ = А = (ВС). Имеем: L С и
L СС) (по аксиоме А1), следовательно, L ВС. В случае ef(В) = 1 и ef(С) = 0 имеют место: А’ =A=(BC), B’ = B, C’ =C. Имеем:

L В, L С.

Пользуясь теоремой L В(СС)), получаем:

L С) =А. Лемма доказана.

Вернёмся к доказательству теоремы о полноте. Пусть А – тавтология. Тогда по доказанной лемме: L А, ибо ef(A) = 1 для любой интерпретации букв . Значит, существуют выводы: L А, и L А . По теореме о дедукции: L аnА и L anА. Пользуясь теоремой L nА) ((аnА) А) и применяя MP, получаем: L А. Повторяя этот процесс ещё n – 1 раз, приходим к теореме: L А, что и требовалось доказать.

Упражнение

Доказать выводимость формул:

L ВВ,

L ВС),

L В(СС))

Следствие (теорема о непротиворечивости). Исчисление высказываний L непротиворечиво в том смысле, что не существует формулы А исчисления L, для которых А и А были бы теоремами.

Доказательство. По теореме о полноте, каждая теорема исчисления является тавтологией. Но отрицание тавтологии не является тавтологией, значит, ни для какой формулы А невозможно, чтобы А и А были теоремами.

3.4. Аксиомы Клини для исчисления высказываний

Обобщим понятие исчисления L. Отношением на множестве X называется любое подмножество Xn = {(x1,…,xn): xi X при 1 i n}.

Определение. Формальная теория Т состоит из четвёрки множеств (,,,), определяемых следующим образом:

  1. произвольное множество, его элементы называются символами, а само – алфавитом;

  2. множество слов, состоящих из символов, элементы из называются формулами;

  3. подмножество множества всех формул, элементы которого называются аксиомами;

  4. множество отношений на множестве формул, элементы из называются правилами вывода.

Формула А называется непосредственным следствием формул F1,F2,…,Fn, если (F1,F2,…,Fn,А) r, для некоторого r. В этом случае пишут:

Выводом формулы А из формул, принадлежащих = {X1,X2,…,Xk} называется последовательность формул:

А1, А2,…,Аn = А,

такая, что, для каждого 1 i n, формула Аi является либо аксиомой, либо Аi Г, либо Аi – непосредственное следствие некоторых формул Аj {A1, A2,…,Ai-1}. Если формула А имеет вывод из формул из Г, то она называется выводимой из Г, и этот факт записывается следующим образом:

Г T А .

В этом случае, если Г = , то А называется теоремой теории Т. Выводимость
Г
T А, в случае Г = {X1,X2,…,Xk}, записывается, как

X1,X2,…,Xk T A.

Если А T В и В T А, то формулы А и В называются эквивалентными.

Формальные теории Т1 и Т2 называются равносильными, если существует биекция между классами эквивалентности формул теорий Т1 и Т2, осуществляющая биекцию между теоремами теорий Т1 и Т2.

Исчислением высказываний К называется формальная теория, такая, что

  • множество символов теории К состоит из символов , , , &, ( , ), и элементов произвольного множества Р,

  • множество формул теории К определено по индукции: буквы из Р являются формулами, и для любых А, В слова А, (АВ), (АВ), (А&В) являются формулами,

  • аксиомами теории К служат аксиомы Клини:

(К1) АА),

(К2) (АС)) ((АВ) С)),

(К3) А&ВА,

(К4) А&ВВ,

(К5) А(А&В)),

(К6) АВ),

(К7) ВВ)

(К8) (АС) ((ВС) ((АВ) С)),

(К9) (АВ) ((АВ) А),

(К10) АА

  • правила вывода:

MP

Интерпретацией теории К называется произвольная функция e: {0,1}, удовлетворяющая для всех А,В соотношениям:

e(A)=, e(AB)=e(A) e(B), e(A&B)=e(A)&e(B), e(AB)=e(A) e(B).

Легко видеть, что если из выводится A в системе L, из выводится A в системе K.

Теорема. Исчисления высказываний К и L равносильны как формальные теории.

Доказательство. Установим, что каждая формула из К эквивалентна формуле из L. Верна теорема АА (см. разд.3.3, упражнение). В силу аксиомы (К10) это влечёт эквивалентность формул А и А. С помощью аксиомы (К5) и правила вывода доказывается А,В K А&В. Из аксиом (К3) и (К4) получаем: А&В K А и А&В K В. В теории L имеет место тавтология:

АВ)).

По теореме о полноте существует вывод:

L АВ)).

Из теоремы о дедукции следует выводимость:

А,В L В).


Применяя аксиомы (К3) и (К4), получаем: А&В K В). Обратно, из тавтологий В) А и В) В будем иметь выводы:

В) L А и В) L В.

Следовательно, формула А&В эквивалентна формуле В). Аналогично доказывается эквивалентность формул АВ и АВ.

Рассмотрим отображение, сопоставляющее каждой формуле из К формулу из L с помощью замены связок: А&В на В), АВ на АВ. Это преобразование будет переводить эквивалентные формулы из К в эквивалентные формулы из L. Аксиомы (К1) – (К10) превратятся в тавтологии в теории L. По теореме о тавтологии они будут теоремами теории L. Значит, каждая теорема теории К будет переходить в теорему теории L. Поскольку каждая формула теории L является формулой теории К, то это преобразование осуществляет биекцию между классами эквивалентности формул и между теоремами теорий К и L. Теорема доказана.

Следствие. Для исчисления высказываний К справедливы теоремы о дедукции и полноте.

3.5. Теорема компактности для исчисления
высказываний


Рассмотрим исчисление высказываний L с произвольным множеством нелогических символов P. Множество всех формул обозначается через S. Логические символы дополняются связками , . Как было доказано в разд. 3.4, эти логические символы можно определить с помощью системы аксиом Клини.

Пусть   S – произвольное подмножество пропозициональных формул. Множество  называется выполнимым, если существует такая интерпретация e: S I, что
e() = 1 для всех   . Множество  называется конечно выполнимым, если каждое его конечное подмножество выполнимо. Множество  называется полным, если для каждой формулы  оно содержит либо , либо . При этом  и  не могут принадлежать  одновременно.

Лемма. Если – конечно выполнимо, то для любой формулы S, либо {}, либо {} конечно выполнимо.

Доказательство. Предположим, что   {} не является конечно выполнимым. Тогда существуют формулы A1, A2, …, Am  , для которых множество {A1, A2, …, Am, } не выполнимо. Для любой интерпретации e: S I, удовлетворяющей e(Ai) = 1 для всех 1  i  m, значение e() будет равно 0. Значит, будет иметь место e(A1&A2&…& Am&) = 0, откуда формула (A1&A2&…&Am&), а вместе с ней и
A1&A2&…&Am, будут тавтологиями. По теореме о полноте формула
A1&A2&…&Am станет выводимой. Для любой другой последовательности B1,…,Bn   невыполнимость множества {B1,…,Bn, } приводит аналогичным образом к выводимости:

L B1 & B2 &…& Bn,  .

Применяя теорему о дедукции, мы получили бы в этом случае B1&B2&…&BnL и из A1 & A2 &…& An L  выводимость:

A1, …, Am, B1, …, Bn L & ,

из которой вытекала бы невыполнимость множества { A1, …, Am, B1, …, Bn }, противоречащая конечной выполнимости множества . Следовательно, множество {B1,…,Bn,} выполнимо для любых B1,…, Bn  . Таким образом, если   {} не является конечно выполнимым, то   {} – конечно выполнимо. Лемма доказана.

Замечание. Если  – конечно выполнимо, то для любой формулы A   формула A не принадлежит , ибо в противном случае {A, A} не выполнимо.

Теорема (о компактности). Пусть – произвольное множество формул исчисления высказываний L. Тогда выполнимо, если и только если – конечно выполнимо.

Доказательство. Ясно, что если  – выполнимо, то оно конечно выполнимо. Докажем обратную импликацию. С этой целью рассмотрим множество всех конечно выполнимых   S, содержащих . Это множество частично упорядочено относительно отношения . Объединение цепи конечно выполнимых подмножеств   будет конечно выполнимым и будет содержать . По лемме Куратовского-Цорна существует   S, максимальное среди конечно выполнимых. Если для некоторого   S ни , ни  не принадлежат , то по лемме либо   {}, либо   {} конечно выполнимо. Это противоречит максимальности множества . Стало быть,  – полное.

Определим функцию е : S I, полагая е() = 1 при  , и е() = 0 в других случаях. Легко видеть, что е будет интерпретацией, доказывающий выполнимость . В самом деле, пусть A, B  . Так как  – полное, то либо (A & B)  , либо
A & B  . Если (A & B)  , то в силу конечной выполнимости  существует интерпретация е, для которой имеют место равенства е(A) = е(B) = е((A & B)) = 1. Эти равенства приводят к е(A & B) = 1 и е(A & B) = 0, опровергающим принадлежность (A & B) к множеству . Следовательно, из A   и B   вытекает
A & B  . Отсюда е(A & B) = е(A) & е(B). Поскольку формула A B равна:
(A & B), то (е(A B)) = (е(A) е(B)). По построению , стало быть, е – интерпретация. Поскольку e’ | = 1, то  – выполнимо. Теорема доказана.





 Вверх...
Заметки:
» Тепловое оборудование, выбор и расчёт мощности
» Электропривод с двигателем постоянного тока приводит в движение лебедку
» Электротехника, решение задач это просто

Обучение за рубежём:
» Учеба в Великобритании
» Образование в Германии
» Образование в США
» Обучение во Франции

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

Hosted by uCoz