Способы решения логических таблиц

Информатика

Именная карта банка для детей
с крутым дизайном, +200 бонусов

Закажи свою собственную карту банка и получи бонусы

План урока:

Способы решения задач по логике

Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:

• рассуждая над условием;
• решая логические операции;
• используя таблицы истинности.

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

Этапы решения логических задач:

• Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
• Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
• Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
• Проверить, соответствует ли полученный результат условию задачи.

Табличный способ – этапы, особенности

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

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

Метод таблиц

Чтобы использовать таблицы истинности, необходимо формализовать условие, то есть отойти от деталей задачи, обозначая первоначальную информацию при помощи букв и цифр 0 и 1.

Существует общий алгоритм построения таблиц:

• Определить число логических значений/переменных (n) в примере.
• Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
• Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
• Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
• Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2 n + 1 (шапка).
• Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
• Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
• Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

• с 2-мя переменными может быть только 4 набора логических переменных;

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

Обязательно учитывают приоритет операций:

• Указанные в скобках.
• Отрицание.
• Логическая конъюнкция чисел.
• Дизъюнкция.
• Строгая дизъюнкция.
• Импликация.
• Эквивалентность.

Обозначение логических операций:

Сравнение методов решения

Метод рассуждений

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

Пример №1.

Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.

• дом плотника правее егеря;
• стоматолог проживает левее егеря;
• дом гитариста с самого краю;
• стоматолог живет рядом с гитаристом;
• Владимир не гитарист, и его дом не соседствует с гитаристом;
• дома Дмитрия и егеря соседние;
• здание, в котором прописан Андрей, правее стоматолога;
• между домами Андрея и Дмитрия один дом.

Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:

Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:

Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.

Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.

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

Табличный метод

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

Чтобы построить таблицу истинности логических выражений, следует:

• Разбить задачу на простейшие утверждения, которые обозначить символами (большие буквы латинского алфавита).
• Записать условие задачи, как составное выражение из символов логических операций.
• Нарисовать таблицу истинности для полученных данных.
• Выбрать такой вариант, при котором полученные значения подходят под условие.
• Проверить соответствие выбранного варианта и условия задачи.

Чтобы преобразовывать условие задачи в логические выражения и операции, удобно пользоваться такой сводной таблицей истинности логических операций:

Рассмотрим тот же пример.

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

Метод компактнее, для некоторых задач нагляднее.

Построение таблиц истинности для различных типов задач

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

Пример 2.

Известно, что если первый студент летал в Англию на стажировку, то и второй тоже летал, но неправда, что если летал третий, то и второй.

Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:

А — «Первый студент летал в Англию»;

В — «Второй студент летал в Англию»;

С — «Третий студент летал в Англию».

Запишем выясненные данные при помощи логических операций:

Пример 3.

Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:

• Если А получит максимальный бал, то максимальный бал получат Ви С.
• А и С получат или не получат максимальный бал одновременно.
• Необходимым условием получения высшего бала С класса является получение высшего бала В классом.

По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.

Выясним, какие же классы добились высшего бала.

Разбиваем условие задачи на элементарные высказывания:

А – «А добьется высшего бала»;

В – «В добьется высшего бала»;

С – «С добьется высшего бала».

Запишем логические операции, описанные в примере:

Мы заполнили таблицу истинности для всех возможных значений исходных данных. В примере говорилось, что только 2 утверждения в конце года казались истинными, а 1- ложным. Такому условию отвечает 3-я строка в таблице.

Пример 4.

Во время знакомства девушка, любительница загадок, сказала, что ее имя узнать легко:

• последняя – гласная (Х1);
• или первая буква согласная (Х2)
• вторая – согласная (Х3).

Предложенные имена: Арина, Артур, Кэтрин, София.

Решим задачу, используя таблицу.

Сначала решим пошагово, выполняя операции по приоритету:

Указанному условию соответствует первое имя.

Пример 5.

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

Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.

Маша Марина: «Саша заняла второе место, а Света – первое».

Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».

Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».

Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».

Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».

Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.

Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.

