AULA 20 27

Aula 20

Funções Booleanas

Seja B uma álgebra de boole e sejam x1, x2, ..., xn variáveis tais que seus valores pertençam a B.
Chama-se função booleana de n variáveis a uma aplicação f de B em B satisfazendo as seguintes regras:
1ª) Se para quaisquer valores de x1, x2, ..., xn ; f (x1, x2, ..., xn ) = a ; a  B, então f é uma função booleana. É a função constante.

2ª) Se para quaisquer valores de x1, x2, ..., xn ; f (x1, x2, ..., xn ) = xi para algum i (i = 1,2,...,n) então f é uma função booleana. É a função projeção ou função identidade.

3ª) Se f é uma função booleana, então g definida por g (x1, x2, ..., xn ) = (f (x1, x2, ..., xn )) para todos x1, x2, ..., xn é uma função booleana.

4ª) Se f e g são funções booleanas, então h e k definidas por: h (x1, x2, ..., xn ) = f (x1, x2, ..., xn ) + g (x1, x2, ..., xn ) e k (x1, x2, ..., xn ) = f (x1, x2, ..., xn ) . g (x1, x2, ..., xn ) para todos os x1, x2, ..., xn são funções booleanas.

5ª) Qualquer função construída por um número finito de aplicações das regras anteriores e somente tal função é booleana.

Observação: Chama-se constante booleana em B a qualquer elemento de uma álgebra de boole B. Chama-se variável booleana em B ao símbolo que pode representar qualquer dos elementos de uma álgebra de boole B.

Exemplos:
1. f (x) = ax + bx’
2. f (x,y) = axy’ + bx’y’ + cxy

Representação da função booleana na forma padrão ou canônica: f (x) = f (1) x + f (0) x’ f (x,y) = f (1,1) xy + f (1,0) xy’ + f (0,1) x’y + f (0,0) x’y’
Teorema
Se f é uma função booleana de uma variável então para todos os valores de x teremos: f (x) = f (1) x + f (0) x’
Demonstração:
1º Caso f é uma função constante f (x) = a f (1) x + f (0) x’ ax + ax’ a (x + x’) a . 1 a 2º Caso f é a função identidade f (x) = x f (1) x + f (0) x’
1x + 0x’ x 3º Caso
Suponhamos que o teorema vale para f e g e seja h (x) = f (x) + g (x) h (x) = f (1) x + f (0) x’ + g (1) x + g (0) x’ h (x) = (f (1) + g (1)) x + (f (0) + g (0)) x’ h (x) = h (1) x + h (0)