Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Построение математических доказательств

Теоретические сведения

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

  • 1. Тезис, т.е. то, что предполагается доказать.
  • 2. Аргументы, т.е. совокупность фактов, общепринятых понятий, законов и т.п. соответствующей науки.
  • 3. Демонстрация, т.е. сама процедура развертывания доказательства; последовательная цепь умозаключений, когда /7-е умозаключение становится одной из посылок (п + 1 )-го умозаключения. Выделяются правила доказательства, указаны возможные логические ошибки.

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

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

Как правило, в математике выделяют следующие понятия:

  • • теоремы, как доказуемые утверждения;
  • • гипотезы, если ни утверждение, ни его отрицание еще не доказаны;
  • • леммы как менее сложные утверждения, которые доказываются.

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

В зависимости от контекста может иметься в виду формальное доказательство (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при желании можно восстановить формальное доказательство. Формальными доказательствами занимается специальная ветвь математики — теория доказательств.

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

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

Ошибочным доказательством называется текст, содержащий логические ошибки, т.е. такой, по которому нельзя восстановить формальное доказательство. Ошибочным может быть только признание «доказательства» на естественном или формальном языке доказательством; формальное доказательство ошибочным не может быть по определению.

При характеристике математического доказательства выделяют две особенности.

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

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

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

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

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

Правило подстановки. В математике подстановка определяется как замена каждого из элементов а данного множества каким-либо другим элементом Р(а) из того же множества. В математической логике правило подстановки формулируется следующим образом: «Если истинная формула М в исчислении высказываний содержит букву, скажем А, то, заменив ее повсюду, где она встречается, произвольной буквой D, мы получим формулу, так же истинную, как и исходная».

Это возможно, и допустимо потому именно, что в исчислении высказываний отвлекаются от смысла высказываний (формул). Учитываются только значения «истина» или «ложь». Например, в формуле R : А —> (В v А)) на место А подставляем выражение (В v А), в результате получаем новую формулу R : (Av В) —> V V В)).

Правило вывода заключений (иногда называют правило отделения) соответствует структуре условно-категорического силлогизма modus pone ns (модус утверждающий) в формальной логике. Он имеет следующий вид:

а, а —> b b

Дано высказывание а и еще дано а —> Ь. Из этого следует Ь.

Например: «Если идет дождь, то мостовая мокрая, дождь идет (а), следовательно, мостовая мокрая (b)». В математической логике это высказывание записывается таким образом: ((а —> Ь) &. а) —> Ь.

Умозаключение определяется как правило отделения для импликации. Если дана импликация —> Ь) и ее посылка (а), то мы вправе присоединить к рассуждению (доказательству) также и следствие данной импликации (b). Силлогизм носит принудительный характер, составляя арсенал дедуктивных средств доказательства, т.е. абсолютно отвечая требованиям математических рассуждений.

Большую роль в математическом доказательстве играет теорема дедукции — общее название для ряда теорем, процедура которых обеспечивает возможность установить доказуемость импликации: А —> В, когда налицо логический вывод формулы В из формулы А. В наиболее распространенном варианте исчисления высказываний (в классической, интуиционистской и других видах математики) теорема о дедукции утверждает следующее: «Если дана система посылок G и посылка А, из которых согласно правилам выводимо В (G, A h В, где Ь — знак выводимости), то следует, что только из посылок G можно получить предложение А —> В».

Выделяется два вида доказательств — прямое и косвенное.

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

Наиболее используемые виды прямых доказательств:

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

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

Прямой логический вывод. При прямом логическом выводе, устанавливая истинность Л —> В, мы предполагаем, что Л — истинно, и показываем истинность В. Такой способ доказательства исключает ситуацию (согласно таблице истинности импликации), когда Л — истинно, а В — ложно.

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

Л—>B = AvB=BvA = B—> А.

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

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

Трансфинитная индукция основана на следующем утверждении.

Пусть М — упорядоченное множество, Р{х) прих е М — некоторое утверждение. Пусть для любого X Е М из того, что Р(у) истинно для всех у <х, следует, что верно Р(х), и пусть верно утверждение Р(х), если х — минимальный элемент М, тогда утверждение Р(х) верно для любого X.

Косвенные доказательства. Не имея в силу ряда причин (недоступность объекта исследования, утрата реальности его существования и т.п.) возможности провести прямое доказательство истинности какого-либо утверждения, тезиса, строят антитезис. Убеждаются, что антитезис ведет к противоречиям и, стало быть, является ложным. Тогда из факта ложности антитезиса делают — на основании закона исключенного третьего v а) — вывод об истинности тезиса.

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

  • • доказательство от противного;
  • • доказательство через контрпример;
  • • внесение противоречия.

Доказательство от противного в математике — один из самых часто используемых методов доказательства утверждений. Дана последовательность формул (7 и отрицание А (С, А). Если из этого следует В

и его отрицание (С, А, В, В, не-/?), то можно сделать вывод, что из последовательности формул (7 вытекает истинность А. Иначе говоря, из ложности антитезиса следует истинность тезиса.

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

Этот способ доказательства основывается на истинности формулы ((А —>/?)&/?)—> Д в классической логике и законе двойного

отрицания А = А.

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

  • 1. Сначала принимают предположение, что утверждение А неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение В, которое заведомо неверно.
  • 2. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение А = А, которое по закону двойного отрицания равносильно утверждению А.

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

  • 1. Сначала принимают предположение, что утверждение Л верно, а затем рассматривается особый случай — контрпример, при котором данное утверждение А неверно.
  • 2. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение А.

Задачи

Задача 4.39. Доказать общезначимость формулы /х/?(х) —» Зх/?(х), используя прямой вывод.

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

  • 1. Предположим, что формула общезначима.
  • 2. Тогда, используя равносильности для двойственности исчисления предикатов, получим тождественно истинную формулу

/xR(x) —> 3xR(x) = /xR(x) v 3xR(x) =

= 3xR(X) v 3xR(x) = 3x(R(X) v R(x)) = 3x(l) = 1.

  • 3. Раз формула тождественно истинна, так она общезначима.
  • 4. т.д.

Задача 4.40. Доказать общезначимость формулы R = (УхР(х) —> —> ЗхР(х)) через обратное рассуждение.

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

Давайте определим, какое высказывание Л —> В мы здесь должны доказать: «Из формулы R следует, что она общезначима». Таким образом, высказывание Л — «формула R», высказывание В — «общезначимость R».

Отрицанием высказывания, что формула общезначима, является: «Формула R тождественно ложна». Отрицанием от формулы R является формула R.

Таким образом, мы должны доказать следующее высказывание:

«Из того, что формула R тождественно ложна, следует, что R равна нулю».

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

R = (/хР(х) —> ЗхР(х)) = /хР(х) v ЗхР(х) = ЗхР(х) v ЗхР(х).

3. Внесем квантор существования под скобку и получим, что R = 0:

R = Зх(Р(х) v Р(х)) = Ш = I = 0.

4. т.д.

Задача 4.41. Пусть Р(п) — предикат, определенный для всех натуральных п.

Требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: Р( 1), Р(2),..., Р(п),..., используя математическую индукцию.

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

Допустим, что:

  • 1. Установлено, что Р( 1) верно. (Это утверждение называется базой индукции.)
  • 2. Для любого п доказано, что если верно Р{п), то верно Р(п + 1), т.е. Уk > 1 импликация Р{п) —> Р(п + 1) верна. (Это утверждение называется индукционным переходом.)
  • 3. Тогда все утверждения нашей последовательности верны, т.е. Р(п) = 1 для любого натурального п.
  • 4. т.д.

Задача 4.42. Доказать, что бинарное отношение T(N) = {res(Z> + 1, а) = 1}, заданное на множестве натуральных чисел N > 1, обладает свойством рефлексивности, используя математическую индукцию. Доказательство.

  • 1. База индукции. Пусть а = 2, b = 2. Тогда res(2 + 1, 2) = 1 и пара (2, 2) принадлежит бинарному отношению Т.
  • 2. Индукционный переход. Рассмотрим Ь- а - /. Тогда res(/ + 1, /) = = (/ + 1) - / = 1 и пара (/, /) принадлежит бинарному отношению Т. Возьмем b = a = i + 1, res(/ + 1 + 1, / + 1) = (/ + 1 + 1) - (/ + 1) = 1 и пара (/+ 1,/ + 1) принадлежит бинарному отношению Гдля любого
  • 3. Тогда наша последовательность верна и все рефлексивные пары на натуральных числах N > 1 принадлежат нашему бинарному отношению Т.
  • 4. т.д.

Задача 4.43. Доказать от противного равносильность формул /хР(х) & VxQ(x) = Vx(P(x) & Q(x)).

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

  • 1. Предположим, что это не так, что формулы неравносильны, т.е. /хР(х) & VxQ{x) Ф Мх(Р(х) & Q(x)).
  • 2. Тогда должны найтись Р(х) и Q(x) такие, что равносильность не выполняется. В этом случае возможно три варианта:
    • Р(х) и Q(x) оба тождественно истинные;
    • • один предикат тождественно истинен, другой — нет, например Р(х) — тождественно истинен, а 0(х) — нет;
    • Р(х) и Q(x) оба не тождественно истинные.
  • 3. Рассмотрим случай, когда Р(х) и Q(x) оба тождественно истинные (табл. 4.6).
  • 4. Рассмотрим случай, когда Р(х) — тождественно истинен, а Q(x) — нет (табл. 4.7).
  • 5. Рассмотрим случай, когда Р(х) и Q(x) оба не тождественно истинные (табл. 4.8).

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

6. Следовательно, указанные формулы равносильны.

Ч.т.д.

Таблица для задачи 4.43 (шаг 3)

Предикат

Значение

Р(х)

Тождественно истинное

Q(x)

Тождественно истинное

Р(Х) & Q(X)

Тождественно истинное

VxP(x)

1

VxQ(x)

1

УхР(х) & VxQ(x)

1

/х(Р(х) & ?(x))

1

Таблица 4.7

Таблица для задачи 4.43 (шаг 4)

Предикат

Значение

Р(Х)

Тождественно истинное

Тождественно истинное

Q(x)

0

1

Р(Х) & Q(X)

0

1

/хР(х)

1

1

/xQ(x)

0

0

/xP(x) & /xQ(x)

0

0

/x(P(x) & 0(х))

0

0

Таблица 4.8

Таблица для задачи 4.43 (шаг 5)

Предикат

Значение

Р(х)

0

0

1

1

Q(x)

0

1

0

1

Р(Х) & Q(x)

0

0

0

1

/хР(х)

0

0

0

0

/xQ(x)

0

0

0

0

/xP(x) & /xQ(x)

0

0

0

0

/x(P(x) & 0(х))

0

0

0

0

Задача 4.44. Доказать от противного общезначимость формулы

/x(R(x) v Р(х)) —> (3xR(x) v ЗхР(х)). Доказательство.

  • 1. Предположим, что это не так, что формула не общезначима, т.е. должны найтись Р(х) и Q(x) такие, на которых формула равна нулю.
  • 2. Тогда

Vx(/?(x) v Р(х)) —> (3xR(x) v ЗхР(х)) =

= Vx(/?(x) v ^(х)) v Зх/?(х) v Зх/>(х) =

= 3x(R(x) & Дх)) v Зх/?(х) v ЗхР(х) =

= 3x(R(x) & Р(х) v R(x) v />(х) = Зх(1) = 1.

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

  • 3. Следовательно, наше предположение об отсутствии общезначимости было неверным и наша формула — общезначима.
  • 4. т.д.

Задача 4.45. Исследовать, используя контрпример, является ли формула /хР(х) v VxQ(x) = Vx(/>(x) v Q(x)) общезначимой. Решение.

  • 1. Предположим, что формула общезначима. Тогда она тождественно истинная для любой области.
  • 2. Приведем контрпример. Положим, ?)(х) = Р(х), оба не тождественно истинные. Тогда:
    • • Vx(/>(x) v Р(х)) = Vxl = 1 — тождественно истинное высказывание;
    • /хР(х) V /хР(х) = О v 0 = 0 — тождественно ложное высказывание.
  • 3. Правая и левая части формулы не равны между собой. Это означает, что мы получили противоречие и на данном контрпримере рассматриваемая формула ложна.
  • 4. Следовательно, наше предположение об общезначимости было неверным.
  • 5. Значит, рассматриваемая формула не является общезначимой. Рассмотрим несколько задач на построение доказательств для

свойства делимости.

Задача 4.46. Доказать методом математической индукции, что число п3 - п делится на 3 для всех натуральных п.

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

  • 1. База индукции. Пусть п = 1, тогда I3 - 1 =0. Число 0 делится нацело на любое натуральное число, в том числе и на 3.
  • 2. Индукционный переход. Предположим, что п3 - п делится на 3 при каком-то натуральном к. Тогда
  • (к + I)3 - (к + 1) = (к + 1 )((к + I)2 - 1) =

= (к + 1 )(к + 1 + 1 )(к + 1 - 1) = (к + 2 )(к + 1 )к.

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

  • 3. Следовательно, наше выражение кратно трем для любого натурального п. Индуктивным рассуждением мы доказали истинность предиката Р(п) для любого п.
  • 4. т.д.

Задача 4.47. Доказать методом математической индукции, что число 7'7 - 1 делится на 6 для всех натуральных п.

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

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

• целое число а делится на целое число b тогда и только тогда, когда

а = kb при каком-то целом числе к

  • • сумма чисел, делящихся на Ь, также делится на Ь.
  • 1. База индукции. Пусть п = 1, тогда 71 - 1 = 6. Число нацело делится на 6.
  • 2. Индукционный переход. Предположим, что 7" - 1 делится на 6 при каком-то натуральном к. Тогда
  • 7*+1 -1 = 7-7*-1 + 6- 6 = 7(7* - 1) + 6.

Число 7* - 1 делится на 6 в соответствии с нашим предположением. Делится на 6 и 7(7* - 1). Сумма чисел, кратных шести, также кратна шести.

  • 3. Следовательно, наше выражение кратно шести для любого натурального п. Индуктивным рассуждением мы доказали истинность предиката Р(п) для любого п.
  • 4. т.д.

Задача 4.48. Даны формулы Зх(Р(х) & Q(x)) и БхР(х) & 3xQ(x). Проверить, являются ли они равносильными.

Задача 4.49. Даны формулы Зх(()(*) —> С) и VxQ(x) —> С. Проверить, являются ли они равносильными.

Задача 4.50. Даны формулы Зх(С —> Q(x)) и С -» 3х0(х). Проверить, являются ли они равносильными.

Задача 4.51. Доказать общезначимость формулы Vx(?(jc) -> Р(х)) -> (Vjc?(jc) -> УхР(х)).

Задача 4.52. Доказать общезначимость формулы

Vx(R(x) V Р(х)) (Vjc/ВД V VxP(x)).

Задача 4.53. Построить прямое доказательство утверждения, что формула

Я : (((А -> (ВС)) -» ((/4 С))) -> Л -> Л

является противоречием.

Задача 4.54. Построить косвенное доказательство утверждения, что формула

Я : ((/4 ^(В-> С)) -»((/4 -» В) -» (Л -> С))) не является ни противоречием, ни тавтологией.

Задача 4.55. Построить прямое доказательство утверждения, что формула

Я : ((А ->(5 -> С)) -> ((Л -> 5) -> -> С))) не является ни противоречием, ни тавтологией.

Задача 4.56. Построить косвенное доказательство утверждения, что формула

Я : ((А ->(5 -> С)) -> ((у4 С)))

является тавтологией.

Задача 4.57. Построить прямое доказательство, что В : А(1) —> —> Зх4(х) — аксиома исчисления предикатов.

Задача 4.58. Построить косвенное доказательство, что Я : /х4(х) —> АЦ) — аксиома исчисления предикатов.

