Простейшие задачи на соответствие

§ 1. Простейшие задачи на соответствие    Логические или ''нечисловые'' задачи составляют обширный класс нестандартных задач. Сюда относятся, прежде всего, текстовые задачи, в которых требуется распознать объекты или расположить их в определенном порядке по имеющимся свойствам. При этом часть утверждений условия задачи может выступать с различной истинностной оценкой (быть истинной или ложной). К классу логических задач относятся также задачи на переливания и взвешивания   (фальшивые монеты и т.п.).    Основной прием, который используется при решении текстовых логических задач, заключается в построении таблиц. Таблицы не только позволяют   наглядно представить условие задачи или ее ответ, но в значительной   степени помогают делать правильные логические выводы в ходе решения  задачи.    Рассмотрим ряд конкретных задач, решаемых с использованием таблиц.  1. Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны? Решение. Составим таблицу, в столбцах которой отметим возможные цвета рубашек и туфель клоунов (буквами К, З и С обозначены красный, зеленый и синий цвета). Будем заполнять таблицу, используя условия задачи. Туфли Бама зеленые, а рубашка не является зеленой. Ставим знак '' + '' в клетку 2-й строки и 5-го столбца, и знак '' - '' в клетку 2-й строки и 2-го столбца. Следовательно, у Бима и Бома туфли уже не могут быть зелеными, так же как не могут быть туфли Бама синими или красными. Отметим все это в таблице (см. табл. 1).   Далее, туфли и рубашка Бома не  являются красными, отметим соответствующие ячейки таблицы знаком  '' – ''. Из таблицы, заполненной на этом этапе, видим, что красные туфли могут быть только у Бима, а, следовательно, туфли Бома - синие. Правая часть таблицы заполнена, мы установили цвета обуви клоунов (табл.1). Цвет рубашки Бима совпадает с цветом его туфель и является красным. Теперь легко устанавливается владелец зеленой рубашки - Бом. Бам, в таком случае, одет в рубашку синего цвета. Мы полностью заполнили таблицу, в которой однозначно устанавливаются цвета туфель и рубашек клоунов (см. табл. 2): Бим одет в красную рубашку и красные туфли, Бам в синей рубашке и зеленых туфлях, Бом в зеленой  рубашке и туфлях синего цвета.    2. На съезде встретились четверо ученых: физик, биолог, историк и  математик. Они были разных национальностей, и хотя каждый из них владел двумя языками из четырех (русский, английский, французский и итальянский), не было такого языка, на котором они могли бы  разговаривать сразу вчетвером, и был только один язык, на котором  могли разговаривать сразу трое. Никто из ученых не владеет французским и итальянским одновременно. Хотя физик не мог говорить по-английски, но он был переводчиком в разговоре биолога и историка. Историк говорит      по-итальянски и может говорить по-русски с математиком, ибо тот не знает ни одного итальянского слова. Физик, биолог и математик не могут  беседовать втроем на одном языке. Какими двумя языками владеет каждый  из ученых?    Решение.  Будем заполнять таблицу, в строках которой выпишем специальности ученых, а в столбцах языки, которыми они владеют. Сначала воспользуемся утверждением, что историк и математик говорят по-рус-ски, но первый владеет еще и итальянским, а второй - нет. Так как каждый ученый знает только два языка, то историк не говорит по-английски и по-французски. Поскольку биолог и историк общались через переводчика, то они не владеют одинаковыми языками. Поэтому биолог должен знать английский и французский языки (см. табл. 3).  Физик не знает английского, но тогда он должен владеть французским, иначе он бы не мог быть переводчиком в разговоре биолога с историком. Второй язык, который должен знать физик, это русский или итальянский. Но последний отпадает, так как никто из ученых не может одновременно владеть итальянским и французским языками. Теперь из таблицы 4 видим, что математик может знать либо английский, либо французский. Осталось воспользоваться утверждением, что физик, биолог и математик не могут беседовать втроем на одном языке. Стало быть, математик не может говорить по-французски. Окончательно имеем: физик  владеет французским и русским языками, математик - английским и русским, историк - итальянским и русским, биолог - английским и французским.     3. На улице, став в кружок, беседуют четыре девочки: Аня, Валя, Галя и Надя. Девочка в зеленом платье (не Аня и не Валя) стоит между девочкой в голубом платье и Надей. Девочка в белом платье стоит между девочкой в розовом и Валей. Какое платье носит каждая из девочек?    Решение. Решать эту задачу будем, используя таблицы из четырех квадратных блоков, расположив их по кругу и добавив к каждой из них еще одну ячейку в форме полукруга (табл.5). В каждом из четырех блоков сразу впишем возможные цвета платьев девочек (буквы Г, З, Р, Б), а в дополнительных полукруглых ячейках будем в дальнейшем отмечать их имена (буквы А, В, Г, Н).      Пусть девочке в зеленом платье соответствует верхний блок нашей таблицы, тогда левый и правый блоки будут соответствовать девочкам в голубом платье и Наде соответственно. Отметим эти данные в таблице (табл.6).         Теперь в правом и нижнем блоке таблицы можем зачеркнуть ячейки, соответствующие зеленому и голубому цвету платьев, так как эти цвета уже расположены в других частях нашей таблицы. Кроме этого, из первого условия ясно, что Аня, Валя и Надя одеты не в зеленое платье, а значит зеленое платье у Гали. Итак, таблица 7 содержит информацию, которую мы получили из первого условия задачи.          Из второго условия задачи следует, что Валя не в белом и не в розовом платье, следовательно, на ней голубое платье, и, значит, ей соответствует левая часть таблицы. Наконец, нижняя часть таблицы соответствует Ане, и она одета в белое платье, а Надя в платье розового цвета. Задача полностью решена, и ее ответ содержится в таблице 8.  § 2. Логические задачи с истинностной оценкой в тексте  Довольно широкий класс логических задач отличается тем, что содержит в условиях утверждения, которые могут быть как истинными, так и ложными. Подход к решению таких задач состоит в следующем. Фиксируется одно из утверждений условия задачи, которое может принимать различные истинностные оценки. Последовательно рассматриваются два случая: а) когда фиксированное утверждение истинно и б) когда фиксированное утверждение ложно. В одном из случаев рассуждения приведут к противоречию, другой случай приведет к решению задачи.    Остановимся на решениях конкретных задач этого класса. 4. Виктор, Роман, Юрий, Сергей заняли на математической олимпиаде первые четыре места. Когда их спросили о распределении мест, они дали  три таких ответа:      1) Сергей – первое, Роман – второе;      2) Сергей – второе, Виктор –  третье;      3) Юрий –  второе, Виктор – четвертое.  Как распределились места, если в каждом из ответов только одно  утверждение истинно?    Решение. Предположим вначале, что в первом ответе ложным является первое утверждение. Будем заполнять таблицу распределения мест между ребятами.  В силу нашего предположения Роман занял второе место. Отметим соответствующую ячейку таблицы знаком '' + '', а все другие клетки в строке ''Роман'' и в столбце 2  знаком ''– ''. Отметим также клетку, соответствующую тому, что Сергей не занял первое место.    Рассмотрим второй ответ. Ясно, что в нем является ложным первое утверждение (Сергей не может быть вторым). Следовательно, Виктор    был третьим (ставим соответствующий знак). В результате получим таблицу 9. Осталось рассмотреть третий ответ. Легко видеть, что оба утверждения третьего ответа являются ложными. Таким образом, предположение о том, что ложным в первом ответе является первое утверждение, было неверным.   1 м 2 м 3 м 4 м Сергей + – – – Роман – – –   Виктор – – + – Юрий –   –   Таблица 10     Пусть теперь в первом ответе является ложным второе утверждение (заполняем таблицу 10). Тогда первое место занял Сергей, а Роман не стал вторым. Зафиксируем это в таблице. Во втором ответе ложным является первое утверждение, а поэтому Виктор был третьим. Из таблицы 10 видим, что вторым мог быть только Юрий, тогда четвертое место занял Роман. Осталось рассмотреть третий ответ. В нем одно утверждение истинно (первое утверждение), а другое ложно. Все условия задачи выполнены и распределение мест среди ребят следующее: Сергей  -  1 место, Юрий - 2 место, Виктор - 3 место, Роман - 4 место. 5.  На столе стоят два одинаковых ящика. В каждом из них находится  либо белый, либо черный шарик. На первом из ящиков надпись: ''По крайней мере, в одном из этих ящиков находится белый шарик''. На втором: ''Черный шарик находится в другом ящике''. Известно, что  либо обе эти  надписи истинны, либо обе ложны. Есть ли в каком-нибудь ящике белый  шарик, и если есть, то в каком именно?       Решение. Предположим вначале, что обе надписи на ящиках истинны. Тогда, согласно надписи на втором ящике, черный шарик находится в первом ящике. Далее, так как надпись на первом ящике также истинна, то во втором ящике находится белый шарик. В результате получим следующее решение (см. табл. 11).    Допустим теперь, что обе надписи на ящиках ложны. Из того, что ложна надпись на первом ящике, следует, что ни в одном из ящиков нет белого шарика  (ставим знаки ''-'' в первом столбце таблицы 12). Согласно же второй надписи (если она ложная) черного шарика в первом ящике нет. Получим противоречие, следовательно, обе надписи не могут быть ложными.   6. Жители города А говорят только правду, жители города Б – только ложь, жители города В – говорят попеременно правду и ложь. В одном из  городов случился пожар. Дежурному пожарной части сообщили: "У нас пожар, приезжайте скорее!'' "Где?'' – спросил дежурный. ''В городе В'' – ответили ему. Куда должна выезжать пожарная дружина?     Решение. Заметим, что звонивший в пожарную часть произнес два утверждения. Первое - ''У нас пожар'', второе - ''Пожар в городе В''. Попробуем разобраться в ситуации, анализируя эти два утверждения в зависимости от того, из какого города был звонок. Предположим вначале, что звонили из города А. Тогда из первого утверждения следует, что пожар в городе А, а из второго утверждения - в городе В. Противоречие. Зафиксируем выводы в таблице 13. Предположив теперь, что звонили из города Б, в котором всегда лгут, получим: из первого предложения - пожар в городе А или В, но не в Б, из второго - пожар в городе А или Б, но не в В. Случай, когда звонили из города В распадается на два события: во-первых, когда первое утверждение звонившего истинно, а второе - ложно, во-вторых, наоборот, первое утверждение ложно, а второе - истинно. Рассмотрим отдельно оба случая и результаты зафиксируем в таблице.   Звонок из города А Б В 1-И, 2-И 1-Л, 2-Л 1-И, 2-Л 1-Л, 2-И 1 утверждение + – – + – + – – + + + – 2 утверждение – – + + + – + + – – – +   А Б В А Б В А Б В А Б В Таблица 13 Анализируя таблицу 13, легко видеть, что имеется единственная ситуация, когда выводы двух утверждений не противоречат друг другу. Таким образом, звонок был из города Б и пожарную дружину следует отправить в город А.    Во всех предлагаемых выше решениях при составлении и заполнении таблиц мы придерживались следующих принципиальных моментов. В таблицу вносились абсолютно все возможные варианты исходов. Затем зачеркивались варианты, невозможность которых устанавливалась условиями задачи и приводимыми рассуждениями. Тем самым количество вариантов сокращалось до единственного, который и давал нам решение задачи.    Отметим, что форма и вид таблицы, а также принципы их заполнения могут  быть различными - все зависит от решающего задачу. Трек 1.1. заданий к теме 1. 3.  Четыре друга: Эдуард, Павел, Юра и Костя пошли вместе со своими женами на дискотеку. Сначала каждый танцевал со своей женой, но потом пары перемешались: 1) Валя танцевала с Эдуардом, 2) Аня танцевала с мужем Ольги, 3) Таня танцевала с мужем Ани, 4) Павел танцевал с женой Юры, 5) Юра танцевал с женой Эдуарда. Кто на ком женат, и кто с кем танцевал? 4.  Пять человек живут в одном городе. Их имена Леонид, Владимир, Николай, Олег, Петр. Их фамилии Степанов, Борисов, Карпов, Демин и Истомин. Борисов знаком только с двумя, а с Карповым знаком только один человек. Петр знаком со всеми, кроме одного, а Леонид знает только одного из них. Николай и Истомин знакомы с детства. Демин и Владимир незнакомы. Олег, Николай и Борисов ходят часто вместе в кино. Назовите имена и фамилии каждого. 5. Три товарища – Иван, Дмитрий и Степан преподают различные предметы в школах Москвы, Санкт-Петербурга и Нижнего Новгорода: химию, биологию, физику. Иван работает не в Москве, Дмитрий – не в Санкт-Петербурге. Москвич преподает не физику. Работающий в Санкт-Петербурге преподает химию, Дмитрий преподает не биологию. Какой предмет и в каком городе преподает каждый? Трек 1.2. заданий к теме 1. 2.   Четверо ребят - Алеша, Боря, Ваня и Гриша соревновались в беге. После соревнований каждого из них спросили, какое место он занял. Алеша ответил:  ''Я не был ни первым, ни последним''. Боря ответил: ''Я не был последним''. Ваня ответил: ''Я был первым''. Гриша ответил: ''Я был последним''. Три из этих ответов правильные, а один неверный. Кто сказал правду? И кто выиграл  соревнования? 3.  В соревнованиях по бегу приняло участие 5 человек: Валерий, Коля, Миша, Игорь, Эдик. Их фамилии: Симаков, Чигрин, Зуев, Копылов, Блинов (порядок имен и фамилий не совпадает). Болельщики высказали предположение о результатах забега: Копылов -  1 место, Валерий — 2 место, Чигрин — 3 место, Эдик — 4 место. Но после забега оказалось, что ни один из прогнозов не оправдался, а результаты были такими: 1 — Миша, 2 — Симаков, 3 — Коля, 4 —   Блинов, Чигрин не занял призовых мест. Определите имена и фамилии  участников бега. 4.  Произошла кража и было задержано трое подозреваемых. Один из них (вор) лжет систематически; другой (соучастник) иногда лжет, а иногда говорит правду; последний (подозреваемый напрасно) вообще никогда не лжет. Дознание началось с вопросов о профессии каждого из задержанных. Их ответы были такими: Бертран: Я – маляр, Альфред – настройщик роялей, Шарль – декоратор; Альфред:  Я – врач, Шарль – страховой агент. Что касается Бертрана,   то, если Вы его спросите, он ответит, что он маляр; Шарль:   Альфред настраивает рояли. Бертран – декоратор, а я – страховой агент.  Судья хотел бы знать профессию и имя соучастника. Тема 2 § 1. Высказывания. Операции над высказываниями. Таблицы истинности. В этом разделе мы будем рассматривать величины, которые могут принимать только два значения - быть истинными или ложными (двоичные величины). Эти величины называются логическими высказываниями. Простое высказывание – повествовательное предложение, принимающее одно из двух возможных значений – истина или ложь. Составное высказывание – комбинация простых высказываний, соединенных логическими операциями. Значения высказываний можно обозначать по-разному: истина-ложь; 1-0;+ -. Приведем примеры высказываний и найдем их значения: 1.                 А = В марте 31 день.                       А = 1; 2.                 В = 13 > 27.                                       В = 0; 3.                 С = 24 – 1 – простое число.            С = 1. Предложения «Закрой окно» и «Который час?» не имеют значения, а значит, не являются высказываниями. Наряду с высказываниями  используются и предикаты – высказывания с переменными, которые при одних значениях переменной могут стать истинными высказываниями, при других – ложными. Например: Х>0; «Город – столица России». В середине XIX века на основе труда английского математика Джорджа Буля «Математический анализ логики» возникла наука, получившая название математической логики. Буль перенес на логику законы и правила алгебраических действий, ввел логические операции. Раздел математической логики, изучающий строение логических высказываний и способы установления их истинности с помощью алгебраических методов, называется алгеброй логики (булевой алгеброй).   Операции над высказываниями 1. Логическое умножение (конъюнкция) – бинарная операция, в результате которой получается составное высказывание, истинное, если истинны оба простых высказывания, и ложное, если хотя бы одно из них ложно. Слово «бинарная» означает, что для выполнения операции необходимы два высказывания. Существует несколько обозначений для этой операции: ∧∧, и, and, &. Пример: А=Сегодня пасмурно.                   В=Идет дождь.                   А∧В=Сегодня пасмурно и идет дождь. А ∧ В=1 тогда и только тогда, когда А=1 и В=1. Для определения значения составных высказываний строятся таблицы истинности:       А          В         А∧В   1 1 1 1 1 2. Логическое сложение (дизъюнкция) – бинарная операция, в результате которой получается составное высказывание, истинное, если истинно хотя бы одно простое высказывание, и ложное, если ложны оба. Обозначение операции: ∨∨, или, or. Пример: А = Сегодня пасмурно.                   В = Идет дождь.                   А∨В = Сегодня пасмурно или идет дождь. А∨В=0 в том и только том случае, когда А=0 и В=0. Таблица истинности:     А             В           А∨В      1 1 1 1 1 1 1   3. Логическое отрицание (инверсия) – унарная операция, в результате которой получается составное высказывание со значением, противоположным исходному. Обозначение операции: ¬ , ¯, не, not. Инверсия может получиться прибавлением частицы «не» к признаку или использованием признака, противоположному данному. Примеры: А=Это платье белое.                   ¬А=Это платье не белое.                     Таблица истинности:     A         ¬A    1 1 Постройте инверсии к следующим высказываниям: ·         У всех треугольников сумма углов равна 180º. ·         Существует человек с кривым носом. ·         Все кошки серые. ·         Каждая рыба в озере – щука. ·         В лицее есть отличники по информатике. Всего в алгебре логики 16 операций, но любую из оставшихся можно выразить через дизъюнкцию, конъюнкцию и отрицание. Мы будем рассматривать еще две операции. 5.  Логическое следование (импликация) – бинарная операция, в результате которой получается составное высказывание, ложное, если из истины следует ложь, и истинное во всех остальных случаях. Обозначение операции: → В русском языке эта операция выражается с помощью конструкций: если …, то …; влечет; следовательно. Таблица истинности:     А          В         А→В       А←В (В→А)    1 1 1 1 1 1 1 1 1 1  Примеры: А = Сегодня 3 февраля.                    В = Идет урок математики.                    А→В =  Сегодня 3 февраля, следовательно, идет урок математики.                    В→А = Идет урок информатики, следовательно, сегодня 3 февраля. 6. Эквиваленция (равнозначность) – бинарная операция, в результате которой получается составное высказывание, истинное, если исходные высказывания имеют одинаковые значения, и ложное, если исходные высказывания имеют разные значения. Обозначение операции: ↔,  ⇔, ~. В русском языке эта операция выражается с помощью конструкций: тогда и только тогда; Это все равно, что …; Это одно и то же, что …; В том и только том случае… Таблица истинности:    А       В       А↔В    1 1 1 1 1 1 Примеры: А = Дважды два равно четырем.                   В = Наступила зима.                   А↔ В = Дважды два равно четырем тогда и только тогда, когда наступила зима. Для операций дизъюнкции, конъюнкции и эквивалентности действует переместительный закон. Приоритетность логических операций при отсутствии скобок: 1.      Отрицание 2.      Конъюнкция 3.      Дизъюнкция 4.      Импликация 5.      Эквиваленция Рассмотрим простой пример интерпретации введённых операций. Пусть даны высказывания:  • А = "5>3" (истинное); • В = "10>7" (истинное); • С = "6<1" (ложное); • D = "8<0" (ложное).   Результаты применения логических операций к этим высказываниям будут таковы: ¬А (неверно, что "5>3") - ложно; ¬С (неверно, что "6<1") - истинно; А∧В ("5>3" и "10>7" (одновременно)) - истинно; А∧С ("5>3" и "6<1" (одновременно)) - ложно; А∨В ("5>3" или "10>7" (истинно хотя бы одно из этих утверждений)) - истинно. А∨С ("5>3" или "6<1" (истинно хотя бы одно из этих утверждений)) - истинно; А⇒В (из А следует В; если А, то В; если"5>3", то "10>7") - истинно; A⇒C(из А следует С; если А, то С; если"5>3", то "6<1") - ложно; С⇒А (из С следует А; если С, то А; если"6<1", то "5>3") - истинно; А⇔В (А эквивалентно В; А справедливо тогда и только тогда, когда справедливо В; для А необходимо и достаточно, чтобы выполнялось В; "5>3"⇔"10>7") - истинно; А⇔C ("5>3" ⇔"6<1") - ложно; D⇔С ("8<0" ⇔"6<1") - истинно. В следующей таблице приведены основные свойства логических операций. Они несложно доказываются. Достаточно записать таблицы истинности высказываний, разделенных знаком ⇔, и показать, что они совпадают при одинаковых значениях истинности составляющих их высказываний. Эти свойства иногда называют законами логических операций и их можно использовать при решении различных задач.  1. (¬¬А) ⇔ (А). 7. ((А∧В)∧C) ⇔ (А∧(В ∧С)). 2. ( ¬ (А∨B)) ⇔ ( ¬А∧¬B). 8. ((А∨В)∧C) ⇔ ((А∧C)∨(В ∧С)). 3. ( ¬ (А∧B)) ⇔ ( ¬А∨¬B). 9. ((А∧В)∨C) ⇔ ((А∨C)∧ (В∧С)). 4. (А∨B) ⇔ (B∨A). 10. (А ⇒ В) ⇔ ( ¬А∨В). 5. (А∧B) ⇔ (B∧A). 11. (А ⇒ B) ⇔ ( ¬B ⇒ A). 6. ((А∨В)∨C) ⇔ (А∨(В ∨С)). 12. (А⇔В) ⇔ (A⇒B)∧(B⇒A). Для описания всех возможных логических значений формулы, в зависимости от значений входящих в нее элементарных высказываний, используют таблицы истинности. Эта таблица будет содержать 2n строк, где n – количество элементарных высказываний, входящих в логическую формулу.  Например, для формулы (¬X∨Y)⇒(X∧¬Y) таблица истинности имеет вид: § 2. Примеры решения задач Решения некоторых из представленных в этом параграфе задач можно увидеть в видеоматериалах - ЗДЕСЬ! Операции над высказываниями и таблицы истинности    Задача 1.  Определите истинностное значение следующих логических переменных: 1)  А = « Если 2 умножить на 2 равно 5, то два умножить на 2 равно 4» 2)   В =  «Всякий квадрат есть параллелограмм и каждый параллелограмм есть четырехугольник» 3)   С = «Всякий параллелограмм есть квадрат, но не треугольник» 4)  D =  «Уравнение x2+5x−6=0x2+5x−6=0 имеет единственное решение, а уравнение   x2+5x+6=0x2+5x+6=0 не имеет решений» 5)  E =  «Если  число делится на 5, то оно обязательно оканчивается цифрой 0 или 5, при этом сумма двух чисел делящихся на 5 оканчивается всегда цифрой 0»      Задача 2.  Какое из приведенных имен удовлетворяет логическому условию:  ¬ (последняя буква гласная → первая буква согласная) Λ вторая буква согласная  1) ИРИНА 2) АРТЕМ 3) СТЕПАН 4) МАРИЯ     Задача 3. Для какого из указанных значений X истинно высказывание ¬((X > 2)→(X > 3))?              1) 1       2) 2         3) 3           4) 4 Решение логических задач с помощью алгебры логики Задача 1. На вопрос, какая завтра будет погода, синоптик  дал три ответа: 1.      Если не будет ветра, то будет пасмурная погода без дождя; 2.      Если будет дождь, то будет пасмурно и без ветра; 3.      Если будет пасмурная погода, то будет дождь и не будет ветра.    Подумав немного, синоптик уточнил, что его три высказывания можно лаконично записать в виде одного составного высказывания. Сформулируйте его, решив задачу с помощью логических операций. Решение. Для каждого высказывания синоптика составим логические высказывания. Выделим простые высказывания, которые составляют сформулированные предложения: υυ  - "будет ветер", pp  - "будет пасмурно",  dd   - "будет дождь". Значение каждого высказывания будет равно 1, поскольку синоптик не лгал:     Каждое из этих высказываний истинно, значит, логическое произведение трех высказываний должно быть равно 1 Построим таблицу истинности и проверим, при каких значениях переменных значение истинности будет равно 1.    Задача 2.  Виктор, Роман, Леонид и Сергей    заняли на олимпиаде по информатике четыре первых места. Когда их спросили о распределении мест, они дали такие ответы: 1.      Сергей – первый,  Роман – второй; 2.      Сергей – второй, Виктор – третий; 3.      Леонид – второй, Виктор – четвертый. Известно, что в каждом ответе только одно утверждение истинно. Как распределились места? Решение. Поскольку в каждом ответе истинно только одно утверждение, будем считать, что дизъюнкция между этими утверждениями возвращает истину: 1)      С1∨∨Р2=1 2)      С2∨∨В3=1 3)      Л2∨∨В4=1. Составим логическую функцию: (С1∨∨Р2) ∧∧ ( С2∨∨В3) ∧∧ (Л2∨∨В4)=(С1∧∧С2∨∨С1∧∧В3∨∨Р2∧∧С2∨∨Р2∧∧В3) ∧∧(Л2∨∨В4)=(С1∧∧В3∧∧Л2) ∨∨(С1∧∧В3∧∧В4) ∨∨(Р2∧∧В3∧∧Л2) ∨∨(Р2∧∧В3∧∧В4)=С1∧∧В3∧∧Л2=1; Ответ: Сергей – 1; Леонид – 2; Виктор -3; Роман – 4.    Задача 3. Определите, кто из подозреваемых участвовал в преступлении, если известно, что: 1. Если Иванов не участвовал, или Петров участвовал, то Сидоров участвовал; 2. Неправда, что, если Иванов участвовал, то Сидоров участвовал.    Решение. Задача 4. Три одноклассницы – Аня, Маша и Валя занимаются во Дворце пионеров в разных кружках: танцевальном, хоровом, драматическом. На вопрос, кто в какой кружок ходит, они ответили: Аня: «Я  в танцевальном». (Ат=1) Валя: «Я не в танцевальном». (Вт=0) Маша: «Я не в хоровом». (Мх=0) В каком кружке каждая из них занимается, если две девочки солгали, а одна сказала правду? Решение. Рассмотрим три случая: 1)     Пусть Аня сказала правду, а Валя и Маша солгали. Тогда получим Ат∧Вт∧МхАт∧Вт∧Мх=1, чего не может быть, т.к. девочки занимаются в разных кружках. 2)      Пусть Валя сказала правду, а Маша и Аня солгали, тогда получим Ат¯¯¯¯¯∧Вт¯¯¯¯¯∧МхАт¯∧Вт¯∧Мх=1, чего также не может быть,  поскольку либо Аня, либо Валя должны ходить на танцы, т.к. в хор уже ходит Маша. 3)     Пусть Маша сказала правду, а Аня и Валя солгали. Тогда Ат¯¯¯¯¯∧Вт∧Мх¯¯¯¯¯¯Ат¯∧Вт∧Мх¯=1. Получили, что Валя ходит на танцы; Маша может ходить либо на танцы, либо на драму, но, поскольку на танцы ходит Валя, то Маша посещает драмкружок; Аня может ходить либо в хор, либо в драмкружок, но, т.к. в драмкружок ходит Маша, то Аня посещает хор. Ответ: Валя – танцы, Маша – драмкружок, Аня – хор § 3. Верно ли проведено рассуждение?  В этом параграфе мы покажем как с помощью таблиц истинности проверить ход рассуждений. В повседневной жизни можно часто встретить ситуацию, когда из определенных фактов, условий и свойств нужно делать какой либо вывод. Например, такую ситуацию можно часто встретить в аналитических программах, ток-шоу на телевидении, в речи на судебном заседании или в корпоративных отчетах. И очень часто можно встретить, что выводы (заключения) делаются не совсем верными. Это может быть, как умышленной, так и неумышленной ошибкой автора заключения. На примере одной задачи, мы покажем, как можно, используя математические методы, проверить правильность рассуждений. ЗАДАЧА. Проверьте правильность рассуждения, используя математические методы:  Если Иванов является участником преступления, то он знал потерпевшего. Иванов не знал потерпевшего, но знал его жену. Потерпевший знал Иванова. Следовательно, Иванов не является участником преступления.   Решение. Введем обозначения следующих высказываний: • А – «Иванов является участником преступления»; • В – «Иванов знал потерпевшего»; • С – «Иванов знал жену потерпевшего»; • D – «потерпевший знал Иванова». Запишем теперь рассуждение задания в виде формулы, она будет выглядеть так: Обозначим ее символом Ф: Если формула Ф является тождественно истинной (тавтологией), то рассуждение является правильным, в противном случае – неправильным. Составим таблицу истинности для формулы Ф.  Таблица истинности примет следующий вид :      a b c d a→b ¬b (¬b)˄c (a→b) ˄ (( ¬b) ˄c) ((a→b) ˄ (( ¬b) ˄c)) ˄d ¬a (((a→b) ˄ ((   ¬b) ˄c)) ˄d)→( ¬a) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  В этой таблице 16 строк, поскольку составляющих нашу формулу переменных 4 (24 = 16). Для удобства формула  для Ф разбита на промежуточные элементы и подсчет истинностного значения ведется последовательно сначала для промежуточных значений, потом делается вывод о формуле Ф в целом. Формула является истинной при любых значениях входящих в нее высказываний. А, следовательно, мы можем сделать вывод, о том, что рассуждение проведено верно и формула является тавтологией.    § 4. Использование Wolfram Alpha для решения логических задач В этом параграфе мы познакомимся с интересным сетевым ресурсом, который позволит нам решить задачи, которые мы выполняли в предыдущих параграфах настоящей темы. Этот ресурс называется Wolfram Alpfa. Что такое Wolfram Alpha? Сервис Wolfram Alpha открыт для всех желающих с мая 2009 года. Это большой проект, инициатором которого является известный британский физик Стивен Вольфрам (Stephen Wolfram), глава компании Wolfram Research и разработчик широко известного в научных кругах пакета  МАТЕМАТИКА. Часто Wolfram Alpha называют веб-поисковиком, но в отличие от традиционных поисковиков, которые по запросу пользователя выдают список ссылок на сайты, соответствующие запросу, сервис Wolfram Alpha самостоятельно анализирует поступивший запрос пользователя и представляет ему сводную релевантную информацию. Авторы сервиса называют свое детище Computational Knowledge Engine(«Вычислительный Двигатель Знания»). Как пользоваться Wolfram Alpha? Достаточно войти на страничку Wolfram Alpha, набрать в текстовом поле свой запрос и нажать кнопку «=» (имеет всплывающую подсказку compute) или просто нажать Enter. Форму запроса Вольфрам Альфа можно вставить в свой сайт или в блог, для этого достаточно вставить код, который генерируется на этой страничке: http://www.wolframalpha.com/addtoyoursite.html. Следует добавить, что вы имеете возможность получить ссылку на источник информации, который использует Вольфрам, для этого достаточно нажать ссылку Source information (внизу, под найденной информацией). Всю информацию, которую вы получите от Вольфрам Альфа, вы можете сохранить в виде pdf-файла, нажав ссылку (внизу) Download as: PDF. Наконец, на этой страничкеhttp://www.wolframalpha.com/downloads.html вы можете загрузить для своих ОС и браузеров гаджеты (Gadgets), тулбары (Toolbars) и аддоны (Add-ons). Существуют и используются мобильные версии. Какие вопросы можно задать Wolfram Alpha? Спросить можно много чего и всякого, но это нужно делать только на английском языке.Вы можете отправить запрос на любую тему: о математике и физике, о химии и астрономии, о статистике и всевозможных данных статистического анализа, о датах и времени, о географии и погоде, о здоровье и медицине, о культуре и медиа, о музыке и об образовании, о людях и истории, о деньгах и финансах, о лингвистике и достижениях высоких технологий, о спорте и спортивных играх… Насколько достоверна информация? В отношении естественнонаучного материала достаточно достоверна, все остальное нужно смотреть и проверять.   Приведем несколько примеров, которые вы так же можете протестировать: • если вы введете название своего города, то получите следующую информацию: где он находится, количество жителей, схематическое расположение на карте, состояние погоды, высоту над уровнем моря и города, ближайшие к вашему городу (с расстоянием до них и с количеством жителей в этих городах). Нажав на ссылку Show coordinates, вы можете узнать координаты города. Нажав на ссылку Satellite image, вы можете загрузить снимки своего города (будет загружена карта Bing); • если вы введете дату (например, день своего рождения) в формате, месяц, дата, год, то сможете узнать, какой был день недели в этот день, сможете подсчитать, сколько времени (лет, месяцев, недель, дней) прошло с этой даты, восход и заход солнца, кто из знаменитых людей родился в этот день, какие праздники приходятся на этот день; • если ввести химическую формулу, например, H2SO4, и вы узнаете основную информацию об этом веществе/химическом элементе; • хотите подсчитать суммарное количество калорий, которые получит ваш организм, после того, как вы съедите яблоко и мандарин? Введите в строку поиска 1 apple + 1 mandarin и вы получите количество калорий, протеинов, витаминов, отсутствия/наличия холестерина и т.д.; • если ввести в поисковую строку имена (например: Ann, Natasha, Ivan), то ответом будут статистические данные об использовании этих имен в US. С примерами запросов самого разного содержания можно познакомиться на специальной страничке (вход по кнопке EXAMPLES). В разделах этой странички приведены протоколы ввода для получения информации вычислительного характера в различных областях знаний. Математические способности ресурса очень обширны. Вольфрам умеет рисовать графики функций, рисовать множество точек на плоскости и в пространстве, задаваемое уравнением или неравенством, умеет дифференцировать и интегрировать функции, решает алгебраические уравнения, диофантовы уравнения, дифференциальные уравнения, делает статистические вычисления. Может привести формулировки основных определений и рассказать об известных математических проблемах и решениях. Если вы впервые используете Вольфрам, начните его исследование с самых простых вопросов. Например: Hello! What's Your Name? What's my Name? What do you like? Why did the chicken cross the road? What's the Answer to Life? Вы убедитесь, что его ответы не лишены юмора! Переходите к поиску интересующей вас информации и тестированию Вольфрама на запросы в рамках вашей предметной области.  Трудно перечислить все, что умеет делать WA! Несомненно он хороший помощник для самообразования и для проведения различных исследований. Неудобство англоязычного интерфейса частично снимется, если вы будете параллельно использовать переводчик Google и Google Chrome. Вернемся к задаче, которую мы решали в предыдущем параграфе. Покажем, как можно использовать WA для решения этой задачи: ЗАДАЧА. Проверьте правильность рассуждения, используя математические методы: Если Иванов является участником преступления, то он знал потерпевшего. Иванов не знал потерпевшего, но знал его жену. Потерпевший знал Иванова. Следовательно, Иванов не является участником преступления. Решение. Введем обозначения следующих высказываний: • А – «Иванов является участником преступления»; • В – «Иванов знал потерпевшего»; • С – «Иванов знал жену потерпевшего»; • D – «потерпевший знал Иванова». Запишем теперь рассуждение задания в виде формулы, она будет выглядеть так: Обозначим ее символом Ф: Если формула Ф является тождественно истинной (тавтологией), то рассуждение является правильным, в противном случае – неправильным. За проверкой истинности формулы Ф обратимся к WA. Введем в форме WA запрос, набрав формулу Ф, вот так: ((A=>B)and(not B and C) and D) => not A Результат, который получен приведен на картинке: формула является тавтологией. А значит, рассуждение проведено верно. Если вы хотите увидеть полностью таблицу истинности для формулы Ф, то введите запрос таким образом: truth table ((A=>B)and(not B and C) and D) => not A. Вольфрам Альфа выведет вам таблицу истинности для высказывания Ф и, естественно, вы увидите, что, при всех значениях составляющих высказываний А, B, C и D, Ф всегда является истинным.  Еще один интересный пример запроса в WA. Если вы наберете в качестве запроса следующий текст "N curve image", где вместо N запишите имя какого-либо известного лица, то WA выведет вам кривую, которая соответствует образу N. Например, на запрос "Vladimir Putin curve image", мы получим параметрическую кривую образа нашего президента. Причем, WA не только рисует эту кривую, но и выдает параметрические функции, которыми она задается! Предлагаем самостоятельно познакомиться с различными возможностями использования WA. Их много, причем, просматривая предлагаемые примеры, вы убедитесь, что WA действительно является машиной знаний!  Трек 2.1. Основные понятия алгебры логики (каждая полностью решенная задача оценивается в 2 балла). В этом треке вы можете получить 12 баллов 1. Определите истинностное значение следующих логических переменных: 1)  А = « Если Два умножить на два равно пяти, то два умножить на 2 равно 4» 2)   В =  «Всякий квадрат есть параллелограмм и каждый параллелограмм есть четырехугольник» 3)   С = «Всякий параллелограмм есть квадрат, но не треугольник» 4)  D =  «Уравнение  х2 - 1=0 имеет единственное решение, а уравнение х+1= - 2 не имеет решений» 5)  E =  «Если  число делится на 5, то оно обязательно оканчивается цифрой 5» 2. Определите значение истинности следующих высказываний: 1)   Высказывание "10 делится на 2 и 5 не больше 3" 2)   Высказывание "Если 10 делится на 2 и 5 не больше 3, то 10 больше 5»   3)   Высказывание "Если 10 не делится на 2 и 5 больше 3, то 4 делится на 3"    4)   Высказывание "Если 10 не делится на 2 и 5 не больше 3, то 2х2=4"  5)  Высказывание "Если 10 делится на 3, то 5 меньше 3" 3. Запишите приведенное высказывание в виде формул логики высказываний: ''Если будет холодное и дождливое или засушливое лето, урожай будет плохим". 4. Составьте таблицу истинности для следующих высказываний: 5.  Докажите тождество:  6.   Перед сдачей вступительных экзаменов в институт Миша предполагал, что: если он сдаст математику, то информатику он сдаст только при условии, что не завалит диктант; не может быть, чтобы он завалил и диктант, и математику; достаточное условие завала по информатике — это двойка по диктанту. После сдачи экзаменов оказалось, что из трех высказанных предположений только одно было ложным. Как Миша сдал экзамены?            Трек 2.2. Проверка истинности рассуждений (решите любые 2 задания из перечисленных ниже, каждая задача оценивается в 2 балла). В этом треке вы можете получить 4 балла. Проверьте правильность рассуждений, используя математические методы: Трек 2.3. Использование WA для решения логических задач. За это задание вы можете получить 4 балла!    Вам будет предложено одно из рассуждений. Требуется проверить, верно ли оно проведено. Вы выбираете вариант рассуждение под номером N = ((p-1) mod 7) + 1 из ЭТОГО ДОКУМЕНТА. Напомним, что k mod n - это остаток от деления числа n на число k. В формуле для вычисления N есть параметр p - это ваш порядковый номер в списке группы (таблице результатов). Для определения вашего варианта N, вы должны обратиться к WA, он сделает это очень быстро! И наконец, подчеркните, почему рассуждение неверно, если вы убедитесь, что оно является таковым. Создайте презентацию в любом редакторе презентаций, например , в Google Drive. Поместите номер вашего варианта и текст задачи, на следующих слайдах поместите решение задачи. Выделите введенные вами обозначения и логическую формулу соответствующую высказыванию, таблицу истинности и т.п. Обязательно выпишите ответ - верно ли проведено рассуждение и, если нет, выделите в таблице истинности строку со значением "ЛОЖЬ" для вашего высказывания. Ссылку на презентацию отправьте модератору (iibazhenov@gmail.com)