Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Рекомендации по дисциплине "Элементы математической логики" (для студентов)

Рекомендации по дисциплине "Элементы математической логики" (для студентов)

Самые низкие цены на курсы профессиональной переподготовки и повышения квалификации!

Предлагаем учителям воспользоваться 50% скидкой при обучении по программам профессиональной переподготовки.

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

Обучение проходит заочно прямо на сайте проекта "Инфоурок".

Начало обучения ближайших групп: 18 января и 25 января. Оплата возможна в беспроцентную рассрочку (20% в начале обучения и 80% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru/kursy

  • Математика

Поделитесь материалом с коллегами:

Задача. «Леночка и разноцветные игрушки»

- Ой, какие красивые разноцветные шарики! А какие коробочки! Дедушка, ну, пожалуйста, подари их мне! – воскликнула Леночка, едва переступив порог дедушкиной комнаты.

- Посмотрим, заслуживаешь ли ты такого подарка, - ответил дедушка, и попросил Леночку на некоторое время выйти из комнаты. Но не прошло и минуты, как девочка услышала, что её уже зовут.

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

- Но ведь это очень трудно, - печально вздохнула Леночка.

- Совсем не трудно, - утешил её дедушка. – К тому же я помогу тебе – вот послушай:

1) ни один шарик не лежит в коробочке того же цвета, что и он сам;

2) в красной коробочке нет синих шариков;

3) в коробочке нейтрального цвета лежат один красный и один зелёный шарик. (Тут Леночка, не выдержав, спросила, что такое нейтральный цвет. Дедушка объяснил, что так принято называть белый или чёрный цвет).

4) в чёрной коробочке лежат шарики холодных тонов (Леночка уже знала, что холодными называют зеленые и синие тона);

5) в одной коробочке лежат белый и один синий шарик;

6) в синей коробочке находится один черный шарик. Помогите Леночке решить дедушкину задачу!



















Cпособ решения (рис.1).

Коробочка

Белая

Черная

Синяя

Зеленая

Красная

Шарик

Белый

-

-

-

-







Черный

-

-

-

-

+






Синий

-

-



-

-



-

-

Зеленый

+

-





-

-



Красный

+

-

-

-





-

-

Рис.1.


Из утверждений 1, 2, 3 ,4 следует, что в белой коробочке лежат один зеленый и один красный шарики. Тогда в черной коробочке лежат либо два синих, либо синий и зеленый; но из утверждения 5 следует, что два синих шарика лежать в черной коробочке не могут. Один зеленый шарик лежит в белой коробочке, второй в черной, значит, зеленых шариков нет в синей и красной коробочках (рис. 2).

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


Коробочка

Белая

Черная

Синяя

Зеленая

Красная

Шарик

Белый

-

-

-

-







Черный

-

-

-

-

+






Синий

-

-

+

-

-

-



-

-

Зеленый

+

-

+

-

-

-

-

-

-

-

Красный

+

-

-

-





-

-

Рис.2.


Красный шарик может лежать только в синей коробочке, а значит белый и черный – в красной (рис.3).

Коробочка

Белая

Черная

Синяя

Зеленая

Красная

Шарик

Белый

-

-

-

-

-

-

+

-

+

-

Черный

-

-

-

-

+

-

-

-

+

-

Синий

-

-

+

-

-

-

+

-

-

-

Зеленый

+

-

+

-

-

-

-

-

-

-

Красный

+

-

-

-

+

-

-

-

-

-

Рис.3.


Пример 1.




X

Y








0

0







0

1







1

0







1

1








Пример 2.



X

Y

Z





0

0

0




0

0

1




0

1

0




0

1

1




1

0

0




1

0

1




1

1

0




1

1

1





Примеры

3

4

5

Решение

Пример 1.




X

Y








0

0

1

1

1

0

1

1

0

1

1

1

0

1

0

0

1

0

0

0

1

1

0

1

1

1

0

1

0

1

0

0


Пример 2.



X

Y

Z





0

0

0

1

1

0

0

0

1

1

1

1

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

1

1

0

1

0

1

1

1

1

1

1

0

0

1

0

1

1

1

0

1

1


Примеры

3

4. 5.

Задача «У кого живет сорока».

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

Известно, что:

  1. поэт пользуется велосипедом;

  2. редактор живет в красном доме;

  3. критик живет в крайнем доме слева, а рядом расположен голубой дом;

  4. тот, кто ездит на мотоцикле, живет в среднем доме;

  5. тот, кто живет в зеленом доме, всегда отправляется в город пешком;

  6. зеленый дом расположен справа от белого;

  7. в доме, где живет снегирь, на завтрак всегда бывает молоко;

  8. тот, кто на завтрак получает какао, живет в доме, соседнем с тем домом, где живет синица;

  9. в желтом доме на завтрак подают чай;

  10. живущий рядом с любителем канареек утром пьет чай;

  11. писатель пьет только кофе;

  12. тот, кто ездит на своем автомобиле, любит пить томатный сок;

  13. в доме журналиста живет попугайчик.

