Лекции по "Алгебре"

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

 

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

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

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

    

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

      

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

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

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

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

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

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

    Тема 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. Теоремы Геделя.

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

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

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