Задача 4.59. Построить прямое доказательство, что Я: ((В —> А) —> ((В —> А) —> 5)) — аксиома исчисления предикатов.

Задача 4.60. Построить доказательство через контрпример для утверждения: «Формула Я = (/х(Р(х) V 0(х)) = /хЯ(х) V /х()(х) не общезначима».

Задача 4.61. Построить доказательство через контрпример для утверждения: «Формула Я = (Бх(Р(х) & 0(х)) = БхР(х) & Зх(9(х) не общезначима».

Задача 4.62. Построить прямое доказательство по индукции для утверждения: «Бинарное отношение ДАО = {ге$(3 + 1, а) = 1}, заданное на множестве натуральных чисел N > 1, обладает свойством рефлексивности».

Задача 4.63. Построить прямое доказательство по индукции для утверждения: «Бинарное отношение ДАО = {геь(Ь, а) = 1}, заданное на множестве натуральных чисел А^> 1, иррефлексивно».

Задача 4.64. Построить прямое доказательство утверждения

Ст а- — ст+^

+ 4* ~ иА?+1 *

Задача 4.65. Построить косвенное доказательство утверждения

г*т — г'П—т ип

Задача 4.66. Построить косвенное доказательство утверждения

 
<<   СОДЕРЖАНИЕ   >>