Табличный методЗадача 87. Перед началом турнира по шахматам болельщики высказали следующие предположения по поводу результатов: А) Максим победит, Борис — второй; Б) Борис — третий, Коля — первый; В) Максим — последний, а первый — Дима. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Как распределились призовые места?
Запишем высказывания трех болельщиков в форме таблицы (заголовок строки обозначает место в турнирной таблице). Будем считать, что каждое место занял ровно один участник. Начнем “раскручивать” эту таблицу с той строчки, где больше всего информации, в данном случае — с первой. Предположим, что Максим действительно занял первое место, как и сказал болельщик “A”. В этом случае “В” ошибся, поставив на первое место Диму. Тогда получается, что второй прогноз болельщика “В” верен, и Максим — последний.
Так как мы предполагали, что Максим занял первое место, получается противоречие. Следовательно, первый прогноз “А” не сбылся. Но тогда должен быть верен его второй прогноз, и Борис занял второе место. При этом он не мог занять еще и третье место, поэтому первый прогноз болельщика “Б” неверный, а верен его второй прогноз: Коля — первый. В этом случае Дима не может быть первым, поэтому верен первый прогноз “В”: Максим — последний. Диме осталось единственное свободное третье место. В результате места распределились так: I — Коля, II — Борис, III — Дима и IV — Максим. Задача 88. На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Василий, Семен, Геннадий и Иван. Известно, что все они имеют разные профессии: скрипач, столяр, охотник и врач. Известно, что (1) Столяр живет правее охотника. (2) Врач живет левее охотника. (3) Скрипач живет с краю. (4) Скрипач живет рядом с врачом. (5) Семен не скрипач и не живет рядом со скрипачом. (6) Иван живет рядом с охотником. (7) Василий живет правее врача. (8) Василий живет через дом от Ивана. Определите, кто где живет. Из условий (1) и (2) следует, что охотник живет не с краю, потому что справа от него живет столяр, а слева — врач. Скрипач по условию (3) живет с краю, он может жить как слева, так и справа от остальных: скрипач? врач охотник столяр скрипач? Согласно условию (4), скрипач живет рядом с врачом, поэтому он занимает крайний дом слева:
Профессии жильцов определили, остается разобраться с именами. Из условия (5) “ Семен не скрипач и не живет рядом со скрипачом” следует, что Семен — охотник или столяр:
Из условия (6) “ Иван живет рядом с охотником” следует, что он — врач или столяр:
Из условия (7) “Василий живет правее врача ” определяем, что Василий — охотник или столяр:
Согласно условию (8), “Василий живет через дом от Ивана”, поэтому Иван — врач, а Василий — столяр:
Тогда сразу получается, что Семен — охотник, а Геннадий должен занять оставшееся свободное место, он — скрипач:
Задача 89. Шесть приятелей, Саша, Петя, Витя, Дима, Миша и Кирилл, встретившись через 10 лет после окончания школы, выяснили, что двое из них живут в Москве, двое — в Санкт-Петербурге, а двое — в Перми. Известно, что (1) Витя ездит в гости к родственникам в Москву и Санкт-Петербург. (2) Петя старше Саши. (3) Дима и Миша летом были в Перми в командировке. (4) Кирилл и Саша закончили университет в Санкт-Петербурге и уехали в другие города. (5) Самый молодой из них живет в Москве. (6) Кирилл редко приезжает в Москву. (7) Витя и Дима часто бывают в Санкт-Петербурге по работе. Определите, кто где живет. Составим таблицу, где каждая строка соответствует городу, а столбец — человеку:
Единица в таблице будет обозначать, что человек живет в данном городе, а ноль — что точно не живет. По условию в каждом городе живут ровно 2 человека, каждый живет только в одном городе. Поэтому в каждой строке должно быть две единицы, а в каждом столбце — одна. Из условия (1) следует, что Витя живет в Перми:
Из (2) и (5) находим, что Петя живет не в Москве. Кроме того, как следует из (6), Кирилл — тоже не москвич. Москва Санкт-Петербург 0 Пермь 1
Согласно (3), Дима и Миша живут не в Перми:
Из условия (4) делаем вывод, что Кирилл и Саша живут не в Санкт-Петербурге, отсюда сразу следует, что Кирилл живет в Перми. Двух пермяков мы уже определили, поэтому Саша и Петя живут не в Перми:
Далее находим, что Саша — москвич, а Петя живет в Санкт-Петербурге.
По условию (7) Витя и Дима — не петербуржцы, поэтому в Петербурге живет Миша, а Дима — в Москве:
Таким образом, Саша и Дима живут в Москве, Петя и Миша — в Санкт-Петербурге, а Витя и Кирилл — в Перми.
Д/З: 90. Три школьника, Миша, Коля и Сергей, остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее: Миша: “Я не бил окно, и Коля тоже…” Коля: “Миша не разбивал окно, это Сергей разбил футбольным мячом! ” Сергей: “Я не делал этого, стекло разбил Миша”. Выяснилось, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба раза соврал. Кто разбил стекло в классе? (Ответ: Миша) 91. В финал соревнований по настольному теннису вышли Наташа, Маша, Люда и Рита. Болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Как распределились места? (Ответ: I — Наташа, II — Люда, III — Рита, IV — Маша) 92. На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Алексей, Егор, Виктор и Михаил. Известно, что все они имеют разные профессии: рыбак, пчеловод, фермер и ветеринар. Известно, что (1) Фермер живет правее пчеловода. (2) Рыбак живет правее фермера. (3) Ветеринар живет рядом с рыбаком. (4) Рыбак живет через дом от пчеловода. (5) Алексей живет правее фермера. (6) Виктор — не пчеловод. (7) Егор живет рядом с рыбаком. (8) Виктор живет правее Алексея. Определите, кто где живет. (Ответ: пчеловод Михаил, фермер Егор, рыбак Алексей, ветеринар Виктор) 93. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У них разные профессии и они живут в разных городах: одна — в Ростове, вторая — в Париже и третья — в Москве. Известно, что (1) Даша живет не в Париже, а Лариса — не в Ростове. (2) Парижанка — не актриса. (3) В Ростове живет певица. (4) Лариса — не балерина. Определите, где живет каждая из дочерей и чем занимается. (Ответ: Даша — певица, Ростов; Анфиса — балерина, Париж; Лариса — актриса, Москва) 94. В состав экспедиции входят Михаил, Сергей и Виктор. На обсуждении распределения обязанностей с руководителем проекта были высказаны предположения, что командиром будет назначен Михаил, Сергей не будет механиком, а Виктор будет утвержден радистом, но командиром не будет. Позже выяснилось, что только одно из этих четырех утверждений оказалось верным. Как распределились должности? (Ответ: Виктор — командир, Михаил — механик, Сергей — радист) 95. В ходе заседания суда выяснилось, что: (1) Если Аськин не виновен или Баськин виновен, то виновен Сенькин. (2) Если Аськин не виновен, то Сенькин не виновен. Виновен ли Аськин? (Ответ: виновен) 96. Аськин, Баськин и Васькин стали свидетелями ограбления банка. Во время расследования Аськин сказал, что взломщики приехали на синей “Тойоте”. Баськин считает, что это был красный “BMW”, а Васькин утверждает, что это был “Форд-Фокус”, но не синий. Выяснилось, что каждый из них назвал неправильно либо марку, либо цвет машины. На каком автомобиле приехали преступники? (Ответ: красная “Тойота”)
9. Построение логических схем. Существуют базовые логические элементы, реализующие основные логические операции:
Их схемы приведены на рисунке. Устройства компьютера строятся на основе базовых логических элементов.
Упражнения. 97. По заданной логической функции
98. По схеме определить логическую функцию, которую она реализует.
99. Логическая схема имеет два входа x и y. Следует определить логические функции F1(x, y) и F2(x, y), которые реализуются на ее двух выходах. Функция F1(x, y)= x & y Функция F2(x, y)=
10. Триггер.
Слово триггер происходит от английского слова trigger — “защелка” или спусковой крючок (В английском языке триггер называется flip-flop.). Так называют электронную схему, которая может находиться только в двух состояниях (их можно обозначить как 0 и 1) и способна почти мгновенно переходить из одного состояния в другое. Триггер изобрели независимо друг от друга М.А. Бонч-Бруевич и англичане У.Икклз и Ф.Джордан в 1918 году. В компьютерах триггер используют для запоминания одного бита информации. Соответственно, для того чтобы запомнить 1 байт информации, требуется 8 триггеров, а для хранения 1 Кб — 8 · 1024 = 8192 триггера. Триггеры бывают разных типов. Самый распространенный — это RS-триггер. Он имеет два входа, которые обозначаются как S (англ. set — установить) и R (англ. reset — сброс), и два выхода — Q и Q, причем выходной сигнал Q является логическим отрицанием сигнала Q (если Q = 1, то Q = 0, и наоборот). RS-триггер можно построить на двух элементах “И–НЕ” или на двух элементах “ИЛИ–НЕ”. На следующем рисунке показаны условное обозначение RS-триггера, внутреннее устройство триггера на элементах “ИЛИ–НЕ” и его таблица истинности.
Триггер использует так называемые обратные связи — сигналы с выходов схем “ИЛИ–НЕ” поступают на вход соседней схемы. Именно это позволяет хранить информацию. Рассмотрим таблицу истинности триггера. Начнем с варианта, когда S = 0 и R = 1. Элемент “ИЛИ–НЕ” в нижней части схемы можно заменить на последовательное соединение элементов “ИЛИ” и “НЕ”. Тогда, независимо от второго входа, на выходе “ИЛИ” будет 1, а на выходе “НЕ” — ноль. Это значит, что Q = 0.
Аналогично легко показать, что на выходе Q тоже остается его предыдущее значение. Это режим хранения бита. Для случая S = 1 и R = 1 мы увидим, что оба выхода становятся равны нулю — в этом нет смысла, поэтому такой вариант запрещен. Для хранения многоразрядных данных триггеры объединяются в единый блок, который называется регистром. Регистры (от 8 до 64 бит) используются во всех процессорах для временного хранения промежуточных результатов. Над регистром, как над единым целым, можно производить ряд стандартных операций: сбрасывать (обнулять), заносить в него код и т.д. Часто регистры способны не просто хранить информацию, но и обрабатывать ее. Например, существуют регистры-счетчики, которые подсчитывают количество импульсов, поступающих на вход. Триггеры применяются также в микросхемах быстродействующей оперативной памяти.
11. Сумматоры Как следует из названия, сумматор предназначен для сложения (суммирования) двоичных чисел. Сначала рассмотрим более простой элемент, который называют полусумматором. Он выполняет сложение двух битов с учетом того, что в результате может получиться двухразрядное число (с переносом в следующий разряд).
Обозначим через A и B входы полусумматора, а через P и S — выходы (перенос в следующий разряд и бит, остаю- щийся в текущем разряде). Таблица истинности этого устройства показана на рисунке. Легко увидеть, что столбец P — это результат операции “И”, а столбец S — результат “исключающего ИЛИ”: P = A × B, S =
Формулу для S можно также записать в таком виде S = что позволяет построить полусумматор, используя всего 4 простейших элемента:
Слева показано условное обозначение полусумматора, греческая буква Σ здесь (и в математике) обозначает сумму.
Логические функции для выходов сумматора вы можете найти самостоятельно. Сумматор можно построить с помощью двух полусумматоров и одного элемента “ИЛИ”:
Сначала складываются биты B и C, а затем к результату добавляется бит A. Перенос на выходе сумматора появляется тогда, когда любое из двух промежуточных сложений дает перенос. Для сложения многоразрядных чисел сумматоры объединяют в цепочку. При этом выход P одного сумматора (перенос в следующий разряд) соединяется с входом C следующего. На рисунке показано, как складываются два трехразрядных разрядных числа: X = 1102 и Y = 0112. Сумма Z = 10012 состоит из четырех бит, поэтому на выходе последнего сумматора бит переноса будет равен 1.
Сложение начинается с самого младшего разряда. На вход первого сумматора подаются младшие биты исходных чисел, x1 и y1 (см. рисунок), а на третий вход — ноль (нет переноса из предыдущего разряда). Выход S первого сумматора — это младший бит результата, z1, а его выход P (перенос) передается на вход второго сумматора и т.д. Выход P последнего из сумматоров представляет собой дополнительный разряд суммы, то есть z4. Сумматор играет важную роль не только при сложении чисел, но и при выполнении других арифметических действий. Фактически является основой арифметического устройства современного компьютера.
Упражнения 100. Используя логические элементы, постройте схемы, соответствующие логическим выражениям
101. Соревнования по поднятию тяжестей судит бригада из трех человек, один из них старший. Лампочка “Вес взят” должна зажигаться, если проголосовали по крайней мере два судьи, причем один из них — старший. Предложите логическую схему, которая решала бы эту задачу. 102. В двухэтажном коттедже есть два выключателя, которые управляют освещением лестницы, один из них — на первом этаже, а второй — на втором. Каждый выключатель имеет два состояния, при нажатии на кнопку состояние изменяется. В исходный момент оба выключателя выключены. Когда человек заходит в неосвещенное здание, он нажимает кнопку выключателя на первом этаже, при этом должна загореться лампочка, освещающая всю лестницу. Поднявшись на второй этаж, он нажимает на кнопку второго выключателя, и лампочка должна погаснуть. Когда следом идет другой человек, он действует так же (хотя оба выключателя находятся в другом положении). Предложите логическую схему, которая решала бы эту задачу. 103. В самолете есть три бака с горючим. Бортовой компьютер получает сигналы от датчиков уровня в каждом баке: если горючего в баке достаточно, то сигнал равен 0, если горючее кончилось—1. Когда горючее заканчивается по крайней мере в двух баках, должна загореться лампочка “Тревога”. Предложите логическую схему, которая решала бы эту задачу. 104. В парламенте некоторой страны выбирают спикера из трех кандидатов. Каждый парламентарий должен нажать одну и только одну из трех кнопок. Если он проголосовал правильно (нажал ровно одну кнопку), на пульте должна загореться зеленая лампочка. Предложите логическую схему, которая решала бы эту задачу. 105. Постройте RS-триггер на элементах “И–НЕ” и составьте его таблицу истинности.
|
построить логическую схему. В выражении использованы две конъюнкции одна дизъюнкция и две инверсии, всего потребуется 5 логических элементов. Построение можно начинать с последней операции – дизъюнкции. На этот элемент подаются сигналы с двух конъюнкторов, на которые в свою очередь один из сигналов проходит через инвертор.
= 
= 
= (A + B) 
,
Полный одноразрядный сумматор учитывает также и третий бит — перенос из предыдущего разряда C. Сумматор имеет три входа и два выхода. Таблица истинности и обозначение сумматора показаны на рисунках.
