Какие законы упрощают это булево выражение?

Question

Какие законы нужно ли мне использовать для упрощения

!X + (!Y + !Z)*(Y + Z) 

к

!X + (Y*!Z) + (!Y*Z) 

Answer 1

Вы можете сначала начать с дистрибутивности умножения относительно сложения:

!X + (!Y + !Z)*(Y + Z) = !X + !Y*Y + !Z*Y + !Y*Z + !Z*Z 

Тогда мы можем использовать комплементации, чтобы удалить элементы формы !p*p:

= !X + 0 + !Z*Y + !Y*Z + 0 

И наконец, удалить 0, как они + нейтральный.

Answer 2

Нет необходимости применять какие-либо конкретные «законы», просто записать простую таблицу, чтобы выяснить два выражения эквивалентны (при условии + является OR и * является AND):

Y Z !Y !Z (!Y+!Z)*(Y+Z)  (Y*!Z) +(!Y*Z) 
0 0 1 1 (1+1=1)*(0+0=0)=0 (0*1=0)+(1*0=0)=0 
0 1 1 0 (1+0=1)*(0+1=1)=1 (0*0=0)+(1*1=1)=1 
1 0 0 1 (0+1=1)*(1+0=1)=1 (1*1=1)+(0*0=0)=1 
1 1 0 0 (0+0=0)*(1+1=1)=0 (1*0=0)+(0*1=0)=0 

Аналогичным образом вы можете вычесть, что (X or Y) and Z эквивалентно (X and Z) or (Y and Z). Это называется дистрибутивностью and за or. Дальнейшее чтение - хорошая статья о Boolean algebra в Википедии.

В вашем примере: (!Y + !Z)*(Y + Z) = !Y*(Y + Z) + !Z*(Y + Z) = !Y*Y + !Y*Z + !Z*Y + !Z*Z. Тривиально A and not A == false, тогда ваше выражение упрощается до !Y*Z + !Z*Y и далее до Y*!Z + !Y*Z из-за коммутативности.

Answer 3

Если память (и я принимаю ваши обозначения правильно), то это УОС разрешение в простом сочетании: http://en.wikipedia.org/wiki/SLD_resolution