Методическое пособие по информатике к разделу «Логические основы компьютера»

Shool23

Методическое пособие по информатике к разделу «Логические основы компьютера»

Календарно-тематический план по данному разделу

№

Тема

Количество часов

1.

Понятие, суждение, умозаключение.

1

2.

Операции конъюнкции, дизъюнкции и отрицания.

1

3.

Операции импликации и эквиваленции.

1

4.

Логические формулы.

1

5.

Связь между алгеброй логикой и двоичной системой счисления.

1

6.

Логические элементы компьютера.

1

7.

Таблицы истинности логических операций.

1

8.

Основные законы алгебры логики.

1

9-10.

Составление таблиц истинности.

2

11-12.

Упрощение логических формул.

2

13.

Схемы И, ИЛИ. НЕ. И-НЕ, ИЛИ-НЕ.

1

14.

Триггеры, сумматор.

1

15-16.

Переключательная схема.

2

17-18.

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

2

19-20

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

2

21-22

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

2

23-24

Решение упражнений.

2

25.

Контрольная работа.

1

26.

Обобщающий урок.

1

Введение

На очном отделении раздел «Логические основы компьютера» начинается изучаться на 1 курсе. Изучение рассчитано на 30 часов. Из них на самостоятельную работу студента отводится 4 часа. Затем выполняется контрольная работа.

Требования к знаниям и умениям

Требования к знаниям:

• Знать логические основы компьютера;

• Знать триггер и сумматор;

• Знать основные логические операции, их свойства и

обозначения;

• Знать основные законы алгебры логики.

Требования к умениям:

• Уметь строить логические схемы из основных логических элементов по формулам логических выражений;

• Уметь представлять логические выражения в виде формул и

таблиц истинности;

• Уметь решать логические задачи;

• Уметь упрощать переключательные схемы;

• Уметь объяснять назначение основных логических устройств

ЭВМ (регистр, сумматор).

Понятие, суждение, умозаключение; операции конъюнкции, дизъюнкции и отрицания; операции импликации и эквиваленции.

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

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

Лабораторные практикумы: Построение таблиц истинности логических функций и выражений (в том числе с использованием электронных таблиц). Преобразование логических выражений с использованием логических законов и правил преобразования (в том числе с использованием инженерных калькуляторов). Построение логических схем основных устройств компьютера (сумматор, триггер).

Урок №1

Тема: Понятие, суждение, умозаключение.

Цели: дать основные понятия логики, рассмотреть основные этапы развития логики, как науки, разобрать ее составные части.

Теоретическая часть.

Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы речи от ее содержания. Он исследовал терминологию логики, подробно разобрал теорию умозаключений и доказательств, описал ряд логических операций, сформулировал основные законы мышления.

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

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

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

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

Между множествами (объемами понятий) могут быть различные виды отношений:

• равнозначность, когда объемы понятий полностью совпадают;

• пересечение, когда объемы понятий частично совпадают;

• подчинения, когда объем одного понятия полностью входит в объем другого и т.д.

Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы Эйлера-Венна. Если имеются какие-либо понятия A, B, C и т.д., то объем каждого понятия (множество) можно представить в виде круга, а отношения между этими объемами (множествами) в виде пересекающихся кругов.

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

О предметах можно судить верно или неверно, т.е. высказывание может быть истинным или ложным. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Ложным суждение будет в том случае, когда связь понятий искажает объективные отношения, не соответствует реальной действительности.

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем - в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным.

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

Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называются составным (сложным).

Высказывания имеют определенную логическую форму. Понятие о предмете мысли называется субъектом и обозначается буквой S, а понятие о свойствах и отношениях предмета мысли называется предикатом и обозначается буквой P. Оба эти понятия - субъект и предикат называются терминами суждения. Отношения между субъектом и предикатом выражается связкой «есть», «не есть», «является», «состоит» и т.д.

Таким образом, каждое высказывание состоит из трех элементов - субъекта, предиката и связки (двух терминов и связки). Состав суждения можно выразить общей формулой «S есть "» или «S не есть P».

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

Умозаключения бывают дедуктивные, индуктивные и по аналогии. В дедуктивных умозаключениях рассуждения ведутся от общего к частному. Например, из двух суждений: «Все металлы электропроводны» и «Ртуть является металлом» путем умозаключения можно сделать вывод, что: «Ртуть электропроводна».

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

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

Практическая часть.

Пример 1. Установите, какие из следующих предложений являются логическими высказываниями, а какие - нет (объясните почему):

• а) "Солнце есть спутник Земли";

• б) "2+3=4";

• в) "сегодня отличная погода";

• г) "в романе Л.Н. Толстого "Война и мир" 3 432 536 слов";

• д) "Санкт-Петербург расположен на Неве";

• е) "музыка Баха слишком сложна";

• ж) "первая космическая скорость равна 7.8 км/сек";

• з) "железо - металл";

• и) "если один угол в треугольнике прямой, то треугольник будет тупоугольным";

• к) "если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный".

Ответ: Являются высказываниями: а), г), д), ж), з), и), к);
не являются высказываниями: б); в); е).

Пример 2. Укажите, какие из высказываний предыдущего упражнения истинны, какие - ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить.
Ответ: Истинные: д), з), к);
ложные: а), и);
истинность трудно установить: г);
можно рассматривать и как истинное, и как ложное в зависимости от требуемой точности представления: ж).

Пример 3. Приведите примеры истинных и ложных высказываний:

• а) из арифметики; б) из физики;

• в) из биологии; г) из информатики;

• д) из геометрии; е) из жизни.

Ответ: Образцы.
Истинные высказывания: а) "2+2=4"; б) "сила притяжения тел обратно пропорциональна квадрату расстояния между ними" в) "зайцы питаются растениями"; г) "бит - фундаментальная единица информации, используемая в теории информации"; д) "два треугольника равны, если две стороны и угол между ними одного треугольника равны двум сторонам и углу между ними другого треугольника"; е) "понедельник - первый день недели".

Ложные высказывания: а) "4+3=5"; б) "тело падает на Землю с ускорением, пропорциональным своей массе"; в) "животные это неживая природа" г) "информатика - наука о термической обработке металлов"; д) "квадрат это фигура у которой пять сторон"; е) "лев - домашнее животное".

Пример 4. Сформулируйте отрицания следующих высказываний или высказывательных форм:

• а) "Эльбрус - высочайшая горная вершина Европы";

• б) "2>=5";

• в) "10<7";

• г) "все натуральные числа целые";

• д) "через любые три точки на плоскости можно провести окружность";

• е) "теннисист Кафельников не проиграл финальную игру";

• ж) "мишень поражена первым выстрелом";

• з) "это утро ясное и теплое";

• и) "число n делится на 2 или на 3";

• к) "этот треугольник равнобедренный и прямоугольный";

• л) "на контрольной работе каждый ученик писал своей ручкой".

Ответ: а) "Эльбрус - не высочайшая горная вершина Европы"; б) "2<5"; в) "10>=7"; г) "не все натуральные числа целые"; д) "не через любые три точки на плоскости можно провести окружность"; е) "теннисист Кафельников проиграл финальную игру"; ж) "мишень не поражена первым выстрелом"; з) "это утро не ясное или оно не теплое" (Пояснение. Пусть А = "это утро ясное", а B = "это утро теплое". Тогда "это утро ясное и теплое" можно записать как А•В, отрицанием чего является , что соответствует высказывательной форме "это утро не ясное или оно не не теплое"; и)"число n не делится на 2 и оно делится на 3"; к) "этот треугольник не равнобедренный или он не прямоугольный"; л) "не каждый ученик писал контрольную своей ручкой" (вариант: "кто-то писал контрольную не своей ручкой").

Пример 5. Определите, какие из высказываний (высказывательных форм) в следующих парах являются отрицаниями друг друга, а какие нет:

• а) "5<10", "5>10";

• б) "10>9", "10<=9";

• в) "мишень поражена первым выстрелом", "мишень поражена вторым выстрелом";

• г) "машина останавливалась у каждого из двух светофоров", "машина не останавливалась у каждого из двух светофоров",

• д) "человечеству известны все планеты Солнечной системы", "в Солнечной системе есть планеты, неизвестные человечеству";

• е) "существуют белые слоны", "все слоны серые";

• ж) "кит - млекопитающее", "кит - рыба";

• з) "неверно, что точка А не лежит на прямой а", "точка А лежит на прямой а";

• и) "прямая а параллельна прямой b", "прямая a перпендикулярна прямой b";

• к) "этот треугольник равнобедренный и прямоугольный", "этот треугольник не равнобедренный или он не прямоугольный".

Ответ: Являются отрицаниями друг друга: б), г), д), к);
не являются отрицаниями друг друга: а), в), е), ж), з), и).

Пример 6. Определите значения истинности высказываний:

• а) "наличия аттестата о среднем образовании достаточно для поступления в институт";

• б) "наличие аттестата о среднем образовании необходимо для поступления в институт";

• в) "если целое число делится на 6, то оно делится на 3";

• г) "подобие треугольников является необходимым условием их равенства";

• д) "подобие треугольников является необходимым и достаточным условием их равенства";

• е) "треугольники подобны только в случае их равенства";

• ж) "треугольники равны только в случае их подобия";

• з) "равенство треугольников является достаточным условием их подобия";

• и) "для того, чтобы треугольники были неравны, достаточно, чтобы они были неподобны";

• к) "для того, чтобы четырёхугольник был квадратом, достаточно, чтобы его диагонали были равны и перпендикулярны".

Ответ: Истинны: б), в), г), з), к), и);
ложны: а), д), е), ж).

Урок №2

Тема: Операции конъюнкции, дизъюнкции и отрицания.

Цели:

1. Закрепить знания, полученные на предыдущем уроке, дать понятие коньюнкции, дизъюнкции, инверсии

Теоретический материал.

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

Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт - истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:

А = {Аристотель - основоположник логики}

В = {На яблонях растут бананы}.

Истинному высказыванию ставится в соответствие 1, ложному - 0. Таким образом, А = 1, В = 0.

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

