Zeroability patterns of monomials in the sign-representation of boolean functions

Abstract

Boolean functions (BF) are one of the fundamental concepts in discrete mathematics. It is possible to represent any BF by a unique polynomial when one takes -1 as True and 1 as False. Coefficients of the polynomial representing the given BF can be found with Lagrange interpolation. When the exact interpolation criterion is replaced with the signmatch criterion, one can find infinitely many sign representing polynomials for a given truth table. The problem of finding a minimum number of monomial set that is sufficient to represent a BF is a difficult mathematical problem. This thesis aims to contribute to its solution by investigating the zeroability patterns of monomials. To this end, we asked which monomials must be in a minimum sign representing polynomial. This question drove us to make numerical investigations on the BFs in lower dimensions. For all 3- and 4-variable BFs, we found all the monomial subsets, whose elements can be zeroed and we introduced a graph representation indicating whether particular pairs of monomials could be absent from any sign representation. In addition to the numerical investigations, we have also proved that if a three-element monomial set S, could not be absent altogether from the sign representation of a BF, then there must be at least a two element subset of S which could not be absent in any sign representation of that BF. We expect these results will give support to the development of heuristic algorithms to construct close-to-minimum number of monomial sign representing polynomials for BFs.

Boolean fonksiyonlar (BF) ayrık matematik alanındaki temel konulardan biridir. 1'i Yanlış ve -1'i Doğru olarak kabul edersek, bir BF'i tek bir polinomla ifade edebiliriz. Verilen BF'in katsayıları Lagrange interpolasyonu ile bulunabilir. Ne zaman tam interpolasyon işaret eşleşme kriteri ile değiştirilirse, verilen bir gerçeklik tablosu için sonsuz tane işaret temsili polinomu bulunabilir. Bir BF'i temsil etmek için yeterli, minimum sayıda terim içeren bir küme bulmak zor bir matematik problemidir. Bu tez bu problemin çözümüne, terimlerin BF'i temsil ederken sıfırlanabilme düzenlerini araştırarak katkı sunmayı hedeflemektedir. Bu amaçla, hangi terimler minimum işaret temsili polinomda olmak zorundadır sorusunu sorduk. Bu soru bizi küçük boyutlarda numerik araştırmalar yapmaya itti. Tüm üç ve dört değişkenli BF'ler için, elemanları bir arada sıfırlanabilen tüm alt kümeleri bulduk ve hangi monomial çiftlerinin birlikte herhangi bir işaret temsilinden eksik olup olamayacağını belirten, bir graf tanımı yaptık. Numerik araştırmalara ek olarak, üç elemanlı bir terim kümesi S, tüm elemanları bir arada bir BF'in işaret temsilinden çıkarılamıyorsa, S'in iki elemanlı alt kümelerinden en az bir tanesinin bu BF'in işaret temsilinden çıkarılamaz olduğunu ispatladık. Bu sonuçların bize, minimum terim sayısına yakın sayıda terim bulunduran, BF'lerin işaret temsili polinomlarını bulmamızı sağlayacak buluşsal bir algoritma bulma konusunda destek olmasını bekliyoruz.