Не найдутся числа удовлетворяющие уравнению

ЛОГИКА И ДОКАЗАТЕЛЬСТВО Введение в раздел Логика необходима

ЛОГИКА И ДОКАЗАТЕЛЬСТВО» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_0.jpg» alt=»>ЛОГИКА И ДОКАЗАТЕЛЬСТВО» /> ЛОГИКА И ДОКАЗАТЕЛЬСТВО

Введение в раздел Логика необходима в любой формальной дисциплине и состоит из правил получения» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_1.jpg» alt=»>Введение в раздел Логика необходима в любой формальной дисциплине и состоит из правил получения» /> Введение в раздел Логика необходима в любой формальной дисциплине и состоит из правил получения обоснованного вывода (заключения). Логику можно выделить из контекста тех дисциплин, в которых она используется, и изучать как отдельный раздел науки. Акцент в этой части курса будет сделан именно на логике, лежащей в основе неоспоримых рассуждений и доказательств.

Мы познакомимся с логикой высказываний, имеющей дело с истинностью (или ложностью) простых описательных утверждений,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_2.jpg» alt=»>Мы познакомимся с логикой высказываний, имеющей дело с истинностью (или ложностью) простых описательных утверждений,» /> Мы познакомимся с логикой высказываний, имеющей дело с истинностью (или ложностью) простых описательных утверждений, что можно рассматривать как короткое введение в логику предикатов. Скажем сразу, что предикатами принято называть утверждения, содержащие переменные величины.