Логическая операция КОНЪЮНКЦИЯ (логическое умножение):

 в естественном языке соответствует союзу и;

 в алгебре высказываний обозначение &;

 в языках программирования обозначение And.

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

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

Таблица истинности Диаграмма Эйлера-Венна

А В А&В

0 0 0

0 1 0

1 0 0

1 1 1

Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение):

 в естественном языке соответствует союзу или;

 обозначение v ;

 в языках программирования обозначение Or.

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

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

Таблица истинности Диаграмма Эйлера-Венна

А В А  В

0 0 0

0 1 1

1 0 1

1 1 1

Логическая операция ИНВЕРСИЯ (отрицание):

 в естественном языке соответствует словам неверно, что... и частице не;

 обозначение ;

 в языках программирования обозначение Not;

Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

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

Таблица истинности Диаграмма Эйлера-Венна

A

0 1

1 0

Практический материал.

Урок №3

Тема: Операции импликации и эквиваленции.

Цели:

Теоретическая часть.

Логическая операция ИМПЛИКАЦИЯ (логическое следование):

 в естественном языке соответствует обороту если ..., то ...;

 обозначение →.

Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

А В А→В

0 0 1

0 1 1

1 0 0

1 1 1

Логическая операция ЭКВИВАЛЕНЦИЯ (равнозначность):

 в естественном языке соответствует оборотам речи тогда и только тогда; в том и только в том случае;

 обозначения ~.

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

А В А ~ В

0 0 1

0 1 0

1 0 0

1 1 1

Практическая часть.

Пример 1. Формализуйте предостережение, которое одна жительница древних Афин сделала своему сыну, собиравшемуся заняться политической деятельностью: "Если ты будешь говорить правду, то тебя возненавидят люди. Если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить правду или лгать. Значит, тебя возненавидят люди или возненавидят боги".

Формализуйте также ответ сына: "Если я буду говорить правду, то боги будут любить меня. Если я буду лгать, то люди будут любить меня. Но я должен говорить правду или лгать. Значит, меня будут любить боги или меня будут любить люди".
Ответ: Решение. Введем обозначения для логических высказываний: а - "ты будешь говорить правду"; b - "тебя возненавидят люди"; c - "тебя возненавидят боги". Договоримся считать, что некоторое заданное высказывание x истинно, если нет оговорки. Тогда предостережение матери можно записать так:
. А ответ сына - так:
.

Пример 2. Пусть a = "это утро ясное", а b = "это утро теплое". Выразите следующие формулы на обычном языке:

Ответ:

а) "это утро ясное и тёплое"; ж) "это утро не ясное или не тёплое";

б) "это утро ясное и оно не тёплое"; з) "это утро не ясное и не тёплое";

в) "это утро не ясное и оно не тёплое"; и) "это утро ясное или не тёплое";

г) "это утро не ясное или оно тёплое"; к) "если это тро ясное, то оно не тёплое";

д) "это утро ясное или оно не тёплое"; л) "если это утро не ясное, то оно тёплое";

е) "это утро не ясное или оно не тёплое"; м) "это утро ясное и не тёплое".

Пример 3. Из двух данных высказываний a и b постройте составное высказывание, которое было бы:

• а) истинно тогда и только тогда, когда оба данных выказывания ложны;

• б) ложно тогда и только тогда, когда оба данных высказывания истинны.

Ответ : а) ; б) .

Пример 4. Из трех данных высказываний a, b, c постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

Ответ: .

Урок №4

Тема: Логические формулы.

Цели:

Теоретическая часть.

Запишем в форме логического выражения составное высказывание

(2*2=5 или 2*2=4) и (2*2 ≠ 5 или 2*2 ≠ 4)

Проанализируем составное высказывание. Что оно содержит?
Оно содержит два простых высказывания:

А= "2*2=5" - ложно (0)
В= "2*2=4" - истинно (1)

Тогда давайте перепишем составное высказывание. Что получится?

(А или В) и (А или В)

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

(AvB)&(AvB)

Теперь выполняем логические операции, причем в строго определенном порядке:

1. отрицание,

2. конъюнкция,

3. дизъюнкция,

4. импликация,

5. эквиваленция

Подставим в логическое выражение значения логических переменных и получим значение логической функции:

F = (AvB)&(AvB) = (0v1) & (1v0) = 1&1 = 1

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

Определение логической формулы:

Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") - формулы.

Если А и В - формулы, то ┐А, А . В , А v В , А B , А В - формулы.

Никаких других формул в алгебре логики нет.

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) → C.

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

Как показывает анализ формулы (A v B) →C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях - значение "ложь". Такие формулы называются выполнимыми.

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v ┐А , соответствующая высказыванию "Этот треугольник прямоугольный или косоугольный". Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями.

Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

Если две формулы А и В одновременно принимают одинаковые значения, то они называются равносильными.

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

Практическая часть.

Пример 1. Найдите значения логических выражений:

• а) (lvl) v (lvO);

• б) ((lvO) vl) vl;

• b)(0v1) v (1v0);

• г)(0&1)&1;

• е) ((lvO) & (l&l)) & (Ov l);

• ж) ((l&O) v (l&O)) v l;

• з) ((l&l) v O) & (Ov l);

• и) ((0&0) v0) & (lv l).

Пример 2. Даны два простых высказывания:

А = {2 • 2 = 4}, В = {2 • 2 = 5}.

Какие из составных высказываний истинны:

а) А; б) В;
в) А&В; г)AvB;
д) А=>В; е) А↔В?

Пример 3. Даны простые высказывания:

• А = {Принтер - устройство ввода информации},

• В = {Процессор - устройство обработки информации},

• С = {Монитор - устройство хранения информации},

• D = {Клавиатура - устройство ввода информации}.

Определите истинность составных высказываний:

a) (A&B)&(CvD); б) (А&В)=>(В&С);
в) (AvB) ↔ (C&2>); г) А↔ В.

Пример 4. Дано составное высказывание не (не А и В), где А и В - простые вы­сказывания. В каком случае данное высказывание будет ложным?

Пример 5. Даны простые высказывания:

А = {5>3}, В = {2=3} и С = {4<2}.

Определите истинность составных высказываний

a)(AvB)&C => (A&C)v(B&C);
б) (A&B)vC ↔ (AvC)&(A&B)).

Урок №5

Тема: Связь между алгеброй логикой и двоичной системой счисления.

Цели:

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

Практическая часть.

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

Из этого следует два вывода:

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

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

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

В электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким уровнем напряжения, чем двоичные нули (или наоборот), например:

Урок №6

Тема: Логические элементы компьютера.

Цели:

Теоретическая часть.

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

Ниже приведены условные обозначения (схемы) базовых логических элементов, реализующих логическое умножение (конъюнктор), логическое сложение (дизъюнктор) и отрицание (инвертор).

Рис. Конъюнктор, дизъюнктор и инвертор

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

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

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

• логический элемент «И» - логическое умножение - конъюнктор;

• логический элемент «ИЛИ» - логическое сложение - дизъюнктор;

• логический элемент «НЕ» - инверсию - инвертор.

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

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

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

Пример 1. По заданной логической функции F(A, B) = B& Ú &A построить логическую схему.

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

Пример 2. Логическая схема имеет два входа X и Y. Определить логические функции F₁(X,Y) и F₂(X,Y), которые реализуются на ее двух выходах.

Функция F₁(X,Y) реализуется на выходе первого конъюнктора, т.е. F₁(X,Y) = X&Y.

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

На другой вход второго конъюнктора подается сигнал XÚY с дизъюнктора, следовательно, функция F₂(X,Y) = & (XÚY).

Рассмотрим схему сложения двух n-разрядных двоичных чисел. При сложении цифр i-го разряда складываются а_i и b_i, а также p_i-1 - перенос из i-1разряда. Результатом будет s_i - сумма и p_i - перенос в старший разряд. Таким образом, одноразрядный двоичный сумматор - это устройство с тремя входами и двумя выходами.

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

Входы Выходы

A_i B_i P_i-1 S_i P_i

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Урок №7

Тема: Таблицы истинности логических операций.

Цели:

1. Обучающие:

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

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

2. Развивающие:

   1. Развивать логическое мышление

   2. Развивать речь учащихся

3. Воспитательные:

   1. Воспитывать умение слушать учителя и одноклассников

Теоретическая часть.

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

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

Алгоритм построения таблицы истинности:

1) подсчитать количество переменных n в логическом выражении;

2) определить число строк в таблице, которое равно m = 2ⁿ;

3) подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;

4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;

5) заполнить столбцы входных переменных наборами значений;

6) провести заполнение таблицы истинности по столбцам, выполняя логические операции.

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

а) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

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

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

Практическая часть.

Пример 1. Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно ложными:

а) д)

б) е)

в) ж)

г)

Ответ: Тождественно истинные: а), в), е);
тождественно ложные: г), д), ж).

Урок №8

Тема: Основные законы алгебры логики.

Цели:

4. Обучающие:

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

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

5. Развивающие:

   1. Развивать логическое мышление

6. Воспитательные:

   1. Воспитывать аккуратность ведения тетради

Теоретическая часть.

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

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

1. Закон двойного отрицания:

А = . Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

А v B = B v A; - для логического сложения:

A&B = B&A. - для логического умножения:

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

В обычной алгебре a + b = b + a, a v b = b v a.

3. Сочетательный (ассоциативный) закон:

(A v B) v C = A v (B v C) - для логического сложения:

(A&B)&C = A&(B&C)- для логического умножения:

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

В обычной алгебре:

(a + b) + c = a + (b + c) = a + b + c,

4. Распределительный (дистрибутивный) закон:

(A v B)&C = (A&C) v (B&C); - для логического сложения

(A&B) v C = (A v C)&(B v C). - для логического умножения:

Определяет правило выноса общего высказывания за скобку.

В обычной алгебре:

(a + b) * c = a * c + b * c.

5. Закон общей инверсии (законы де Моргана):

= &; - для логического сложения

= v - для логического умножения:

6. Закон идемпотентности ( от латинских слов idem - тот же самый и potens -сильный; дословно - равносильный):

A v A = A; - для логического сложения:

A&A = A. - для логического умножения

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