Построение электронных схем, реализующих логические операции

Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.

Попробуем нарисовать логические элементы схемы питания лампочки для нескольких простых операций.

Электросхема с конъюнктором

Рассмотрим все варианты:

• Все контакты включены, тогда источник света горит.
• Первый контакт в положении «выключено» – свет не горит.
• Второй контакт выключен – лампа не светит.
• Все контакты отключены – свет не горит.

Заключение – эта электрическая цепь реализует операцию «И».

Дизъюнктор, схема электропитания

Рассмотрим этот вид электрической цепочки:

• Все контакты включены – лампа горит.
• Первый контакт включен, второй выключен – свет горит.
• Обратная ситуация – выключен первый, включен второй – лампа светится.
• Все контакты выключены – света нет.

Заключение – такой вид электросхем соответствует логической операции «ИЛИ».

Инвертор в электросхемах

В этой схеме переключатель не ручной, а автоматический. Здесь процесс обратный – когда ток не идет, контакты замыкаются, горит свет. Если же в сеть подается электричество, пластинка размыкается вследствие электромагнитной индукции, и сеть разъединяется – света нет.

Заключение: схема соответствует логической операции «НЕ».

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

Обозначение логических элементов

Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.

Источник

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

Разделы: Математика

В книге “Занимательная логика” Э.Кольмана и О.Зиха имеется много интересных логических задач. Вот одна из них.

1. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. “Замечательно, что один из нас имеет белые, один черные и один рыжие волосы, но ни у одного из нас нет волос того цвета, на который указывает его фамилия”, — заметил черноволосый. “Ты прав”, — сказал Белов. Какой цвет волос у художника?

Решение. Для решения подобных логических задач полезно составить таблицу.

Белов	Чернов	Рыжов
блондин
брюнет
рыжий

Белов	Чернов	Рыжов
блондин	—	+	—
брюнет	—	—	+
рыжий	+	—	—

В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком.

Куда налита каждая жидкость?

бутылка	стакан	кувшин	банка
Молоко	—	—	+	—
Лимонад	+	—	—	—
Квас	—	—	—	+
вода	—	+	—	—

3. В течение последних четырех лет Алексеев, Фомин, Дементьев и Иванов получали очередной отпуск в мае, июне, июле или в августе. Причем, если один из них отдыхал в мае, то другой — в июне, третий – в июле, а четвертый – в августе. Каждый их них получал отпуск в эти четыре года в разные месяцы. Так в первый год Дементьев отдыхал в июле, во второй год – в августе. Алексеев во второй год отдыхал в мае, Иванов в третий год – в июне, а Фомин в четвертый год – в июле.

Кто в каком месяце отдыхал в каждом из этих четырех лет?

1 –й год	2 –й год	3 –й год	4 –й год
Алексеев	июнь	май	июль	август
Фомин	май	июнь	август	июль
Дементьев	июль	август	май	июнь
Иванов	август	июль	июнь	май

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

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

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

Аня	Валя	Наташа	Аня	Валя	Наташа
Белые туфли	+	—	—	Белое платье	+	—	—
Зеленые туфли	—	—	+	Зеленое платье	—	+	—
Синие туфли	—	+	—	Синее платье	—	—	+

белое платье	зеленое платье	синее платье	белые туфли	зеленые туфли	синее платье
Аня
Валя
Наташа
белые туфли
зеленые туфли
синие туфли

5. Три друга – спортсмена — Алеша, Вася и Сережа – учились в одном классе. Каждый из них увлекался двумя видами спорта из следующих шести: футбол, волейбол, баскетбол, теннис, плавание и велоспорт. Известно, что:

• все трое – Сережа, теннисист и пловец ходят из школы домой вместе,
• пловец и футболист – соседи по дому,
• Алеша самый старший из троих, а теннисист старше велосипедиста,
• Наиболее интересные спортивные передачи по телевизору все трое – Алеша, велосипедист и волейболист – смотрят вместе.

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

Ответ.

