Solucionador SAT polinomial de Zhegalkin

Os sistemas polinomiais s o ferramentas fundamentais para a resolu o de problemas dif ceis em ci ncia e engenharia, como a rob tica, o racioc nio autom tico, a intelig ncia artificial e o processamento de sinais. Do mesmo modo, desde os prim rdios da era digital, as vari veis booleanas t m sido a base das opera es inform ticas. Assim, a aplica o de t cnicas alg bricas comuns lgebra booleana atualmente utilizada como um m todo para resolver sistemas complexos de equa es booleanas que antes s podiam ser resolvidos utilizando t cnicas de l gica booleana. O objetivo deste projeto demonstrar que os polin mios de Zhegalkin (tamb m conhecidos por Algebraic Normal Form - ANF) s o uma forma alternativa de representar fun es booleanas. Para testar a hip tese, foi desenvolvido um Zhegalkin SAT Solver (ZPSAT). Os resultados obtidos ap s os testes conclu ram que o ZPSAT pode resolver uma conjun o de equa es XOR de forma eficiente em termos de fiabilidade e tempo de computa o. A heur stica utilizada para construir o ZPSAT baseou-se principalmente nos conceitos utilizados pelas F rmulas de Horn e num m todo de multiplica o r pida de dois polin mios ANF conhecido como transformada de Mobius.