Дискретная алгебра

[webaib1]

Помогите доказать, а то что в голову ни чего не лезет.
(х1 & x2) or (x2 & (not x3)) = (x1 & x3) or (x2 & (not x3)) or (x1 & x2)
не могу понять чем дополнить левую часть...

[PAV]

Это неверно. Если $x_1=x_3=1$ и $x_2=0$, то слева ложь, а справа истина.

[webaib1]

Ох, извините. Ошибся в левой части.
(х1 & x3) or (x2 & (not x3)) = (x1 & x3) or (x2 & (not x3)) or (x1 & x2)

[PAV]

Тогда все элементарно. Левая часть является следствием выражения (x1 & x2) (т.е. если эта скобка истинна, то и левая часть также истинна). Нетрудно понять, что такая добавка не изменяет истинности всего выражения.

[webaib1]

накатав таблицу истинности, я это и сам заметил, но не вижу, как с помощью правил привести обе части к одному виду.
(x1 & x2) or (x3 & (not x3))
((x1 & x2) or x3) & ((x1 & x2) or (not x3))
(x1 or x3) & (x2 or x3) & (x1 or (not x3)) & (x2 or (not x3))
grrrrr

[PAV]

Это выводится так.

(x1 & x3) = (x1 & x3) or (x1 & x2 & x3)

аналогично

(x2 & (not x3)) = (x2 & (not x3)) or (x1 & x2 & (not x3))

далее объединяете и две последние скобки дают в точности (x1 & x2)

[webaib1]

Спасибо за помощь, теперь все ясно.

[webaib1]

Хех, продолжаю неравную борьбу с дискретной алгеброй )
Есть таблица стоимости операций:
not = 1
and, or, nand, nor = 2
mux = 3
xor, xnor = 4
Не совсем ясно откуда взяты эти цифры, особенно про nand и nor и...

Суть задачи в том что нужно построить "полный сумматор" (full adder) со стоимостью 11. В тупую получается
(A xor B) xor Cin = S
(A and B) or (A and Cin) or (B and Cin) = Cout
Путем не хитрых преобразований получается сложить схему из 2 xor, 2 and, 1 or. Но это 13. Пробывал разбивать xor, но они при этом дорожают с 4 до 7. Может кто подскажет?

[luitzen]

Кажется, нашёл кое-что. Из двух xor и одного mux…

[webaib1]

Спасибо, действительно сложилось. Я просто старался разбить xor-ы и смотрел, что можно будет убрать ) чуть-чуть не в ту сторону понесло.

[webaib1]

Наткнулся на толковое решение сей проблеммы
www.cs.uiuc.edu/class/sp06/cs231/lectur ... lexers.ppt