2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Карта Карно, булевы функции
Сообщение19.05.2009, 03:05 
С помощью карты Карно найти сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции $$f$$ заданной вектором значений.


Вот функция $$\tilde f=0010010111100101$$.

Нарисовал карту Карно (синим цветом выделил истинные значения):
Изображение

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

Так. Полазил, почитал. Пришел к выводу, что скорее всего будет правильным следующий вариант (предыдущий тоже, видимо, правильный):
Изображение
Получаются элементарные конъюнкции:
$$K_1=x_2x_4$$
$$K_2=x_1\bar x_2\bar x_3$$
$$K_3=\bar x_2x_3\bar x_4$$

Собираем вместе $$f(x_1,x_2,x_3,x_4)=x_2x_4\vee x_1\bar x_2\bar x_3\vee \bar x_2x_3\bar x_4$$.
Вопрос. Что это получилось? Что за ДНФ?
Как мне теперь найти, то что надо из условия?

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 05:14 
Некоторая информация по картам Карно есть в Дж. Андерсон "Дискретная математика и комбинаторика". Ищи в сети. Вроде бы я ее видел где-то в электронном виде.

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

$k_1 \vee k_2 \vee k_3 \vee k_4 \vee k_5$

где

$k_1 = X_2 \wedge X_4$
$k_2 = X_1 \wedge \bar{X_3} \wedge \bar{X_4}$
$k_3 = X_1 \wedge \bar{X_2} \wedge \bar{X_3}$
$k_4 = \bar{X_2} \wedge X_3 \wedge \bar{X_4}$
$k_5 = X_1 \wedge \bar{X_2} \wedge \bar{X_4}$

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

$k_2 = (X_1 \wedge \bar{X_2} \wedge \bar{X_3} \wedge X_4) \vee (X_1 \wedge X_2 \wedge \bar{X_3} \wedge X_4) =
(X_1 \wedge \bar{X_3} \wedge X_4) \vee (X_2 \wedge \bar{X_2}) = X_1 \wedge \bar{X_3} \wedge X_4$

Вроде бы нигде не ошибся. :)

p.s. Сорри за ошибки в техе. Поправил

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 08:14 
Спасибо конечно. Но я еще полазил-почитал и переделал немного.

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:12 
Аватара пользователя
rar
Ваше первое покрытие соответствует сокращенной ДНФ (сокр. ДНФ содержит все максимальные грани функции)

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:43 
Xaositect в сообщении #215205 писал(а):
rar
Ваше первое покрытие соответствует сокращенной ДНФ (сокр. ДНФ содержит все максимальные грани функции)


А второе покрытие минимальной ДНФ?
Сколько их возможно в моем случае?

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

Да. И помогите ядро(а) найти.

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:47 
Аватара пользователя
карты Карно надо покрывать максимальными(по включению) прямоугольниками размера $2^i\times 2^j$
Так что если какая-то грань лежит целиком внутри квадрата, то ее рисовать не нужно.

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

-- Вт май 19, 2009 13:50:34 --

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

У Вас тут 4 ядровых точки и две ядровых грани

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:51 
Xaositect в сообщении #215226 писал(а):
Второе покрытие соответствует минимальной ДНФ, но, вообще говоря, это неплохо бы доказать.

А как доказать? Я честно говоря, даже не знаю.

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:53 
Аватара пользователя
Ну, есть такая теорема, что среди тупиковых ДНФ содержится минимальная.
То есть можно построить все тупиковые ДНФ и выбрать из них минимальную.

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:54 
Xaositect в сообщении #215226 писал(а):
Ядровая точка - точка, покрываемая ровно одной гранью
Ядровая грань - грань, содержащая ядровую точку
Ядро - совокупность всех ядровых граней
(Определения из книги Ложкина по основам кибернетики)

У Вас тут 4 ядровых точки и две ядровых грани

А можно это на язык карты Карно перевести, а не на языке булевого куба.

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 13:55 
Аватара пользователя
Точки - клетки
Грани - прямоугольники

-- Вт май 19, 2009 14:00:32 --

Вообще, карта Карно - это и есть четырехмерный булев куб, по хитрому развернутый на плоскости

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 14:06 
А ребру что соответствует?

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 14:10 
Аватара пользователя
Прямоугольник $2\times 1$(или $1\times 2$)

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

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 14:11 
Xaositect в сообщении #215234 писал(а):
Ну, есть такая теорема, что среди тупиковых ДНФ содержится минимальная.
То есть можно построить все тупиковые ДНФ и выбрать из них минимальную.


А разве я не тоже самое сделал, только графическим методом?

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 14:12 
Аватара пользователя
Видимо то же самое :)
На конечном разбиении не видно, что Вы из чего-то выбирали.

Человек вообще очень хорошо находит минимальную ДНФ "на глаз", пока размерность меньше 6-7

 
 
 
 Re: Карта Карно (дискретная математика)
Сообщение19.05.2009, 14:16 
Все-таки с ядровыми я не совсем разобрался. Можете объяснить, что такое ядровые и каков их смысл. Я этого не понимаю, пока. И как на карте Карно их определять, по какому принципу.

-- Вт май 19, 2009 15:22:32 --

И еще. Скажите. Вот такой вариант возможен:
Изображение

Если да - объясните почему. Если нет, тоже - почему?

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group