I. Решение логических задач средствами алгебры логики icon

I. Решение логических задач средствами алгебры логики



НазваниеI. Решение логических задач средствами алгебры логики
Дата конвертации15.07.2012
Размер137.15 Kb.
ТипРешение

I. Решение логических задач средствами алгебры логики


Обычно используется следующая схема решения:

  1. изучается условие задачи;

  2. вводится система обозначений для логических высказываний;

  3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

  4. определяются значения истинности этой логической формулы;

  5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение. Введем обозначения для логических высказываний:

^ Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:



Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание



Высказывание истинно только при Ш=1, А=0, Х=0.

^ Ответ. Победителем этапа гонок стал Шумахер.


Пример N2

В одной стране жили рыцари, которые всегда говорили правду, только правду и ничего кроме правды, и лжецы, которые всегда лгали. Однажды в страну проник шпион по имени Мердок, который, как и всякий шпион, иногда говорил правду, иногда лгал, в зависимости от того, что ему было выгодно. Шпион поселился с двумя жителями страны - рыцарем и лжецом. Всех троих арестовали в один день и привели на допрос. Никто не знал, кто из них кто.
Они сделали следующие заявления:
А сказал: Я - ^ Мердок.
В сказал: А говорит правду.
С сказал: Я не Мердок.

Кто же из них шпион - А, В или С ?

Решение:

Введем следующие переменные:
Пусть Аш =А-шпион, тогда ¯Aш =А - не шпион.
Пусть Вш =В-шпион, тогда ¯Bш = В- не шпион.
Пусть Cш =С-шпион, тогда ¯Cш = C- не шпион.

В наших обозначениях высказывания А, В, С записываются так:
А= Аш ;В= Аш ;С=¯Cш .

По условиям задачи ясно, что из трёх высказываний истинным может быть либо одно (если шпион лжет), либо два ( если шпион говорит правду). Следовательно, возможны следующие варианты распределения истинных (И) и ложных (Л) высказываний:
ИИЛ V ИЛИ V ЛИИ V ЛЛИ V ЛИЛ V ИЛЛ=1.(*)

Посмотрим, что означает ИИЛ для введенных нами обозначений.

Высказывание пленника А истинно, следовательно, Аш =1; высказывание пленника В истинно, следовательно, Аш =1; высказывание пленника С ложно, следовательно, Сш=1. То есть Ашшш =1. Но А и С не могут одновременно быть шпионами, следовательно, это неверно и данная конъюнкция ложна.

Аналогично вариант ИЛИ "переводится" в наши обозначения так:
Аш &¯Аш &¯Сш =1. Эта конъюнкция тоже ложна, поскольку А не может одновременно быть шпионом и не быть им.

Интерпретируем полностью формулу (*), опуская для кратности знак конъюнкции:
Аш Аш Сш U Аш ¯Аш ¯Cш U ¯Аш Аш ¯Cш U ¯Аш ¯Аш ¯Cш U ¯Аш Аш Cш U Аш ¯Аш Cш = 0 U 0 U 0 U ¯Аш ¯Cш U 0 U 0= ¯Аш ¯Cш =1.

То есть ни А ни С не шпионы, следовательно, шпион v В. далее уже просто сделать вывод, что А - лжец, С - рыцарь.


Таблицы

Пример №1 Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби.

Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги.

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

Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

Решение.

Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение).

Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Имя

Юра

 

 

Профессия

 

врач

 

Увлечение

 

туризм

 

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:

Имя

Юра

Тимур

Влад

Профессия

физик

врач

юрист

Увлечение

бег

туризм

регби

Ответ. Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун.


Пример №2

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

Определить цвет платья и туфель каждой из подруг.

Решение: можно решать, составляя две таблицы, а можно таблицы объединить в одно целое.

 

Аня

Валя

Наташа

 

 

Аня

Валя

Наташа

Белые туфли

+

-

-

Белое платье

+

-

-

Зеленые туфли

-

-

+

Зеленое платье

-

+

-

Синие туфли

-

+

-

Синее платье

-

-

+

 

 

белое платье

зеленое платье

синее платье

белые туфли

зеленые туфли

синее платье

Аня

 

 

 

 

 

 

Валя

 

 

 

 

 

 

Наташа

 

 

 

 

 

 

