Урок №2 Элементы логики. Метод математической индукции

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

Высказывания. Операции над высказываниями

Высказывание — это любое утверждение, о котором можно сказать, что оно либо истинно либо ложно.

Существует всего пять операций над высказываниями:

  • конъюнкция;
  • дизъюнкция;
  • инверсия;
  • импликация;
  • эквиваленция

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

Конъюнкция — оба высказывания истинны. Данной операции соответствует союз «и». Обозначается А ∧ В (А и В) .

Таблица истинности в двоичной системе (1-истинно, 0-ложно):

A B A ∧ B
1 1 1
1 0 0
0 1 0
0 0 0

Как видно из таблицы конъюнкцией двух высказываний А и В называется новое высказывание, которое считается истинным, если оба высказывания А и В истинны, и ложным, если хотя бы одно из них ложно.

Пример №1

Высказывания: А — «8 делится на 4»; В — «8 делится на 2»

Тогда: A ∧ B — «8 делится на 4» и «8 делится на 2» — истинно.

Из определения операции конъюнкции видно, что союз «и» в логике употребляется в том же смысле, что и в повседневной речи.

 

Дизъюнкция — одно из высказываний истинно. Данной операции соответствует союз «или». Обозначается: A ∨ B (А или В).

Кстати, данную операцию еще называют «логическое сложение», и сейчас по таблице истинности вы увидите почему:

A B A ∨ B
1 1 1
1 0 1
0 1 1
0 0 0

Как видно из таблицы дизъюнкцией двух высказываний А и В называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний А или В истинно и ложным, если они оба ложны.

Пример №2

Высказывания: А — «6 > 4»; B — «2 > 3»

Тогда A ∨ B — «6 > 4» или «2 > 3» — истинно, потому что истинно одно из высказываний (А).

 

Инверсия (отрицание) — это обратное высказывание (если было истинно — то оно становится ложным, а если было ложным, то становится истинным). Данной операции соответствует союз «не». Обозначается ¬А (не А), также обозначается

Двойное отрицание (  ) соответствует изначальному высказыванию х.

Таблица истинности:

А ¬А
1 0
0 1

Как видно из таблицы отрицанием высказывания А называется новое высказывание, которое является истинным, если высказывание А ложно, и ложным, если высказывание А истинно.

Импликация (следование) — это высказывание, содержащее условие и следствие. Данной операции соответствует слова «если…, то…» Обозначается A → B (если А, то В), где А — условие (посылка), а В — следствие (заключение).

Таблица истинности:

А В А →В
1 1 1
1 0 0
0 1 1
0 0 1

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

Пример №3

Высказывания: А– «15 делится на 5», В – «15 делится на 3».

Тогда импликация А → В – «если 15 делится на 5, то оно делится на 3» истинна, так как истинно условие А, и истинно заключение В.

 

Эквиваленция (двойная импликация) — это высказывание, при котором либо оба высказывания истинны либо оба ложны. Соответствует словам «тогда и только тогда, когда…» Обозначается А ⇔ В (А тогда и только тогда, когда В).

Таблица истинности:

А В А ⇔ В
1 1 1
1 0 0
0 1 0
0 0 1

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

Пример №4

Высказывания: А – «Треугольник MNK с вершиной M и основанием NK равнобедренный», В – «N=K».

Тогда эквиваленция А ⇔ В – «Треугольник MNK с вершиной M и основанием NK равнобедренный тогда и только тогда, когда N=KЭквиваленция A⇔B истинна, так как высказывания A и В либо одновременно истинны, либо одновременно ложны.

 

Предложения, зависящие от переменной.

Предложение Р(х), зависящее от переменной х, принадлежащей некоторому множеству М (х ∈ М), не является, вообще говоря, высказыванием. Например, об истинности предложения Р(х) = {х — простое число} ничего нельзя сказать, если не указать число х. Это предложение является истинным при одних значениях х (например, при х = 5, х = 7) и ложным при других значениях х (например, при х = 8, х = 15). Такие предложения называют неопределенными высказываниями (предикатами).

Знак общности ∀ (перевернутая первая буква английского слова All — все) заменяет слова “все”, “всякий”, “каждый”, “любой”. Если Р(х) — некоторое неопределенное высказывание, то запись ∀х Р(х) (или (∀x)P(x)) означает, что для любого элемента х ∈ М истинно Р(х), и представляет собой высказывание. Это высказывание истинно, если Р(х) истинно для каждого х ∈ М. Чтобы убедиться в ложности высказывания ∀х Р(х), достаточно указать хотя бы один противоречащий пример, допустим а ∈ М, для которого Р(а) — ложное высказывание.

Знак существования ∃ (перевернутая первая буква английского слова Exists — существует) заменяет слова “существует”, “найдется”. Запись ∃х Р(х) представляет собой высказывание; оно истинно, если существует такой элемент а ∈ М, для которого Р(а) истинно. В противном случае (если в множестве М нет ни одного элемента а, для которого Р(а) истинно) высказывание ∃х Р(х) ложно.

Правила построения отрицаний для предложений, содержащих символы ∀ и ∃ (их в логике называют кванторами), можно записать

¬(∀x ∈ M P(x)) ⇔ ∃x0 ∈ M ¬(P(x0))

¬(∃x0 ∈ M P(x0)) ⇔ ∀x ∈ M ¬(P(x))

Таким образом, для построения отрицания предложения, содержащего знаки ∀ и ∃ и утверждение Р, следует знак ∀ заменить на ∃, знак ∃ — на знак ∀, а утверждение Р — на его отрицание ¬Р.

Метод математической индукции

Чтобы доказать, что некоторое утверждение верно для любого номера n, достаточно установить, что:

А) это утверждение верно при n = 1;

Б) если утверждение справедливо для номера n (n — любое натуральное число), то оно верно и для следующего номера n + 1.

Пример №5

Пусть y = aх^2 + bx + C, a ≠ 0, — квадратичная функция, D = b^2 - 4ac. Доказать, что

∀x ∈ R  у ≥ 0} ⇔ {D ≤ 0, а > 0}

Составим равенство из уравнения и дискриминанта:

y = a(x+frac{b}{2a})^2+c-frac{b^2}{4a} = a[(x+frac{b}{2a})^2-frac{D}{4a^2}]   (1)

Из данного равенства и условий D ≤ 0, a > 0 следует, что y ≥ 0 для всех х ∈ R (первый кусок доказали).

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

Допустим, что D > 0 и квадратный трехчлен y = aх^2 + bx + C имеет действительные корни x_1 и x_2, а квадратичная функция меняет знак при переходе через точки x_1 и x_2. Следовательно, данное условие не возможно и D ≤ 0 и из равенства (1) и условия у ≥ 0 при всех x ∈ R следует, что а > 0 (доказано).

Если у вас остаются вопросы по теории или по практической части смело задавайте их в комментариях.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *