Задачи

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

·        Число 376 четное и трехзначное.

·        Неверно, что Солнце движется вокруг Земли.

·        Если сумма цифр числа делится на 3, то число делится на 3.

·        Число 15 делится на 3 тогда и только тогда, когда сумма цифр числа 15 делится на 3.

2)  Найдите значения логических выражений:

а)         (l v l) v (l v 0);

б)        ((l v 0) v l) v l;

в)        (0 v l) v (l v 0);

г)         (0 & 1) & 1;

д)        1 & (1 & 1) & 1;

е)         ((1 v 0) & (l & l)) & (0 v l);

ж)         ((l & 0) v (l & 0)) v l;

з)         ((l & l) v 0) & (0 v l);

и)        ((0 & 0) v 0) & (l v l).

3)  Даны два простых высказывания:

А = {2 • 2 = 4}, В = {2 • 2 = 5}.

Какие из составных высказываний истинны:

а.) не А;                б) не В ;

в) А & В;        г) A v B;

4)  Назовем штрихом Шеффера A | B булеву функцию, которая принимает значение 1 тогда и только тогда, когда обе переменные не равны одновременно 1. Построить таблицу, определяющую штрих Шеффера. Выразить штрих Шеффера через основные операции.

5)  Назовем символом Лукашевича булеву функцию, которая принимает значение 1 тогда и только тогда, когда ни одна из переменных не равна 1. Построить таблицу, определяющую символ Лукашевича. Выразить его через основные булевы операции.

Задачи для развития логического мышления

Задача 1: 10 книг стоят больше 11 рублей, а 9 книг стоят меньше 10 рублей. Сколько стоит одна книга?

Задача 2: Если зарплату сначала увеличить на 20, а потом уменьшить на 20, увеличится она в результате или уменьшится?

Задача 3: Есть два стакана: один с молоком, другой с водой.

a) Из первого перелили ложку во второй, перемешали и перелили ложку смеси обратно. Чего больше: воды в стакане с молоком или молока в стакане с водой?

b) Тот же вопрос, если описанную процедуру повторили 100 раз.

Задача 4: В комнате стоят несколько четырехногих стульев и трехногих табуреток. Когда на всех стульях и табуретках сидит по человеку, в комнате всего 39 ног. Сколько в комнате стульев и сколько табуреток?

Задача 5: В кружке есть девочки, но мальчиков больше 94 состава. Какое минимальное число людей может быть в кружке?

Задача 6: В двух стаканах было поровну воды. Количество воды в первом увеличилось вначале на 1, потом на 2, потом на 3, и так далее до 27. Во втором стакане количество воды увеличилось вначале на 27, потом на 26, потом на 25 и так далее до 1. В каком стакане стало больше воды?

Задача 7: Из ста человек 85 – без уха, 75 – без глаза. Какое наименьшее возможное число полных инвалидов?

Задача 8: В партии из 300 сапог 150 левых и 150 правых, кроме того, по 100 штук каждого из трех размеров. Доказать, что есть по крайней мере 50 годных пар.

Задача 9: В автобусе едут 20 пассажиров, и у каждого много монет по 10, 15 и 20 копеек. Каждый должен заплатить 5 копеек. Могут ли они сделать это, использовав (в том числе и для обмена межу собой) a) 24 монеты b) 25 монет?

Задача 10: Лифт в 100-этажном доме имеет 2 кнопки: « + 7» и «-9». (первая поднимает лифт на 7 этажей, вторая опускает на 9).Можно ли проехать:

a) с первого на второй;

b) со второго на первый;

c) с любого на любой этаж?

Задача 11: В 15-этажном доме имеется лифт с двумя кнопками: « + 7" и « – 9". Можно ли проехать с третьего этажа на двенадцатый ?

Задача 12: Как с помощью наименьшего числа прямолинейных разрезов разрезать квадрат 3 × 3 на единичные квадраты

a) если части нельзя накладывать (т.е. каждый раз можно разрезать только одну часть)

b) если части можно накладывать.

c) если перед разрезами квадрат можно сложить? (Ответ: достаточно одного разреза)

Задача 13: Как разрезать на единичные квадраты квадрат a)4 × 4 b) 5 × 5 за наименьшее число разрезов. (Части при разрезании можно накладывать друг на друга).

Задача 14: Расставьте в ряд числа от 1 до 100 так, чтобы любые два соседних отличались по крайней мере на 50.

Задача 15: 50 команд сыграли турнир по волейболу в один круг. Говорят, что команда А сильнее В, если А выиграла у В или есть команда С, такая, что А выиграла у С, а С выиграла у В.Доказать, что команда, набравшая наибольшее число очков, сильнее любой другой.

Задача 16: 30 команд сыграли турнир по олимпийской системе. Сколько всего было сыграно матчей?

Задача 17: Квадрат 8 × 8 раскрашен в два цвета. Можно любой прямоугольник 1 × 3 перекрашивать в преобладающий в нем цвет. Доказать, что такими операциями можно сделать весь квадрат одноцветным.

Задача 18: Некто А загадал число от 1 до 15. Некто В задает вопросы на которые можно отвечать «да" или «нет". Может ли В отгадать число, задав a)4 вопроса b)3 вопроса.

Задача 19: a) В группе из четырех человек, говорящих на разных языках, любые трое могут общаться (возможно, один переводит двум другим). Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.

b) То же для группы из 100 человек.

c) То же для группы из 102 человек.

Задача 20: 12 команд сыграли турнир по волейболу в один круг. Две команды одержали ровно по 7 побед. Доказать, что найдутся команды А, В, С такие, что А выиграла у В, В выиграла у С, а С – у А.

Задача 21: Когда встречаются два жителя Цветочного города, один отдает другому монету в 10 копеек, а тот ему – 2 монеты по 5 копеек. Могло ли случиться так, что за день каждый из 1990 жителей города отдал ровно 10 монет?

Задача 22: Матч между двумя футбольными командами закончился со счетом 8:5. Доказать, что был момент, когда первая команда забила столько же мячей, сколько второй оставалось забить.

Задача 23: В центре куба 3 × 3 × 3 сидит жук. Доказать, что он, переползая через ребра, не сможет обойти все кубики 1 × 1 × 1 по одному разу.

Задача 24: В ряд выписаны числа от 1 до 9999. Как вычеркнуть из этой записи 100 цифр так, чтобы оставшееся число было a) максимальным b) минимальным?

Задача 25: В прямоугольнике 3 × n стоят фишки трех цветов, по n штук каждого цвета. Доказать, что можно переставить фишки в каждой строке так, чтобы в любом столбце были фишки всех цветов.

Задача 26: К числу 2¹ºº приписано число 5¹ºº. Сколько цифр написано?Задача 27: Сколько решений в натуральных числах имеет уравнение ?

Задача 27: Имеется бесконечная арифметическая прогрессия с натуральными членами. Доказать, что найдется член, в котором есть 100 девяток подряд.

Задача 28: 12 шахматистов сыграли турнир в один круг. Потом каждый из них написал 12 списков. В первом только он, в (k + 1)-м – те, кто были в k-м и те, у кого они выиграли. Оказалось, что у любого шахматиста 12-й список отличается от 11-го. Сколько было ничьих?

Задача 29: В городе 100 домов. Какое наибольшее число замкнутых непересекающихся заборов можно построить так, чтобы любые 2 забора ограничивали разные группы домов?

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

Задача 31: Несколько человек построились в два ряда. Каждый во втором ряду выше стоящего перед ним. Доказать, что если каждый ряд построить по росту, то это свойство сохранится.

Задача 32: Имеются две одинаковых шестеренки по 14 зубьев на общей оси. Их совместили и выбили 4 пары зубьев. Доказать, что шестеренки можно повернуть так, что они образуют полноценную шестеренку (без дырок).

Задача 33: Фигура может ходить вправо, вниз и по диагонали «вверх"-«влево". Может ли она обойти прямоугольную доску и вернуться?

Задача 34: На круглом столе лежат 12 табличек с именами. 12 человек, имена которых написаны на табличках, сели за стол как попало. Доказать, что можно повернуть стол так, что по крайней мере двое оказались рядом со своей табличкой.

Задача 35: В ста домах жили 100 гномов. Однажды некоторые из них (возможно, все) переехали так, что расстояние между любыми двумя гномами не уменьшилось. Доказать, что все эти расстояния остались прежними.

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

Задача 37: Автомат разменивает любую монету, кроме 1коп. и 2коп., на 3 монеты (бывают монеты по 1, 2, 3, 5, 10, 15, 20 и 50 коп.). Способ размена фиксирован. Вначале имеется монета 50 коп.

a) Можно ли ее разменять на 20 монет?

b) Всегда ли можно получить 23, 25, 27 монет?

c) Всегда ли можно получить 29 монет?

d) Доказать, что можно так задать способ размена, что 50коп. можно будет разменять на 49 монет.