Кроме того, мы рассмотрим различные методы доказательств (прямое рассуждение, метод «от противного» и обратное» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_3.jpg» alt=»>Кроме того, мы рассмотрим различные методы доказательств (прямое рассуждение, метод «от противного» и обратное» /> Кроме того, мы рассмотрим различные методы доказательств (прямое рассуждение, метод «от противного» и обратное рассуждение), снабженные простыми примерами проверки фактов о четных и нечетных числах, иллюстрирующими методологию рассуждений. Наконец, мы рассмотрим сильный метод доказательства, называемый методом математической индукции.

Высказывания и логика Стандартными блоками формальной логики являются высказывания. Высказыванием называется утверждение,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_4.jpg» alt=»>Высказывания и логика Стандартными блоками формальной логики являются высказывания. Высказыванием называется утверждение,» /> Высказывания и логика Стандартными блоками формальной логики являются высказывания. Высказыванием называется утверждение, которое имеет значение истинности, то есть может быть истинным (обозначается буквой И) или ложным (обозначается буквой Л). Например, земля плоская; Анна — доктор; 17 — простое число.

Каждое из высказываний можно обозначить своей буквой. Пусть, например, Р обозначает высказывание «земля плоская»,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_5.jpg» alt=»>Каждое из высказываний можно обозначить своей буквой. Пусть, например, Р обозначает высказывание «земля плоская»,» /> Каждое из высказываний можно обозначить своей буквой. Пусть, например, Р обозначает высказывание «земля плоская», Q — «Анна — доктор» и R — «17 — простое число». Используя такие логические операции, как не, или, и, можно построить новые, так называемые составные высказывания, компонуя более простые.

Например, (не Р) — это высказывание «земля не плоская»; (Р или Q) -» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_6.jpg» alt=»>Например, (не Р) — это высказывание «земля не плоская»; (Р или Q) -» /> Например, (не Р) — это высказывание «земля не плоская»; (Р или Q) — «земля плоская или Анна — доктор»; (Р и Q) — «земля плоская и Анна — доктор».

Пример 2.1. Обозначим через Р высказывание «логика — забава», а через Q — «сегодня» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_7.jpg» alt=»>Пример 2.1. Обозначим через Р высказывание «логика — забава», а через Q — «сегодня» /> Пример 2.1. Обозначим через Р высказывание «логика — забава», а через Q — «сегодня пятница». Требуется выразить каждое из следующих составных высказываний в символьной форме. (а) Логика — не забава, и сегодня пятница. (б) Сегодня не пятница, да и логика — не забава. (в) Либо логика — забава, либо сегодня пятница.

Решение: (а) (не Р) и Q. (б) (не Р) и (не Q). (в) Р» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_8.jpg» alt=»>Решение: (а) (не Р) и Q. (б) (не Р) и (не Q). (в) Р» /> Решение: (а) (не Р) и Q. (б) (не Р) и (не Q). (в) Р или Q.

Чтобы уметь определять значение истинности составных высказываний, нам необходимо разобраться со смыслом логических операций,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_9.jpg» alt=»>Чтобы уметь определять значение истинности составных высказываний, нам необходимо разобраться со смыслом логических операций,» /> Чтобы уметь определять значение истинности составных высказываний, нам необходимо разобраться со смыслом логических операций, т. е. какой эффект они оказывают на истинностное значение простых высказываний. Это можно аккуратно сделать с помощью так называемых таблиц истинности.

Отрицанием произвольного высказывания Р называется высказывание вида (не Р), чье истинностное значение строго противоположно» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_10.jpg» alt=»>Отрицанием произвольного высказывания Р называется высказывание вида (не Р), чье истинностное значение строго противоположно» /> Отрицанием произвольного высказывания Р называется высказывание вида (не Р), чье истинностное значение строго противоположно значению Р. Определяющая таблица истинности отрицания высказывания приведена в табл. 2.1.

Таблица 2.1″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_11.jpg» alt=»>Таблица 2.1″ /> Таблица 2.1

Конъюнкцией или логическим умножением двух высказываний Р и Q называют составное высказывание вида (Р» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_12.jpg» alt=»>Конъюнкцией или логическим умножением двух высказываний Р и Q называют составное высказывание вида (Р» /> Конъюнкцией или логическим умножением двух высказываний Р и Q называют составное высказывание вида (Р и Q). Оно принимает истинное значение только в том случае, когда истинны обе его составные части. Такое определение хорошо согласуется с обычным пониманием союза «и» в разговорном языке. Соответствующая таблица истинности — это табл. 2.2.

Таблица 2.2″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_13.jpg» alt=»>Таблица 2.2″ /> Таблица 2.2

Дизъюнкцией или логическим сложением двух высказываний Р и Q называется составное высказывание (Р или» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_14.jpg» alt=»>Дизъюнкцией или логическим сложением двух высказываний Р и Q называется составное высказывание (Р или» /> Дизъюнкцией или логическим сложением двух высказываний Р и Q называется составное высказывание (Р или Q). Оно истинно, если хотя бы одна из ее составных частей имеет истинное значение, что в некотором смысле также согласуется с обыденным пониманием союза «или». Другими словами, (Р или Q) означает, что «или Р, или Q, или и то, и другое». Таблица истинности дизъюнкции обозначена как табл. 2.3.

Таблица 2.3″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_15.jpg» alt=»>Таблица 2.3″ /> Таблица 2.3

Пример 2.2. Что можно сказать об истинности составного высказывания: «либо Луна состоит из сыра» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_16.jpg» alt=»>Пример 2.2. Что можно сказать об истинности составного высказывания: «либо Луна состоит из сыра» /> Пример 2.2. Что можно сказать об истинности составного высказывания: «либо Луна состоит из сыра и у английского короля Генриха VIII было шесть жен, либо не верно, что птица дронт вымерла»?

Решение. Обозначим через Р высказывание «Луна состоит из сыра», через Q — «у Генриха» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_17.jpg» alt=»>Решение. Обозначим через Р высказывание «Луна состоит из сыра», через Q — «у Генриха» /> Решение. Обозначим через Р высказывание «Луна состоит из сыра», через Q — «у Генриха VIII было шесть жен» и через R — «птица дронт вымерла». Символьная запись данного высказывания имеет вид: (Р и Q) или (не R). Известно, что высказывание Р ложно, a Q и R истинны. Поэтому высказывание (Р и Q) или (не R) имеет такое истинностное значение: (Л и И) или (Л) = Л или Л, что эквивалентно Л.

Два составных высказывания, построенные из одних и тех же простых утверждений, но разными путями,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_18.jpg» alt=»>Два составных высказывания, построенные из одних и тех же простых утверждений, но разными путями,» /> Два составных высказывания, построенные из одних и тех же простых утверждений, но разными путями, могут принимать одинаковые значения истинности на любом возможном наборе значений истинности своих составных частей. Такие высказывания называются логически эквивалентными.

Пример 2.3. Показать, что высказывание (не (Р и (не Q))) логически эквивалентно утверждению» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_19.jpg» alt=»>Пример 2.3. Показать, что высказывание (не (Р и (не Q))) логически эквивалентно утверждению» /> Пример 2.3. Показать, что высказывание (не (Р и (не Q))) логически эквивалентно утверждению ((не Р) или Q). Решение. Заполним совместную таблицу истинности (табл. 2.4) для составных высказываний: R = (не (Р и (не Q))) и S= ((не Р) или Q). Вспомогательные колонки таблицы используются для построения обоих выражений из Р и Q.

Две последние колонки этой таблицы идентичны. Это означает, что высказывание R логически эквивалентно высказыванию» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_20.jpg» alt=»>Две последние колонки этой таблицы идентичны. Это означает, что высказывание R логически эквивалентно высказыванию» /> Две последние колонки этой таблицы идентичны. Это означает, что высказывание R логически эквивалентно высказыванию S. Таблица 2.4

Важно изучить еще один тип логического оператора, результатом которого является условное высказывание. Примером такого» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_21.jpg» alt=»>Важно изучить еще один тип логического оператора, результатом которого является условное высказывание. Примером такого» /> Важно изучить еще один тип логического оператора, результатом которого является условное высказывание. Примером такого высказывания является следующее: «если завтра будет суббота, то сегодня — пятница». При определении истинностного значения условного высказывания, необходимо различать фактическую истину и логическую.

В логике условное высказывание «если Р, то Q» принято считать ложным только в том» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_22.jpg» alt=»>В логике условное высказывание «если Р, то Q» принято считать ложным только в том» /> В логике условное высказывание «если Р, то Q» принято считать ложным только в том случае, когда предпосылка Р истинна, а заключение Q ложно. В любом другом случае оно считается истинным. Используя символ импликации « », мы пишем Р Q для обозначения условного высказывания «если Р, то Q». Такая запись читается как «из Р следует Q» или, «Р влечет Q», или «Р достаточно для Q», или «Q необходимо для Р».

Рассмотрим высказывание «если Р, то Q». В том случае, когда предпосылка Р истинна, мы» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_23.jpg» alt=»>Рассмотрим высказывание «если Р, то Q». В том случае, когда предпосылка Р истинна, мы» /> Рассмотрим высказывание «если Р, то Q». В том случае, когда предпосылка Р истинна, мы не можем получить логически корректного заключения, если Q ложно. Однако если посылка Р ложна, мы имеем логически корректное высказывание и когда Q ложно, и когда оно истинно.

Таблица истинности импликации приведена в табл. 2.5. Таблица 2.5″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_24.jpg» alt=»>Таблица истинности импликации приведена в табл. 2.5. Таблица 2.5″ /> Таблица истинности импликации приведена в табл. 2.5. Таблица 2.5

Пример 2.4. Пусть Р — (ложное) высказывание 1 = 5, Q — (тоже ложное)» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_25.jpg» alt=»>Пример 2.4. Пусть Р — (ложное) высказывание 1 = 5, Q — (тоже ложное)» /> Пример 2.4. Пусть Р — (ложное) высказывание 1 = 5, Q — (тоже ложное) высказывание 3 = 7 и R — (истинное) утверждение 4 = 4. Показать, что условные высказывания: «если Р, то Q» и «если Р, то R», — оба истинны.

Решение. Если 1 = 5, то, прибавляя 2 к обеим частям равенства, мы получим,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_26.jpg» alt=»>Решение. Если 1 = 5, то, прибавляя 2 к обеим частям равенства, мы получим,» /> Решение. Если 1 = 5, то, прибавляя 2 к обеим частям равенства, мы получим, что 3 = 7. Следовательно, высказывание «если Р, то Q» справедливо («если Р = Л, то Q = Л»). Вычтем теперь из обеих частей соотношения 1 = 5 число 3 и придем к — 2 = 2. Поэтому, возведя в квадрат: (-2)2 = 22, получим 4 = 4. Таким образом, высказывание «если Р, то R» тоже верно.

Пример 2.5. Высказывание ((не Q) (не Р)) называется противоположным или» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_27.jpg» alt=»>Пример 2.5. Высказывание ((не Q) (не Р)) называется противоположным или» /> Пример 2.5. Высказывание ((не Q) (не Р)) называется противоположным или контрапозитивным к высказыванию (Р Q). Показать, что ((не Q) (не Р)) логически эквивалентно высказыванию (Р Q).

Решение. Рассмотрим совместную таблицу истинности Таблица 2.6″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_28.jpg» alt=»>Решение. Рассмотрим совместную таблицу истинности Таблица 2.6″ /> Решение. Рассмотрим совместную таблицу истинности Таблица 2.6

Поскольку два последних столбца этой таблицы совпадают, то и высказывания, о которых идет речь,» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_29.jpg» alt=»>Поскольку два последних столбца этой таблицы совпадают, то и высказывания, о которых идет речь,» /> Поскольку два последних столбца этой таблицы совпадают, то и высказывания, о которых идет речь, логически эквивалентны.

Предикаты и кванторы Логика высказываний применяется к простым декларативным высказываниям, где базисные высказывания» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_30.jpg» alt=»>Предикаты и кванторы Логика высказываний применяется к простым декларативным высказываниям, где базисные высказывания» /> Предикаты и кванторы Логика высказываний применяется к простым декларативным высказываниям, где базисные высказывания — либо истинны, либо ложны. Утверждения, содержащие одну и более переменных, могут быть верными при некоторых значениях переменных и ложными при других.

Предикатом называется утверждение, содержащее переменные, принимающее значение истины или лжи в зависимости от значений» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_31.jpg» alt=»>Предикатом называется утверждение, содержащее переменные, принимающее значение истины или лжи в зависимости от значений» /> Предикатом называется утверждение, содержащее переменные, принимающее значение истины или лжи в зависимости от значений переменных. Например, выражение «x — целое число, удовлетворяющее соотношению x = x2» является предикатом, поскольку оно истинно при x = 0 или x = 1 и ложно в любом другом случае.

Логические операции можно применять и к предикатам. » src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_32.jpg» alt=»>Логические операции можно применять и к предикатам. » /> Логические операции можно применять и к предикатам. В общем случае истинность составного предиката в конечном счете зависит от значений входящих в него переменных. Однако существуют некоторые, еще незнакомые вам пока логические операторы, называемые кванторами, применение которых к предикатам превращает их в ложные или истинные высказывания.

Пример 2.6. Какие из следующих высказываний истинны, а какие ложны? (а) Сумма внутренних углов» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_33.jpg» alt=»>Пример 2.6. Какие из следующих высказываний истинны, а какие ложны? (а) Сумма внутренних углов» /> Пример 2.6. Какие из следующих высказываний истинны, а какие ложны? (а) Сумма внутренних углов любого треугольника равна 180°. (б) У всех кошек есть хвост. (в) Найдется целое число x, удовлетворяющее соотношению х2=2. (г) Существует простое четное число.

Решение: (а) Истинно. (б) Ложно. У бесхвостой кошки хвоста нет. (в) Ложно. (г) Истинно.» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_34.jpg» alt=»>Решение: (а) Истинно. (б) Ложно. У бесхвостой кошки хвоста нет. (в) Ложно. (г) Истинно.» /> Решение: (а) Истинно. (б) Ложно. У бесхвостой кошки хвоста нет. (в) Ложно. (г) Истинно. Число 2 является и простым, и четным.

В примере 2.6 мы имеем дело с набором объектов и утверждениями о том, что» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_35.jpg» alt=»>В примере 2.6 мы имеем дело с набором объектов и утверждениями о том, что» /> В примере 2.6 мы имеем дело с набором объектов и утверждениями о том, что некоторое свойство имеет место для всех рассматриваемых объектов, или что найдется (существует) по крайней мере, один объект, обладающий данным свойством.

Выражения «для всех» и «найдется» («существует») называются кванторами и обозначаются, соответственно, («перевернутое А») и» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_36.jpg» alt=»>Выражения «для всех» и «найдется» («существует») называются кванторами и обозначаются, соответственно, («перевернутое А») и» /> Выражения «для всех» и «найдется» («существует») называются кванторами и обозначаются, соответственно, («перевернутое А») и « » . Включая в предикат кванторы, мы превращаем его в высказывание. Поэтому предикат с кванторами может быть истинным или ложным.

Пример 2.7. Обозначим через Р(x) предикат «x — целое число и х2 = 16».» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_37.jpg» alt=»>Пример 2.7. Обозначим через Р(x) предикат «x — целое число и х2 = 16».» /> Пример 2.7. Обозначим через Р(x) предикат «x — целое число и х2 = 16». Выразите словами высказывание: x: Р(x) и определите его истинностное значение. Решение. Высказывание x: Р(x) означает, что найдется целое число x, удовлетворяющее уравнению х2 = 16. Высказывание, конечно, истинно, поскольку уравнение х2 = 16 превращается в верное тождество при x = 4. Кроме того, х = -4 — также решение данного уравнения. Однако нам не требуется рассуждать о знаке переменной x, чтобы проверить истинность высказывания x: Р(x).

Пример 2.8. Пусть Р(x) — предикат: «x — вещественное число и х2 + 1″ src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_38.jpg» alt=»>Пример 2.8. Пусть Р(x) — предикат: «x — вещественное число и х2 + 1″ /> Пример 2.8. Пусть Р(x) — предикат: «x — вещественное число и х2 + 1 = 0». Выразите словами высказывание: x: Р(x) и определите его истинностное значение. Решение. Данное высказывание можно прочитать так: существует вещественное число x, удовлетворяющее уравнению х2 + 1 = 0. Поскольку квадрат любого вещественного числа неотрицателен, т. е. х2 ≥ 0, мы получаем, что х2 + 1 ≥ 1. Следовательно, утверждение x: Р(x) ложно.

Отрицание высказывания из примера 2.8 записывается в следующем виде: » src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_39.jpg» alt=»>Отрицание высказывания из примера 2.8 записывается в следующем виде: » /> Отрицание высказывания из примера 2.8 записывается в следующем виде: не x: Р(x). Это, естественно, истинное высказывание, которое означает, что не существует вещественного числа x, удовлетворяющего условию х2 + 1 = 0. Иными словами, каково бы ни было вещественное x, х2 + 1 ≠ 0. В символьной форме это можно записать как x не Р(x).

Для общего предиката Р(x) есть следующие логические эквивалентности: не » src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_40.jpg» alt=»>Для общего предиката Р(x) есть следующие логические эквивалентности: не » /> Для общего предиката Р(x) есть следующие логические эквивалентности: не x: Р(х) x не Р(х); не x Р(х) x: Р(х). Знак обозначает в символьной форме логически эквивалентные высказывания. Как показывает следующий пример, некоторые трудности возникают, когда в высказывании участвует более одного квантора.

Пример 2.9. Предположим, что x и у — вещественные числа, а Р(x, у) обозначает» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_41.jpg» alt=»>Пример 2.9. Предположим, что x и у — вещественные числа, а Р(x, у) обозначает» /> Пример 2.9. Предположим, что x и у — вещественные числа, а Р(x, у) обозначает предикат x + у = 0. Выразите каждое из высказываний словами и определите их истинность. (а) x у : P(x, у); (б) у : x P(x, y).

Решение. (а) Высказывание x у: Р(x, у) говорит» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_42.jpg» alt=»>Решение. (а) Высказывание x у: Р(x, у) говорит» /> Решение. (а) Высказывание x у: Р(x, у) говорит о том, что для любого вещественного числа x найдется такое вещественное число у, что x + у = 0. Оно, очевидно, верно, поскольку какое бы число x мы ни взяли, число у = -x обращает равенство x + у = 0 в верное тождество.

(б) Высказывание у: x Р(x, у) читается следующим» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_43.jpg» alt=»>(б) Высказывание у: x Р(x, у) читается следующим» /> (б) Высказывание у: x Р(x, у) читается следующим образом: существует такое вещественное число у, что для любого вещественного числа x выполнено равенство x + у = 0. Это, конечно, не так: не существует вещественного числа у, обладающего указанным свойством. Следовательно, высказывание ложно.

Методы доказательств При доказательстве теорем применяется логическая аргументация. Доказательства в» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_44.jpg» alt=»>Методы доказательств При доказательстве теорем применяется логическая аргументация. Доказательства в» /> Методы доказательств При доказательстве теорем применяется логическая аргументация. Доказательства в информатике — неотъемлемая часть проверки корректности алгоритмов. Необходимость доказательства возникает, когда нам нужно установить истинность высказывания вида (Р Q). Существует несколько стандартных типов доказательств, включающих следующие:

Прямое рассуждение Предполагаем, что высказывание Р истинно и показываем справедливость Q. Такой» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_45.jpg» alt=»>Прямое рассуждение Предполагаем, что высказывание Р истинно и показываем справедливость Q. Такой» /> Прямое рассуждение Предполагаем, что высказывание Р истинно и показываем справедливость Q. Такой способ доказательства исключает ситуацию, когда Р истинно, a Q — ложно, поскольку именно в этом и только в этом случае импликация (Р Q) принимает ложное значение.

Обратное рассуждение Предполагаем, что высказывание Q ложно и показываем ошибочность Р. То» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_46.jpg» alt=»>Обратное рассуждение Предполагаем, что высказывание Q ложно и показываем ошибочность Р. То» /> Обратное рассуждение Предполагаем, что высказывание Q ложно и показываем ошибочность Р. То есть, фактически, прямым способом проверяем истинность импликации ((не Q) (не Р)), что согласно примеру 2.5, логически эквивалентно истинности исходного утверждения (Р Q).

Метод «от противного» Предположив, что высказывание Р истинно, a Q ложно, используя» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_47.jpg» alt=»>Метод «от противного» Предположив, что высказывание Р истинно, a Q ложно, используя» /> Метод «от противного» Предположив, что высказывание Р истинно, a Q ложно, используя аргументированное рассуждение, получаем противоречие. Этот способ опять-таки основан на том, что импликация (Р Q) принимает ложное значение только тогда, когда Р истинно, a Q ложно.

Пример 2.10. Покажите прямым способом рассуждений, что произведение xу двух нечетных целых чисел x» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_48.jpg» alt=»>Пример 2.10. Покажите прямым способом рассуждений, что произведение xу двух нечетных целых чисел x» /> Пример 2.10. Покажите прямым способом рассуждений, что произведение xу двух нечетных целых чисел x и у всегда нечетно. Решение. Прежде всего заметим, что любое нечетное число, и в частности x, можно записать в виде x = 2т + 1, где т — целое число. Аналогично, у = 2n + 1 с некоторым целым n. Значит, произведение xу = (2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1 тоже является нечетным числом.

Пример 2.11. Пусть n — натуральное число. Покажите, используя обратный способ доказательства, что если» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_49.jpg» alt=»>Пример 2.11. Пусть n — натуральное число. Покажите, используя обратный способ доказательства, что если» /> Пример 2.11. Пусть n — натуральное число. Покажите, используя обратный способ доказательства, что если n2 нечетно, то и n нечетно. Решение. Отрицанием высказывания о нечетности числа n2 служит утверждение «n2 четно», а высказывание о четности n является отрицанием утверждения «число n нечетно». Таким образом, нам нужно показать прямым способом рассуждений, что четность числа n влечет четность его квадрата n2. Так как n четно, то n = 2т для какого-то целого числа т. Следовательно, n2 = 4m2 = 2(2m2) — четное число.

Пример 2.12. Методом «от противного» покажите, что решение уравнения х2 = 2 является иррациональным» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_50.jpg» alt=»>Пример 2.12. Методом «от противного» покажите, что решение уравнения х2 = 2 является иррациональным» /> Пример 2.12. Методом «от противного» покажите, что решение уравнения х2 = 2 является иррациональным числом, т. е. не может быть записано в виде дроби с целыми числителем и знаменателем. Решение. Здесь нам следует допустить, что решение x уравнения x2 = 2 рационально, т. е. записывается в виде дроби x = m/n с целыми m и n, причем n 0. Предположив это, нам необходимо получить противоречие либо с предположением, либо с каким-то ранее доказанным фактом.

Как известно, рациональное число неоднозначно записывается в виде дроби. Например, » src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_51.jpg» alt=»>Как известно, рациональное число неоднозначно записывается в виде дроби. Например, » /> Как известно, рациональное число неоднозначно записывается в виде дроби. Например, и т.д. Однако можно считать, что т и n не имеют общих делителей. В этом случае неоднозначность записи пропадает.

Итак, предполагаем дополнительно, что дробь x = » src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_52.jpg» alt=»>Итак, предполагаем дополнительно, что дробь x = » /> Итак, предполагаем дополнительно, что дробь x = несократима (т и n не имеют общих делителей). По условию число x удовлетворяет уравнению х2 = 2. Значит, = 2, откуда т2 = 2n2.

Из последнего равенства следует, что число т2 четно. Следовательно, т тоже четно и может» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_53.jpg» alt=»>Из последнего равенства следует, что число т2 четно. Следовательно, т тоже четно и может» /> Из последнего равенства следует, что число т2 четно. Следовательно, т тоже четно и может быть представлено в виде т = 2р для какого-то целого числа р. Подставив эту информацию в равенство т2 = 2n2, мы получим, что 4р2 = 2n2, т. е. n2 = 2р2. Но тогда n тоже является четным числом. Таким образом, мы показали, что как m, так и n — четные числа. Поэтому они обладают общим делителем 2. Если же теперь вспомнить, что мы предполагали отсутствие общего делителя у числителя и знаменателя дроби , то увидим явное противоречие.

Найденное противоречие приводит нас к однозначному выводу: решение уравнения х2 = 2 не может» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_54.jpg» alt=»>Найденное противоречие приводит нас к однозначному выводу: решение уравнения х2 = 2 не может» /> Найденное противоречие приводит нас к однозначному выводу: решение уравнения х2 = 2 не может быть рациональным числом, т. е. оно иррационально.

Математическая индукция Компьютерную программу в информатике называют правильной или корректной, если она делает» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_55.jpg» alt=»>Математическая индукция Компьютерную программу в информатике называют правильной или корректной, если она делает» /> Математическая индукция Компьютерную программу в информатике называют правильной или корректной, если она делает то, что указано в ее спецификации. Несмотря на то, что тестирование программы может давать ожидаемый результат в случае каких-то отдельных начальных данных, необходимо доказать приемами формальной логики, что правильные выходные данные будут получаться при любых вводимых начальных значениях. О доказательствах такого сорта будет рассказано ниже.

Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется «математическая» src=»https://present5.com/presentacii/20170505/23-razdel_2_logika_i_dokazatelystvo.ppt_images/23-razdel_2_logika_i_dokazatelystvo.ppt_56.jpg» alt=»>Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется «математическая» /> Проверка корректности алгоритма, содержащего циклы, нуждается в довольно мощном методе доказательства, который называется «математическая индукция». Продемонстрируем преимущества этого важного метода, доказав корректность следующего рекуррентного алгоритма, определяющего максимальный элемент из набора a1, a2, a3, …, an натуральных чисел.

begin i := 0; М := 0; while i begin i := 0; М := 0; while i begin i := 0; М := 0; while i Действие алгоритма на наборе данных: а1 = 4, а2 = 7, а3 = 3″ /> Действие алгоритма на наборе данных: а1 = 4, а2 = 7, а3 = 3 и а4 = 8 прослежено в табл. 2.7. Таблица 2.7

Метод анализа делимости нацело

Метод анализа делимости нацело. Использование признаков делимости

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

Пример №7.

Доказать, что при любом натуральном п выражение делится нацело на 6.

Решение:

Преобразуем выражение к виду и докажем, что произведение трёх последовательных целых чисел всегда делится нацело на 6. В самом деле, каждое второе целое число кратно двум, а каждое третье — трём. Поэтому можно утверждать, что среди подряд идущих чисел п — 1, п и п + 1 по крайней мере одно делится на 2, и (одновременно с этим) одно делится на 3. Следовательно, их произведение будет делиться на 6, что и требовалось доказать.

Замечание. Аналогичными рассуждениями можно доказать, что произведение четырёх последовательных натуральных чисел делится нацело на 24.

Пример №8.

Доказать, что число делится нацело на 9.

Решение:

Преобразуем число к виду

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

Пример №9.

Найти все числа вида такие, чтобы они делились без остатка на 36.

Решение:

Поскольку 36 = 4 • 9 , то воспользуемся признаками делимости на 4 и 9. Начнём с признака делимости на 4 (он использует только одну из двух неизвестных цифр). Число кратно 4 тогда и только тогда, когда двузначное число делится нацело на 4, а это выполняется, только если Y = 2 или Y = 6 . Рассмотрим эти два случая и в каждом из них применим признак делимости на 9.

1) Если Y = 2, то число должно делиться нацело на 9, т.е. сумма всех цифр данного числа 3 + 4 + Х + 5 + 2 = 14+Х должна быть кратна 9. Это возможно лишь при X = 4 . Имеем число 34452.

2) Если Y = 6, то число кратно кратно 9, т.е. X = 0 или X = 9. Таким образом, нашли ещё два числа: 34056 и 34956. Ответ: 34452, 34056 и 34956.

Пример №10.

Решить уравнение в целых числах

Решение:

Заметим, что при целых X и Y в левой части уравнения стоит нечётное число, а в правой — чётное, что невозможно. Следовательно, данное уравнение не имеет решений в целых числах.

Пример №11.

Доказать, что уравнение не имеет целочисленных решении.

Доказательство. Достаточно заметить, что при целых X и Y выражение в левой части уравнения делится нацело на 5, а число 13 справа — нет. Полученное противоречие доказывает утверждение.

Пример №12.

Существуют ли целые числа т и п , удовлетворяющие уравнению

Решение:

Преобразуем уравнение к виду

Так как — всегда числа одинаковой чётности, то их произведение либо нечётно (что невозможно, так как 1998 — чётное число), либо кратно четырём. Но 1998 на 4 не делится.

Ответ: не существуют.

Пример №13.

Решить в целых числах систему уравнений

Решение:

1-й способ. Из первого уравнения системы следует, что числа x и у имеют разную чётность (если одно четно, то другое — нечётно, и наоборот). Из второго уравнения аналогично следует, что у и z — разной чётности, а из третьего, что X и Z также имеют разную чётность, что невозможно.

2-й способ. Сложив все три уравнения системы, получим следствие

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

Пример №14.

Известно, что 4п = 5т . Найти все натуральные числа т и n , удовлетворяющие этому равенству.

Решение:

Целочисленное выражение 4n в левой части равенства кратно 4, следовательно, и выражение 5т справа также должно делиться на 4 нацело. Но так как 5 на 4 нацело не делится, то, значит,, т.е. для любого т , удовлетворяющего исходному равенству, найдётся такое число , что Подставим в равенство: , откуда . Итак, уравнение имеет бесконечно много решений в натуральных числах, общий вид которых

Пример №15.

При каких наименьших натуральных значениях n и m выполняется равенство

Решение:

1) Заметим, что левая часть уравнения делится нацело на 3, следовательно, и правая часть уравнения должна делиться на 3, а значит, m должно быть кратно 3, т.е. Аналогично правая часть уравнения кратна 2, следовательно, и левая часть должна делиться на 2, а значит, n должно быть кратно 2, т.е. Подставим в уравнение:

2) Так как ; аналогично рассуждая, получим, что, так как Подставим в последнее уравнение:

3) Так как Подставим в уравнение:

Очевидно, что последнее равенство выполняется при Это наименьшие возможные натуральные значения и , и им соответствуют наименьшие возможные значения п и т . Найдём их.

Ответ:

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

Пример №16.

На какую минимальную величину могут отличаться друг от друга натуральные числа т и п, если известно, что дробь является натуральным числом?

Решение:

Так как число 89 — простое (убедитесь в этом сами), то данная дробь является натуральным числом тогда и только тогда, когда выражение принимает значения С учётом натуральности т и п возможен только случай, когда

Это линейное диофантово уравнение. Решим его. Очевидно, пара чисел является одним из его решений. Для нахождения множества всех решений уравнения (1) вычтем из него почленно тождество , получив уравнение, равносильное уравнению (1):

Переписав последнее уравнение в виде

воспользуемся анализом делимости левой и правой частей. Так, поскольку левая часть уравнения (2) делится нацело на 3, то и правая часть, т.е. выражение должно быть кратным числу 3. Следовательно, Это означает, что найдётся такое целое , что , т.е. Подставляя в (2), находим . Итак, множество пар где образует множество всех целочисленных решений уравнения (1). Учитывая натуральность m и n, получаем:

Тогда принимает наименьшее значение, равное 3, при l = 2 . Ответ: на

Пример №17.

Целое число кратно 7 и при делении на 4 даёт в остатке 3. Найти остаток от деления этого числа на 28.

Решение:

По условию Приравнивая, получаем линейное уравнение

которое необходимо решить в целых числах. Подберём любую пару целых чисел (k,m), удовлетворяющих уравнению, например (l,l). Вычитая из уравнения тождество , приходим к уравнению, равносильному решаемому:

В последнем уравнении выражение справа делится нацело на 4, следовательно, Тогда что означает, что число n делится на 28 с остатком 7.

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

Пример №18.

Найти хотя бы одну пару целых чисел а и b , удовлетворяющих соотношению

Решение:

1) Так как и в правой части , то отсюда следует, что для того чтобы удовлетворять данному уравнению, выражение 59b должно быть кратно 3, т.е. найдётся такое , что . Подставим в уравнение, и после сокращения на 3 получим новое уравнение (заметим, что коэффициент при а уменьшился):

2) Продолжаем анализировать делимость. Поскольку в последнем равенстве число чётно, то , должно быть нечётным, а значит, и число должно быть нечётным, т.е. Подставив в последнее уравнение и сократив на 2, получим

