Карта Карно, булевы функции

[rar]

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

$$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$$

.
Вопрос. Что это получилось? Что за ДНФ?
Как мне теперь найти, то что надо из условия?

[grgdvo]

Некоторая информация по картам Карно есть в Дж. Андерсон "Дискретная математика и комбинаторика". Ищи в сети. Вроде бы я ее видел где-то в электронном виде.

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

$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. Сорри за ошибки в техе. Поправил

[rar]

Спасибо конечно. Но я еще полазил-почитал и переделал немного.

[Xaositect]

rar
Ваше первое покрытие соответствует сокращенной ДНФ (сокр. ДНФ содержит все максимальные грани функции)

[rar]

Xaositect в сообщении #215205 писал(а):

rar
Ваше первое покрытие соответствует сокращенной ДНФ (сокр. ДНФ содержит все максимальные грани функции)

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

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

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

[Xaositect]

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

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

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

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

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

[rar]

Xaositect в сообщении #215226 писал(а):

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

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

[Xaositect]

Ну, есть такая теорема, что среди тупиковых ДНФ содержится минимальная.
То есть можно построить все тупиковые ДНФ и выбрать из них минимальную.

[rar]

Xaositect в сообщении #215226 писал(а):

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

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

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

[Xaositect]

Точки - клетки
Грани - прямоугольники

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

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

[rar]

А ребру что соответствует?

[Xaositect]

Прямоугольник $2\times 1$(или $1\times 2$)

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

[rar]

Xaositect в сообщении #215234 писал(а):

Ну, есть такая теорема, что среди тупиковых ДНФ содержится минимальная.
То есть можно построить все тупиковые ДНФ и выбрать из них минимальную.

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

[Xaositect]

Видимо то же самое
На конечном разбиении не видно, что Вы из чего-то выбирали.

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

[rar]

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

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

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


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