• Алеша – баскетбол и плавание,
• Вася – волейбол и теннис,
• Сережа – футбол и велоспорт.

6. На школьном вечере четыре юноши: Валентин, Николай, Владимир и Алексей все из разных классов, и их одноклассницы танцевали танец, но каждый юноша танцевал не своей одноклассницей.

Лена танцевала с Валентином, Аня – с одноклассником Наташи, Николай — с одноклассницей Владимира, а Владимир танцевал с Олей.

Танцевали Лена с Валентином, Оля с Владимиром, Аня с Николаем, Наташа с Алексеем.

Учатся в одних классах Аня и Владимир, Оля и Валентин, Лена и Алексей, Наташа и Николай.

Кто с кем танцевал?

А вот эту задачу придумали дети после очередного занятия математического кружка в 6 классе.

7. В одном поселке живут три товарища: Саша, Коля и Петя, которые осваивают новую профессию. Один из них готовится стать дизайнером, другой — садоводом, третий — парикмахером. Кроме того, все они имеют и другую профессию: один строитель, другой – руководитель драмкружка, а третий ведет дискотеки. В разное время они сказали разные фразы:

• Петя, ты меня не жди, я должен доделать прическу,
• Эх, Коля, вести дискотеку – сложно, но мне очень нравится,
• Завтра, Коля, ко мне не приходи, я буду на конкурсе парикмахеров,
• На днях я получу новый диск “ Комнатные растения”.Для меня, как для будущего садовода, он будет интересным и полезным.
• Наблюдал я вчера за тобой во время репетиции и подумал, что тебе поставить пьесу не легче, чем мне вывести новый сорт роз.
• С применением новых технологий в строительстве я совершенно не знаком, хотя как дизайнеру надо сними познакомиться.

Попробуйте по этим фразам установить, кто из друзей осваивает какую профессию и какую профессию они уже имеют?

Ответ.

• Саша – парикмахер и строитель,
• Коля – дизайнер и руководитель драмкружка,
• Петя — садовод и ведущий дискотек.

Три пирата: Нытик, Стрелец и Барс зарыли свои сокровища на одном острове. Один из них зарыл возле дерева лимона, другой – банана, а третий – абрикоса. Ёмкость для хранения тоже у каждого была своя: один использовал сундучок, второй – большую морскую ракушку, а третий – кожаный мешочек.

Определите имя пирата, а также где и чем хранил свои сокровища каждый из них, если известно, что:

1. Ракушку использовал не Нытик.
2. Тот, кто закопал сокровища под абрикосом, использовал мешочек.
3. Барс закопал сундучок, но не под лимоном.

банан	абрикос	лимон	сундучок	ракушка	мешочек
Нытик
Стрелец
Барс
сундучок
ракушка
мешочек

имя	дерево	тара
Нытик	абрикос	мешочек
Стрелец	лимон	ракушка
Барс	банан	сундучок

9. После традиционного вечера встречи с бывшими выпускниками школы в стенгазете появилась заметка о трех бывших учениках школы. В этой заметке было написано, что Иван, Борис и Андрей стали учителями. Теперь они преподают разные дисциплины: один – математику, второй – физику, третий – химию. Живут они тоже в разных городах: Минске, Витебске и Харькове. В заметке было еще написано, что первоначальные их планы осуществились не полностью: Иван работает не в Минске, Андрей – не в Витебске; житель Минска преподает не математику, Андрей преподает не физику. Повезло только жителю Витебска: он преподает любимую им химию. Кто есть кто?

Ответ.

• Иван – химик — Витебск
• Борис — физик — Минск
• Андрей — математик – Харьков

10. Арташ, Отар, Гурам и Сурен занимаются в разных спортивных секциях. Один из них играет в баскетбол, другой – в волейбол, третий – в футбол, четвертый – в теннис. У них различные увлечения: один из них любит кино, другой – театр, третий – эстраду, а четвертый – цирк. Арташ не играет ни в волейбол, ни в баскетбол. Отар играет в футбол и любит театр. Сурен не играет в волейбол. Тот из ребят, кто играет в волейбол, любит ходить в кино, а тот, кто играет в баскетбол, не любит цирк. Какое у каждого из них увлечение, и каким видом спорта занимается каждый?

