128-12. Mostre que F(x, y, z)=x y+x z+y z tem o valor 1 se e somente se pelo menos duas das variáveis x, y e z tiverem o valor 1 .

Passo 1

O enunciado pede para mostrar que, considerando x,y,z\in\{0,1\} e interpretando \cdot como AND e + como OR em álgebra booleana,
F(x,y,z)=x y \;+\;x z\;+\;y z
vale 1 se e somente se pelo menos duas das variáveis x,y,z forem 1. Vamos usar a definição de AND e OR e analisar pelo número de variáveis iguais a 1.

Passo 2

Note que
F(x,y,z)= (x\wedge y)\;\vee\;(x\wedge z)\;\vee\;(y\wedge z).
Em álgebra booleana, x\wedge y=1 exatamente quando x=1 e y=1; e uma disjunção OR só é 1 se pelo menos um de seus termos for 1.

Passo 3

Se menos de duas variáveis estão em 1, isto é, se há 0 ou 1 variável igual a 1, então cada par (x,y), (x,z) e (y,z) contém ao menos um zero. Logo
x\wedge y = 0,\quad x\wedge z=0,\quad y\wedge z=0
e, por OR de zeros,
F(x,y,z)=0\;\vee\;0\;\vee\;0=0.

Passo 4

Se pelo menos duas variáveis são 1, há dois casos:
  1. Exatamente duas delas são 1. Suponha, sem perda de generalidade, que x=1 e y=1 (e z=0 ou z=1). Então
x\wedge y=1\quad\implies\quad F(x,y,z)=1\;\vee\;(\dots)=1.
  1. Todas as três são 1. Então
x\wedge y=1,\quad x\wedge z=1,\quad y\wedge z=1
e
F(x,y,z)=1\;\vee\;1\;\vee\;1=1.

Passo 5

Combinando os dois casos, vemos que F(x,y,z)=1 se e somente se há pelo menos duas entradas iguais a 1.

Resposta

Mostramos que
F(x,y,z)=x y + x z + y z = 1
exatamente quando pelo menos duas das variáveis x,y,z têm valor 1.

Exercícios de Livros Relacionados