Как заполнить карту карно из таблицы истинности? Ни где не могу найти подробное описание.

Здесь описание задания

задан 18 Мар '13 17:26

изменен 18 Мар '13 19:56

10|600 символов нужно символов осталось
2

Вот это описание подойдёт?

Добавление. Я посмотрел описание из Вашего задания. Мне кажется, лучше всего на него ориентироваться, так как оно вполне ясное. Там строится вспомогательная таблица $%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

изменен 18 Мар '13 21:20

Обновил вопрос. Чувствую себя мягко сказать глупо. На указанную Вами ссылку я заходил но я так и не понял как образуется карта. В описании задания (оно же и решение) мне не понятно как это произошло. Попытаюсь пока ещё почитать теорию.

(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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×523

задан
18 Мар '13 17:26

показан
5251 раз

обновлен
22 Мар '13 18:58

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru