Sobre o conjunto parcialmente ordenado induzido pela relação de menor entre funções booleanas e os seus membros irredutíveis

Nesta apresentação estaremos interessados numa quasi-ordem de funções, conhecida como a relação de menor, considerada no caso mais simples de funções de várias variáveis, as chamadas funções Booleanas. Esta quasi-ordem pode ser definida do seguinte modo: uma função g é dita um menor de uma função f, g \leq f, se g pode ser obtida de f por meio das operações de Mal'cev de identificação de variáveis, permutação de variáveis ou adição de variáveis fictícias. A importância desta relação de menor na definição equacional de propriedades de funções tornou-se aparente num trabalho de Ekin, Foldes, Hammer e Hellerstein onde foi mostrado que classes (ou propriedades) de funções Booleanas definíveis por meio de equações coincidem exactamente com os segmentos iniciais desta quasi-ordem \leq. Esta correspondência com a definição equacional de funções levou a vários estudos desta quasi-ordem. Como qualquer quasi-ordem, a relação de menor \leq sobre o conjunto \Omega de todas as funções Booleanas induz uma ordem parcial sobre o conjunto \widetilde{Omega}constituído por classes de equivalência, onde as propriedades de \leq são mais facilmente expressas. Vários resultados a respeito da estrutura deste conjunto parcialmente ordenado (CPO) foram obtidos e, recentemente, conexões com a teoria de hipergrafos foram estabelecidas. Neste seminário iremos apresentar estes e outros resultados sobre o CPO \widetilde{Omega}. Começaremos por divulgar algumas propriedades deste CPO e estabelecer conexões com a teoria equacional de funções. De seguida, apresentaremos uma classificação deste CPO \widetilde{Omega} (que revelará o seu carácter universal entre CPOs contáveis) e iremos propor alguns problemas em aberto. Em particular, iremos considerar a questão de determinar os membros irredutíveis deste CPO, i.e., os elementos que cobrem um único membro de \widetilde{Omega}. Fazendo uso duma correspondência natural entre funções Booleanas (vistas como funções polinomiais) e hipergrafos, irredutibilidade traduz-se em propriedades combinatoriais de hipergrafos (e.g., ?set-transitivity" e ?monomorphicity", a última no caso de sistemas de Steiner). Como caso particular, apresentaremos uma descrição explícita daqueles grafos que correspondem a membros irredutíveis do CPO \widetilde{Omega}. Alguns dos resultados que iremos discutir foram obtidos em conjunto com Stephan Foldes, Maurice Pouzet, Erkko Lehtonen e Moncef Bouaziz.