Ответ.

• Арташ – теннис – цирк, Отар – футбол – театр,
• Гурам – волейбол – кино, Сурен – баскетбол – эстрада.

Год назад с нашего двора первый раз в первый класс пошли 5 мальчиков. Их имена: Петя, Коля, Ваня, Гена и Миша. Получилось так, что все пятеро попали в разные классы: один в класс “А”, другой – в “Б”, третий – в “В”, четвертый — в “Г”, пятый – в “Д”. Каждому из ребят досталась в качестве классного руководителя добрая учительница: Лидия Михайловна, Елена Анатольевна. Екатерина Кирилловна. Татьяна Григорьевна и Виктория Николаевна. Дети учились прекрасно, напротив их фамилий ( Анисин, Белов, Кукушкин, Степанов и Харитонов) всегда были практически одни пятерки.

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

1. Ваня учится у Татьяны Григорьевны и его фамилия не Степанов.
2. В классе “Д” преподает не Екатерина Кирилловна.
3. Коля учится в классе “Б”. Он старше на 1месяц, чем Белов, и младше на 12 дней, чем тот, кто учится у Татьяны Григорьевны.
4. Елена Анатольевна преподает в классе “Г” и у нее нет ученика по фамилии Белов.
5. Харитонов Гена дружит с Петей и с тем, кто ходит в класс “А”.
6. Кукушкин учится в классе “А”. Его учительница не Лидия Михайловна и не Екатерина Кирилловна.
7. Анисин учится в классе “В” и его имя не Петя и не Миша.

Учительница

Имя

Класс

Петя

Коля

Ваня

Гена

Миша

Лидия Михайловна

Елена Анатольевна

Екатерина Кирилловна

Татьяна Григорьевна

Виктория Николаевна

А

Б

В

Г

Д

Фамилия

Анисин

Белов

Кукушкин

Степанов

Харитонов

Класс

А

Б

В

Г

Д

Учительница

Лидия Михайловна

Елена Анатольевна

Екатерина Кирилловна

Татьяна Григорьевна

Виктория Николаевна

фамилия	имя	учительница	класс
Анисин	Ваня	Татьяна Григорьевна	В
Белов	Петя	Лидия Михайловна	Д
Кукушкин	Миша	Виктория Николаевна	А
Степанов	Коля	Елена Анатольевна	Б
Харитонов	Гена	Елена Анатольевна	Г

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

Ответ.

• Лева – закусочная – ряженка,
• Коля – буфет – молоко,
• Миша – кафе – чай,
• Петя – столовая – кофе.

Задачи для самостоятельного решения.

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

Назовите имена каждого из избранных.

Ответ.

• Вася – староста, Боря – председатель отряда,
• Дина – звеньевая 1 –го звена, Аня – 2-го звена, Гриша — 3-го звена.

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

Кто в какой секции занимается?

Ответ.

• Петя – баскетболист, Гена – волейболист,
• Дима – гимнаст. Вова – легкоатлет.

3. Пять человек живут в одном городе. Их имена: Леонид, Владимир, Николай, Олег и Петр. Их Фамилии: Степанов, Борисов, Козин, Дроздов и Истомин. Известно, что

• Козин знаком только с двумя, а с Козиным знаком только один человек,
• Петр знаком со всеми, кроме одного, а Леонид знает только одного из всех,
• Николай и Истомин знают друг друга с детства.
• Владимир, Николай и Олег знакомы между собой,
• Дроздов и Владимир незнакомы,
• Олег, Николай и Борисов Часто вместе ходят на работу,

Назовите имена и фамилии каждого.

Ответ. Борисов Владимир, Степанов Николай, Козин Леонид, Дроздов Петр. Истомин Олег.

Источник