(коэффициент при а стал ещё меньше).

3) Так как , то, следовательно, , делится на 6, т.е. После подстановки и упрощения получим:

4) Из последнего уравнения анализом делимости на 2 получаем, что нечётно, т.е. . Подставим в уравнение и найдём общий вид всех а , удовлетворяющих исходному уравнению:

Осталось найти b :

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

(мы переобозначили для простоты на ). Для получения одного из решений положим, например, ; тогда

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

Эта лекция взята со страницы, где размещён подробный курс лекций по предмету математика:

Эти страницы возможно вам будут полезны:

Образовательный сайт для студентов и школьников

Копирование материалов сайта возможно только с указанием активной ссылки «www.lfirmal.com» в качестве источника.

math4school.ru

Уравнения в целых числах

Немного теории

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который исследовал некоторые типы таких уравнений ещё до нашей эры.

Современной постановкой диофантовых задач мы обязаны французскому математику Ферма. Именно он поставил перед европейскими математиками вопрос о решении неопределённых уравнений только в целых числах. Наиболее известное уравнение в целых числах – великая теорема Ферма: уравнение

не имеет ненулевых рациональных решений для всех натуральных n > 2.

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

В 1970 году ленинградский математик Юрий Владимирович Матиясевич доказал, что общего способа, позволяющего за конечное число шагов решать в целых числах произвольные диофантовы уравнения, не существует и быть не может. Поэтому следует для разных типов уравнений выбирать собственные методы решения.

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

