Статья по информатике на тему "Способы решения логических задач"

Решение логических задач

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

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

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

Многие логические задачи связаны с рассмотрением нескольких конечных множеств с одинаковым количеством элементов, между которыми имеются некоторые зависимости. Требуется установить взаимно-однозначное соответствие между элементами данных множеств.

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

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

1.           Табличное решение логических задач

Кондрашов, Давыдов, Мишин и Сорокин живут в одном городе. Их профессии: программист, врач, продавец и учитель.

1)    Кондрашов и Давыдов живут в одном подъезде и на работу ездят вместе.

2)    Давыдов старше Мишина.

3)    Кондрашов почти всегда обыгрывает Сорокина в теннис.

4)    Программист ходит на работу пешком.

5)    Учитель не живет рядом с врачом.

6)    Продавец и учитель встретились один раз на собрании в школе.

7)    Учитель старше врача и продавца.

Определите, кто чем занимается.

	программист	врач	учитель	продавец
Кондрашов	-	+	-	-
Давыдов	-	-	-	+
Мишин	+	-	-	-
Сорокин	-	-	+	-

 Решение: из 1 и 4 следует, что программист не Давыдов и не Кондрашов.

Из 2 и 7 следует, что учитель не Мишин.

Из 1 и 6 следует, что учителем  не может быть ни Кондрашов, ни Давыдов. Следовательно, Сорокин — учитель. Тогда, Мишин — программист.

Из 6, 1 и 2 следует, что Кондрашов — не продавец, а врач.  Давыдов — продавец.

2.           Решение логических задач с помощью графов

В школьном кружке готовятся к постановке мультфильма «Простоквашино». Между участниками возник спор, когда стали распределять роли.

Юра: Я буду дядей Федором.

Кирилл: Нет, я буду дядей Федором.

Юра: Ладно, я могу сыграть Матроскина.

Кирилл: Я могу сыграть почтальона Печкина.

Максим: Я согласен быть только котом Матроскиным.

Желания мальчиков были выполнены. Как распределились роли?

Задача 2. На одной улице живут сварщик, токарь и слесарь. Их фамилии: Петров, Семенов, Иванов. Недавно токарь попросил своего знакомого слесаря сделать кое-что в своей квартире, но слесарь ушел к сварщику. Известно, что Иванов никогда не слышал о Семенове. Кто чем занимается?

Рассмотрим первую схему: Токарь Петров знаком со слесарем Семеновым ушел к сварщику Иванову. Противоречит, что Семенов не знает Иванова.

Вторая схема: Токарь Семенов  знаком со слесарем Петровым ушел к сварщику Иванову. Верно.

Задача 3. В начале лета школьники организовали сельскохозяйственную бригаду и избрали бригадира, заместителя бригадира и звеньевых первого, второго и третьего звеньев. Их имена: Аня, Боря, Вася, Гриша и Дина. Звеньевая первого звена решила подружиться со звеньевой второго звена. Дина удивилась, узнав, что бригадир и звеньевая второго звена — брат и сестра. Гриша дружит с бригадиром и его заместителем. У Васи нет сестер. Назовите должности каждого из ребят.

Ответ: Гриша — 3 звено,  затем Вася — зам. бригадира, Дина — 1 звено, Аня — 2 звено, Боря — бригадир.

3.           Решение логических задач с помощью таблиц истинности.

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

Для данного метода надо:

1)    выделить простые высказывания и обозначить их буквами.

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

3)    Составить единое логическое выражение для всех требований задачи.

4)     Используя законы алгебры логики, попытаться упростить полученное выражение и вычислить все его значения,  либо построить таблицу истинности для рассматриваемого выражения.

5)    Выбрать решение, при котором логическое выражение является истинным.

6)    Проверить, удовлетворяет ли полученное решение условию задачи.

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

По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:

1)    если Иванов не виновен, то Сидоров не виновен.

2)    Если Иванов не виновен или Петров виновен, то Сидоров виновен.

Виновен ли Иванов?

Рассмотрим простые высказывания:

А = Иванов виновен

В = Петров виновен

С = Сидоров виновен

Запишем на языке алгебры логики факты, установленные следствием:

   и  

