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

Содержание

Введение………………………………………………………………………    2

Глава 1. Элементы математической логики………………………………..     3

1.1.           Строение и виды теорем……………………………………………….   3

1.2.           Высказывания…………………………………………………………..   4

1.3.           Отрицание………………………………………………………………   7

1.4.           Неопределенные высказывания……………………………………….   9

1.5.           Знаки общности и существования…………………………………….   10

Глава 2. Необходимые и достаточные условия……………………………..   16

2.1. Необходимые и достаточные условия…………………………………..   16

2.2. Обратная и противоположная теоремы………………………………….  22

Глава 3. Примеры………………………………………………………………  28

Заключение……………………………………………………………………..  35

Список используемой литературы …………………………………………..   36

Введение

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

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

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

Для достижения поставленной цели в работе решаются следующие задачи:

1.      Раскрыть суть и содержание необходимых и достаточных условий.

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

3.      Сделать выводы по проделанной работе.

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

Глава 1. Элементы математической логики .

1.1. Строение и виды теорем.

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

Теоремы часто формулируются в виде импликаций.

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

Если импликация р  q выражает некоторую теорему, то основание р импликации выражает условие, а следствие q – заключение теоремы.

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

Приведем несколько примеров.

1.              Известная теорема о среднем арифметическом и среднем пропорциональном двух неравных положительных чисел имеет следующую структуру:

p1p2p3  q –

( a ≠ b)  (a > 0)  (b > 0)  a + b /2 > √ab .

2.              Теорема «Если диагонали параллелограмма взаимно перпендикулярны или делят его углы пополам, то этот параллелограмм – ромб» имеет структуру:

p1    p2  q,

где p1 - «Диагонали параллелограмма взаимно перпендикулярны»;

p2 - «(Диагонали параллелограмма) делят его углы пополам»;

q – «Этот параллелограмм – ромб».

3.              Теорема о средней линии трапеции имеет структуру:

p  q1q2,

где p – «Четырехугольник – трапеция»;

q1 – «Его средняя линия параллельна основаниям»;

q2 - «(Его средняя линия) равна полусумме оснований».

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

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

( a, b  R) * [(a ≠ b)  (a > 0)  (b > 0)  a + b/2 > √ab]

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

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

Так, предложение о существовании и единственности решения уравнения ах = b множестве R вещественных чисел запишется так:

( a, b  R)  [а ≠ 0  (!х) (ах = b)].

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

( a, b, c  R)  [a ≠ 0  b2 – 4ac  > 0  ( x1, x2  R) (x1 ≠ x2  ax12 + bx1 + c = 0  ax22 + bx2 + c = 0)].

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

1.2. Высказывания.

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

А ≡{число 100 делится на 4}

B ≡{число 17 делится на 8}

C ≡{три меньше пяти}

D ≡{число 2 является единственным корнем уравнения x2-4=0}.

Сразу же видно, что в некоторых из этих высказываний утверждается нечто правильное; такие высказывания называются истинными. В других же из приведенных выше высказываний утверждается нечто неверное; такие высказывания называются ложными. В приводимой ниже таблице поставлена буква И под обозначением истинных высказываний  и буква Л под обозначением ложных высказываний:

Указанные выше высказывания мы обозначали большими латинскими буквами. Так мы будем обозначать высказывания и в дальнейшем.

Всякое высказывание является предложением и может быть выражено словами. Однако при записи высказываний математики пользуются не только буквами, но и специальными математическими знаками. Каждый знак заменяет собой слово (или даже несколько слов). Используются знаки для сокращения записи. Например, высказывание C можно с помощью знаков записать следующим образом 3<5.

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

1)     Число 0,00000001 очень мало,

2)     Существует ли число, квадрат которого равен 2?

3)     x > 2,

4)     х + 5 = 12.

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

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

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

Е ≡ {число (1263728 + 1515 876)2387 + (11135 933 - 1891183)4914 + 4 является простым},

G ≡ {в записи числа  √2= в виде бесконечной десятичной дроби √2 = 1,41421… на 1 000 000-м месте после запятой стоит цифра 7}.

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

Всякое высказывание является либо истинным, либо ложным (закон исключенного третьего).

Никакое выказывание не может быть одновременно истинным и ложным (закон противоречия).

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

1.3. Отрицание.

Из всякого высказывания А можно получить новое высказывание, отрицая его, т.е. утверждая, что высказывание А не имеет места, не выполняется. Отрицание высказывания А обозначается символом ┐А. Запись ┐А читается как «отрицание высказывания А» или, короче, «не А».

Отрицание высказывания можно получить, сказав: «утверждение А места не имеет « или «А не выполняется». Однако в ряде случаев отрицание можно получить еще проще. Если, например, высказывание А выражается простым предложением с одним сказуемым, то для получения его отрицания ┐А нужно лишь добавить к сказуемому частицу «не». Приведем примеры высказываний и их отрицаний:

1)     А ≡ {число 23 делится на 7},

    ┐А ≡ {число 23 не делится на 7};

2)     В ≡ {3>5}  (т.е. три больше пяти),

               ┐В ≡ {три не больше пяти} (т.е 3≤5);

3)     С ≡ {5 + 3 = 8},

               ┐С ≡ {5 + 3  ≠ 8};

4)     D ≡ {30 (есть) простое число},

               ┐D ≡ {30 не (есть) простое число}.

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

Мы видим, что, каково бы ни было высказывание А, из двух высказываний А, ┐А одно является истинным, а другое ложным.

Например, из высказываний, указанных выше, ┐А, ┐В, ┐С, ┐D истинны, а А, В, ┐С, D ложны.

Самый простой прием образования отрицания заключается, как мы отмечали, в том, что к сказуемому добавляется частица «не». Например:

А ≡ {11 делится на 3},

┐А ≡ {11 не делится на 3}.

Однако этот простой прием будет неприменим, если само высказывание уже является отрицательным, т.е. уже содержит частицу «не» перед сказуемым. Рассмотрим, например, высказывание

В ≡ {18 не делится на 5}.

Для образования отрицания ┐В мы уже не можем добавить еще одео отрицание к сказуемому (т.е. не можем сказать: «18 не не делится на 5»). Поэтому отрицание приходится формулировать так:

┐В ≡ {высказывание «18 не делится на 5» места не имеет}.

Но что означает это утверждение? Оно означает, что 18 делится на 5, т.е. отрицание ┐В можно проще сформулировать так:

┐В ≡ {18 делится на 5}.

Таким образом, если в некотором высказывании В перед сказуемым уже стоит отрицательная частица «не», то для образования отрицания ┐В достаточно выбросить частицу «не».

Пусть теперь А – произвольное высказывание. Его отрицание ┐А также является высказыванием. Значит, можно рассматривать и его отрицание, т.е. высказывание ┐┐А. Оно называется двойным отрицанием высказывания А. Его можно сформулировать словами так: утверждение о том, что высказывание А не выполняется, места не имеет. Но это по смыслу ничем не отличается от утверждения о справедливости самого высказывания А.

Более точно, двойное отрицание ┐┐А истинно в том и только в том случае, если истинно само высказывание А (т.е. если А истинно, то и ┐┐А истинно, а если А ложно, то  и ┐┐А ложно).