Tautology problem: Conversion of propositional logic formulas to two dimensional forms

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

Abstract

Checking whether a propositional formula is a tautology or not in a feasible lime is an important problem of computer science. A simple way of achieving this is to evaluate the formula for each possible interpretation and find whether it is true for every interpretation. However, as the number of variables increases, the number of interpretation increases exponentially and the time to solve the problem becomes unfeasable for even a few variables. In this study, various ways are investigated to solve the problem in a shorter time and at last a two dimensional form of the propositional formulas is obtained. To do this, firstly, the original formula is reduced to other propositional formulas which have less variables but the same truth value. Then it is investigated whether this reduction can be achieved by other means. As a result, the concepts of AND links and AND terms are introduced By the aid of these concepts, some two dimensional forms of the propositional formulas are got and their equivalance to the propositional formulas are shown. Also it is shown that converting a propositional formula to its two dimensional form takes ks lime where k is a constant and s is the size of the propositional formula. Thus if the problem is solved for a two dimensional formula in $partial$(s) times, then it would be solved for its propositional form in $partial$(s)+ks times.

Özet

Bir önerme ifadesinin hepdoğnı (totoloji) olup olmadığının kabul edilebilir bir zamanda bulunması, bilgisayar bilimlerinin önemli bir problemidir. Herhangi bir önerme ifadesinin hepdoğnı 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.