İTÜDERGİSİ/c, Cilt 3, Sayı 1 (2005)

Yazı Büyüklüğü:  Küçük  Orta  Büyük

Hepdoğruluk problemi: Önerme mantığı ifadelerinin iki boyutlu biçimlere dönüştürülmesi

Lokman KOLUKISA

Özet


Bir önerme ifadesinin hepdoğru (totoloji) olup olmadığının kabul edilebilir bir zamanda bulunması, bilgisayar bilimlerinin önemli bir problemidir. Herhangi bir önerme ifadesinin hepdoğru olup olmadığı, sadece bir kaç değişkene sahip ifadelerde, mümkün her yorum için ifadenin değerini hesaplayarak kolayca bulunabilir. Fakat, ifadedeki değişken sayısı arttıkça yorum sayısı üssel olarak büyümekte ve çözüm için gereken zaman kabul edilebilir sınırların ötesine geçmektedir. Bu çalışmada, bu problemi daha kısa zamanda çözmek için değişik yollar denenmiş ve önerme ifadelerinin iki boyutlu biçimleri elde edilmiştir.  Bunun için önerme ifadeleri, daha az değişkene fakat aynı hepdoğruluk değerine sahip başka önerme ifadelerine indirgenmiştir.. Daha sonra bu indirgemeyi başka türlü yapıp yapamayacağımız araştırılmıştır. Bunun sonucu olarak VE bağları ve VE terimleri kavramı ortaya atılmıştır. En sonunda önerme ifadelerinin iki boyutlu biçimlerine ulaşılmıştır.

 

Anahtar Kelimeler: Önerme mantığı, Boole ifadeleri, totoloji, hepdoğruluk, çizge, iki boyutlu ifadeler.


Tam Metin: PDF