А у кого живет сорока?
































Решение.

Для решения задачи сразу составим основную таблицу, которую будем заполнять по ходу решения (рис. 1). Воспользуемся условиями 3 и 4. По условию 6 имеем две возможности: 31 – зеленый дом №4, 32 – зеленый дом №5. Продолжим заполнять основную таблицу, если за истину принять предложение 31 (рис. 1, подчеркнуто одной чертой). Из 6 следует, дом №3 – белый; (2,3) – дом №5 красный, тогда дом №1 – жёлтый. Учтем условия 5 и 9; (9; 10) – в голубом доме живут канарейки; 1- в голубом доме живет поэт, который пользуется велосипедом. Из условия 12 следует, что редактор ездит на автомобиле и любит томатный сок.

Где живет писатель? Имеем две возможности:

- П1: писатель живет в белом доме;

- П2: писатель живет в зеленом доме.

Продолжим рассуждения, считая верным утверждение П1 (рис.1). Тогда в зеленом доме живет журналист. Из условия 11 следует , что в среднем доме пьют кофе. Из 13 – следует, в доме №4 живет попугайчик.

Рассмотрим условие 7. Молоко на завтрак может быть либо в доме №2, либо в доме №4. Но там не может жить снегирь. Получив противоречивые данные, возвращаемся к гипотезе П2. Снова условие приводят к противоречию (рис. 2).

Рис.1

Цвет дома

желтый

голубой

белый

зеленый

красный

Глава семьи

критик

поэт

писатель

журналист

редактор

Напиток

чай



кофе

сок

Способ передвижения


велосипед

мотоцикл

пешком

автомобиль

Птичка


канарейки

попугайчик




дома

1

2

3

4

5

Цвет дома

желтый

голубой

красный

белый

зеленый

Глава семьи

критик

поэт

редактор

журналист

писатель

напиток

чай

какао

молоко

сок

кофе

Способ передвижения


велосипед

мотоцикл

автомобиль

пешком

птичка

синица

канарейки

снегирь

попугайчик

сорока

Рис 2

Возвращаемся к гипотезе 32. Тогда из 2 следует: дом №1 желтый, а следовательно, в голубом доме живут канарейки. Попробуйте ответить на вопрос: «Где живет поэт?». Два варианта ответа (так как по условию 1, поэт пользуется велосипедом):

- ПТ1 – поэт живет в голубом доме;

- ПТ2 – поэт живет в белом доме.

Предположим, что вариант ПТ1 верен (рис. 3). Из 12 следует: сок пьют в белом доме. Из 11 следует, что писатель живет в зеленом доме и пьет кофе; в белом доме живет журналист, у которого есть попугайчик (условие 13). По условию 8, какао на завтрак могут получать поэт и редактор. Но у редактора нет соседа, который держит синицу. Значит какао, любит поэт, а синица живет у критика.

Условие 7: молоко на завтрак может быть только у редактора. Получаем ответ: сорока живет у писателя. Но нужно проверить ещё гипотезу ПТ2. Приведет ли она к тому же ответу?



Цвет дома

желтый

голубой

белый

зеленый

красный

Глава семьи

критик

поэт

писатель

журналист

редактор

Напиток

чай



кофе

сок

Способ передвижения


велосипед

мотоцикл

пешком

автомобиль

Птичка


канарейки

попугайчик





Рис. 3.

Из 13 следует, хозяин голубого дома пьет сок и ездит на автомобиле.

Из 12 следует, писатель живет в зеленом доме и пьет кофе, тогда в голубом доме живет журналист. Но по условию 13, он держит попугайчика. Получили противоречие, ведь в голубом доме живут канарейки (рис. 4).

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


дома

1

2

3

4

5

Цвет дома

желтый

голубой

красный

белый

зеленый

Глава семьи

критик


редактор

поэт

писатель

напиток

чай

сок



кофе

Способ передвижения


автомобиль

мотоцикл

велосипед

пешком

птичка


канарейки




Рис 4.




ЗАДАЧА.

Англичанин – живет в красном доме.

Швед – держит собаку.

Датчанин – пьет чай.

Зеленый дом стоит слева от белого.

Жилец зеленого дома пьёт кофе.

Человек, который слушает Rolling Stones, - держит птицу.