способ перебора вариантов;

применение алгоритма Евклида;

представление чисел в виде непрерывных (цепных) дробей;

разложения на множители;

решение уравнений в целых числах как квадратных (или иных) относительно какой-либо переменной;

метод бесконечного спуска.

Задачи с решениями

1. Решить в целых числах уравнение x 2 – xy – 2y 2 = 7.

Запишем уравнение в виде (x – 2y)(x + y) = 7.

Так как х, у – целые числа, то находим решения исходного уравнения, как решения следующих четырёх систем:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Решив эти системы, получаем решения уравнения: (3; –2), (5; 2), (–3; 2) и (–5; –2).

Ответ: (3; –2), (5; 2), (–3; 2), (–5; –2).

2. Решить в целых числах уравнение:

а) 20х + 12у = 2013;

в) 201х – 1999у = 12.

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

Ответ: решений нет.

б) Подберём сначала некоторое конкретное решение. В данном случае, это просто, например,

Поскольку числа 5 и 7 взаимно простые, то

Значит, общее решение:

х = 1 + 7k, у = 2 – 5k,

где k – произвольное целое число.

Ответ: (1+7k; 2–5k), где k – целое число.

в) Найти некоторое конкретное решение подбором в данном случае достаточно сложно. Воспользуемся алгоритмом Евклида для чисел 1999 и 201:

НОД(1999, 201) = НОД(201, 190) = НОД(190, 11) = НОД(11, 3) = НОД(3 , 2) = НОД(2, 1) = 1.

Запишем этот процесс в обратном порядке:

1 = 2 – 1 = 2 – (3 – 2) = 2·2 – 3 = 2· (11 – 3·3) – 3 = 2·11 – 7·3 = 2·11 – 7(190 – 11·17) =

= 121·11 – 7·190 = 121(201 – 190) – 7·190 = 121·201 – 128·190 =

= 121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

Значит, пара (1273, 128) является решением уравнения 201х – 1999у = 1. Тогда пара чисел

x₀ = 1273·12 = 15276, y₀ = 128·12 = 1536

является решением уравнения 201х – 1999у = 12.

Общее решение этого уравнения запишется в виде

х = 15276 + 1999k, у = 1536 + 201k, где k – целое число,

или, после переобозначения (используем, что 15276 = 1283 + 7·1999, 1536 = 129 + 7·201),

х = 1283 + 1999n, у = 129 + 201n, где n – целое число.

Ответ: (1283+1999n, 129+201n), где n – целое число.

3. Решить в целых числах уравнение:

а) x 3 + y 3 = 3333333;

б) x 3 + y 3 = 4(x 2 y + xy 2 + 1).

а) Так как x 3 и y 3 при делении на 9 могут давать только остатки 0, 1 и 8 (смотрите таблицу в разделе «Делимость целых чисел и остатки»), то x 3 + y 3 может давать только остатки 0, 1, 2, 7 и 8. Но число 3333333 при делении на 9 даёт остаток 3. Поэтому исходное уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

б) Перепишем исходное уравнение в виде (x + y) 3 = 7(x 2 y + xy 2 ) + 4. Так как кубы целых чисел при делении на 7 дают остатки 0, 1 и 6, но не 4, то уравнение не имеет решений в целых числах.

Ответ: целочисленных решений нет.

а) в простых числах уравнение х 2 – 7х – 144 = у 2 – 25у;

б) в целых числах уравнение x + y = x 2 – xy + y 2 .

а) Решим данное уравнение как квадратное относительно переменной у. Получим

у = х + 9 или у = 16 – х.

Поскольку при нечётном х число х + 9 является чётным, то единственной парой простых чисел, которая удовлетворяет первому равенству, является (2; 11).

Так как х, у – простые, то из равенства у = 16 – х имеем

С помощью перебора вариантов находим остальные решения: (3; 13), (5; 11), (11; 5), (13; 3).

Ответ: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

б) Рассмотрим данное уравнение как квадратное уравнение относительно x:

