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

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.