boolfunc

Express˜es e Fun¸˜es Booleanas o co
1.1

Express˜es Booleanas o a e Vari´veis e literais: Dada uma ´lgebra booleana A, +, ·, , 0, 1 , uma vari´vel booleana ´ uma a a vari´vel que toma valores em A. a Dada uma vari´vel booleana x, o complemento de x, denotado x, ´ uma vari´vel booleana tal que a e a x = a sempre que x = a para qualquer a ∈ A.
Um literal ´ uma vari´vel booleana x ou o seu complemento x. e a
Express˜es booleanas: Dada uma ´lgebra booleana A, +, ·, , 0, 1 , express˜es booleanas em n o a o v´ri´veis x1 , x2 , . . . , xn s˜o definidas pelas seguintes regras: a a a • os elementos em A s˜o express˜es booleanas; a o
• as vari´veis x1 , x2 , . . . , xn s˜o express˜es booleanas; a a o • se x e y s˜o express˜es booleanas ent˜o tamb´m s˜o as express˜es (x) + (y), (x) · (y) e (x); a o a e a o
• uma express˜o ´ booleana se e somente se pode ser obtida aplicando-se as trˆs regras um n´mero a e e u finito de vezes.
Observe que uma express˜o booleana em n v´ri´veis x1 , x2 , . . . , xn n˜o necessariamente precisa cona a a a ter todas as n vari´veis. Parˆnteses podem ser removidos da express˜o desde que n˜o introduzam a e a a ambiguidades. Por exemplo, a express˜o (x1 ) + (x2 ) pode ser escrita x1 + x2 . a Se uma express˜o pode ser derivada a partir de outra aplicando-se um n´mero finito de vezes as regras a u
(leis/propriedades) da ´lgebra booleana, ent˜o elas s˜o ditas equivalentes. O valor de express˜es a a a o equivalentes, para cada atribui¸˜o de valores `s vari´veis booleanas, ´ o mesmo. ca a a e
Express˜es booleanas definem uma fun¸˜o. Express˜es equivalentes definem uma mesma fun¸˜o. o ca o ca

1.2

Fun¸˜es booleanas co Dada uma ´lgebra booleana A, +, ·, , 0, 1 , uma express˜o booleana em n vari´veis x1 , x2 , . . ., xn dea a a n → A. O valor da fun¸˜o f para um elemento a = (a , a , . . . , a ) ∈ fine uma fun¸˜o booleana f : A ca ca
1 2 n An ´ calculado substituindo-se