x 2 – (y + 1)x + y 2 – y = 0.

Дискриминант этого уравнения равен –3y 2 + 6y + 1. Он положителен лишь для следующих значений у: 0, 1, 2. Для каждого из этих значений из исходного уравнения получаем квадратное уравнение относительно х, которое легко решается.

Ответ: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Существует ли бесконечное число троек целых чисел x, y, z таких, что x 2 + y 2 + z 2 = x 3 + y 3 + z 3 ?

Попробуем подбирать такие тройки, где у = –z. Тогда y 3 и z 3 будут всегда взаимно уничтожаться, и наше уравнение будет иметь вид

Чтобы пара целых чисел (x; y) удовлетворяла этому условию, достаточно, чтобы число x–1 было удвоенным квадратом целого числа. Таких чисел бесконечно много, а именно, это все числа вида 2n 2 +1. Подставляя в x 2 (x–1) = 2y 2 такое число, после несложных преобразований получаем:

y = xn = n(2n 2 +1) = 2n 3 +n.

Все тройки, полученные таким образом, имеют вид (2n 2 +1; 2n 3 +n; –2n 3 – n).

6. Найдите такие целые числа x, y, z, u, что x 2 + y 2 + z 2 + u 2 = 2xyzu.

Число x 2 + y 2 + z 2 + u 2 чётно, поэтому среди чисел x, y, z, u чётное число нечётных чисел.

