Урок №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)) ⇔ ∃x₀ ∈ M ¬(P(x₀))

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

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

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

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

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

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

Пример №5

Пусть , a ≠ 0, — квадратичная функция, . Доказать, что

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

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

  (1)

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

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

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

Ну а тем кто добрался так далеко представляю

Задания для самостоятельно работы

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

Задача №1 Никакие три диагонали выпуклого десятиугольника не пересекаются в одной точке. Определить число точек пересечения диагоналей.

Можно перепроверить другим способом: число точек пересечения диагоналей выпуклого n-угольника, лежащих внутри этого многоугольника можно найти по формуле:

Посчитаем для нашего случая: 10*9*8*7:24 = 210

Ответ: 210 точек

Задача №2 Сколько различных десятизначных чисел можно записать, используя только цифры 1 и 2.

Если число, записанное единицами и двойками, содержит десять цифр, то таких чисел будет:

Ответ: 1024 числа

Задача №3 Сколькими способами можно упаковать 9 разных книг в 5 бандеролей, если 4 бандероли должны содержать по 2 книги.

1. выбираем книгу в маленькую бандероль — 9 способов;
2.  из оставшихся 8 выбираем пару книг в первую бандероль 8*7, причем так как у нас получается дублирующие случаи (сначала берем 1, потом 3 или сначала 3, потом 1 книги) , делим пополам;
3.  аналогично заполняем третью, четвертую и пятую бандероли.

В итоге получаем:

Ответ: 945 способов

Если остались вопросы по задачам — пишите в комментариях, обязательно ответим

На следующей урок задам вам всего 1 задачку:

Выяснить, какое из утверждений А и В следует из другого, используя символы ⇒ и ⇔:

1) А ≡ {каждое из чисел а, b делится на 7}, В ≡ {сумма а + b делится на 7};

2) А ≡ {последняя цифра числа а четная}, В ≡ {число А делится на 4};

3) А ≡ {треугольник равнобедренный}, В ≡ {две медианы треугольника равны между собой};

4) А ≡ {из отрезков, длины которых равны а, b, с, можно составить треугольник}, В ≡ {положительные числа а, b, с связаны неравенствами а + b > с, b + с > а, с + а > b}.

Ответ на поставленную задачу вы найдете в следующем уроке «Действительные числа»