A v 1 = 1, A v 0 = A; - для логического сложения:

A&1 = A, A&0 = 0. - для логического умножения:

8. Закон противоречия:

A&= 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего:

A v = 1.

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

10. Закон поглощения:

A v (A&B) = A; - для логического сложения:

A&(A v B) = A. - для логического умножения

11. Закон исключения (склеивания):

(A&B) v (&B) = B; - для логического сложения:

(A v B)&(v B) = B. - для логического умножения:

12. Закон контрапозиции (правило перевертывания):

(A Û B) = (BÛ A).

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

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

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон Для ИЛИ Для И

Переместительный

Сочетательный

Распределительный

Правила де Моргана

Идемпотенции

Поглощения

Склеивания

Операция переменной с ее инверсией

Операция с константами

Двойного отрицания

Практическая часть.

Пример 1. Упростите следующие формулы, используя законы склеивания:

• а)

• б)

• в)

• г)

• д)
  Ответ: а) b•c; б) a; в) c•(a v b) v a•b (Указание: повторить четвертое логическое слагаемое 3 раза); г) a v c.

Пример 2. Упростите следующие формулы, используя законы поглощения:

• а)

• б)

• в)

• г)

Ответ: а) a; б) a•b; в) a; г) a•b;

Урок №9-10

Тема: Составление таблиц истинности.

Цели:

7. Обучающие:

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

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

8. Развивающие:

   1. Развивать память

   2. Развивать речь учащихся

9. Воспитательные:

   1. Воспитывать самостоятельность.

Теоретическая часть.

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

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

(0, 0), (0, 1), (1, 0), (1, 1).

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

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

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

1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах - значения промежуточных формул и в последнем столбце - значение формулы. В результате получим таблицу:

Переменные Промежуточные логические формулы Формула

0 0 1 0 0 1 1 1

0 1 1 1 1 0 1 1

1 0 0 0 1 0 0 1

1 1 0 0 1 0 0 1

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

Практическая часть.

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

• а)

• б)

• в)

• г)

• д)

• е)

• ж)

• з)

• и)

• к)

Ответ: а) a v c; б) ; в) ; г) a v c; д) a•(c v b•d); е) ; ж) ; з) ; и) a•(b v c•d); к) .

Урок №11-12

Тема: Упрощение логических формул.

Цели:

• Закрепить навыки упрощения логических выражений, используя логические законы

• Развивать логическое мышление

• Воспитывать умение слушать учителя и одноклассников

Теоретическая часть.

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1)
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);

2)
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

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

4)
(вводится вспомогательный логический сомножитель (); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);

5)
(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)
(выносятся за скобки общие множители; применяется правило операций с константами);

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

Практическая часть.

Урок №13

Тема: Схемы И, ИЛИ. НЕ. И-НЕ, ИЛИ-НЕ.

Цели:

Теоретическая часть.

С х е м а И

Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами

Таблица истинности схемы И

x y x ^. y

0 0 0

0 1 0

1 0 0

1 1 1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x ^. y
(читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.

С х е м а ИЛИ

Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами. Знак "1" на схеме - от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y").

Таблица истинности схемы ИЛИ

x y x v y

0 0 0

0 1 1

1 0 1

1 1 1

С х е м а НЕ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z =, где читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на структурных схемах инвертора

Таблица истинности схемы НЕ

x

0 1

1 0

С х е м а И-НЕ

Схема И-НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: , где читается как "инверсия x и y". Условное обозначение на структурных схемах схемы И-НЕ с двумя входами

Таблица истинности схемы И-НЕ

x y

0 0 1

0 1 1

1 0 1

1 1 0

С х е м а ИЛИ-НЕ

Схема ИЛИ-НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: , где , читается как "инверсия x или y ". Условное обозначение на структурных схемах схемы ИЛИ-НЕ с двумя входами представлено на рис. 5.5.

Таблица истинности схемы ИЛИ-НЕ

x y

0 0 1

0 1 0

1 0 0

1 1 0

Практическая часть.

Урок № 14

Тема: Триггеры, сумматор.

Цели:

Теоретическая часть.

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

Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое и наоборот.

Самый распространённый тип триггера - так называемый RS-триггер (S и R, соответственно, от английских set - установка, и reset - сброс). Условное обозначение триггера - на рис.

Он имеет два симметричных входа S и R и два симметричных выхода Q и , причем выходной сигнал Q является логическим отрицанием сигнала .

На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных импульсов ( ).

Наличие импульса на входе будем считать единицей, а его отсутствие - нулем.

На рис. показана реализация триггера с помощью вентилей ИЛИ-НЕ и соответствующая таблица истинности.

S R Q

0 0 запрещено

0 1 1 0

1 0 0 1

1 1 хранение бита

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы ИЛИ-НЕ

1. Если на входы триггера подать S="1", R="0", то (независимо от состояния) на выходе Q верхнего вентиля появится "0". После этого на входах нижнего вентиля окажется R="0", Q="0" и выход станет равным "1".

2. Точно так же при подаче "0" на вход S и "1" на вход R на выходе появится "0", а на Q - "1".

3. Если на входы R и S подана логическая "1", то состояние Q и не меняется.

4. Подача на оба входа R и S логического "0" может привести к неоднозначному результату, поэтому эта комбинация входных сигналов запрещена.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 х 2¹⁰ = 8192 триггеров. Современные микросхемы памяти содержат миллионы триггеров.

Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел.

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

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

При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами:

1. цифра a_i первого слагаемого;

2. цифра b_i второго слагаемого;

3. перенос p_i-1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра c_i для суммы;

2. перенос p_i из данного разряда в старший.

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

Входы Выходы

Первое слагаемое Второе слагаемое Перенос Сумма Перенос

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

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

Например, схема вычисления суммы C = (с₃ c₂ c₁ c₀) двух двоичных трехразрядных чисел A = (a₂ a₁ a₀) и B = (b₂ b₁ b₀) может иметь вид:

Практическая часть.

Пример 1. Существует 16 логических функций от двух переменных Построить их логические схемы с помощью логических элементов И, ИЛИ, НЕ.

Ответ:

F₁ (константа 0)

F₂ (конъюнкция)

F₃ (отрицание импликации Х в Y)

F₄ (переменная Х)

F₅ (отрицание импликации Y в Х)

F₆ (переменная Y)

F₇ (отрицание эквивалентности)

F₈ (дизъюнкция)

F₉ (ИЛИ-НЕ)

F₁₀ (эквивалентность) F₁₁ (отрицание Y)

F₁₂ (импликация Y в Х)

F₁₃ (отрицание Х)

F₁₄ (импликация Х в Y)

F₁₅ (И-НЕ)

F₁₆ (константа 1)

Пример 2 Доказать, что рассмотренная в примере 3.11 логическая схема является одноразрядным двоичным полусумматором (не учитывается перенос из младшего разряда).

Ответ: Таблица сложения одноразрядных двоичных чисел X и Y с учетом переноса в старший разряд выглядит следующим образом:

Слагаемые Перенос Сумма

X Y P S

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

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

P = F₁(X,Y) =X&Y

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

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

S = F₂(X,Y) = (XÚY)&( )

Пример 3. Построить логическую схему одноразрядного двоичного сумматора.

Ответ:

Пример 4. Какое количество базовых логических элементов необходимо для реализации 64-разрядного сумматора двоичных чисел.

Ответ: Для построения одноразрядного сумматора двоичных чисел необходимо 9 базовых логических элементов. Следовательно: 9 ´ 64 = 576.

Пример 5. Какое количество базовых логических элементов составляют оперативную память современного компьютера объемом 64 Мбайта.

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

4 ´ 8 ´ 64 ´ 1024 ´ 1024 = 2 147 483 648

Урок №15-16

Тема: Переключательная схема.

Цели:

1. Познакомиться со схематическими обозначениями логических элементов, научиться по формулам строить и читать электрические схемы

Теоретическая часть.

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

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

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

Найдем функции проводимости F некоторых переключательных схем:

a)

Схема не содержит переключателей и проводит ток всегда, следовательно F=1;

б)

Схема содержит один постоянно разомкнутый контакт, следовательно F=0;

в)

Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x;

г)

Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = ;

д)

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x ^. y;

е)

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y;

ж)

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

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

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

Задача нахождения среди равносильных схем наиболее простых является очень важной. Большой вклад в ее решение внесли российские учёные Ю.И. Журавлев, С.В. Яблонский и др.

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;

2. упрощению этой функции;

3. построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к

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

2. получению упрощённой формулы.

Практическая часть.

Пример 1. Найдите функции проводимости следующих переключательных схем:

а) б)

в) г)

Ответ.

Пример 2. Проверьте равносильность следующих переключательных схем:

• а)

• б)

• в)

• г)

• д)

Ответ: Равносильны: б), в), д);
неравносильны: а), г).
Пояснения. Обозначим функции проводимости рассматриваемых переключательных схем как F₁ и F₂, соответственно. Тогда: а) ; ;
б) ; ;
в) ; ;
д) ; .

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

Пример 4. Упростите функции проводимости и постройте переключательные схемы, соответствующие упрощенным функциям:

а)

б)

в)

г)

д)

е)

ж)

з)

и)
Ответ : Упрощенные функции:

Пример 5. Упростите следующие переключательные схемы:

• а)

• б)

• в)

• г)

Ответ: Функции проводимости упрощенных схем:

Урок №17-18

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

Цели:

1. Обучающие:

   1. Научить решать логические задачи

2. Развивающие:

   1. Развивать логическое мышление

   2. Развивать внимание

3. Воспитывающие:

   1. Воспитывать дисциплинированность

Теоретическая часть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок №19-20

Тема: Решение логических задач табличным способом.

Цели:

1. Обучающие:

1.Научить решать логические задачи

2. Закрепить навыки решения логических задач

2.Развивающие:

1.Развивать внимание

3.Воспитывающие:

2. Воспитывать аккуратность ведения тетради

Теоретическая часть.

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

Пример 1. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

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

1. Смит самый высокий;

2. играющий на скрипке меньше ростом играющего на флейте;

