Yazan : Şadi Evren ŞEKER

Bu gösterim, bool cebirinde (boolean algebra) kullanılan ve kaziyeleri (önerme, proposition) ve (and) bağlacı ile bağlamanın özel bir şeklidir. Kısaca CNF (conjuction normal form) olarak ifade edilir. Diğer bir normal şekil olan Chomsky Normal Form (CNF) ile ilgili bilgi arıyorsanız buradan ulaşabilirsiniz.

Bu özel şeklin taşıdığı kuralları aşağıdaki şekilde sıralayabiliriz:

Ters (not) işlemi, sadece önermelerin lafzi gösterimlerin (literal) başında bulunacaktır. Bir kaziyenin (önerme, propositon) başında bulunmayacaktır.

Örneğin ¬A şeklindeki tek lafzi gösterim üzerinde olan ters işlemi kabul edilirken ¬(A V B) şekli kabul edilemez.

Ve (and) işlemi, iki operand almaktadır. Yani a ve b şeklindeki bir işlemde a ve b adında iki lafzi gösterim (literal) bulunmaktadır. Bu işlemin herhangi bir operandı, basit bir lafzi gösterim (literal) veya disjunction (veya operatörü (or opeartor) ile oluşturulmuş bir) kaziye (önerme, proposition) olmalıdır.

Örneğin aşağıdaki gösterimler bu kurala uymaktadır:

A Λ B

(A V B ) Λ (C V D)

A Λ (C V D V F)

Ancak aşağıdaki gösterimler bu kurala uymaz

A Λ (B Λ C)

A Λ (B V C Λ D)

(A Λ B) Λ C

Ancak yukarıdaki gösterimler CNF (conjuction normal form) yani ve bağlacı normal şekline çevrilebilir. Bu çevirimler aşağıda gösterilmiştir (yukarıdaki her satır için sırasıyla)

A Λ B Λ C

A Λ ( B V C ) Λ ( B V D)

A Λ B Λ C

Görüldüğü üzere yukarıdaki yeni hallerinde, verilen gösterimler ve bağlacı üzerinde basitleştirilmiştir.

Disjunction Normal Form (DNF, Veya bağlacı normal şekli) ise yukarıdaki ve bağlacı için söylenen her şeyin, veya bağlacı için geçerli olması durumudur.

Kısaca bu şekilde kabul edilemeyecek gösterimleri ve çevrilmiş şekillerini aşağıda verelim:

DNF şeklinde olmayanlar DNF karşılığı
(A V B) Λ C (A Λ C) V (B Λ C)
A Λ (B V C Λ D) (A Λ B) V (A Λ (C Λ D))
¬(A Λ B) ¬A V ¬B

İki gösterimin doğruluğunun tespiti. Yani verilen bir boole cebiri diziliminin gerçekten CNF veya DNF olduğunun sınanması, veya verilen bir denklemin sonucunun doğru (true) veya yanlış (false) olarak bulunabilmesi, bu denklemdeki lafzi terim (literal) sayısına bağlıdır. Örneğin 3CNF bir denklemin, yani sadece 3 terimin conjunction (ve bağlacı ile bağlanmasından) oluşan bir denklemin karmaşıklığı NP-Complete olurken, bu terim sayısı 2’ye indirildiğinde yani 2CNF bir denklem söz konusu olduğunda, karmaşıklık P zamanda (polinom zamanda) çözülebilmektedir.
Daha detaylı bilgi için ikili tatmin problemleri (boolean satisfaction problem) başlıklı yazıyı okuyabilirsiniz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir