Как заполнить карту карно из таблицы истинности? Ни где не могу найти подробное описание. Здесь описание задания задан 18 Мар '13 17:26 shaman888 |
Вот это описание подойдёт? Добавление. Я посмотрел описание из Вашего задания. Мне кажется, лучше всего на него ориентироваться, так как оно вполне ясное. Там строится вспомогательная таблица $%4\times4$%, строки и столбцы которой промаркированы переменными $%x_i$% или $%\bar{x_i}$%. Смотрим на каждую клетку; ей соответствует какой-то набор. Скажем, левой верхней клетке соответствует набор $%\bar{x_1}\bar{x_2}x_3x_4$%. Это значит, что надо в таблице истинности найти строку со значениями $%0011$% (наличие черты -- это $%0$%, отсутствие -- $%1$%). "Крестики" можно заполнять по своему усмотрению, вписывая туда хоть $%0$%, хоть $%1$%. При этом все единицы (включая дописанные от себя вместо "крестиков") надо "упаковать" в возможно меньшее число прямоугольников из единиц. В Вашем примере их получилось четыре. Они также соответствуют произведениям, в которые могут входить уже не все члены. Скажем, прямоугольник, образованный пересечением строк $%1,2$% и столбцов $%2,3$% (два "крестика" там приняли за единицу) соответствует набору $%x_1x_4$%: он именно на пересечении этих "зон" и находится. Теперь просто складываем все полученные произведения, или берём их дизъюнкцию (в данном случае это одно и то же). Осталось применить закон де Моргана: отрицание дизъюнкции есть конъюнкция отрицаний. После чего функция выражается через "И", "НЕ", и строится схема по образцу. отвечен 18 Мар '13 17:58 falcao Обновил вопрос. Чувствую себя мягко сказать глупо. На указанную Вами ссылку я заходил но я так и не понял как образуется карта. В описании задания (оно же и решение) мне не понятно как это произошло. Попытаюсь пока ещё почитать теорию.
(18 Мар '13 20:00)
shaman888
про само заполнение мне всё понятно, потому приму ответ. Но, начиная со слова "крестики" я не уверен до конца, что понял. Если существует какая нибудь конкретная готовая формула, или алгоритм нахождения наименьшего числа прямоугольников из единиц, буду рад узнать.
(21 Мар '13 15:22)
shaman888
По поводу "крестиков": это такой вариант задачи, который особых трудностей не вызывает, но предоставляет дополнительные возможности. На практике такая ситуация может возникать, если известно, что какие-то комбинации клавиш точно не встречаются, и тогда значение функции можно положить равным хоть нулю, хоть единице. Что касается алгоритма, то здесь таблица имеет совсем малый размер, и выбор прямоугольников осуществляется вручную (на уровне головоломок, игр и прочего). Это несложно. Алгоритмы имеет смысл применять при больших объёмах данных. Как правило, они основаны на полном переборе случаев.
(21 Мар '13 18:27)
falcao
Продолжение здесь - http://math.hashcode.ru/questions/14859/
(21 Мар '13 19:52)
shaman888
|