Если все четыре числа x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 делится на 4, но при этом 2xyzu не делится на 4 – несоответствие.

Если ровно два из чисел x, y, z, u нечётны, то x 2 + y 2 + z 2 + u 2 не делится на 4, а 2xyzu делится на 4 – опять несоответствие.

Поэтому все числа x, y, z, u чётны. Тогда можно записать, что

и исходное уравнение примет вид

Теперь заметим, что (2k + 1) 2 = 4k(k + 1) + 1 при делении на 8 даёт остаток 1. Поэтому если все числа x₁, y₁, z₁, u₁ нечётны, то x₁ 2 + y₁ 2 + z₁ 2 + u₁ 2 не делится на 8. А если ровно два из этих чисел нечётно, то x₁ 2 + y₁ 2 + z₁ 2 + u₁ 2 не делится даже на 4. Значит,

и мы получаем уравнение

Снова повторив те же самые рассуждения, получим, что x, y, z, u делятся на 2 n при всех натуральных n, что возможно лишь при x = y = z = u = 0.

7. Докажите, что уравнение

(х – у) 3 + (y – z) 3 + (z – x) 3 = 30

не имеет решений в целых числах.

Воспользуемся следующим тождеством:

(х – у) 3 + (y – z) 3 + (z – x) 3 = 3(х – у)(y – z)(z – x).

Тогда исходное уравнение можно записать в виде

(х – у)(y – z)(z – x) = 10.

Обозначим a = x – y, b = y – z, c = z – x и запишем полученное равенство в виде

Кроме того очевидно, a + b + c = 0. Легко убедиться, что с точностью до перестановки из равенства abc = 10 следует, что числа |a|, |b|, |c| равны либо 1, 2, 5, либо 1, 1, 10. Но во всех этих случаях при любом выборе знаков a, b, c сумма a + b + c отлична от нуля. Таким образом, исходное уравнение не имеет решений в целых числах.

8. Решить в целых числах уравнение 1! + 2! + . . . + х! = у 2 .

если х = 1, то у 2 = 1,

если х = 3, то у 2 = 9.

Этим случаям соответствуют следующие пары чисел:

Заметим, что при х = 2 имеем 1! + 2! = 3, при х = 4 имеем 1! + 2! + 3! + 4! = 33 и ни 3, ни 33 не являются квадратами целых чисел. Если же х > 5, то, так как

5! + 6! + . . . + х! = 10n,

можем записать, что

1! + 2! + 3! + 4! + 5! + . . . + х! = 33 + 10n.

Так как 33 + 10n – число, оканчивающееся цифрой 3, то оно не является квадратом целого числа.

Ответ: (1; 1), (1; –1), (3; 3), (3; –3).

9. Решите следующую систему уравнений в натуральных числах:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0, то a 3 > b 3 + c 3 ;

таким образом имеем

b 2 2 + х = у 4 + у 3 + у 2 + у.

Разложив на множители обе части данного уравнения, получим:

х(х + 1) = у(у + 1)(у 2 + 1),

х(х + 1) = (у 2 + у)(у 2 + 1)

Такое равенство возможно, если левая и правая части равны нулю, или представляют собой произведение двух последовательных целых чисел. Поэтому, приравнивая к нулю те или иные множители, получим 4 пары искомых значений переменных:

Произведение (у 2 + у)(у 2 + 1) можно рассматривать как произведение двух последовательных целых чисел, отличных от нуля, только при у = 2. Поэтому х(х + 1) = 30, откуда х₅ = 5, х₆ = –6. Значит, существуют ещё две пары целых чисел, удовлетворяющих исходному уравнению:

Ответ: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Задачи без решений

1. Решить в целых числах уравнение:

б) х 2 + у 2 = х + у + 2.

2. Решить в целых числах уравнение:

а) х 3 + 21у 2 + 5 = 0;

б) 15х 2 – 7у 2 = 9.

3. Решить в натуральных числах уравнение:

4. Доказать, что уравнение х 3 + 3у 3 + 9z 3 = 9xyz в рациональных числах имеет единственное решение

5. Доказать, что уравнение х 2 + 5 = у 3 в целых числах не имеет решений.

источники:

http://lfirmal.com/metod-analiza-delimosti-natselo-v-matematike/

http://math4school.ru/uravnenija_v_celih_chislah.html