3. играющие на скрипке и флейте и Браун любят пиццу;

4. когда между альтистом и трубачом возникает ссора, Смит мирит их;

5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна - альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

скрипка флейта альт кларнет гобой труба

Браун 0 0 1 1 0 0

Смит 0 0 0

Вессон 0 0

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

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки "Вессон" можно заполнить нулями:

скрипка флейта альт кларнет гобой труба

Браун 0 0 1 1 0 0

Смит 0 0 0 0

Вессон 1 0 0 0 0 1

Из таблицы видно, что играть на флейте и на гобое может только Смит.

скрипка флейта альт кларнет гобой труба

Браун 0 0 1 1 0 0

Смит 0 1 0 0 1 0

Вессон 1 0 0 0 0 1

Ответ: Браун играет на альте и кларнете, Смит - на флейте и гобое, Вессон - на скрипке и трубе.

Практическая часть.

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

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

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

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

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

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

Имя Юра

Профессия врач

Увлечение туризм

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

Имя Юра Тимур Влад

Профессия физик врач юрист

Увлечение бег туризм регби

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

Пример 3. Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго.

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

Джуди живет не в Париже, а Линда - не в Риме;

парижанка не снимается в кино;

та, кто живет в Риме, певица;

Линда равнодушна к балету.

Где живет Айрис, и какова ее профессия?

Решение. Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:

Париж Рим Чикаго Пение Балет Кино

0 Джуди

Айрис

0 Линда 0

Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке "Линда" и столбцу "Пение", ставим 0.

Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино.

Париж Рим Чикаго Пение Балет Кино

0 Джуди 0

Айрис 0

0 Линда 0 0 1

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.

В результате постепенного заполнения получаем следующую таблицу:

Париж Рим Чикаго Пение Балет Кино

0 0 1 Джуди 1 0 0

1 0 0 Айрис 0 1 0

0 0 1 Линда 0 0 1

Ответ. Айрис балерина. Она живет в Париже.

Пример 4.Один из четырех мальчиков испортил выключатель. На вопрос «Кто это сделал?» были получены такие ответы:

(1) «Это сделал или Миша, или Коля»;

(2) «Это сделал или Витя, или Коля»;

(3) «Это не могли сделать ни Толя, ни Миша»;

(4) «Это сделал или Витя, или Миша».

Можно ли по этим данным установить, кто виновен в поломке выключате­ля, если известно, что из четырех высказываний три истинны?

Решение.

Обозначим через М высказывание «Виноват Миша», В - «Виноват Витя», К - «Виноват Коля», Т - «Виноват Толя». Тогда ответы на вопрос о винов­нике поломки описываются следующими формулами алгебры высказываний:

В первые четыре столбца таблицы поместим значения высказываний М, В, К и Т, в столбцы с 5-го по 8-й поместим значения высказываний (1) - (4). Так как виноват только один из четырех мальчиков, количество строк в таблице равно 4, причем первые четыре столбца таблицы содержат только по одному значению «истина» (единицу), а остальные - «ложь» (нуль). Значения в столбцах с 5-го по 8-й вычисляем в соответствии с записанными формулами.

М в к т (1) (2) (3) (4)

1 0 0 0 1 0 0 1

0 1 0 0 0 1 1 1

0 0 1 0 1 1 1 0

0 0 0 1 0 0 0 0

Из таблицы видно, что возможны два варианта одновременной истинности трех ответов: из четырех строк таблицы две (2-я и 3-я) содержат по три единицы. Но эти строки соответствуют значениям истинности для высказыва­ний В и К. Следовательно, виноват или Витя, или Коля, т. е. однозначно ответить на вопрос «Кто виноват?» при заданных условиях нельзя.

Ответ. По ответам, данным мальчиками, определить виновника нельзя.

Пример 5. Один из трех братьев - Витя, Толя или Коля - разбил окно. В разговоре участвуют еще два брата - Андрей и Дима.

(1) - Это мог сделать только или Витя, или Толя, - сказал Андрей.

(2) - Я окно не разбивал, - возразил Витя, - и Коля тоже.

(3) - Вы оба говорите неправду, - заявил Толя.

(4) - Нет, Толя, один из них сказал правду, а другой сказал неправ­ду, - возразил Дима.

(5) - Ты, Дима, не прав, - вмешался Коля.

Их отец, которому, конечно, можно доверять, уверен, что трое из пяти братьев сказали правду. Кто же разбил окно?

Решение.

Обозначим через В высказывание «Окно разбил Витя», Т - «Окно разбил Толя», К - «Окно разбил Коля». Тогда высказывания участников разговора опишутся формулами:

Составим таблицу, поместив в первые три столбца значения высказываний В, Т, К, as столбцы с 4-го по 8-й - значения высказываний (1) - (5). Так как только один из братьев может быть виновником неприятного события, то возможны только три варианта значений для В, Т, К, поэтому таблица содержит три строки, в каждой из которых в первых трех столбцах одна единица и два нуля. Значения в остальных столбцах таблицы вычисляем в соответствии с записанными формулами.

В Т к (1) (2) (3) (4) (5)

1 0 0 1 0 0 1 0

0 1 0 1 1 0 0 1

0 0 1 0 0 1 0 1

Теперь воспользуемся истинностью утверждения отца о том, что правду сказали трое из пяти братьев. В соответствии с таблицей это возможно, только если окно разбил Толя (2-я строка).

Ответ. Окно разбил Толя.

Пример 6. Ключ от замка спрятан в одной из трех шкатулок - черной, белой или красной, - на крышках которых сделаны надписи:

(1) на черной шкатулке: «Ключ не в белой шкатулке»;

(2) на белой шкатулке: «Ключ не в этой шкатулке»;

(3) на красной шкатулке: «Ключ в этой шкатулке».

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

Решение.

Обозначим через Ч высказывание «Ключ в черной шкатулке», Б - «Ключ в белой шкатулке», К - «Ключ в красной шкатулке». Тогда надписи на шкатулках опишутся формулами:

(1) ¬Б;

(2) ¬Б;

(3) К.

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

Ч Б К (1) (2) (3)

1 0 0 1 1 0

0 1 0 0 0 0

0 0 1 1 1 1

Теперь, пользуясь дополнительной информацией о том, что по крайней мере одна надпись истинна и по крайней мере одна ложна, проанализируем 4-й, 5-й и 6-й столбцы таблицы. Условиям задачи удовлетворяет только первая строка таблицы. Следовательно, ключ спрятан в черной шкатулке.

Ответ. Ключ спрятан в черной шкатулке.

Рассмотрим два подхода применения табличного метода к решению задач из серии «Кто где живет?» («Кто кем работает?», «Как составить расписа­ние?» и т. д.). В задачах такого рода надо найти только одно истинное сложное конъюнктивное высказывание из всех подобных высказываний, описывающих возможные варианты. Первый подход основан на так называемом «тупом» переборе, второй - на переборе со стратегией (этот подход достаточно подробно описан в [2]).

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

(1) или Антонов не едет в Москву, или Сомов едет в Санкт-Петербург;

(2) или Антонов едет в Москву и Вехов не едет в Киев, или Сомов едет в Санкт-Петербург;

(3) если Антонов едет в Киев, то Сомов едет в Москву. При этом Вехов не едет в Санкт-Петербург;

(4) если Вехов едет в Москву, то Антонов едет в Санкт-Петербург? Рассмотреть варианты, когда из этих ограничений:

а) верны все;

б) верны только два;

в) верны только три. Решение.

Обозначим через am, An и ак высказывания «Антонов едет в Москву», «Антонов едет в Санкт-Петербург» и «Антонов едет в Киев» соответственно. Аналогично определим высказывания Бм, Бп, Бк, См, Сп, Ск. В этих обозна­чениях ограничения из условия задачи опишутся формулами:

Составим таблицу, содержащую 13 столбцов: в первые девять поместим значения am, Вм, См, An, Вп, Сп, ак, Вк, Ск, а в столбцы с 10-го по 13-й - значения, вычисленные по формулам (1) - (4). Единицы и нули в первых девяти столбцах расставляем так, чтобы перебрать все возможные варианты поездок друзей в города с учетом того, что каждый едет в какой-нибудь город и в один город едет только один из друзей. Получим шесть вариантов.

Ам Вм См Аи Вп Сп Ак Вк Ск (1) (2) (3) (4)

1 0 0 0 1 0 0 0 1 0 1 0 1

1 0 0 0 0 1 0 1 0 1 1 1 1

0 1 0 1 0 0 0 0 1 1 0 1 1

0 1 0 0 0 1 1 0 0 1 1 0 0

0 0 1 1 0 0 0 1 0 1 0 1 1

0 0 1 0 1 0 1 0 0 1 0 0 1

Анализируя таблицу, получаем ответ на вопрос задачи.

Ответ.

а) Можно, так как в случае, когда Антонов едет в Москву, Сомов - в Санкт-Петербург, а Вехов - в Киев, верны все ограничения (2-я строка таблицы);

б) нельзя, так как ровно два ограничения верны в трех случаях (1-я, 4-я и 6-я строки);

в) нельзя, так как ровно три ограничения верны в двух случаях (3-я и 5-я строки).

Приведем решение этой задачи перебором со стратегией, используя таб­личный метод. Составим таблицу размера 3x3, столбцы которой обозначим фамилиями друзей, а строки - названиями городов:

Города Фамилии

Антонов Вехов Сомов

Москва

Киев

Санкт-Петербург

Для решения задачи в случае а) надо так расставить единицы в этой таблице, чтобы в каждой ее строке и каждом столбце было ровно по одной единице и при этом формулы (1) - (4) были бы одновременно истинны. Из (1) выбираем истинность дизъюнкта Сп, который дает однозначный ответ о Сомо­ве, и ставим единицу в соответствующую ячейку таблицы. Так как Сомов едет только в один город и в Санкт-Петербург едет только один из друзей, то заполняем нулями остальные строки 3-го столбца и столбцы 3-й строки.

Города Фамилии

Антонов Вехов Сомов

Москва 0

Киев 0

Санкт-Петербург 0 0 1

