Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по дискретной математике - файл Раздел 4 Логика предикатов.doc


Загрузка...
Лекции по дискретной математике
скачать (389.4 kb.)

Доступные файлы (8):

desktop.ini
Folder.htt
Раздел 1 Логика.doc601kb.18.08.2002 15:14скачать
Раздел 2 теория множеств.doc384kb.03.09.2001 22:42скачать
Раздел 3 Теория графов.doc272kb.28.02.2002 20:24скачать
Раздел 4 Логика предикатов.doc156kb.10.06.2002 21:25скачать
Раздел 5 Теория простейших автоматов.doc313kb.28.03.2002 21:18скачать
Раздел 6 Комбинаторика.doc141kb.15.05.2002 22:05скачать

Раздел 4 Логика предикатов.doc

Реклама MarketGid:
Загрузка...

Раздел 4. Логика предикатов

Тема 4.1 Основные понятия и определения


Логика предикатов или исчисление предикатов – это раздел математической логики, исследующий операции над высказываниями, расчлененными на субъект и предикат.

Это расширение понятий и логических средств по сравнению с логикой высказываний или Булевой алгеброй. Логические операции с высказываниями, не разделенными на субъект и предикат – это простейший вид логических операций. «В исчислении предикатов делается дальнейший шаг анализа и разрешается рассматривать объектно–предикатную структуру простых предложений и пользоваться операциями композиции, зависящими от этой структуры», - пишет Клини.

Слово предикат (от латинского praedicatum – сказуемое), то что высказывается (утверждается или отрицается) в суждении о субъекте. Предикат выражает наличие или отсутствие того или иного признака у субъекта.

Например: в суждении «Советская ракета достигла Луны» объектом суждения служит «Советская ракета», а предикат – «достигла Луны».

В логике предикатов под предикатом понимается некоторое свойство или отношение.

Примеры:

одноместного предиката (свойства):

1. Р(х) - «Быть простым числом». Подставив значение х, мы получим высказывание «х – простое число».

2. Р(х) – «Быть животным», тогда подставив значение х = Жучка, получим высказывание «Жучка – животное».

двуместного предиката (отношения)

3. Р(х,у) – «х и у – муж и жена».

4. Р(х,у) – «х < у ».

В логике предикатов, как и в логике высказываний, высказывания представляют собой или «Истину» или «Ложь». Разница в том, что в логике предикатов истинностное значение ставится в соответствие определенному предмету или группе предметов, тогда как в логике высказываний они относились к высказыванию. Так в примере 1 для х = 7 Р(х) – Истинно, а для х = 8, Р(х) – Ложно.

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

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

Чтобы задать n – местный предикат Р(х1…хN) следует указать множества Di i=1,N - области изменения предметных переменных Х. Предикат определяется заданием подмножества М в декартовом произведении Di. При этом Р(х1…хN) понимают как высказывание "упорядоченный набор (х1…хN) принадлежит М". Понятие предиката может еще интерпретироваться так: "Из посылок х1…хN, следует заключение В".

Определение: Квантор – это логическая операция, которая по предикату Р(х) строит высказывание, характеризующее область истинности предиката Р(х).

В математической логике наиболее употребительный квантор всеобщности  и квантор существования . Высказывание х Р(х) означает, что область истинности предиката совпадает с областью значения переменной х. Высказывание х Р(х) означает, что область истинности предиката не пуста.
Примеры

х А(х) – т.е. существует число х, такое что х – простое число.

х у G(х,у) - для любого х и для любого у выполняется условие G(х,у)

Определение: Формула

1. Любая переменная – это формула.

2. Если А и В – формулы, то А, (АВ), (АВ), (АВ),х А, х А - формулы

Пример:

