Encontre as expansões em somas de produtos da função booleana F\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right) que tem o valor 1 se e somente se três ou mais das variáveis x_{1}, x_{2}, x_{3}, x_{4} e x_{5} têm o valor 1 .

Passo 1

O enunciado define a função booleana F(x_{1},x_{2},x_{3},x_{4},x_{5}) que vale 1 se e somente se pelo menos três das entradas são iguais a 1.
Conteúdo: expansão em soma de produtos (SOP). Vamos primeiro achar a forma canônica (soma de todos os mintermos onde F=1) e depois a forma simplificada mínima.

Passo 2

Para a forma canônica, identificamos todos os mintermos de peso 3, 4 ou 5 (isto é, todas as combinações de entradas com 3, 4 ou 5 uns).
Peso 3 ( \binom{5}{3}=10 casos):
(1,2,3)→ 11100_{2}=28, (1,2,4)→ 11010_{2}=26, (1,2,5)→ 11001_{2}=25, (1,3,4)→ 10110_{2}=22, (1,3,5)→ 10101_{2}=21, (1,4,5)→ 10011_{2}=19, (2,3,4)→ 01110_{2}=14, (2,3,5)→ 01101_{2}=13, (2,4,5)→ 01011_{2}=11, (3,4,5)→ 00111_{2}=7.
Peso 4 ( \binom{5}{4}=5 casos):
(2,3,4,5)→ 01111_{2}=15, (1,3,4,5)→ 10111_{2}=23, (1,2,4,5)→ 11011_{2}=27, (1,2,3,5)→ 11101_{2}=29, (1,2,3,4)→ 11110_{2}=30.
Peso 5: (1,2,3,4,5)→ 11111_{2}=31.

Passo 3

A forma canônica em soma de mintermos é
F \;=\;\sum m(7,11,13,14,15,19,21,22,23,25,26,27,28,29,30,31).
Em termos de produtos de literais, isso corresponde a listar cada mintermo, por exemplo
m(7)=\bar x_1\bar x_2\bar x_3x_4x_5,\quad m(11)=\bar x_1\bar x_2x_3x_4\bar x_5,\;\dots\;, m(31)=x_1x_2x_3x_4x_5.

Passo 4

Para simplificar, note que qualquer combinação de 4 ou 5 uns já faz com que algum produto de 3 variáveis seja 1. Logo a expressão mínima é a soma de todos os produtos de três variáveis distintas:
F = x_1x_2x_3 \;+\; x_1x_2x_4 \;+\; x_1x_2x_5 \;+\; x_1x_3x_4 \;+\; x_1x_3x_5 \;+\; x_1x_4x_5 \;+\; x_2x_3x_4 \;+\; x_2x_3x_5 \;+\; x_2x_4x_5 \;+\; x_3x_4x_5.
Isto cobre exatamente todos os casos em que há pelo menos três entradas iguais a 1.

Resposta

Forma canônica (SOP de mintermos):
F=\sum m(7,11,13,14,15,19,21,22,23,25,26,27,28,29,30,31).
Forma mínima (SOP simplificada):
F = \sum_{1\le i<j<k\le5} x_i\,x_j\,x_k \quad\text{i.e.}\quad x_1x_2x_3 + x_1x_2x_4 + x_1x_2x_5 + x_1x_3x_4 + x_1x_3x_5 + x_1x_4x_5 + x_2x_3x_4 + x_2x_3x_5 + x_2x_4x_5 + x_3x_4x_5.

Exercícios de Livros Relacionados