С помощью карты Карно найти сокращенную ДНФ

[Karabas]

С помощью карты Карно найти сокращенную ДНФ.

$$ \begin{tabular}{|l|c|c|c|c|} \hline $ $ & 00 & 01 & 11 & 10\\\hline 00 & 0 & 0 & 1 & 1 \\\hline 01 & 1 & 1 & 1 & 0 \\\hline 11 & 1 & 1 & 1 & 0 \\\hline 10 & 1 & 1 & 1 & 1 \\\hline \end{tabular} $$

Как написано в учебнике, я выделил максимально возможные блоки из единиц.
Получилось,что совершенная ДНФ :

$$f(x_1,x_2,x_3,x_4)=x_2\bar x_3\vee x_2 x_4\vee x_1\bar x_3\vee x_1x_4\vee x_1\bar x_2\vee x_3x_4\vee\bar x_2x_3$$

Однако, ответ задачника

$$f(x_1,x_2,x_3,x_4)=x_2\bar x_3\vee x_1\bar x_3\vee x_1x_4\vee x_1\bar x_2\vee x_3x_4\vee\bar x_2x_3$$

И я не могу понять где ошибся.Прошу помощи.

[svv]

Вы нигде не ошиблись. Просто блок, соответствующий $x_2 x_4$, уже покрывается блоками $x_2\bar x_3$ и $x_3 x_4$. Так как мы стремимся к минимальности, его в таком случае надо выбросить (вернее, просто не выделять на карте те блоки, все клетки которых уже отошли к другим блокам). Можно показать, что
$x_2 x_4 \to x_2\bar x_3 \lor x_3 x_4$,
поэтому добавление $x_2 x_4$ с помощью "или" к уже имеющимся "слагаемым" ничего не меняет. Собственно, покрывание этого блока на карте Карно двумя другими и есть такое доказательство.

[Karabas]

А почему тогда нельзя убрать блок $x_1 x_4$ ?

[svv]

Можно. Этого не заметили ни составители задач, ни я.
Чтобы у Вас не было сомнений, подробно излагаю ход рассуждения.

Имеется претендент на правильный ответ -- Выражение (с большой буквы, чтобы было ясно: именно следующее выражение):

$$f(x_1,x_2,x_3,x_4)=x_2\bar x_3\vee x_1\bar x_3\vee x_1\bar x_2 \vee x_3x_4 \vee\bar x_2x_3$$

Покажем, что добавление ($\vee$) к нему $x_1x_4$ не изменит его значения ни при каких значениях переменных.

От противного. Пусть в случае каких-то конкретных значений $x_1, x_2, x_3, x_4$ значение Выражения все-таки изменится после добавления к нему $x_1x_4$ . Это могло бы случиться двумя способами:
а) значение Выражения было равно $1$, а с $x_1x_4$ стало $0$;
б) значение Выражения было равно $0$, а с $x_1x_4$ стало $1$.

Вариант а) невозможен, так как $1 \vee x_1 x_4=1$, независимо от $x_1 x_4$.
Вариант б) по свойствам "или" может иметь место лишь при $x_1 x_4=1$, что по свойствам "и" означает $x_1=1$ и $x_4=1$. Сгруппируем вместе "слагаемые" $x_1\bar x_3$ и $x_3 x_4$, уже входящие в Выражение:
$x_1\bar x_3 \vee x_3 x_4 = 1 \bar x_3 \vee {x_3}{1} = \bar x_3 \vee x_3 = 1$
Но тогда и Выражение равно $1$, что противоречит предположению б).

Итак, не существует случаев, при которых добавление к Выражению $x_1 x_4$ изменяло бы его значение.

P.S. И даже так правильно:

$$f(x_1,x_2,x_3,x_4)=x_2\bar x_3 \vee x_1\bar x_2 \vee x_3 x_4 \vee \bar x_2 x_3$$

[Chifu]

svv в сообщении #495686 писал(а):

P.S. И даже так правильно:

$$f(x_1,x_2,x_3,x_4)=x_2\bar x_3 \vee x_1\bar x_2 \vee x_3 x_4 \vee \bar x_2 x_3$$

Разве карта Карно соответствует ответу? f = 1 на {1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 14, 15}:

$$f(x_4,x_3,x_2,x_1)=x_2 \bar x_1 \vee x_4 \bar x_1 \vee \bar x_4 x_1 \vee x_4 x_3$$

f = 1 на {2, 6, 10, 14}, {1, 3, 5, 7}, {8, 10, 12, 14}, {12, 13, 14, 15}.
В строках младшая часть, в столбцах старшая.

[svv]

Я считал, что независимые переменные в заголовках строк и столбцов расположены, как здесь:
http://ru.wikipedia.org/wiki/Карта_Карно
Уверен, так же считал и автор темы. Правильность трактовки подтверждается эквивалентностью ответа автора, ответа в книге и моих вариантов.

[Chifu]

A, понял, если $x_1$ и $x_2$, $x_3$ и $x_4$ поменять местами, то так же будет :). Я привык двоичные числа справо налево записывать как $x_3x_2x_1x_0$, а википедии как $x_1 x_2 x_3 x_4$.

[svv]

А вот в английской Википедии ближе к Вашему варианту. Соглашения могут быть разные...