Формула (2) будет истинна в силу истинности Сп- В формуле (3) конъюнкт ¬Bn истинен, а для истинности импликации Ак  См мы должны выбрать вариант, при котором Ак ложно, так как См ложно. Таким образом, истинно должно быть am, т. е. Антонов должен ехать в Москву. Ставим единицу в со­ответствующую ячейку таблицы и нули в остальные ячейки по Москве и Ан­тонову. Получаем единственную незаполненную ячейку, соответствующую поездке Вехова в Киев, в которую и ставим единицу.

Города Фамилии

Антонов Вехов Сомов

Москва 1 0 0

Киев 0 1 0

Санкт-Петербург 0 0 1

Проверяем истинность формулы (4). Она следует из ложности Вм. Таким образом, получили такой вариант ответа: Антонов едет в Москву, Вехов едет в Киев, Сомов едет в Санкт-Петербург.

Чтобы убедиться в однозначности этого ответа, рассмотрим другие вариан­ты истинности формулы (1).

Города Фамилии

Антонов Вехов Сомов

Москва 0 0 1

Киев 1 0 0

Санкт-Петербург 0 1 0

В представленном варианте получаем истинность формул (1) и (4) и лож­ность формул (2) и (3). Еще один вариант:

Города Фамилии

Антонов Вехов Сомов

Москва 0 1 0

Киев 0 0 1

Санкт-Петербург 1 0 . 0

В этом варианте получаем истинность формул (1), (3) и (4) и ложность (2).

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

Мы видим, что в этой задаче первоначальный «тупой» перебор оказался более эффективным и кратким в оформлении.

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

(1) учитель математики просил поставить его урок в расписании или первым, или вторым;

(2) учитель истории - или первым, или третьим;

(3) учитель литературы - или вторым, или третьим.

Как составить расписание уроков, чтобы учесть пожелания учителей?

Решение.

Обозначим через M₁, M₂ и Мз высказывания «Математика поставлена в расписании первым уроком», «Математика - второй урок», «Математика - третий урок» соответственно. Аналогично определим И1, И2, И3,Л1, Л2, Л3.

В этих обозначениях пожелания учителей опишутся следующими форму­лами:

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

Mi Hi Лг М2 И₂ Л₂ Мз Из Лз (1) (2) (3)

1 0 0 0 1 0 0 0 1 1 0 1

1 0 0 0 0 1 0 1 0 1. 1. 1.

0 1 0 1 0 0 0 0 1 1 !_ I

0 1 0 'о 0 1 1 0 0 0 1 1

0 0 1 1 0 0 0 1 0 1 1 0

0 0 1 0 1 0 1 0 0 0 0 0

В таблице во 2-й и 3-й строках в столбцах для (1) - (3) стоят все единицы. Следовательно, для удовлетворения всех пожеланий расписание можно соста­вить двумя способами: первый урок - математика, второй - литература, третий - история или первый урок - история, второй - математика, тре­тий - литература.

Ответ. Расписание можно составить двумя способами:

1) первый урок -• математика, второй - литература, третий - история;

2) первый урок - история, второй - математика, третий - литература.

Перебор со стратегией выбора варианта истинности формулы (1), аналогич­ный решению задачи 4, приводит к составлению двух таблиц размера 3x3, дающих оба варианта составления расписания.

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

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

Цели:

-учить решать задачи с помощью рассуждений;

- сформулировать правила преобразования логических задач;

- воспитывать внимательность, смекалку.

Этим способом обычно решают несложные логические задачи.

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

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

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

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

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

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

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

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

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

Пример 2. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:

Россия - "Проект не наш, проект не США";
США - "Проект не России, проект Китая";
Китай - "Проект не наш, проект России".

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз - неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия - "Проект не наш" (1), "Проект не США" (2);
США - "Проект не России" (3), "Проект Китая" (4);
Китай - "Проект не наш" (5), "Проект России" (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный - министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее - российский, скрытнее - министр США.

Пример 3. Жили-были две фигуры: круг и квадрат. На их улице было 3 дома: один был с окном и трубой, другой - с окном , но без трубы, а третий - с трубой, но без окна. Каждая фигура жила в своем доме. Круг и Квадрат жили в домах с окнами. Квадрат любил тепло и часто топил печку. Кто в каком доме жил?

Решение.

Ответ: квадрат живет в доме с трубой и окном, круг - с окном.

Пример 4. Встретились три подруги - Белова, Краснова и Чернова. На одной было черное платье, на другой - красное, на третьей - белое. Девочка в белом платье сказала Черновой: «Нам троим надо поменяться платьями, а то цвета наших платьев не соответствуют нашим фамилиям». Кто в каком платье был?

Ответ: Краснова - белое, Чернова - красное, Белова - черное.

Пример 5. В кафе встретились три друга - Белов, Чернов и Рыжов. «Замечательно, что у одного из нас белые, у другого черные, у третьего рыжие волосы, но ни у кого цвет волос не соответствует фамилии», - заметил черноволосый. «Ты прав», - сказал Белов. Какой цвет волос у Рыжова?

Ответ: У Рыжова черные волосы.

Пример 6. Наташа, Валя, Маша, Галя и Лена вырезали из бумаги разные фигуры. Кто-то из них вырезал круг из бумаги в клетку, кто-то из бумаги в линейку, кто-то - квадрат из бумаги в клетку, кто-то - квадрат из бумаги в линейку, а кто-то - флажок из белой бумаги. Галя и Валя вырезали круги. Галя и Наташа вырезали фигуры из бумаги в клетку. Наташа и Маша вырезали квадраты. Кто какие фигуры вырезал?

Ответ: Галя - круг в клетку, Валя - круг в линейку, Наташа - квадрат в клетку, Маша - квадрат в линейку, Лена - флажок.

Пример 7. У Джека - красная, у Питера - не черная, не синяя, не голубая, у Майкла - черная и синяя, у Алекса есть машины всех цветов, у Бери - белого и синего. На пикник юноши выехали на своих машинах, причем все они оказались разного цвета. Кто был на какой машине?

Ответ: Джек - красная, Питер - белая, Майкл -черная, Алекс - голубая, Бери - синяя.

Пример 8. Катя, Соня, Галя и Тамара родились: 2 марта, 17 мая, 2 июля и 20 марта. Соня и Галя родились в одном месяце, а у Гали и Кати дни рождения обозначаются одинаковыми числами. Кто какого числа и какого месяца родился?

Ответ: Галя 2 марта, Соня - 20 марта, Катя - 2 июля, Тамара - 17 мая.

Пример 9. Коля, Боря, Вова, и Юра заняли первые четыре места в соревновании. На вопрос, какие места заняли, трое из них ответили:

1. Коля - ни первое, ни четвертое;

2. Боря - второе;

3. Вова не был последним.

Какое место занял каждый мальчик?

Ответ: Коля -3, Боря - 2, Вова - 1, Юра - 4

Пример 10.Клоуны Ам, Бам и Там вышли на арену со своими собаками, которых звали Ум, Бум и Гумм. Имя каждой собаки не начиналось на первую букву имени хозяина. Ам- хозяин Гума. Кто вышел с собакой Ум?

Ответ: Бам

Пример 11. Эдика, Колю и Васю угостили печеньем 3-х сортов: с вареньем, с орехами и глазурью. Коля не любит орехи, Эдик не ест варенье, а Коля любит глазурь. Каждый ел печенье только одного сорта. Кто ел печенье с вареньем?

Ответ: Коля

Пример 12. В семье четверо детей 5,8,13,15 лет. Их имена - Аня, Боря, Валя и Галя. Одна из девочек ходит в детский сад. Аня старше Бори. Сумма возрастов Ани и Вали делится на 3. сколько лет Боре?

Решение. Одна из девочек ходит в д\с - Боре не 5 лет. Аня старше Бори - Ане не 5 и не 8. сумма возрастов Ани и Вали делится на 3 15 в сумме с другим числом дает число не кратное 3, значит Ане - 13 лет.

Ответ: Боре - 8 лет

Урок 25

Тема: Урок контроля знаний

Цели:

- контроль уровня теоретических и практических знаний по теме «логические основы компьютера»;

• развитие познавательного интереса;

• Воспитывать саомтоятельность

Содержание контрольной работы

1 вариант

1)Пусть А = «президент США - демократ», a В = «пингвины живут в Антарктиде». Выразите следующие формулы на обычном языке: А  В, ĀÚВ, А 

2) Составьте таблицы истинности и определите истинность формулы:

((С v В)В)А ВВ

3) Упростите переключательную схему:

4) Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем «Бьюике», Джонс сказал, что это был черный «Крайслер», а Смит утверждал, что это был «Форд Мустанг» и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них указал правильно либо марку машины, либо только ее цвет. Какого цвета был автомобиль?

5) В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

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

Смит самый высокий;

играющий на скрипке меньше ростом играющего на флейте;

играющие на скрипке и флейте и Браун любят пиццу;

когда между альтистом и трубачом возникает ссора, Смит мирит их;

Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

2 вариант

1) Пусть А = «волк - травоядное животное», a В = «бензоколонке есть бензин». Выразите следующие формулы на обычном языке: АВ, vА, Ā В

2) Составьте таблицы истинности и определите истинность формулы:

(Ā v В Ù С) Ù А Ù

3) Упростите переключательную схему:

4) Виновник ночного дорожно-транспортного происшествия скрылся с ме­ста аварии. Первый из опрошенных свидетелей сказал работникам ГИБДЦ, что это были «Жигули», первая цифра номера машины - единица. Вто­рой свидетель сказал, что машина была марки «Москвич», а номер начи­нался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании вы­яснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

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

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

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

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

3 вариант

1) Пусть А = «спутник - это летательный аппарат», a В = «в Африке водятся жирафы». Выразите следующие формулы на обычном языке: А , ĀÚВ, А В

2) Составьте таблицы истинности и определите истинность формулы:

(XvY) Ù (ZvX) Ù (ZvY).

3) Упростите переключательную схему:

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

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

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

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

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

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

5) Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго.

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

Джуди живет не в Париже, а Линда - не в Риме;

парижанка не снимается в кино;

