Доказать тождество: аналитический метод и метод перебора

[OcbMuHor]

Задача состоит в следующем: доказать аналитически и методом перебора следующее тождество
$\[{x_1}({x_1} + \overline {{x_1}} {x_2})(\overline {{x_1}} + {x_2}\overline {{x_2}} ) = 0\]$

Ничего сложного, но только загвоздка в том, что я немного не соображаю о каких методах идет речь.

[svv]

Совет: $x_1$ обозначьте $x$, $x_2$ обохначьте $y$. Получится $\[x(x + \overline {x} {y})(\overline {x} + {y}\overline {y} ) = 0\]$, что гораздо приятней на вид, и набирать легче.
Аналитически: используя какие-нибудь тождества, упростите левую часть, и если Вы не ошиблись, получите $0$, это и будет доказательство.
Перебором: рассмотрите все комбинации $x,y \in \{0,1\}$ и вычислите левую часть для каждой комбинации. Если Вы не ошибетесь, все комбинации дадут $0$. Это и будет доказательство.

[OcbMuHor]

Вот что вышло:
$\[x(x + \overline x y)(\overline x + y\overline y ) = x(x + y)\overline x = 0 \wedge (x + y) = 0\]$ правильность не вызывает сомнений, а для перебора прийдется постороить таблицу истинности... трудоемко. Хорошо что 2 переменные

[svv]

Можно пойти на небольшой компромисс и применить при переборе немного аналитики: неужели требуется тупо и честно выписывать все варианты для $y\overline y$, если мы понимаем, что это $0$?

OcbMuHor писал(а):

трудоемко. Хорошо что 2 переменные

"Задачедатели" нас щадят и не требуют прописывать всё это в многовариантных случаях. В то же время от нас ожидают, что мы хотя бы в принципе представляем, что под этим понимается и как выполняется.

Ещё можно заметить, что сложность выписывания всех вариантов зависит от количества переменных по показательному закону ($2^n$), а от длины формулы линейно, так что это еще не самый ужасный случай.

[Null]

почему $x + \overline x y = x + y$ ?

[svv]

Поздно, зачет сдан.

[OcbMuHor]

Null в сообщении #407738 писал(а):

почему $x + \overline x y = x + y$ ?

Ерош И.Л., Дискретная математика. Булева алгебра, комбинационные схемы, преобразования двоичных последовательностей. параграф 1.4.
Думаю что в любой книге по булевой алгебре подобное не трудно найти.

[Gortaur]

Null
Как можно вообще такое спрашивать? Там же 4 варианта.

[venco]

Null в сообщении #407738 писал(а):

почему $x + \overline x y = x + y$ ?

$x+y=x+1\cdot y=x+(x+\overline x)y=x+xy+\overline x y=x(1+y)+\overline x y=x\cdot 1+\overline x y=x+\overline x y$