Bn grafı yardımıyla boole fonksiyonunun minumum kontaktla gerçekleştirimi

Abstract

ÖZET n değişkenli bir Boole fonksiyonunu realize eden lojik devreler içersinden minimum kontak içeren devrenin bulunması problemi bugüne kadar, Roth £16], Bakoğlu l 1, 23, Scale- Lee - Chang [17], Sureschender C 1 9 3. Hwa [13], vb. araştırıcılar tarafından çeşitli açılardan ele alınarak incelenmiştir. Bizim amacımız bu önemli probleme graf aracılığı ile bir çözüm getir mektir. Çalışmanın birinci bölümünde, problemin çözümün de yararlanılan graflarla ilgili tanımlar ve teorem ler ifade edilmiştir. îkinci bölümde, minimizasyon probleminin çözü münde kullanılacak olan bir Bn Boole grafi tanımlan mış ve bunun yapısı, özellikleri incelenmiştir: Bn grafının n2 tane ayrıta sahip bir Hamilton graf olduğu ve her çevresinin çift sayıda ayrıt içerdiği, Bn grafının kromatik - sayısının 2 olduğu gösteril miş ve aynı benzerlik dereceli ayrıtlara tanımlanarak bu ayrıtların özellikleri, Bn grafının çekirdek küme leri, Line grafı incelenmiştir. AıyrıcaBg, B3 ve B4 graflarının izomorf grafları çizilmiştir. Bn grafının komşuluk matrisinin karekteristik fonksiyonu ve karek- teristik değerleri hesaplanarak, B, B^ b, ? Bfl grafları nın 2,3,4 ayrıtlı çevrelerinin sayısı bulunmuştur. üçüncü bölümde verilen n değişkenli bir Boole fonksiyonunun Toplamsal Taylor açılımı ile buna karşı gelen Bn Boole grafı arasında bir izomorf izmanın mevcut olduğu ve bu izomorfi zmadan yararlanılarak, Boole fonksiyonlarının minimizasyonu probleminin Bn grafındaki izole tepe sayısının minimizasyonu proble mine dönüştürülebildiği gösterilmiştir: Bn grafındanbir ağaç seçip verilen kurala göre yeni bir graf elde etme işi ard arda sürdürülerek sadece izole tepeler den oluşmuş bir graf elde edilmektedir. Bundan sonra açıklanmış olan kural gereğince izole tepelerin temsil ettiği fonksiyona bir kontakt şebekesi grafı karşı getirilmiş ve buradan da kontakt şebekesi grafının tepe geçiş matrisi yazılmıştır. Bu matristen ispatlanmış olan bir teorem aracılığıyla ilkel bağlantı matrisine geçilebileceği gösterilmiştir, ilkel bağlantı matrisine uygulanan iki teoremle matrisin boyutu küçültülerek istenilen minimizasyona varılabilmektedir. Çalışmanın sonundaki örnekler kısmında yöntem bir kaç örneğe uygulanmıştır.

SUMMARY The problem of finding the circuits having minimum contacts, which realizes a Boolean function with n variable, those are logic circuits has been studied by Roth [16], Bakoğlu CI, 2], Scale-Lee- Chang C 17 3, Sureschender [ 19 ], Hwa [13]. Our aim is to find a solution to this problem via graphs. In the first part, the definitions and some theorems which are used in solution of the problem have been given. In the second part, Boolean graph Bn has been defined which is being used in the solution of the problem and the properties and its structure has been studied: B has n2n lines and it is a Hamiltonian graph and every circuit has even number of lines and its chromatic number is 2. Also the lines having similar degree have been defined and their properties nucleous sets of B and the line graph have been studied. Isomorphic graphs of B2, B, and B^ are drawn. The characteristic polynomial of the adjacent matrix of B and calculating the eigenvalues of B,, B2' B3 j B4 the number of tne circuits which have 2,3 and 4 lines have been found. In the final part, we show that there exists an isomorphism between the additional Taylor expansion and corresponding Boolean graph B, and by using this, the problem of minimization of Boolean function can be interchanged to the problem of minimization of the number of isolated vertices of Boolean graph Bn*. The operation of getting a new graph by successively repeating by choosing a tree from graph Bn with respect to the given rule, a graph having onlyisolated vertices has been obtained. So according to the rule which will be given, a contact circuit has been corresponded to the function, which is represen ted by isolated vertices and hence, the vertices transition matrix of contact circuit graph is given. By this matrix, via a theorem proved before we show that it will be possible to pass to the primitive connection matrix in which we decrease the.dimension of matrix, the required minimization is obtained. The method is applied to a few examples at the end of the examples section.