Жилец среднего дома – пьёт молоко.

Жилец желтого дома – любит слушать Бейонс.

Норвежец живет в первом доме.

Поклонник Мэрай Кэрн живет около того, кто держит кошку.

Человек, у которого есть лошадь, живет около того, кто слушает Бейонс.

Фанат Aerosmith пьет колу.

Норвежец живет около голубого дома.

Немец слушает Раммштайн.

Поклонник Мэрай Кэрн живет по соседству с тем, кто пьёт – воду.

ВОПРОС: Кому принадлежит рыба?



Желтый

Красный

Зеленый

Голубой

Белый

Чай

Кофе


Молоко

Кола

Вода

R.S.

Бейонс

Мэрай Кэрн

Aerosmith

Раммштайн

Англичанин

0

1

0

0

0

0

0

1

0

0

1

0

0

0

0

Швед

0

0

0

0

1

0

0

0

1

0

0

0

0

1

0

Датчанин

0

0

0

1

0

1

0

0

0

0

0

0

1

0

0

Немец

0

0

1

0

0

0

1

0

0

0

0

0

0

0

1

Норвежец

1

0

0

0

0

0

0

0

0

1

0

1

0

0

0





Задача «Город мастеров».

В нашем городе живут 5 друзей: Иванов, Петров, Сидоров, Веселов и Гришин. У них разные профессии: маляр, мельник, парикмахер, почтальон, плотник. Но я точно знаю, что Петров и Гришин никогда не держали в руках малярной кисти, а Иванов и Гришин давно собираются посетить мельницу, где работает их товарищ. Петров и Веселов живут в одном доме с почтальоном. Иванов и Петров каждое воскресенье играют в городки с плотником и маляром, а Гришин и Веселов по субботам встречаются в парикмахерской, где работает их друг. Почтальон же предпочитает бриться дома. Помогите мне установить профессию каждого из друзей.




Решение

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

Правило 1: В каждой строке и в каждом столбце таблицы может стоять только один знак соответствия (например «1»).

Правило 2: Если в строке (или столбце) все «места», кроме одного, заняты элементарным запретом (знак несоответствия, например «0»), то на свободное место нужно поставить знак «1»; если в строке (или столбце) уже есть знак «1», то остальные места должны быть заняты знаком «0».

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

Заполнив по условию задачи таблицу, сразу получим два типичных решения: Гришин – плотник, а Иванов – парикмахер (рис. 5).

Дальше ответ получается автоматически, но этот «автоматизм» можно «перевести» на язык логических рассуждений. Такой «перевод» и интересен, и помогает увидеть, откуда берется решение.


Профессия

Почтальон

Маляр

Мельник

Парикмахер

Плотник

Фамилия

Гришин

0

0

0

0

1

Иванов

0

0

0

1

0

Сидоров

1

0

0

0

0

Петров

0

0

1

0

0

Веселов

0

1

0

0

0

Рис.1.

После того, как произошло «сужение информации» и точно установлено, что Гришин – плотник, а Иванов – парикмахер, рассуждать можно так: т.к. Иванов не почтальон (он парикмахер) и из условий задачи следует, что Гришин, Петров и Веселов не работают почтальоном, значит, Сидоров – почтальон (а значит, не маляр и не мельник); мельником может быть только Петров, а Веселов – маляром. Эта задача предполагает только одно решение.

Ответ: Гришин – плотник, Иванов – парикмахер, Сидоров – почтальон, Петров – мельник, Веселов – маляр.


Идёт приём заявок на самые массовые международные олимпиады проекта "Инфоурок"

Для учителей мы подготовили самые привлекательные условия в русскоязычном интернете:

1. Бесплатные наградные документы с указанием данных образовательной Лицензии и Свидeтельства СМИ;
2. Призовой фонд 1.500.000 рублей для самых активных учителей;
3. До 100 рублей за одного ученика остаётся у учителя (при орг.взносе 150 рублей);
4. Бесплатные путёвки в Турцию (на двоих, всё включено) - розыгрыш среди активных учителей;
5. Бесплатная подписка на месяц на видеоуроки от "Инфоурок" - активным учителям;
6. Благодарность учителю будет выслана на адрес руководителя школы.

Подайте заявку на олимпиаду сейчас - https://infourok.ru/konkurs

Автор
Дата добавления 19.04.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров70
Номер материала ДБ-041245
Получить свидетельство о публикации

УЖЕ ЧЕРЕЗ 10 МИНУТ ВЫ МОЖЕТЕ ПОЛУЧИТЬ ДИПЛОМ

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

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

Список всех тестов можно посмотреть тут - https://infourok.ru/tests


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