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

Abstract

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.

Boolean functions (BF) are one of the fundamental concepts in discrete mathematics. Itis possible to represent any BF by a unique polynomial when one takes -1 as True and 1as False. Coefficients of the polynomial representing the given BF can be found withLagrange interpolation. When the exact interpolation criterion is replaced with the signmatchcriterion, one can find infinitely many sign representing polynomials for a giventruth table. The problem of finding a minimum number of monomial set that is sufficientto represent a BF is a difficult mathematical problem. This thesis aims to contributeto its solution by investigating the zeroability patterns of monomials. To this end,we asked which monomials must be in a minimum sign representing polynomial. Thisquestion drove us to make numerical investigations on the BFs in lower dimensions. Forall 3- and 4-variable BFs, we found all the monomial subsets, whose elements can bezeroed and we introduced a graph representation indicating whether particular pairs ofmonomials could be absent from any sign representation. In addition to the numericalinvestigations, we have also proved that if a three-element monomial set S, could notbe absent altogether from the sign representation of a BF, then there must be at least atwo 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 toconstruct close-to-minimum number of monomial sign representing polynomials forBFs.