(А(В&А) – не формула (не хватает одной закрывающей скобки).

(А(В&А)) – формула

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

Обратите внимание, что одна и та же переменная может быть и свободной и связанной в одной и той же формуле.

Пример: х у (Р(х,у))  Q(у,z)

В данном примере переменная у имеет как свободное, так и связанное вхождение в формулу.

Определение: Формула называется замкнутой, если никакая предметная переменная не является в ней свободной.

Приведем примеры более сложных предикатов:

Пример1: «Всякий человек смертен» - х (Человек(х)  Смертен(х))

Пример2: «Всякий студент изучает какую-нибудь науку» - х (Студент(х)  у Наука(у)&Изучает(х,у))

Пример3: «Квадрат любого четного числа больше 1» - х (Четное число(х)  >(Квадрат(х),1))
^

Тема 4.2 Правила вывода


Определение: Правила, по которым в логике из истинных формул образуются новые истинные формулы называются правилами вывода.

Определение: Выводом называется непустая конечная последовательность формул С1…Сn, таких что:

  • каждая Сi – есть либо посылка, либо получена из предыдущих формул по одному из правил вывода.

  • Если в выводе применялись правила 5 или 7, то все формулы, начиная с последней посылки и вплоть до результата применения данного правила, исключаются из дальнейших шагов построения вывода.


Выпишем правила формального вывода:

1. 2.

3. 4.

5. 6.

7. 8.

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

Правило 5 называется правилом введения импликации. Она позволяет по любой формуле В перейти к импликации, но обязательно в качестве посылки используется последнее допущение (или последняя посылка).

При обнаружении двух противоречащих друг другу формул (правило 7) позволяет говорить о выводимости отрицания последнего допущения (и только его).

Пример: Показать выводимость формулы r из посылок pq, qr, p

1.

2.

Определение: Доказательство есть вывод из пустого множества посылок. Последняя формула в доказательстве называется доказанной формулой или теоремой.

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

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

Тема 4.3 Умозаключения.


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

Логики и философы, тысячелетия рассуждая о природе и законах человеческого мышления, нашли правила получения новых знаний из набора разрозненных, но истинных фактов. Эти правила принято называть умозаключениями. Их достаточно много. Мы приведем самые распространенные из них и рассмотрим примеры их использования. Однако следует хорошо понимать, что все эти типы рассуждений можно получить из базового набора правил вывода математической логики.
^

условно-категоричные умозаключения


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



Данные способ рассуждения в средневековой логике получил название modus ponens, т е. «утверждающий способ рассуждения».

Пример: Если отмечается спад производства, то растет число безработных. В России отмечается спад производства. Следовательно, число безработных растет.

Другой тип правильных условно-категорических умозаключений является modus tollens, т е. «^ Отрицательный способ рассуждения».



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

Покажем вывод этого умозаключения из правил вывода исчисления высказываний. Одновременно продемонстрируем и способы применения этих правил.



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


^

Разделительно-категоричные рассуждения


Эти рассуждения так же являются двухпосылочными и содержат дизъюнктивную или строго – дизъюнктивную посылку.

Правильными являются следующие способы рассуждения



Это правило получило название modus tolledo, т.е. «отрицающе-утверждающий способ рассуждения».

Пример: Этот человек заблуждается сам, или сознательно вводит в заблуждение других. Но сам этот человек не заблуждается. Следовательно, он сознательно вводит в заблуждение других.

Приведенные ниже примеры не являются корректными:



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



Умозаключения подобного типа называются modus ponendo tolens, что означает «утверждающе-отрицающий способ рассуждений».

Пример: Шахматист К. примет участие в одном из двух турниров: он либо выступит на турнире в Тилбурге, либо на турнире в Линаресе. Известно, что К. дал согласие принять участие в Линаресе. Следовательно, К. не выступит на турнире в Тилбурге.
^

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


- простая конструктивная дилемма

Пример: Если Н. Упорен в достижении цели, то он способен овладеть логикой. Если у него есть склонность к строгому абстрактному мышлению, то он способен овладеть логикой. Известно, что Н. Упорен в достижении цели или имеет склонность к строгому абстрактному мышлению. Следовательно, он способен овладеть логикой.

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



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



- сложная конструктивная дилемма

Пример: Если президент подпишет законопроект, то он лишится поддержки профсоюзов. Если же президент наложит на данный проект вето, то он потеряет доверие предпринимателей. Ясно, что президент подпишет законопроект или наложит на него вето. Следовательно, он лишится поддержки профсоюзов или доверия предпринимателей.

- простая деструктивная дилемма

Пример: Если ученый А. Честолюбив, то он хочет защитить диссертацию. Если А. Честолюбив, то он стремиться к продвижению по службе. У А. Нет желания защищать диссертацию или продвинуться по службе. Следовательно, А. Нечестолюбив.

- сложная деструктивная дилемма.

Если В. верит слухам о близком конце света, то он глуп. Если же В. сам распускает такие слухи, то он беспринципен. В. не глуп, и не лишен принципов. Следовательно, В. не верит слухам о близком конце света или не распускает такие слухи сам.
^

Тема 4.4 Принципы построения формальных систем



Пример: Представим себе, что кому-то сообщили следующую информацию о родственных отношениях между четырьмя мальчиками Андреем, Борисом, Владимиром, и Геннадием: "Б брат А", "В брат Б","Г не является братом В","А брат Б и В, но не является братом Г","В брат А, но не является братом Г", " Г не является братом А и не является братом Б". Попытаемся привести в порядок эту сумбурную информацию.

Скажем, что нам дано некое множество М={А,Б,В,Г} и отношение на этом множестве б – быть братом. Таким образом, в терминах теории множеств мы имеем 12 высказываний.

р1: БбА р5 : АбВ р9 : ВбА

р2: ВбБ р6 : АбГ р10: ВбГ

р3: ГбВ р7 : БбВ р11: ГбА

р4: АбБ р8 : БбГ р12: ГбБ

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

  1. Симметрично ( ХбУ то УбХ).

  2. Транзитивно (ХбУ и УбZ то ХбZ)

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

Такими высказываниями могут быть р1, р2, р3. Убедитесь, что все остальные высказывания выводятся из этих.

Отметим, что эта система не единственна. Так, за основные утверждения можно принять р1, р5, р6.

Таким образом, мы построили математическую теорию, которая состоит из набора объектов, отношения на множестве объектов, системы аксиом, набора правил вывода (в данном случае свойства отношения) и доказываемых на основе этих правил и системы аксиом теорем.

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

Таким образом, мы подошли к описанию структуры построения формальных систем. Любая математическая система задается множеством (обязательно не пустым) объектов, рассматриваемых в рамках этой системы (числа, функции, высказывания, геометрические фигуры), операциями, определенными над объектами данного множества, отношениями и системой аксиом. Такие системы называются Исчислениями.

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

При полностью формальном представлении теории никаких «интуитивно понятных» действий над объектами теории не разрешается: все должно быть заложено в синтаксисе (алфавите, правилах образования формул) и средствах дедукции – постулатах (включая правила введения новых знаков по определения).

Понятие исчисления является формализацией интуитивного представления об индуктивно порождаемом множестве. Такие множества широко используются в математике, начиная с множества переменных, формул и, заканчивая множеством теорем, которые выводятся из множества аксиом данной теории при помощи логических переходов. Именно логические исчисления были первыми примерами полностью формализованных дедуктивных систем. Некоторые из специальных видов исчислений хорошо пригодны для описания формальных грамматик и для задания множеств распознаваемых конечными автоматами. Одной из основных сфер применения теории исчисления является теория алгоритмов.

Необходимо сказать, что множество аксиом или система аксиом любой дедуктивной теории истинна, если она полна, непротиворечива и независима.

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

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

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

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

«Стремление к полноте, - как правило, естественное стремление науки, хотя его «абсолютная реализация» представляется скорее недостижимым идеалом, к которому можно лишь приближаться. Этот идеал, во всяком случае, недостижим не только в опытно-экспериментальных науках (опыт всегда незавершен), но и во многих дедуктивно-математических областях».

Непротиворечивость – свойство системы аксиом, состоящее в том, что не каждая формула этой системы доказуема в ней. Формальные системы, обладающие этим свойством, называются непротиворечивыми, или формально непротиворечивыми. В противном случае формальная система называется противоречивой или несовместимой. Для широкого класса формальных систем, язык которых содержит отрицание, непротиворечивость эквивалентна свойству «Не существует в рамках данной формальной системы такой формулы А, что А и А обе одновременно доказуемы».

Формальная система называется содержательно непротиворечивой, если существует модель, в которой истинны все теоремы этой системы. Если формальная система содержательно непротиворечива, то она и формально непротиворечива. Доказательство непротиворечивости формальной системы является точной математической проблемой. Клини подчеркивает: «Математическое доказательство непротиворечивости формальной системы дает гарантию против возникновения противоречия в соответствующей содержательной теории». Для формальных систем, основанных на классическом исчислении предикатов, справедливо и обратное утверждение всякая такая непротиворечивая система имеет модель. Таким образом, один из способов доказательства непротиворечивости состоит в построении модели.

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

Проблема непротиворечивости возникает при рассмотрении любого исчисления, это одна из «кардинальных проблем» математической логики. При использовании какой-либо системы аксиом уверенность в ее внутренней непротиворечивости необходима, т.к. в противоречивой системе нет различия истины и лжи.

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

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

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

Пример:

Мы специально рассмотрим очень простой пример, для того чтобы стали очень прозрачными и понятными описанные ранее свойства. В качестве формальной системы мы будем рассматривать множество векторов в трехмерном пространстве. Покажем, что такая формальная система является исчислением. В качестве множества объектов данной системы мы естественно будем рассматривать все вектора, которые можно построить в данном пространстве. Аксиомами данного исчисления мы назовем ортонормированнный базис трехмерного пространства т.е. привычные и знакомые вам из линейной геометрии единичные векторы i, j, k. В качестве правил вывода будем рассматривать операции над векторами:

  1. Умножение вектора на число.

  2. Сложение векторов между собой.

Можно определить операции и отношения в данном исчислении, но это не так интересно. Покажем, что какая система аксиом данного исчисления независима.

О полноте системы аксиом: из известных и строго доказанных теорем линейной алгебры известно, что любой вектор можно представить в виде линейной комбинации векторов i, j, k . следовательно, используя оба названный правила вывода мы можем построить любой вектор в трехмерном пространстве. А добавление любого из векторов сделает систему аксиом линейно зависимой, в силу того же утверждения. В линейной алгебре же доказано, что ни один из базисных векторов нельзя выразить через оставшиеся базисные вектора. Следовательно приведенная система аксиом для данного исчисления независима.
^

Тема 4.5. Теоремы Геделя.


Любое формальное математическое доказательство непротиворечивости использует средства той или иной математической теории, а потому лишь сводит вопрос о непротиворечивости одной теории к вопросу о непротиворечивости другой теории. При этом говорят, что первая теория непротиворечива относительно второй теории.

Эти фундаментальные понятия рассматриваются в теореме Геделя о полноте классического исчисления предикатов. Всякая предикатная формула, истинная во всех моделях, выводима (по всем формальным правилам классического исчисления предикатов). Т.е. теорема говорит о том, что множество формально выводимых формул этого исчисления в каком-то смысле максимально – оно содержит все чисто логические законы теоретико-множественной математики.

И в тоже время, Гедель доказывает пожалуй самую известную теорему современности, обсуждаемую и комментируемую учеными в разных областях знаний. Теорема о неполноте: в любой непротиворечивой, формальной системе, содержащей минимум математики («+», «*», кванторы и обычные правила обращения с ними) найдется формально неразрешимое суждение т.е. такая замкнутая формула А, что ни А, ни А не являются выводимыми в системе. Эта теорема знаменовала неудачу первоначального понимания программы, предусматривающей полную формализацию всей существующей математики, и обоснования полученной формальной системы путем финитного доказательства ее непротиворечивости. Теорема показала, что даже если финитными считаются все средства формализованной арифметики, этого не хватит для доказательства непротиворечивости арифметики.

Исторический аспект важности результатов, полученных Геделем, состоит в том, что к этому моменту существовали обширные системы аксиом, что все методы доказательства, существующие в математике, были сведены к небольшому числу аксиом и правил вывода. Поэтому разумно было предположить, что этих аксиом и правил вывода будет достаточно, чтобы получить ответ на любой математический вопрос, который вообще может быть поставлен в этих системах. В теореме было показано, что это не так, что в системах имеются проблемы – и даже очень простые, относящиеся к теории целых чисел. И это обстоятельство не связано ни с какой специфической природой систем, напротив, оно имеет место для широкого класса формальных систем, к которым в частности, принадлежат все системы, полученные из базовых, путем присоединения к ним конечного числа аксиом, если это присоединение не приводит к тому, что доказуемым становится какое-либо ложное предложение.

Для доказательства своей теоремы Гедель строит формальную систему, родственную формальной арифметике. Показывает рекурсивность функций сложения, умножения и возведения в степень. Отталкиваясь от этих утверждений, Гедель вводит способ сведения любой формулы к формальной арифметике, и показывает простые алгоритмы определения истинности или ложности формулы (используется классическое определение формулы). А потом строит высказывание, которое не является ни доказуемым, ни недоказуемым в рамках этой формальной системы. Тем самым показывается неполнота непротиворечивой формальной системы. Наличие в системе содержательно истинной, но формально недоказуемой формулы говорит о неполноте системы, в данном случае области арифметики натуральных чисел. Следовательно, если арифметика непротиворечива, то она неполна. А если она противоречива, то понятие теоремы в ней лишается смысла, т.к. в противоречивой системе доказуема любая ее формула. Из всего сказанного следует вывод: невозможно доказывать непротиворечивость арифметики, средствами, формализуемыми в самой арифметике. Это касается любой формальной теории, содержащей математику.

Открытия Геделя положили начало исследованиям о некоторой внутренней ограниченности регулярных процедур дедуктивного и математического характера и о невозможности представления процесса расширения знания в виде завершенной формальной системы.


Скачать файл (389.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru