задачка про сломанный инвертор - Алгоритмы, методы, исходники / Форум
#logotable a {
text-decoration:none;
}
#logotable * {
border-style: none;
}
Добро пожаловать, гость
Запомнить?
Регистрация
Справка
Пользователи
Календарь
Поиск
Сообщения за день
Все разделы прочитаны
Форум
» Олимпиады
» Задачи
»
задачка про сломанный инвертор
Архив 2004
Архив 2007
Опции темы
Поиск в этой теме
Опции просмотра
#1
28.10.2006, 18:58
CD_Eater
Пользователь
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 92
задачка про сломанный инвертор
задачка не олимпиадная, но интересная
студент чипоруков регулярно прогуливал лекции по курсу "введение в цифровую технику".
на экзамене он получил билет про составление схем из цифровых логических элементов.
лектор вольтошоков, принимавший у него экзамен, был недоволен прогулами и решил "завалить" его, задав следующую задачку:
устройство под названием "трёхканальный инвертор" имеет 3 логических входа и 3 логических выхода, а внутри состоит из трёх логических элементов "не", так что каждый выход вычисляет логическое отрицание соответствующего входа.
такое устройство сломалось - сгорел один элемент "не".
однако из запасных деталей имеются только двухвходовые элементы "и" и "или" в большом количестве, и ни одного элемента "не".
можно ли починить трёхканальный инвертор ?
в качестве ответа лектор вольтошоков примет либо доказательство невозможности, либо пример схемы.
помогите студенту чипорукову
Последний раз редактировалось CD_Eater, 28.10.2006 в 19:01.
#2
28.10.2006, 23:54
Michael_Rybak
Новичок
Регистрация: 14.10.2006
Сообщений: 22
Офигенная задачка.
Решение получилось такое. У нас есть входы 1, 2, 3. Т.е. у нас есть, фактически, три функции: x, y и z. Функция x равна значению первого входа, y - второго, z - третьего.
С помощью двух отрицаний (элементов "не") строим функции g = not(xy or xz or yz) и f = not((x or y or z)g or xyz). Здесь произведение подразумевает операцию and.
Посмотрим на таблицу истинности полученного базиса:
Код:
x y z f g
0 0 0 0 0 0 1 1
0 0 1 0 0 1 0 1
0 1 0 0 1 0 0 1
0 1 1 0 1 1 1 0
1 0 0 1 0 0 0 1
1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 0
1 1 1 1 1 1 0 0
Видим, что для любой тройки входов, если рассмотреть только функции из базиса, значение которых на ней равно 1, то получится, что на любой другой тройке хотя бы одна из этих функций примет значение 0. К примеру, тройка входов (1, 0, 1). На ней функции x, z, и f принимают значения 1, y и g - 0. Смотрим во все остальные строки, игнорируя столбцы y и g:
Код:
x z f
0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 0 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 0 1
1 1 1 1 1 0
Видим, что все три функции равны 1 только для нашей тройки (1, 0, 1).
Другой пример - тройка (0, 0, 1). На ней единице равны только z и g. Выбрасываем остальные функции:
Код:
z g
0 0 0 0 1
0 0 1 1 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 0 0
1 1 1 1 0
Обе функции равны 1 только на тройке (0, 0, 1).
Точно так же - для любой другой тройки.
Из этого следует, что если взять какую-то тройку, и выполнить and всех тех функций (из x, y, z, f, g), которые принимают на этой тройке значение 1, то получится функция, которая на этой тройке равна 1, а на всех остальных - 0 (!). Конечно, не каждая пара функций f и g удовлетворила бы такому требованию таблички. Назовем такую пару f и g особенной (она, оказывается, единственна).
Например, как мы уже видели, для тройки (1, 0, 1) это будут функции x, z и f. Поэтому x and z and f = xzf - функция, равная 1 на тройке (1, 0, 1), и равная 0 на всех остальных тройках.
Запишем такую функцию для каждой тройки:
Код:
x y z f g функция
0 0 0 0 0 0 1 1 fg
0 0 1 0 0 1 0 1 zg
0 1 0 0 1 0 0 1 yg
0 1 1 0 1 1 1 0 yzf
1 0 0 1 0 0 0 1 xg
1 0 1 1 0 1 1 0 xzf
1 1 0 1 1 0 1 0 xyf
1 1 1 1 1 1 0 0 xyz
А теперь все просто. Чтобы получить на выходе not x, возьмем его нормальную дизъюнктивную форму, и построим ее с помощью полученных функций из предыдущей таблицы:
not x = (0, 0, 0) or (0, 0, 1) or (0, 1, 0) or (0, 1, 1) = fg or zg or yg or yzf
Аналагично:
not y = (0, 0, 0) or (0, 0, 1) or (1, 0, 0) or (1, 0, 1) = fg or zg or xg or xzf
not z = (0, 0, 0) or (0, 1, 0) or (1, 0, 0) or (1, 1, 0) = fg or yg or xg or xyf
Как по этому построить схему - понятно.
Возникает вопрос, как я получил особенную пару функций f и g. Я сначала понял, какими свойствами они должны обладать (точнее, какой должна оказаться объединенная таблица истинности функций x, y, z, f и g), и подобрал табличку руками, с помощью прямой цепочки рассуждений. Получив таблицы истинности f и g, я подобрал комбинацию функций x, y и z, которая дает not f, и другую комбинацию, дающую not g.
#3
29.10.2006, 11:07
CD_Eater
Пользователь
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 92
ну чтож, продолжим.
студент чипоруков успешно решил задачку, заданную лектором вольтошоковым. но недовольные прогулами экзаменаторы, да ещё со злобной фамилией, просто так не сдаются - они продолжают валить. лектор с ехидством продолжил:
теперь представьте, что вам принесли рабочий трёхканальный инвертор (все три отрицания исправны).
от вас требуется повысить канальность этого инвертора.
ситуация с наличием запчастей, разумеется, не изменилась.
например, с помощью полученного выше результата вы можете с помощью двух элементов "не" реализовать трёхканальный инвертор, и использовать третий элемент "не" для четвёртого канала.
но это будет результат на двоечку.
каждый дополнительный канал будет прибавлять один балл к вашей оценке (напр., если реализуете пятиканальный инвертор, вы получите в зачётку тройку, и так далее).
какую оценку получит студент чипоруков ?
#4
30.10.2006, 12:50
Michael_Rybak
Новичок
Регистрация: 14.10.2006
Сообщений: 22
Пятерку! Он получит пятерку!
Будем оперировать с немного видоизмененными таблицами истинностей.
В "стандартной" форме строки записываются в порядке увеличения двоичного числа, разрядами которого являются аргументы. Например, для 4:
Код:
a b c d
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
А мы запишем эту табличку в другом порядке: в порядке увеличения количества единиц в строке (а строки с одинаковым количеством единиц сортируем как угодно, например, лексикографически):
Код:
a b c d N1 = количество единиц
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 1 0 0 1
1 0 0 0 1
0 0 1 1 2
0 1 0 1 2
0 1 1 0 2
1 0 0 1 2
1 0 1 0 2
1 1 0 0 2
0 1 1 1 3
1 0 1 1 3
1 1 0 1 3
1 1 1 0 3
1 1 1 1 4
Получили 5 групп строк. В нулевой группе - строки без единиц, в первой - с одной единичкой, в четвертой - единственная строка, состоящая из одних единиц. Что нам дает такой порядок - увидим в самом конце.
Теперь добудем студенту пятерку
Для этого нам надо с помощью трех "не" получить отрицания семи входов.
Запишем таблицу истинности для 7 переменных, с указанным выше порядком строк:
Код:
a b c d e f g N1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
...
1 0 0 0 0 0 0 1
0 0 0 0 0 1 1 2
0 0 0 0 1 0 1 2
...
1 1 0 0 0 0 0 2
0 0 0 0 1 1 1 3
...
1 1 1 0 0 0 0 3
0 0 0 1 1 1 1 4
...
0 0 1 1 1 1 1 5
...
0 1 1 1 1 1 1 6
...
1 1 1 1 1 1 1 7
Получили восемь групп строк по признаку количества единиц. Теперь нас не будут интересовать отдельные строки, а будут интересовать уже эти группы строк (каждая из трех дополнительных функций, которые мы получим с помошью трех отрицаний, будет принимать одно и то же значение на всех строках одной группы).
Теперь воспользуемся описанным в прошлом посте приемом - построим "особенную" тройку функций x, y, z. Их может быть несколько, а нам понадобится следующий вариант:
Код:
N1 x y z
0 1 1 1
1 1 1 0
2 1 0 1
3 1 0 0
4 0 1 1
5 0 1 0
6 0 0 1
7 0 0 0
Т.е. мы просто записали трехзначные двоичные числа в порядке убывания.
Эта табличка означает, например, что для любой семерки аргументов, в которой значение true принимает ровно 4 из них, функции x, y и z равны, соответственно, 0, 1 и 1.
Убедимся, что тройка функций (x, y, z) является особенной.
Вспомним введенное определение: особенной является тройка, дополняющая таблицу истинности имеющихся функций до таблицы, обладащей таким свойством: если рассмотреть любой набор аргументов, и выбросить из таблицы те функции, которые на этом наборе равны 0, то оставшиеся функции будут *одновременно* равны 1 только на этом, рассматриваемом наборе. Это означает, что любой элементарный дизъюнкт можно получить пересечением соответствующих функций.
Обратимся теперь к построенной нами табличке. Легко убедится, что описанное свойство выполняется. Рассмотрим некоторую семерку, в которой, к примеру, ровно 5 единиц.
Все строки среди тех, в которых тоже ровно 5 единиц, и меньше, обязательно обращают в 0 одну из функций a, b, .., g, которые равны 5 на нашей тройке (это следует из способа сортировки строк, хотя выполнялось бы и при обычном порядке строк таблицы истинности; это не важно).
С другой стороны, все строки среди тех, в которых больше 5 единиц, обязательно обращают в 0 одну из функций x, y, z (это следует из их таблицы истинности).
Все, что нам осталось - получить функции x, y, z с помощью трех отрицаний.
В прошлой задаче я это делал интуитивным подбором, здесь же выработал систему. Воспользуемся, наконец, выбранным порядком строк в таблице.
С помощью комбинирования and'ов и or'ов мы легко можем получить пороговую функцию, т.е. функцию, равную true тогда и только тогда, когда, среди всех аргументов, true равны не меньше некоторого заданного (ненулевого) количества.
Действительно:
Функция F1, равная true, когда хотя бы один из аргументов равен true - это a or b or c or d or e or f or g
Функция F2, равная true, когда хотя бы два из аргументов равны true - это ab or ac or ad or ... or fg
Функция F3, равная true, когда хотя бы три из аргументов равны true - это abc or abd or ... or efg
И так далее, до F7.
А таблица истинности пороговой функции с выбранным нами порядком строк будет выглядеть так: все строки, до некоторой, дают 0, а все нижеследующие - 1!
Теперь посмотрим на функцию x. Сразу видим, что она - не что иное, как not F4.
А y - это not (F6 or (x and F2))
A z - это not (F7 or (y and F5) or (x and F3) or (x and y and F1))
Вот и всё.
Фактически, получив x, мы получили возможность выбирать половинку. Получив y - четвертинку. Так, z более наглядно можно записать вот так:
Код:
not ((!x and !y and F7) or
(!x and y and F5) or
( x and !y and F3) or
( x and y and F1))
Эту систему легко теперь продолжить. Например, с помощью четырех элементов "не" можно построить 15-канальный инвертор, с помощью пяти - 31-канальный.
А доказать, что больше - нельзя, тоже не очень сложно. Жду, когда студента Чипорукова попросят доказать, что шестерку он получить не мог
Спасибо за задачу, получил море удовольствия.
#5
30.10.2006, 13:26
Wasya
Новичок
Регистрация: 22.09.2006
Адрес: Екатеринбург
Сообщений: 22
Вы бы уже опубликовали свои результаты на исходниках. А то там люди совсем в другую сторону пошли.
Michael_Rybak ты гений!
#6
30.10.2006, 13:42
Michael_Rybak
Новичок
Регистрация: 14.10.2006
Сообщений: 22
Запостил ссылку
Головоломки перестал читать на исходниках, т.к. редко новое появляется. Буду опять читать
«
задача I с контеста станкевича 3 октября
|
разрез минимального среднего веса
»
Опции темы
Поиск в этой теме
Версия для печати
Отправить по электронной почте
Поиск в этой теме:
Расширенный поиск
Опции просмотра
Линейный вид
Комбинированный вид
Древовидный вид
Похожие темы
Тема
Автор
Раздел
Ответов
Последнее сообщение
задачка коммивояжера
il33
Реализация, исходники, языки
5
31.03.2008 13:28
Задачка на строки
NeiroN
Задачи
2
31.05.2007 03:38
задачка
незарегистрированный
Задачи
4
04.03.2007 18:12
задачка с юсаки Fence Rails
necro
Задачи
0
30.12.2006 03:28
задачка про переключатели
@Alex@
Задачи
12
27.12.2006 21:31
AlgoList -
Архив -
Вверх
shell
.
ppg
fifa 2006
pki
asus p505
li-da
-
contiwinterviking
dhl
gislaved
kyiv apartaments rent
telecomfm gsmphone
rvg
dimplex model lee rc
r-600
knauf
asus p505
master
mobil pegasus
-95
hansa
407
asko
asus p505
de luxe 5040.11
contiwinterviking
thuraya sg 2520
fargo
1000
.
stihl
4
407
8800 gold
264-27-00
sky link
trinity hi-fi
-
-4361
li-da