TQBF Problemi: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
2. satır:
'''Boolean Formülü''' içerisinde; [[boolean]] değişkenleri, sabitler {0,1} ve işlemler {<math>\land</math>, <math> \lor</math>, <math> \lnot</math>} içeren formüllerdir. Bu formüller :<math> \forall </math>(bütün hepsi) ve <math> \exists</math> (en az bir) belirleyicileri ekleyerek daha genel bir yapıya sokabiliriz. <math> \forall x Q </math> ifadesi bütün ''x'' değişkenleri için ''Q'' formülü doğrudur anlamı taşımaktadır. Benzer bir şekilde; <math>\exists x Q </math> ifadesi ise bazı ''x'' değişkenleri için ''Q'' formülü doğrudur anlamı taşımaktadır.
Örnek olarak, [[doğal sayılar]] kümesinde <math>\forall x |x+1 > x | </math> ifadesi doğrudur. Çünkü, bütün [[doğal sayılar]]ın bir fazlası sayının kendisinden büyüktür. Fakat, <math>\exists y |y + y > 3| </math> ifadesi doğal sayılar kümesi için yanlıştır. Çünkü; hiçbir doğal sayının iki katı 3'e eşit değildir. Ancak biz örek uzay olarak doğal sayıları değilde [[gerçek sayılar]] alsaydık bu ifade doğru olacaktı.
Boolean formüllerin belirleyicilerle gösterilmesine, ''belirleyici boolean formülü'' denir. Burada kullanılan uzay {0,1} den oluşur. Örnek olarak:
| |||