белые туфли

 

 

 

 

зеленые туфли

 

 

 

синие туфли

 

 

 



Рассуждения

Пример 6. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

  1. Вадим изучает китайский;

  2. Сергей не изучает китайский;

  3. Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

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

^ Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.


Круги Эйлера


Этот метод даёт ещё более наглядное представление о возможном способе изображения условий, зависимости, отношений в логических задачах.

Один из величайших математиков петербургский академик Леонард Эйлер за свою долгую жизнь (он родился в 1707 г., а умер в 1783 г.) написал более 850 научных работ. В одной из них и появились эти круги. Эйлер писал тогда, что «они очень подходят для того, чтобы облегчить наши размышления». Наряду с кругами в подобных задачах применяют прямоугольники и другие фигуры.

Пример№1

1. Часть жителей города умеет говорить только по-русски, часть – только по-узбекски и часть умеет говорить на обоих языках. По-узбекски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?

Решение. Составим схему –







У ? Р

85% 75%


В кружке под буквой «У» обозначим жителей, говорящих по-узбекски, под буквой «Р» - по-русски. В общей части кружков обозначим жителей, говорящих на обоих языках. Теперь от всех жителей (100%) отнимем кружок «У» (85%), получим жителей, говорящих только по-русски (15%). А теперь от всех, говорящих по-русски (75%), отнимем эти 15%. Получим говорящих на обоих языках (60%).


Пример N2

Из сотрудников фирмы 16 побывали во Франции,10-в Италии,6-в Англии; в Англии и Италии-5; в Англии и Франции -6; во всех трех странах - 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работают 19 человек, и каждый из них побывал хотя бы в одной из названных стран?

Решение:

Нам известно, что во всех трех странах было 5 сотрудников. В Англии и Италии тоже 5, значит эти же сотрудники были и во Франции и поэтому в пересечении кругов А и И ставим 0. В Франции и Италии нам неизвестно поэтому пишем х-5 в пересечении кругов А и Ф. Т.к. в Англии было 6 человек, то 6-5-1=0 пишем 0,во Франции 16-х+5-6 и Италии 10-х+5-5 и всего в фирме 19 сотрудников, то остается составить и решить уравнение:
1+16-х+5-6+5+х-5+10-х+5-5=19, отсюда х=7, значит в Италии и Франции побывало 7-5=2 сотрудника фирмы.




Пртимер №3

В классе всего 36 человек. Учащиеся посещают математический, физический и химический кружки, причем, математический кружок посещают 18 человек, физический - 14 человек, химический - 10 человек. Кроме того, известно, что все три кружка посещают 2 человека, математический и физический - 8, математический и химический - 5, физический и химический - 3.

Сколько учеников класса не посещают никаких кружков?

Решение

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

Общей части всех трех кругов соответствует множество ребят, посещающих все три кружка, поэтому она обозначена МФХ.

Через МФХ_ обозначено множество ребят, посещающих математический и физический кружки, но не посещающих химический кружок. Аналогичным образом обозначены и все остальные области. Здесь для удобства обозначений мы будем отрицание отмечать чертой над символом.

Теперь обратимся к числовым данным.

В область МФХ впишем число 2, т.к. все три кружка посещают 2 ученика. Далее известно, что ребят, посещающих математический и физический кружки, было 8. Значит, в область МФ надо вписать число 8. Но область МФ состоит из двух частей: МФХ и МФХ, причем в МФХ входят 2 человека. Значит, на долю МФХ остается 6 человек. Здесь мы используем очевидные соображения о том, что количество элементов в двух непересекающихся множеств равно сумме количеств элементов в каждом из них. Это утверждение будет неверным для пересекающихся множеств, отсюда и возникает некоторая непривычная с точки зрения школьной арифметики сложность данной задачи.

Теперь рассмотрим множество МХ, на которое приходится 5 человек. Эта область также состоит из двух частей. На МФХ приходится 2 человека, значит, на МФХ приходится 3.

Рассмотрим теперь множество М, в которое входят 18 учеников. Оно состоит из 4 частей. Количественный состав трех подмножеств мы уже нашли: это 2, 6 и 3. Значит, в четвертое подмножество МФХ входит 18 - (2+3+6) = 7 человек.

Таким образом, в классе 8 ребят, не посещающих никаких кружков.


