953

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

Лекция

Прямые доказательства Теория доказательства разработана в формальной логике и включает три структурных компонента: 1. Демонстрация (сама процедура развертывания доказательства; последовательная цепь умозаключений, когда n-ное умозаключение становится одн

2013-07-18

14.65 KB

0 чел.


Чтобы скачать работу - расскажи о ней в социальной сети с помощью кнопок.

искретная математика: Математическая логика

Лекция 15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Правило подстановки 

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

Это возможно, и допустимо потому именно, что в исчислении высказываний отвлекаются от смысла высказываний (формул). Учитываются только значения "истина" или "ложь". Например, в формуле M: A--> (BUA) на место A подставляем выражение (AUB), в результате получаем новую формулу (AUB) -->[(BU(AUB)].

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

а, a--> b.

b

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

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

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

 Дедукция

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

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

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

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

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

Пример 1 .   Прямой вывод

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

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

1. Предположим, что формула общезначима.

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

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

Ч.т.д.

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

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами:  P1, P2, …, Pn, Pn+1,

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

  1.  Установлено, что P1 верно. (Это утверждение называется базой индукции.)
  2.  Для любого n доказано, что если верно Pn, то верно Pn + 1. (Это утверждение называется индукционным переходом.)
  3.   Тогда все утверждения нашей последовательности верны.

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

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

Пусть M —упорядоченное множество, P(x) при — некоторое утверждение. Пусть для любого  из того, что P(y) истинно для всех y<x следует, что верно P(x), и пусть верно утверждение P(x), если x — минимальный элемент M, тогда утверждение P(x) верно для любого x.

Пример 2.   Доказательство по индукции

Доказать, что бинарное отношение T(N)={res(b+1,a)=1}, заданное на множестве натуральных чисел N>1 , обладает свойством рефлексивности

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

1. База индукции. Пусть, а=2, в=2. Тогда res(2+1,2)=1 и пара (2,2) принадлежит бинарному отношению Т.

2.Индукционный переход. Рассмотрим b=а=i. Тогда,  res(i+1 ,i)=(i+1)-i=1 и пара (i,i) принадлежит бинарному отношению Т. Возьмем b=а=i+1, res(i+1+1, i+1)=(i+1+1)-(i+1)=1 и пара (i+1, i+1) принадлежит бинарному отношению Т для любого i.

3. Тогда наша последовательность верна и все рефлексивные пары на натуральных числах N>1 принадлежат нашему бинарному отношению Т.

Ч.т.д.

Литература

  1.  Капитонова Ю.В.  и др.  Лекции по дискретной математики СПб.: БХВ-Петербург, 2004.- 624с.
  2.  www.wikipedia.org

PAGE  5


Данной работой Вы можете всегда поделиться с другими людьми, они вам буду только благодарны!!!
Кнопки "поделиться работой":

 

Другие работы

21002. .40 учебная практика по по . 11.73 KB
  00 учебная практика учебная практика 10.40 учебная практика по по 12.00 учебная практика учебная практика 10.40 учебная практика по по 12.
21003. Найдите значение выражения . 37.84 KB
  Найдите значение выражения . Найдите значение выражения . Найдите значение выражения: Найдите значение выражения: Найдите значение выражения: Найдите значение выражения: при . Найдите значение выражения: Найдите значение выражения: Найдите значение выраж
21006. Busting Top List The President hs clled for swift pssge of the Sfegurds for New Economy S. 4.66 KB
  The omnibus economic pckge includes federl mximum wge mndtory ldquo;True Cost ccountingrdquo; phsed withdrwl from complex finncil instruments nd other mesures intended to improve life for ordinry mericns. See highlights sidebr He lso repeted erlier clls
21007. Часть хозяйств образовавшихся до 1995 года продолжает работать как юридические лица и их правовой статус на 5.68 KB
  Такие средства представляют собой сумму наличных денежных средств в кассе предприятия свободные денежные средства на расчетном валютном и других счетах в банке ценные бумаги и прочие денежные средства предприятия.2000 N 94н используются следующие счета в
21009. Физическому лицу или законному представителю юридического лица в отношении которых возбуждено дело об ад. 2.25 KB
  Физическому лицу или законному представителю юридического лица в отношении которых возбуждено дело об административном правонарушении должна быть предоставлена возможность ознакомления с протоколом об административном правонарушении. В случае неявки физи
загрузка...

RSS-лента