Логические задачи

 
 
 
 
 

      Установим соответствие  между этими двумя множествами  так, чтобы условия задачи выполнялись.  Будем соответствующие элементы  двух множеств соединять стрелками,  а не соответствующие не будем  соединять. Так как яблоки 1-го  сорта лежат только в корзине  Д , то именно этой корзине и нужно дать номер 1; проведём стрелку между точками Д и 1. Далее, номер 2 можно присвоить только корзине В, а после этого номер 5 – лишь корзине Г. Наконец, номера 3 и 4 дадим корзинам А и Б ( в любом порядке).

     Ответ: корзины расположились, начиная с №1, в

                                   6 
 

     последовательном порядке Д, В, А, Б, Г или в порядке Д, В, Б, А, Г.

     Задача 2. Три подруги были в белом, красном голубом платьях. Их туфли были тех же трёх цветов. Только у Тамары цвета платья и туфель совпадали. Валя была в белых туфлях. Ни платье, ни туфли Лиды не были красными. Определите цвет платья и туфель каждой из подруг.

     Решение: изобразим три  множества: множество подруг, множество  их платьев, множество их туфель   (рис).

        платья                                                                                    туфли                               подруги

     Проведём на рисунке  сплошные и пунктирные линии, отвечающие условиям задачи. Ответ должен получиться в виде трёх треугольников со сплошными  сторонами. Теперь ясно, что у Лиды голубые туфли, у Тамары – красные  туфли, следовательно, и красное  платье. Далее, у Лиды – белое  платье, у Вали – голубое.

     Ответ: Тамара – в красном  платье и красных туфлях, Валя –  в голубом платье и белых туфлях, Лида – в белом платье и голубых  туфлях.

     Рассмотрим задачу, при  решении которой 

                                   7 
 

     используются вершины, стороны и диагонали многоугольника.

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

     Решение: изобразим каждую команду точкой, а проведённую  ею встречу – отрезком, исходящим  из этой точки.  Девять точек лучше  расположить так, чтобы при последовательном соединении их отрезками образовался  выпуклый  9 - угольник. Задача сводится к следующей: можно ли 9 точек соединить  отрезками так, чтобы из каждой точки  выходили четыре отрезка? Другими словами, существует ли граф с девятью вершинами, у которого степень каждой вершины  равна 4?

     Прежде всего, проведём все стороны 9 – угольника; они будут означать, что каждая команда провела две встречи. Для того, чтобы получить ещё по две встречи, будем, например, соединять все вершины диагоналями через одну (см. рис). (Целесообразно для всех вершин держаться одной и той же системы проведения из них отрезков.) 

     

                                                                                   Ответ: можно.

                                   8 
 

     Займёмся задачами на обведение контура фигуры непрерывной  линией.

     Задача 4. В ХVIII веке город Кенигсберг был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами (рис.1).  Можно ли обойти все эти мосты так, чтобы побывать на каждом из них ровно один раз?

     Решение:  

       В       В                            С      К   А                         Рис 1     Рис 2    А

     Обозначим различные  части города буквами А , В, С и К и изобразим их точками. Мосты изобразим линиями, соединяющими эти точки. Получим граф (рис. 2).

     Задача сводится к  следующей : существует ли путь, проходящий по всем рёбрам графа, причём по каждому ребру только один раз?

Рассмотрим  два случая:

1. Предположим, что существует такой замкнутый путь. Тогда степень каждой вершины графа должна быть чётной, так как входя в какую либо вершину, мы затем должны из неё выйти, причём по другому ребру. Что касается начала пути, то после выхода из него мы должны, в конце концов, в него и вернуться, поскольку путь замкнутый. Однако на рис. 2 нет ни одной вершины, степень которой была бы чётной. Значит, этот случай невозможен.
2. Пусть существует такой незамкнутый путь; например, пусть

9 
 
 

он  начинается в вершине А , а заканчивается в С. Тогда из вершин А и С должно выходить уже нечётное число рёбер, а из промежуточных вершин В и К – по – прежнему чётное число. Но на рисунке степени вершин В и К нечётны. И этот случай отпадает.

Ответ: нельзя.

Хотя  рассуждение, проведённое при решении  этой задачи, выполнено для частного случая, оно носит общий характер:

1. Если существует замкнутый путь, проходящий по всем рёбрам графа, причём по каждому ребру только один раз, то степени всех вершин графа чётные;
2. Если существует аналогичный незамкнутый путь, то степени начала и конца пути нечётные, а остальных вершин – чётные.

 
 

3.Операции над множествами

Приведём  определения пересечения и объединения  множеств.

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

Объединением  двух множеств А и В называется множество всех элементов, которые входят по меньшей мере в одно из множеств А и В. АВ

В случае, когда множеств не два, а любое конечное число, эти определения вводятся аналогично. Приведём пример. Пусть А = {1; 2; 3; 4}, В = {2; 4; 6; 8}. Тогда АВ = {2; 4}, АВ = {1; 2; 3; 4; 6; 8}. Для решения задач на пересечение и объединение множеств часто изображают множества кругами (иногда используют и другие фигуры, например, прямоугольники или овалы). Эти круги называются кругами

                                    10 
 
 

Эйлера. Тогда пересечение множеств А и В изобразится как общая часть этих кругов, а объединение – как множество, состоящее из всех элементов множества А и всех элементов множества В. 

 
 
 
 
 

А В                                                                  А В 

Рассмотрим  некоторые свойства операций над  множествами:

1)для  любого множества А выполняются равенства: АА = А, АА = А;

2)пересечение  любых множеств А и В включается в каждое из них, а каждое из этих множеств включается в их объединение:

АВ ⊂ А , А ⊂ АВ;

3)для  любых множеств А и В, где А есть подмножество множества В, их пересечение равно более узкому, а объединение – более широкому из них: АВ = А , АВ = В.

Задача 1. Известно, что АВ = {1; 2}, АС = {2; 5}, АВ = {1; 2; 5; 6; 7; 9}, ВС = {1; 2; 3; 4; 5; 7; 8}. Найдите множества А , В, С.

Решение: будем составлять таблицу. Заполнять  её удобнее не по строкам, а по столбцам. Если, например, элемент 5 входит в множество В, то на пересечении соответствующих строки и столбца таблицы условимся ставить плюс, в противном случае – минус.

1)начнём с числа 1. Так как  1АВ, то 1 А и 1 В. Но 1 С,

                                    11 
 
 

поскольку, если бы 1 С, то она принадлежала бы и пересечению множеств А и С, а это противоречит условию;

2)возьмём  число 2. Аналогично предыдущему  2 А, 2 В, 2 С;

3)возьмём  число 3. Обратим внимание на то, что 3 не принадлежит объединению множеств А и В. Следовательно, это число не принадлежит ни одному из множеств А и В. Но так как 3 ВС, то 3 С. 

 

4)для числа 4 аналогично получаем: 4 А, 4 В, 4 С;

5)рассмотрим число 5: 5 А, 5 С, 5 В;

6)для числа 6: 6 В, 6 С, 6 А;

7)сложнее  обстоит дело с числом 7. Допустим, что 7 А. Поскольку 7 ВС, то 7 В или 7 С, а тогда соответственно 7 АВ или 7 АС.

Однако и то и другое противоречит условиям задачи. Значит, 7 А. Так как 7 АВ, 7 А, то 7 В. Что касается С, то 7 может принадлежать, а может и не принадлежать С.;

8)число 8: 8 А, 8 В, 8 С;

9)для числа 9 получаем: 9 В, 9 С, 9 А;

Ответ: А = {1; 2; 5; 6; 9}, В = {1; 2; 7}, С = {2; 3; 4; 5;7; 8} или А = {1; 2; 5; 6; 9}, В = {1; 2; 7}, С = {2; 3; 4; 5; 8}. Познакомимся с задачами, при решении которых используются круги Эйлера. 

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

                                    12 
 
 

причём 435 человек говорят на обоих языках. Сколько жителей в этом селе?

Решение: применим круги Эйлера. Через А обозначим множество жителей села, которые говорят по-башкирски, через В – множество жителей, которые говорят по-русски.

    

 
 

   А     В 

     Будем обозначать число  элементов любого конечного множества А через n (А). Тогда по условию n (А) = 912, n (В) = 653, n (АВ) = 435. Нам нужно найти число элементов в объединении множеств А и В. Прежде всего сложим числа n (А) и n (В). Но при этом элементы, входящие в пересечение множеств А и В считаются дважды. Следовательно, из этой суммы нужно вычесть n (АВ). Получаем n (АВ) = n (А)+ n (В)- n (АВ). Подставим в эту формулу значения n (А), n (В), n (АВ). n (АВ) = 912+653-435 = 1130.