e) Какое максимальное число монет заведомо можно получить (независимо от устройства автомата)?

Задача 38: Плоскость разбита на правильные треугольники со стороной 1. По границам этих треугольников проведена замкнутая ломанная, все углы которой равны 60  . Доказать, что длина этой ломаной делится на 3.

Задача 39: Доказать, что из чисел 0,1,2, … ,3^k – 1 можно выбрать 2^k чисел, никакое из которых не равно полусумме двух других.

Задача 40: Квадрат 8 × 8 замощен доминошками. Доказать, что найдутся две соседние доминошки, образующие квадрат 2 × 2.

Задача 41: Имеется набор гирь, вес каждой из которых не больше 100 грамм. Известно, что гири нельзя разбить на две группы, каждая из которых весит больше 100 грамм. Какой максимальный суммарный вес такого набора?

Задача 42: В клетках бесконечной плоскости записаны натуральные числа без повторений. Доказать, что есть две соседние клетки, числа в которых отличаются больше, чем на миллион.

Задача 43: На столе лежат 15 тетрадей в нескольких стопках. С ними повторяют следующую операцию: берут из каждой стопке по тетради и составляют из них новую стопку. Доказать, что когда-нибудь окажется 5 стопок, в которых будут 1, 2, 3, 4 и 5 тетрадей.

Задача 44: В ряд лежат 20 монет: орел, решка, орел, решка, и т.д.. Можно одновременно переворачивать несколько подряд. За какое наименьшее число операций можно перевернуть все монеты орлами вверх?

Задача 45: Число x заменили на x² – 600, с полученным числом снова проделали такую операцию и так 100 раз. Получилось опять число x. Найти x.

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

Задача 47: В каждой клетке бесконечной плоскости стоит натуральное число, равное среднему арифметическому соседей. Доказать, что все числа равны.

Задача 48: В таблице 7 × 7 в клетках стоят плюсы и минусы. Можно одновременно менять знаки в любом столбце или строке. Доказать, что можно сделать так, чтобы в любом столбце и в любой строке плюсов было больше, чем минусов.

Задача 49: На плоскости лежит правильный треугольник. Его «катают», переворачивая через сторону. Через несколько шагов он вернулся на исходное место. Доказать, что

a) Он сделал четное число переворотов.

b) Все вершины вернулись на свои места.

 Задача 50: 50 детей сидят за круглым столом. Среди них мальчиков и девочек поровну. Докажите, что найдется ребенок, сидящий между двумя девочками.

Задача 51: Таня К. сварила набор полосок лапши массами 1 г, 2 г, …, 2001 г. На какое наибольшее число ушей она может повесить лапшу так, чтобы на каждом ухе висело поровну (по массе)?

Задача 52: Во время линейки учащиеся ЛМШ столпились внутри правильного треугольника со стороной 30 метров. Игорь Соломонович дал 10 школьникам по наряду. Доказать, что найдутся два огорченных школьника на расстоянии не более 10 метров друг от друга.

Задача 53: Константин Александрович перенумеровал всех учеников 7 класса и приказал построиться в одну шеренгу, обещая дать наряд каждому, чей номер окажется средним арифметическим какого-то стоящего слева и какого-то стоящего справа от него человека (не обязательно соседа). Докажите, что хитрые дети могут построиться так, что Константин Александрович не сможет выдать ни одного наряда.

Задача 54: В поисках наилучшего тактического расположения футбольная команда 8 класса расположилась сначала в виде ромба ABCD, а затем в виде того же ромба, но повернутого на 90 относительно его центра. Игроки, которые оказались в точках пересечения этих двух ромбов, получили наряд за непосещение бани. Докажите, что на поле нарядники находились в вершинах квадрата.

Задача 55: Для выполнения наряда требуется три юноши и две девушки, причем эти девушки должны жить в одной комнате. Сколькими способами можно организовать бригаду, если накануне Лариса Ивановна и Борис Юрьевич застукали после отбоя в комнате, где живут три девушки, кроме хозяек, еще трёх девушек из соседней комнаты и пятерых юношей черт знает откуда?

Задача 56: Усатый стажер Рома построил 12 учащихся по кругу и выдает им наряды, причем за один раз по одному наряду получает сразу группа из четырёх рядом стоящих учеников. После того, как он несколько раз повторил эту процедуру, оказалось, что учащиеся имеют следующее число нарядов: 2,6,7,7,8,9,8,10,9,4,4,6. Докажите, что кое-кто из этих учащихся получал наряды не только от Ромы.