Элементы теории доказательств в курсе математической логики | Статья в журнале «Педагогика высшей школы»

Авторы: , ,

Рубрика: Методика преподавания учебных дисциплин

Опубликовано в Педагогика высшей школы №3 (6) ноябрь 2016 г.

Дата публикации: 21.07.2016

Статья просмотрена: 77 раз

Библиографическое описание:

Иванисова О. В., Сухан И. В., Кравченко Г. Г. Элементы теории доказательств в курсе математической логики // Педагогика высшей школы. — 2016. — №3. — С. 37-38. — URL https://moluch.ru/th/3/archive/43/1192/ (дата обращения: 17.07.2018).



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

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

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

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

В алгебре высказываний обычно приходится доказывать, что некоторое высказывание B является логическим следствием некоторых высказываний A1, A2, …, An(в символической записи A1, A2, …, An |= B). Для этого применяют две схемы доказательств: прямое доказательство и косвенное.

Прямое доказательство того, что A1, A2, …, An |= B проводят по следующей схеме:

  1. Формулы A1,A2, …,Anсчитают входящими в доказательство.
  2. К доказательству присоединяют ранее доказанные формулы, в частности тавтологии.
  3. К доказательству присоединяют новые формулы, полученные по правилам вывода.
  4. Доказательство закончено, если последняя формула есть B.

Эта схема обосновывается теоремой [5] о представлении доказательства в виде цепочки формул. Для доказательства этой теоремы требуется две леммы.

Лемма 1. A1, A2, …, An |=Ai, i = 1, 2, …, n.

Доказательство следует из определения логического следствия.

Лемма 2. Если A1, A2, …, An |= Bj, j = 1, 2, …, m, и если B1, B2, …, Bm |= C, то

A1, A2, …, An |= C.

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

Доказательство проведем с помощью таблицы истинности высказываний Ai, Bj, C, построенной по переменным, входящим хотя бы в одну из формул Ai, Bj, C.

Рассмотрим строки таблицы, в которых все Ai принимают значение T (истина). Из определения логического следствия получаем, что все Bj в этих строках также получают значения T, следовательно, и C в этих строках принимает значение T, а это и означает, что A1, A2, …, An |= C.

Теорема о представлении доказательства в виде цепочки формул.

A1, A2, …, An |= B, если можно составить цепочку формул E1, E2, …, Em= B, в которой либо Ek = Aj, либо в этой цепочке есть предшествующие формулы такие, что.

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

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

Пусть такая цепочка построена, Ek удовлетворяют условию теоремы, т. е. либо Ek= Aj, либо существуют предшествующие формулы такие, что.

Докажем, что A1, A2, …, An|= Ek для k = 1…, m (Em = B). Доказательство проведем методом математической индукции.

При k = 1 имеем: предшествующих формул нет, значит E1 одна из посылок, т. е. E1 = Ai для некоторого i= 1, 2, …, n. По лемме 1 имеем: A1, A2, …, An |= Ai= E1, i = 1, …, n.

Пусть это справедливо для E1, E2, …, Ek1, т. е. A1, A2, …, An |= Ei, i= 1, …, k — 1.

Докажем, что это справедливо и для Ek.

Если Ek посылка, то применима лемма 1. Если Ekпосылкой не является, то из условия теоремы следует, что и так, как , то по предположению индукции A1, A2, …, An |= , j = 1, …, s и по лемме 2 имеем:

A1, A2 …, An |= Ek.

Тогда A1, A2, …, An |= Ek для любого k = 1, …, m.

Замечание. Очевидно, что в цепочку можно включать любую тавтологию. Если |=D (D — тавтология), то для любой формулы A имеем |=A→D. В качестве формулы A можно взять любую посылку Ai, тогда |=Ai→ D или Ai |=D.

Косвенное доказательство (или доказательство от противного) того, что

A1, A2, …, An |= B проводят по следующей схеме:

  1. Формулы A1,A2, …,Anсчитают входящими в доказательство.
  2. К доказательству присоединяют формулу .
  3. К доказательству присоединяют ранее доказанные формулы, в частности тавтологии.
  4. К доказательству присоединяют новые формулы, полученные по правилам вывода.
  5. Доказательство закончено, если в нем имеются две формулы и .

Для обоснования этой схемы нами была доказана следующая теорема.

Теорема (обоснование метода доказательства от противного).

A1, A2 …, An |= B, если из A1, A2, …, An, An+1 = можно составить цепочку формул E1, E2, …, Em в которую входят две формулы и , и в которой либо Ek = Aj, либо в этой цепочке есть предшествующие формулы такие, что.

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

Пусть такая цепочка построена.

После формул и вставим в цепочку тавтологию и применим правило отделения: Применим еще раз правило отделения .

Таким образом, в цепочке появилась формула . По теореме о представлении доказательства в виде цепочки формул имеем

A1, A2 …, An, |= . Отсюда получаем: A1, A2, …, An |= [5, с. 95].

Рассмотрим такой набор переменных, входящих во все формулы, что все Aiпринимают значение T, тогда и = T.

Так, как = F, то и = F, а следовательно B = T, а это означает, что

A1, A2, …, An |= B.

Замечание. Для присоединения к доказательству новых формул используют основные правила вывода алгебры высказываний [2]:

  1. (правило отделения, правило заключения, modus ponens).
  2. (правило отрицания, modus tollens).
  3. (правило введения конъюнкции).
  4. (правило удаления конъюнкции).
  5. (правило введения дизъюнкции).
  6. (правило удаления дизъюнкции).
  7. (правило введения эквиваленции).
  8. (правило удаления эквиваленции).
  9. (правило контрапозиции).
  10. (правило цепного заключения, правило силлогизма).
  11. (правило перестановки посылок).
  12. , (правило объединения и разъединения посылок).

Литература:

  1. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. — М.: Физматлит, 2007. — 128 с.
  2. Игошин В. И. Математическая логика и теория алгоритмов. М.: Издательский центр «Академия», 2010. — 448 с.
  3. Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. М.: Издательство Московского университета, 1982. — 120 с.
  4. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1976. — 320 с.
  5. Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.
Основные термины (генерируются автоматически): доказательство, формула, представление доказательства, правило отделения, правило вывода, вид цепочки формул, логическое следствие, цепочка формул, условие теоремы, прямое доказательство.

Похожие статьи

Логические нормы обоснования в научном познании

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

Аксиоматические теории в курсе математической логики

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

Методические аспекты обучения доказательству студентов...

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

При работе над формулировкой и доказательством теорем можно придерживаться следующего плана [5]

Формирование метапредметных умений при обучении...

доказательстве теорем и выводе формул; – решении уравнений, неравенств и их систем

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

Доказательством называется конечная последовательность...

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

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

Доказательство. Формула в стандартной интерпретации выражает невозможность вывода в теории S какой-либо формулы вместе с

Если , то по правилу отделения получаем, что . Из теоремы Гёделя следует, что если теория S непротиворечива, то формула в ней невыводима.

Целеполагание при проектировании курса «Дискретная...»

Доказательство в алгебре высказываний. Правила вывода.

Уметь представлять доказательство ЛС в виде цепочки формул.

Формировать умение формулировать прямую, обратную, противоположную, обратную противоположной теоремы.

Анализ существующих алгоритмов перевода функции алгебры...

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

Согласно правилам теории вероятностей, вероятность реализации опасного состояния системы при развитии аварии можно вычислить по формуле

К вопросу об алгоритмической сложности задачи Рейдемейстера

Прародителем ее является К. Ф. Гаусс, который дал формулу для вычисления числа

Учитывая теорию особенностей (известную как теория катастроф) теорема Рейдемейстера вполне очевидна.

Как издать спецвыпуск? Правила оформления статей. Оплата и скидки.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Логические нормы обоснования в научном познании

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

Аксиоматические теории в курсе математической логики

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

Методические аспекты обучения доказательству студентов...

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

При работе над формулировкой и доказательством теорем можно придерживаться следующего плана [5]

Формирование метапредметных умений при обучении...

доказательстве теорем и выводе формул; – решении уравнений, неравенств и их систем

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

Доказательством называется конечная последовательность...

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

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

Доказательство. Формула в стандартной интерпретации выражает невозможность вывода в теории S какой-либо формулы вместе с

Если , то по правилу отделения получаем, что . Из теоремы Гёделя следует, что если теория S непротиворечива, то формула в ней невыводима.

Целеполагание при проектировании курса «Дискретная...»

Доказательство в алгебре высказываний. Правила вывода.

Уметь представлять доказательство ЛС в виде цепочки формул.

Формировать умение формулировать прямую, обратную, противоположную, обратную противоположной теоремы.

Анализ существующих алгоритмов перевода функции алгебры...

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

Согласно правилам теории вероятностей, вероятность реализации опасного состояния системы при развитии аварии можно вычислить по формуле

К вопросу об алгоритмической сложности задачи Рейдемейстера

Прародителем ее является К. Ф. Гаусс, который дал формулу для вычисления числа

Учитывая теорию особенностей (известную как теория катастроф) теорема Рейдемейстера вполне очевидна.

Как издать спецвыпуск? Правила оформления статей. Оплата и скидки.

Посетите сайты наших проектов

Задать вопрос