128-12. Mostre que
tem o valor 1 se e somente se pelo menos duas das variáveis
e
tiverem o valor 1 .
Passo 1
O enunciado pede para mostrar que, considerando
e interpretando
como AND e
como OR em álgebra booleana,
vale
se e somente se pelo menos duas das variáveis
forem
. Vamos usar a definição de AND e OR e analisar pelo número de variáveis iguais a
.
Passo 2
Note que
Em álgebra booleana,
exatamente quando
e
; e uma disjunção OR só é
se pelo menos um de seus termos for
.
Passo 3
Se menos de duas variáveis estão em
, isto é, se há 0 ou 1 variável igual a
, então cada par
,
e
contém ao menos um zero. Logo
e, por OR de zeros,
Passo 4
Se pelo menos duas variáveis são
, há dois casos:
- Exatamente duas delas são
. Suponha, sem perda de generalidade, que e (e ou ). Então
- Todas as três são
. Então
e
Passo 5
Combinando os dois casos, vemos que
se e somente se há pelo menos duas entradas iguais a
.
Resposta
Mostramos que
exatamente quando pelo menos duas das variáveis
têm valor
.