Пусть F=((  B)  

Составим для данного высказывания таблицу истинности:

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Необходимо проанализировать все строки таблицы истинности, где F=1. И если хотя бы в одном случае F=1 при A=0 (Иванов не виновен), то у следствия недостаточно фактов для того, чтобы обвинить Иванова в преступлении.  Из таблицы видно, что сложное высказывание истинно во всех случаях, когда А — истинно. Поэтому Иванов виновен в ограблении.

4.           Решение логических задач путем упрощения логических выражений

Предыдущую задачу решим другим способом. Запишем полученную формулу:

F=((  B)  

Перейдем от операции следования к операции дизъюнкции, пользуясь правилом замены операции импликации: .

 

Из закона де Моргана (закон общей инверсии):  получаем:

F= ((A   ) =

=AA A +  = A (

Получается, что высказывание А всегда истинно.

5.           Решение логических задач с помощью рассуждений

Левкин, Михеев и Набоков работают в качестве судьи, адвоката и прокурора. У каждого из мужчин только одна профессия.

1.    Если Набоков — адвокат, то Михеев — прокурор.

2.    Если Набоков — прокурор, то Михеев — судья.

3.    Если Михеев — не адвокат, то Левкин — не прокурор.

4.    Если Левкин — судья, то Набоков — прокурор.

Кто какую  должность занимает?

Предположим, Набоков  — адвокат,  Михеев — прокурор. Следовательно,  из 3 утверждения следует, что  Левкин — не прокурор, а значит, судья. Противоречит 1 утверждению.

Предположим, Набоков — прокурор,  Михеев — судья. Левкин — не прокурор, а значит, адвокат. Невозможно.

Набоков  не может быть прокурором и не может быть адвокатом. Поэтому Набоков — судья.  Михеев — не прокурор, не судья.  и Левкин — не судья. Остается единственное решение: Левкин — прокурор, Михеев — адвокат.

6.           Решение логических задач с помощью  языка программирования

Четыре подруги — Анна, Вера, Света и Даша — участвовали в соревнованиях по бегу и заняли первые четыре места.

1)      Света была второй, а Вера — первой.

2)      Света была первой, а второй — Даша.

3)      Анна была третьей, а Вера прибежала четвертой.

По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое — ложно.

uses crt;

    var

    a, b, c, d: integer;

    f1,f2, f3: boolean;

    begin

    clrscr;

      for a:=1 to 4 do

        for b:=1 to 4 do

          for c:=1 to 4 do

            for d:=1 to 4 do

            begin

              f1:= (c=2)and (not(b=1)) or (b=1)and (not(c=2))=true;

              f2:= (c=1) and (not(d=2)) or (d=2) and (not(c=1))=true;

              f3:= (a=3) and (not (b=4)) or (b=4)and (not(a=3)) =true;

              if f1 and f2 and f3 and (a<>b)and(b<>c) and (a<>d) and (a<>c) and (c<>d) and (b<>d)  then 

writeln('a=' , a,' b=' , b, ' c=', c, ' d=', d) ;

            end;

   end.

В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

1)      Сима первой, Валя — второй.

2)      Сима будет второй, Даша — третьей.

3)      Алла будет второй, Даша — четвертой.

По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое — ложно.

Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах?

А = Сима первая.

В = Алла вторая.

С = Даша третья.

D = Валя вторая.

uses crt;

  var

  a, b, c, d: integer;

  f1,f2, f3: boolean;

  begin

   clrscr;

   for a:=1 to 4 do

     for b:=1 to 4 do

       for c:=1 to 4 do

         for d:=1 to 4 do

         begin

           f1:= (c=1)and (not(b=2)) or (b=2)and (not(c=1))=true;

           f2:= (c=2) and (not(d=3)) or (d=3) and (not(c=2))=true;

           f3:= (a=2) and (not (d=4)) or (d=4)and (not(a=2)) =true;

           if f1 and f2 and f3 and (a<>b)and(b<>c) and (a<>d) and (a<>c) and (c<>d)and (b<>d) then

               writeln('a=' , a,' b=' , b, ' c=', c, ' d=', d) ;

          end;

  end.

7.           Решение логических задач с помощью MS Excel

Решим предыдущую задачу в  MS Excel.

=ЕСЛИ(ИЛИ(И(C1=1;НЕ(B1=2));И(B1=2;НЕ(C1=1)));1;0)

=ЕСЛИ(ИЛИ(И(C1=2;НЕ(d1=3));И(d1=3;НЕ(C1=2)));1;0)

=ЕСЛИ(ИЛИ(И(a1=2;НЕ(d1=4));И(d1=4;НЕ(a1=1)));1;0)

Задача  Изумруды

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

8.          

Задача «Шахматная доска»

На шахматной доске 64 клетки. На первую клетку кладут 1 зерно, на вторую-2 зерна, на третью – 3 зерна и т.д.: на каждую следующую клетку кладут на одно зерно больше, чем на предыдущую. Сколько зерен будет на всей доске и каков вес этих зерен в килограммах, если 15 зерен весят 1 г?

 Ответ: 138,6667 грамм

9.       С помощью блок-схем.

На одном берегу находятся мама, папа, 2 сына, 2дочери, полицейский и заключенный.  Надо всех переправить на другой берег, выполняя условия:

1. На плоту могут одновременно перемещаться максимум 2 человека.

2. Папе не разрешается находиться с дочерьми без присутствия матери.

3. Маме не разрешается находиться с сыновьями без присутствия отца.

4. Заключённого нельзя оставлять одного ни с одним из членов семьи.

5. Управлять плотом могут только полицейский и родители.

1 берег	2 берег
Пол+З →	П ←
Пол+Д→	Пол+З←
М+Д→	М←
М+П→	П←   (мама и 2 дочки)
Пол+З→	М←
М+П→	П←
П+С→	Пол+З←
Пол+С→	Пол←
Пол+З→

Список литературы:

1.       Щербакова Ю.В., Гераськина И.Ю «Занимательная математика на уроках и аненклассных мероприятиях».

2.       Златопольский Д.М. «Занимательная информатика»

3.       Богомолова О.Б. «Логические задачи»

4.       Босова Л.Л, Босова А.Ю. «Занимательные задачи по информатике»

5.       Босова Л.Л «Арифметические и логические основы ЭВМ»