та, кто живет в Риме, певица;

Линда равнодушна к балету.

Где живет Айрис, и какова ее профессия?

4 вариант

(А vВ) (vС) С

1) Пусть А = «арбуз - это ягода», a В = «на севере водятся медведи». Выразите следующие формулы на обычном языке: Ā В, vА, А В

2) Составьте таблицы истинности и определите истинность формулы:

3) Упростите переключательную схему:

4) Внимание Андрея, Дениса и Марата привлек промчавшийся мимо них автомобиль.

- Это английская машина марки «Феррари», - сказал Андрей.

- Нет, машина итальянская марки «Понтиак», - возразил Денис.

- Это «Сааб», и сделан он не в Англии, - сказал Марат.

Оказавшийся рядом знаток автомобилей сказал, что каждый из них

прав только в одном из двух высказанных предположений.

Какой же марки этот автомобиль и в какой стране изготовлен?

5) Пятеро одноклассников - Ирена, Тимур, Камилла, Эльдар и Залим ста­ли победителями олимпиад школьников по физике, математике, инфор­матике, литературе и географии. Известно, что: победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере; Камилла и Эльдар тоже заинтересовались информатикой; Тимур всегда побаивался физики; Камилла, Тимур и победитель олимпиады по литературе занима­ются плаванием; Тимур и Камилла поздравили победителя олимпиады по математике; Ирена сожалеет о том, что у нее остается мало времени на литературу. Победителем какой олимпиады стал каждый из этих ребят?

Обобщающий урок №26 (КВН)

Цели урока:

1. учебные:

   • закрепление пройденного материала;

   • контроль уровня знаний, умений и навыков учащихся по теме «Логика»;

2. воспитательные:

   • повысить мотивацию учащихся на уроке за счет игровой формы работы;

   • добиться сознательного усвоения материала;

   • научить умению «слушая, слышать»;

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

   • работать над повышением грамотности устной речи;

3. образовательные:

   • развивать у школьников умение выделять главное, существенное, обобщать имеющиеся факты, логически излагать мысли;

   • расширять связи с другими учебными предметами.

Подготовительный этап

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

Команды как игроков, так и болельщиков получают домашнее задание.

Домашнее задание для команд игроков:

1. Придумать название команды и ее эмблему. Они должны быть связаны с изучаемой темой («Логика»).

2. Подготовить представление двух понятий изучаемой темы («Логика») с помощью средств мимики и жестов.

Проведение КВН

Ведущий. «...Ложное направление ума заключается исключительно в привычке рассуждать, исходя из плохо определенных принципов» (Э. Кондильяк). Сегодня мы проведем соревнование между двумя командами и определим, кто лучше усвоил эти принципы, а болельщики смогут не только поддержать вас, но и помочь своим командам набрать дополнительные очки, отвечая на вопросы. Жюри будет учитывать ответы болельщиков и в конце игры может добавить командам максимум по 3 балла.

Проводится жеребьевка.

Конкурс 1. Приветствие. (Максимальная оценка за конкурс - 2 балла.)

В конкурсе участвуют команды в полном составе. Команды представляют свое название и эмблему.

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

Идет представление членов жюри и выставление оценок.

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

Из объявления: «Уважаемые жильцы! В среду, 20 августа, в нашем доме будут производить дезинсекцию против тараканов. Убедительно просим жильцов быть в это время дома, так как уничтожение тараканов будет производиться вместе с ними».

Конкурс 2. Разминка. (Максимальная оценка за конкурс - 6 баллов.)

Задание конкурса.

Ведущий вызывает попеременно игроков разных команд - всего по 3 игрока от каждой команды. Каждому игроку задается вопрос и дается 15 секунд для обдумывания. Если игрок ответил неправильно, вопрос адресуется болельщикам.

Примерные задачи:

1. Этот вопрос обращен к тем, кто знает что-нибудь о католицизме. Может ли католик жениться на сестре своей вдовы?

2. Крыша одного дома несимметрична. Один скат ее составляет с горизонталью угол 60 градусов, другой - угол 70 градусов. Предположим, что петух откладывает яйцо на гребень крыши. В какую сторону упадет яйцо - в сторону более пологого или более крутого ската?

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

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

5. Если вы любите грамматику, то наверняка ответите на этот интересный вопрос. Как правильно сказать: «Не вижу белый желток» или «Не вижу белого желтка»?

6. Поезд отправляется из Бостона в Нью-Йорк. Через час-другой поезд отправляется из Нью-Йорка в Бостон. Оба поезда едут с одной и той же скоростью. Какой из них в момент встречи будет находиться на меньшем расстоянии от Бостона?

7. У меня две монеты на общую сумму 15 копеек. Одна из них не пятак. Что это за монеты?

8. Некий мистер Смит ехал в машине со своим сыном Артуром. Их машина попала в катастрофу. Отец погиб на месте, а сын в тяжелом состоянии доставлен в ближайшую больницу. Взглянув на пострадавшего, дежурный хирург побледнел и сказал: «Я не могу оперировать его. Ведь это же мой сын Артур!» Как вы это объясните?

Ведущий. Пока жюри совещается, несколько слов о том, что думал о занятиях литературой Марк Твен.

«Литература, - очень опасное занятие, - сказал как-то Марк Твен. - Обратите внимание: Шекспир умер, Мильтон умер, Теннеси тоже скончался, да и мне что-тo нездоровится».

Жюри объявляет оценки за конкурс.

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

Конкурс 3. Истина или ложь. (Максимальная оценка за конкурс - 5 баллов.)

В конкурсе участвуют команды в полном составе.

Задание 1.

Определите форму приведенных высказываний (по 2 высказывания каждой команде).

Примеры высказываний:

1. «Если подозрение подтвердится... то наш план... развернется ровно в двенадцать часов ночи. Если же... не окажется ничего подозрительного, то план будет другой» (А. С. Грин).

2. «Если ты направился к цели и станешь дорогою останавливаться, чтобы швырять камнями во всякую лающую на тебя собаку, то никогда не дойдешь до цели» (Ф. М. Достоевский).

3. «Право собственности на самовольную постройку не может быть признано за указанными лицами, если сохранение постройки нарушает права и охраняемые законом интересы других лиц либо создает угрозу жизни и здоровью граждан» (из Гражданского кодекса РФ).

4. «Если у двух человек есть по одному яблоку и они обменяются ими, у каждого из них окажется по одному яблоку. Но если у двух человек есть по одной идее и они обменяются ими, у каждого будет по две идеи» (Б. Шоу).

5. Формализуйте предостережение, которое одна жительница древних Афин сделала своему сыну, собиравшемуся заняться политической деятельностью: "Если ты будешь говорить правду, то тебя возненавидят люди. Или, если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить правду или лгать. Значит, тебя возненавидят люди или возненавидят боги".

6. Формализуйте также ответ сына: "Если я буду говорить правду, то боги будут любить меня. Или, если я буду лгать, то люди будут любить меня. Но я должен говорить правду или лгать. Значит, меня будут любить боги или меня будут любить люди".

Задание 2.

С помощью простых суждений:

• А: «Я учусь в школе»;

• В: «Я люблю учиться»;

• С: «Я учусь в математическом классе»

составьте высказывания на естественном языке, соответствующие следующим формулам, и отрицания к ним:

I Примеры формул:

1. С→(А & В);

2. В→ (A v С);

3. (А &В) →С ;

4. (В→А) & (В→С)

Жюри объявляет оценки за конкурс.

Ведущий. «По одной капле воды... человек, умеющий мыслить логически, может сделать вывод о существовании Атлантического океана или Ниагарского водопада, даже если он не видел ни того, ни другого и никогда о них не слыхал... По ногтям человека, по его рукавам, обуви, сгибу брюк на коленях, по выражению лица и обшлагам рубашки - по таким мелочам нетрудно угадать его профессию. И можно не сомневаться, что все это вместе взятое, подскажет сведущему наблюдателю верные выводы» (А. Конан Дойл).

Таковы, наверное, и наши капитаны. А как они владеют логическими понятиями покажет

Конкурс 4. Конкурс капитанов. (Максимальная оценка за конкурс - 3 балла).

В конкурсе участвуют капитаны команд.

Задание конкурса.

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

Побеждает капитан, назвавший больше понятий. Жюри объявляет оценки за конкурс.

Перерыв

В перерыве готовятся отдельные места для проведения конкурса конструкторов и команды выбирают по два представителя для этого конкурса.

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

У нас, правда, не физики, но свои конструкторы тоже есть, а поэтому

Конкурс 5. Юные конструкторы. (Максимальная оценка за конкурс - б баллов).

В конкурсе принимают участие по 2 человека от команды (в следующих конкурсах они не участвуют).

Задание конкурса.

1) Составьте структурную формулу по заданной функциональной схеме и постройте для неё таблицу истинности:

2) Составьте структурную формулу по заданной функциональной схеме и постройте для ней таблицу истинности:

Задание: Составить логическую функцию и таблицу истинности для схемы:

Ведущий. «В самый солнцепек, вернувшись домой, говорится в одном из анекдотов о Насреддине, эфенди попросил жену: «Принеси-ка мне миску простокваши! Нет ничего полезней и приятней для желудка в такую жару!» Жена ответила: «Миску?! Да у нас даже ложки простокваши нет в доме!» Эфенди сказал: «Ну и ладно, ну и хорошо, что нет. Простокваша вредна человеку». «Странный ты человек, - сказала жена, - то у тебя простокваша полезна, то вредна. Какое же из твоих мнений правильно?» Эфенди ответил: «Если она есть дома, правильно первое, а если ее нет, правильно второе» (Сборник упражнений по логике).

А какие вы знаете законы логики и умеете ли распознать их нарушение?

Конкурс 6. Знаешь ли ты законы логики? (Максимальная оценка за конкурс - 6 баллов.)

В конкурсе участвуют команды в полном составе (за исключением тех игроков, которые выполняют задание конкурса юных конструкторов).

Задание конкурса.

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

На обдумывание дается не более 10 минут.

Примеры:

1. «Изо всей силы я ударил себя кулаком по правому глазу. Из глаза, конечно, так и посыпались искры, и порох в то же мгновение вспыхнул. Советую вам всякий раз, когда вы вздумаете развести огонь, добывать из правого глаза такие же искры» (Э. Распе «Приключения барона Мюнхгаузена»).

2. Шестилетний Андрюша моется в ванной.
   - Мама, можно я твоим шампунем вымою голову?
   - Можно.
   Взял флакон в руки и прочитал: «Для сухих волос».
   - Нет, мне нельзя, у меня ведь уже мокрые волосы!

3. «Сижу я, - пишет он, - в унылом моем уединении и всеминутно о том мыслю, какие законы к употреблению наиболее благопотребны суть. Есть законы мудрые, которые хотя человеческое счастье усвояют (таковы, например, законы о повсеместном для людей продовольствовании), но, по обстоятельствам, не всегда бывают полезны; есть законы немудрые, которые, ничьего счастья не устрояя, по обстоятельствам бывают однако ж благопотребны (примеров сему не привожу: сам знаешь!); и есть, наконец, законы средние, не очень мудрые, но и не весьма немудрые, такие, которые, не будучи ни полезными, ни бесполезными, бывают однако ж благопотребны в смысле наилучшего человеческой жизни наполнения.
   И поверишь ли, друг? Чем больше я размышляю, тем больше склоняюсь в пользу законов средних» (М. Е. Салтыков-Щедрин «История одного города»).

4. «Итак, вот весь налицо герой наш, каков он есть! Но потребуют, может быть, заключительного определения одною чертою: кто же он относительно качеств нравственных? Что он не герой, исполненный совершенств и добродетелей, это видно. Кто же он? Стало быть, подлец? Почему же подлец, зачем же быть так строгу к другим? Теперь у нас подлецов не бывает, есть люди благонамеренные, приятные, а таких, которые бы на всеобщий позор выставили свою физиогномию под публичную оплеуху, отыщется разве каких-нибудь два, три человека, да и те уже говорят о добродетели. Справедливее всего назвать его: хозяин, приобретатель» (Н. В. Гоголь «Мертвые души»).

5. «Как отличаются столовые от ресторанов, можно проследить на примере некоторых пищевых заведений. В одной ростовской «пищеточке» днем полы посыпают опилками и запирают гардероб. Получается столовая. Вечером опилки выметают и возле гардероба появляется бородатый швейцар. Получается ресторан. Отсюда можно сделать вывод, что ресторан есть заведение для публики «почище» (из фельетона).
   «Ты опять права, Соня. Это все вздор, почти одна болтовня! Видишь: ты ведь знаешь, что у матери моей почти ничего нет. Сестра получила воспитание случайно и осуждена таскаться в гувернантках. Все их надежды были на одного меня. Я учился, но содержать себя в университете не мог и на время принужден был выйти. Если бы даже и так тянулось, что лет через десять, двенадцать (если б обернулись хорошо обстоятельства) я все-таки мог надеяться стать каким-нибудь учителем или чиновником с тысячью рублями жалованья... (он говорил как будто заученное). А к тому времени мать высохла бы от забот и от горя, и мне все-таки не удалось бы успокоить ее, а сестра... ну, с сестрой могло бы еще и хуже случиться!.. Да и что за охота всю жизнь мимо всего проходить и от всего отвертываться, про мать забыть, а сестрину обиду, например, почтительно перенесть? Для чего? Для того ль, чтоб, их схоронив, новых нажить - жену да детей, и тоже потом без гроша да без куска оставить? Ну... ну, вот я и решил, завладев старухиными деньгами, употребить их на мои первые годы, не мучая мать, на обеспечение себя в университете, на первые шаги после университета, - и сделать все широко, радикально, так чтоб уж совершенно всю новую карьеру устроить и на новую, независимую дорогу стать... Ну... ну, вот и всё... Ну, разумеется, что я убил старуху, - это я худо сделал... Но и довольно!» (Ф. М. Достоевский «Преступление и наказание»).

Жюри объявляет оценки за конкурс.

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

Конкурс 7. Попробуй, угадай! (Максимальная оценка за конкурс - 5 баллов.)

В конкурсе участвуют команды в полном составе (за исключением тех игроков, которые выполняют задание конкурса юных конструкторов).

Задание конкурса.

Изобразить средствами мимики и жестов содержание понятий.

На обдумывание дается 1 минута.

По одному понятию команды предлагают друг другу, по одному понятию предлагает командам ведущий, а еще по одному понятию они представляют сами (домашнее задание). Всего каждой команде достается по 3 понятия. Жюри, болельщики, ведущий, команда противников пытаются угадать, какое понятие изобразила команда.

Примеры понятий для задания ведущим:

• Иван-царевич на сером волке;

• Колобок на носу у лисы.

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

- Вы не читали моего приказа? - спросил мэр сердито.
- Читал, - ответил нормандец. - Вот мой фонарь.
- Но в фонаре у вас ничего нет!
- В приказе об этом ничего не упоминается.
На утро появился приказ, обязывающий горожан вставить в фонарь свечу npи выходе ночью на улицу. Вечером мэр снова наткнулся на этого горожанина.
- Где фонарь?! - закричал мэр.
- Вот он, и в нем - свеча.
- Но она не зажжена.
- В приказе не сказано, что свечу надо зажигать.
И мэру пришлось издать еще один приказ» (А. А. Степанов «Общение лектора с аудиторией и законы логики»).

Жюри объявляет оценки за конкурс.

Ведущий. В приведенном примере горожанин строго следует изданным зам, а как вы думаете, правильны ли выводы в приведенных сюжетах?

Конкурс 8. Умозаключение или умозлоключение? (Максимальная оценка за конкурс - 4 балла.)

В конкурсе участвуют команды в полном составе (за исключением тех игроков которые выполняют задание конкурса юных конструкторов).

Задание конкурса.

Есть ли ошибки в данных умозаключениях, и если есть, то в чем? Каждой команде предлагается по 2 примера. На обдумывание дается не более 5 минут.

Примеры:

1. «Да, он умер от голода, так как медведи утоляют свой голод лишь тем, что сосут свою лапу. А. этот медведь никак не мог пососать своих лап и потому погиб голодной смертью» (Э. Распе «Приключения барона Мюнхгаузена»).

2. «В одном конце залы - широкая лестница... и по обеим ее сторонам высокие двери с прибитыми над ними оленьими головами - они ведут в бильярдную, библиотеку, большую, желтую залу и в гостиные. На втором этаже по меньшей мере двадцать спален,... Наша классная помещается на втором этаже, и из нее одна дверь ведет в мою спальню, а другая в спальню девиц. Затем идут апартаменты мистера Питта - мистера Кроули, как его здесь называют, - старшего сына, и покои мистера Родона Кроули - он офицер, как и еще некто, и находится сейчас в полку. Словом недостатка в помещении тут нет, могу тебя уверить! Мне кажется, что в этом доме можно было бы разместить все население Рассел-сквер, да и то осталось бы место!» (У. Теккерей «Ярмарка тщеславия»).

3. У больного Карпового улучшилось самочувствие сразу же после того, как его перевели из первого отделения во второе. Следовательно, причиной улучшения самочувствия больного Карпового является его перевод из одного отделения в другое.

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

Жюри объявляет оценки за конкурс.

Ведущий. Вот мы с вами и подошли к последнему конкурсу.

Конкурс 9. Помоги узнику! (Максимальная оценка за конкурс - 6 баллов.)

В конкурсе участвуют команды в полном составе (за исключением тех игроков, которые выполняют задание конкурса юных конструкторов).

Задание конкурса.

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

Примеры задач.

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

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

Первое испытание.

- А что, если в обеих комнатах сидят тигры? - спросил узник. - Что же мне тогда-то делать?
- Считай, не повезло, - ответил король.
- А если в обеих комнатах окажется по красавице? - поинтересовался узник.
- Считай, подфартило, - сказал король, - уж это ты и сам мог бы сообразить!
- Ну хорошо, а если в одной комнате принцесса, а в другую посадили тигра, чго тогда? - не успокаивался узник.
- Вот тут-то уже все зависит от тебя! Не так ли?
- Да откуда же мне знать, где кто? - сокрушенно вздохнул узник.
Тут король указал на таблички, прикрепленные к дверям каждой из комнат. На них было написано: «В этой комнате находится принцесса, а в другой комнате - тигр»; «В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр».
- А то, что здесь написано, правда? - спросил узник.
- На одной табличке - правда, - отвечал король, - на другой - нет.

А вы на месте узника какую бы дверь открыли? (Конечно, если предпочитаете принцессу тигру.)

Второе испытание.

Итак, первое испытание узник выдержал. Таблички на дверях сменили, соответственно были подобраны и обитатели комнат. На этот раз на табличках можно было прочитать следующее:

«По крайней мере в одной из этих комнат находится принцесса»; «Тигр сидит в другой комнате».

- Истинны ли утверждения на табличках? - спросил узник.
- Может, оба истинны, а может, оба ложны, - ответил ему король. Какую из комнат следует выбрать узнику?

Третье испытание.

Успешно справившись со вторым испытанием, узник перевел дух и увидел, что таблички на дверях заменили. Король объявил, что опять утверждения на обеих табличках одновременно либо истинны, либо ложны. Надписи же были вот какие!

«Либо в этой комнате сидит тигр, либо принцесса - в другой комнате»; «Принцесса в другой комнате».

Узник успешно разрешил последнюю задачу и вместе с принцессой отбыл за пределы этого царства (Р. М. Смаллиан «Принцесса или тигр?»).

Жюри объявляет оценки за конкурс. Подводится общий итог всех конкурсов.

Во время совещания команд (конкурсы 3, 4, 6, 7, 8, 9) задаются вопросы болельщикам. Ответы принимаются от первого поднявшего руку болельщика (за этим следит специальный член жюри).

Примерные вопросы болельщикам:

1. Отца некоего гражданина зовут Николай Петрович, а сына этого гражданина - Алексей Владимирович. Как зовут этого гражданина?

2. «Позавчера мне было двадцать лет, - сказал Андрей, - а в будущем году мне исполнится двадцать три года». Может ли такое быть на самом деле?

3. Может ли минутная стрелка пройти 6 минут за то же время, когда секундная пройдет только одну секунду?

4. Существует ли дробь, числитель которой меньше знаменателя, которая бы сохраняла это свойство, если ее перевернуть?

5. Иванова спросили, кто изображен на портрете, который висит на стене в ей комнате. Иванов ответил: «Отец изображенного на портрете лица приходится единственным сыном того, кто это говорит». Чей это портрет?

6. В одной семье семь братьев. Каждый из них имеет по одной сестре. Сколько детей в этой семье?

7. Верно ли утверждение, что куб имеет 5 или 6 граней?

8. Логик, оказавшись случайно в небольшом городке и желая хоть как-то убить время, решил подстричься. В городке имеются лишь два мастера (у каждого из них своя парикмахерская). Заглянув к одному мастеру, логик увидел, что в салоне грязно, сам мастер одет неряшливо, плохо выбрит и небрежно подстрижен. В салон другого мастера было идеально чисто, а владелец его был безукоризненно одет чисто выбрит и аккуратно подстрижен. Логик отправился стричься к первому парикмахеру. Почему? (М. Гарднер «Математические новеллы»)

9. Некий школьник предложил... гипотезу: он утверждал, что органы слуха у пауков находятся на ногах... Положив пойманного паука на стол, он крикнул: «Бегом!» Паук побежал. Мальчик еще раз повторил свой приказ. Паук снова побежал. Затем юный экспериментатор оторвал пауку ноги и, снова положив его на стол скомандовал: «Бегом!» Но на сей раз паук остался неподвижен. «Вот видите, заявил торжествующе мальчик, - стоило пауку оторвать ноги, как он сразу оглох (Э. Боно де. «Рождение новой жизни»).

Ответы на вопросы конкурсов

Конкурс 2.

1. Нет: если католик жив, то его жена не вдова, если он умер, то тем более не может жениться.

2. Яйцо никуда не упадет, так как петухи яйца не откладывают.

3. Результаты совпадают, так как полтора часа и есть 90 минут.

4. Уцелевших пассажиров нигде хоронить не надо.

5. Оба варианта неверны, так как желток - желтый.

6. В момент встречи поезда находятся на одинаковом расстоянии от Бостона.

7. 10 копеек и 5 копеек (не пятак - десятикопеечная монета).

8. Хирург - мать Артура.

Конкурс 3.

Задание 1.

1. • А: «Подозрение подтвердится»;

   • В: «Наш план... развернется ровно в двенадцать часов ночи». (А→В) {А→ В)

2. • А: «Ты направился к цели»;

   • В: «Ты станешь дорогою останавливаться»;

   • С: «Ты станешь швырять камнями во всякую лающую на тебя собаку»;

   • D: «Ты дойдешь до цели».

3. • А: «Сохранение постройки нарушает права других лиц»;

   • В: «Сохранение постройки нарушает охраняемые законом интересы других лиц»;

   • С: «Сохранение постройки создает угрозу жизни граждан»;

   • D: «Сохранение постройки создает угрозу здоровью граждан»;

   • Е: «Право собственности на самовольную постройку может быть признано за казанными лицами». ((А & В) v (С & D)) →Е

4. • А: «У двух человек есть по одному яблоку»;

   • В: «У двух человек есть по одной идее»;

   • С: «Люди обменяются имеющимися у них «предметами»;

   • D: «У двух человек есть по две идеи». ((А & С→А) & ((В &C) →D)

Задание 2.

1. Если я учусь в математическом классе, то я учусь в школе и люблю учиться.

2. Если я люблю учиться, то я учусь в школе или в математическом классе.

3. Если я не учусь в школе и не люблю учиться, то я не учусь в математическом классе.

4. Если я не люблю учиться, то учусь в школе, и если я не люблю учиться, то не учусь в математическом классе.

Конкурс 4.

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

Конкурс 5.

Конкурс 6.

1. Нарушается закон тождества (понятие «искра» используется в разных значениях).

2. Нарушается закон тождества (понятие «сухие волосы» используется в разных значениях).

3. Нарушается закон исключенного третьего (если есть законы «мудрые» и «не мудрые», то «третьего не дано»).

4. Иллюстрация к закону исключенного третьего. Нарушений нет (высказывания «персонаж - герой» и «персонаж - подлец» не являются противоположными по истинности, а следовательно, возможен и третий вариант: «персонаж - хозяин, приобретатель», и другие варианты).

5. Нарушается закон достаточных оснований (вывод недостаточно обоснован).

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

Конкурс 8.

1. Неверна предпосылка («Медведи утоляют свой голод лишь тем, что сосут свою лапу»), а значит, сделать вывод о причине смерти на основании приведенных данных нельзя.

2. Ошибок в умозаключении нет (возможен вариант для обсуждения, что насе­ление Рассел-сквера чересчур велико, а значит, есть и ошибка, но в выводе есть слова «Мне кажется, что...», и это сводит на нет возможность ошибки.

3. Есть широко распространенная ошибка в умозаключении: «после этого» не значит «вследствие этого».

4. Ошибок в умозаключении нет.

Конкурс 9.

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

Введем обозначения:

А: «В первой комнате - принцесса»;
В: «Во второй комнате - принцесса».

Тогда инверсии этих высказываний будут выглядеть так:

А : «В первой комнате - тигр»;
В: «Во второй комнате - тигр».

Первое испытание.

Запишем текст на табличках в виде формул:
Табличка на двери первой комнаты - А&В.
Табличка на двери второй комнаты - (А & В) (А &. В) (либо принцесса - в первой комнате, тигр - во второй, либо наоборот).
Так как на одной табличке - правда, а на другой - нет, то общее уравнение будет иметь вид:
(А & В) ((А & В) (А & В)) = 1;
((А &В) (А& В)) (А & В) = 1;
О (А & В) = 1;
(А&В) = 1;
А = 1, В = 1.

Итак, в первой комнате - тигр, во второй - принцесса.

Второе испытание.

Табличка на двери первой комнаты - Av В .
Табличка на двери второй комнаты - А .
Так как оба утверждения истинны или оба ложны, то общее уравнение имеет вид:
(A v В) А =1;
(A v В & A) v ((A v В) & А) = 1;
(А & B & A) v (А & В) = 1;
О v (А & В) = 1;
А = 1,B = 1.

Итак, в первой комнате - тигр, во второй - принцесса.

Третье испытание.

Табличка на двери первой комнаты - А В.
Табличка на двери второй комнаты - А.
Так как оба утверждения истинны или оба ложны, то общее уравнение имеет вид!
(А В) А = 1;
А В А = 1;
1 В = 1;
В = 1.

Итак, принцесса находится во второй комнате.

Вопросы болельщикам.

1. Владимир Николаевич.

2. Да. День рождения Андрея - 31 декабря, а говорит он это 1 января.

3. Нет.

4. Нет.

5. Внука Иванова.

6. Восемь.

7. Да.

8. Так как второго парикмахера стриг первый, то первый парикмахер - лучший.

9. Гипотеза неверна («после этого» не значит «вследствие этого»).

Для того чтобы сбросить информацию и подготовиться к приему новой, подается сигнал 1 на выход R (сброс), после чего триггер возвратится к исходному «нулевому» состоянию.

Литература

1. Кушниренко А.Г. и др. Информатика. - М.: Дрофа, 1998.

2. Кузнецов А.А. и др. Основы информатики. - М.: Дрофа, 1998.

3. Гейн А.Г., Сенокосов А.И. Информатика. - М.: Дрофа, 1998.

4. Сенокосов А.И., Гейн А.Г. Информатика, VIII-IX кл. школ с углубленным изучением информатики. - М.: Просвещение, 1995.

5. Шафрин Ю.А. Основы компьютерной технологии. Учебное пособие для VII-XI классов. - M.: ABF, 1996.

6. Ляхович В.Ф. Информатика для X-XI классов. - М.: Просвещение, 1997.

7. Лебедев Г.В., Кушниренко А.Г. 12 лекций по преподаванию курса информатики. - М.: Дрофа, 1998.

8. Кирюхин В.М., Лапунов А.В. Окулов С.М. Задачи по информатике. Международные олимпиады 1989-1996, для факультативов по информатике в старших классах. - М.: ABF, 1996.

9. Каймин В. А. и др. Основы информатики и вычислительной техники. - М.: Просвещение, 1989.

17. Бордовский Г.А. Информатика в понятиях и терминах. - М.: Просвещение, 1991.

10. Знакомьтесь: компьютер. Пер. с англ. - М.: Мир, 1989.

11. Кершан Б., Новембер А., Стоун Дж. Основы компьютерной грамотности. - М.: Мир, 1989.

12. Хасэгава Х. Мир компьютеров в вопросах и ответах. В 2-х томах. - М.: Мир, 1988.

13. Фролов Г.Д., Кузнецов Э.И. Элементы информатики. - М.: Высшая школа, 1989.

14. Власов В.К. и др. Элементы информатики. - М.: Наука, 1988.

15. Дудников Е.Е. Персональные компьютеры. - М.: МНИИПУ, 1988.

16. Чоговадзе Г.Г. Персональные компьютеры. - М.: Финансы и статистика, 1989.

17. Калбертсон Дж.Т. Математика и логика цифровых устройств. - М.: Просвещение, 1965.

18. Никольская И.Л. Математическая логика. - М.: Высшая школа, 1981.

19. Математическая энциклопедия. Т. 1. - М.: Советская энциклопедия, 1977.

Словарь основных понятий и терминов

Алгебра логики.

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

.

Логический тип.

Тип данных, представляемый значениями "истина" или "ложь" ("да" или "нет"). Иногда также называется булевским в честь английского математика XIX века Джорджа Буля.

Логический элемент (вентиль).

Часть электронной логической схемы, выполняющая элементарную логическую функцию.

Логическое высказывание.

Любoе пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Система счисления.

Совокупность приемов и правил, по которым записываются и читаются числа.

Электронная логическая схема, выполняющая суммирование двоичных чисел.

Таблица истинности.

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

Триггер.

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

70