Задача 8.3. Равносильны ли высказывания А и Б? Если нет, то следует ли хотя бы одно из них из другого?
1) А: «Некоторые принцессы – красавицы»; Б: «Некоторые красавицы – принцессы».
2) А: «Все принцессы – красавицы»; Б: «Все красавицы – принцессы».
3) А: «Число N кратно 11»; Б: «Сумма цифр числа А, стоящих на четных местах, равна сумме цифр, стоящих на нечетных местах».
4) А: «Число N является квадратом натурального числа»; Б: «У числа N нечетное число делителей».
5) А: «У любой девочки из 6 „А“ больше друзей среди одноклассников, чем у любого мальчика из 6 „А“ среди одноклассниц»; Б: «В 6 „А“ мальчиков больше, чем девочек».
Ответ. 1) Равносильны; 2) нет; 3) нет, но Б ⇒ А; 4) равносильны; 5) нет, но А ⇒ Б.
Решение. Пункты 1 и 2 уже обсуждались в задачах 2.3 и 2.11.
3) Утверждение А ⇒ Б следует из признака делимости на 11; обратное неверно, например, 803 кратно 11, но суммы цифр на четных и нечетных местах не равны друг другу.
4) Объединим делители числа N в пары так, чтобы произведение двух чисел в паре равнялось N. Ясно, что N = n>2 равносильно существованию числа п, которое является парным самому себе, при этом число делителей нечетно.
5) Поставим в соответствие каждому шестикласснику количество его друзей противоположного пола. Сумма этих чисел у всех девочек такая же, как и у всех мальчиков, и равна количеству дружб между мальчиком и девочкой. Так как все слагаемые для девочек больше, чем для мальчиков, у мальчиков должно быть больше слагаемых. Поэтому А ⇒ Б. Обратное неверно, для доказательства достаточно любого контрпримера. Например, в классе одна девочка и два мальчика, и никто из них ни с кем не дружит.
Задача 8.4. Чтобы доказать равносильность двух утверждений А и Б, необходимо доказать две теоремы: А ⇒ Б и Б ⇒ А. А какое наименьшее число теорем надо доказать, чтобы убедиться в равносильности: а) трех утверждений;
б) десяти утверждений?
Ответ, а) Три; б) десять.
Решение. Чтобы доказать, что из любого утверждения следует любое другое, достаточно получить их друг из друга по кругу (для трех утверждений А ⇒ Б ⇒ В ⇒ А, для десяти аналогично), при этом число теорем равно числу утверждений.
С другой стороны, теорем не может получиться меньше, чем утверждений. Действительно, для каждого утверждения должна быть теорема, где оно стоит справа от знака «⇒», иначе оно ни из чего не следует.
Доказательство по кругу не всегда оказывается самым удобным. Иногда доказывают не минимальное количество теорем, а больше, зато каждая из них достаточно проста. Убедимся в этом, решив следующую задачу.
