Certas formas normais de funções Booleanas, e.g. formas normais conjuntivas, disjuntivas e polinomiais, podem ser vistas como certas factorizações do clone $\Omega $ de todas as funções Booleanas em clones minimais (i.e., clones que cobrem o clone das projecções). Este facto foi o ponto de partida do trabalho de C., Foldes, Lehtonen [1] no qual baseamos esta exposição.

Começaremos por recordar algumas noções básicas na teoria de funções Booleanas e apresentar alguns resultados a respeito de clones. De seguida, iremos então considerar a operação de composição restrita a clones Booleanos: apresentaremos algumas propriedades fundamentais e uma descrição completa desta operação na forma de uma tabela tipo multiplicativa.

Desta descrição iremos obter todas as possíveis factorizações do clone $\Omega $ em clones minimais o que nos levará a uma formalização da noção intuitiva de "forma normal". Como resultado, iremos ver que, além das representações clássicas, existe essencialmente uma outra, a que chamamos "forma normal mediana", e que exprime o facto de toda a função Booleana poder ser representada como uma composição sucessiva de funções medianas aplicada a variáveis, variáveis negadas e constantes. Terminaremos esta palestra com o estudo comparativo desta com as formas normais clássicas mostrando que a forma normal mediana é de certo modo mais eficiente.

[1] M. Couceiro, S. Foldes, E. Lehtonen. "Composition of Post classes and normal forms of Boolean functions", Discrete Mathematics, 306 (2006) 3223--3243.