^ C помощью графов

  1. Граф - один из видов моделей, отражающих взаимодействие объектов или систем.

Графом называют схему, в которой обозначаются только наличие объектов (элементов системы) и наличие и вид связи между объектами.

Объекты представляются в графе вершинами (на схеме они обозначаются кружочками, прямоугольниками и т.п.). Связи между объектами представляются, если связь однонаправленная (обозначается на схеме линиями со стрелками) или ребрами, если связь между объектами двусторонняя ( обозначается на схеме линиями без стрелок).

Например, если нужно представить в графе, что из состояния А в состояние В возможен переход под воздействием V, то это можно изобразить так:



Если нужно представить, что к-тый участник соревнования занял n-е место ( или, что то же самое, n-е место занял к-тым участником), это можно изобразить так:




Пример №1

1. В первенстве класса по теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводилось по круговой системе: каждый из участников играет с каждым из остальных один раз. Некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой, Борис с Галиной, Виктор с Галиной, Дмитрием и Еленой. Сколько пар проведено и сколько ещё осталось?

Решение. Изобразим данные задачи в виде схемы. Участников будем изображать точками, Андрея – А, Бориса – Б и т.д.. Если двое участников уже сыграли между собой, то будем соединять их точки отрезками.

Б В


А Г


Е Д

Число игр, уже проведённых, равно числу рёбер, т.е.7.

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

Б В


А

Г

Е Д

Рёбер у этого графа оказалось 8, значит, осталось провести 8 игр.

Пример №2.
Марина, Лариса, Жанна и Катя умеют играть на разных инструментах( пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий и испанский), но каждая только один. Известно:

    1. Девушка, которая играет на гитаре говорит по v испански.

    2. Лариса не играет ни на скрипке ни на виолончели и не знает английского языка.

    3. Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского.

    4. Девушка, которая говорит по - немецки, не играет на виолончели.

    5. Жанна знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Решение:



Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и рассматривая первое условие она играет на гитаре. Из условия N2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.



Т.к. Жанна не играет на скрипке, то остается один инструмент, на котором она может играть это виолончель. Тогда Катя играет на скрипке, и знает английский язык.




Похожие:

I. Решение логических задач средствами алгебры логики iconТема урока: «Основы логики. Алгебра высказываний»
Цель урока: обучающая Познакомить учащихся с основными понятиями логики, алгебры высказываний, с основными законами логики при упрощении...
I. Решение логических задач средствами алгебры логики iconТема урока: «Основы логики. Алгебра высказываний»
Цель урока: обучающая Познакомить учащихся с основными понятиями логики, алгебры высказываний, с основными законами логики при упрощении...
I. Решение логических задач средствами алгебры логики iconАлгебра логики Мышление Логика – наука о формах и способах мышления
Алгебра логики- раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности)...
I. Решение логических задач средствами алгебры логики iconРешение задачи с помощью алгебры логики
Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предположения
I. Решение логических задач средствами алгебры логики icon5. 11. Как упростить логическую формулу?
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для...
I. Решение логических задач средствами алгебры логики iconДокументы
1. /ЗАКОНЫ ДЕ МОРГАНА3.doc
2. /Задача разбор.doc
I. Решение логических задач средствами алгебры логики icon1. Количество нулей в столбце f таблицы истинности для логической функции Количество нулей в столбце f таблицы истинности для логической функции
На языке алгебры логики высказывания а и ((А и В) либо (А или В)) после минимизации логических операций имеет вид
I. Решение логических задач средствами алгебры логики iconМетодические рекомендации по использованию различных методов при решении задач с модулем
Методические разработки по теме: «Решение уравнений с модулем в курсе алгебры 8 класса»
I. Решение логических задач средствами алгебры логики iconПрактическая работа: «Решение задач на поясное время» 1 –вариант 8 класс
Решение задач на определение различий поясного времени на территории страны (без использования кат атласа)
I. Решение логических задач средствами алгебры логики iconРешение генетических задач в старших классах. Цель: обобщить опыт по решению генетических задач. План: Значение решения генетических задач в школьном курсе
Ы: «Генетика» «Молекулярная биология» являются одними из самых сложных для понимания в школьном курсе общая биология. Облегчению...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов