Cevap :
A={a,b,c,d} kümesinin altkümeleri içinKaç tanesinde a elemanı bulunur?
Kaç tanesinde a elemanı bulunmaz?
Kaç tanesinde a ve b bulunur?
Kaç tanesinde a veya b bulunur?
Çözüm
a yı içeren altkümelerin dökümünü yapalım. {a},{a,b},{a,c},{a,d},{a,b,c},{a,b,d},{a,c,d},{a,b,c,d}. a yı içeren tüm altkümeler8 tanedir ve yukarıda görüldüğü gibidir. Şimdi tüm bu altkümelerde a yı görmeyelim, a yı atarak baktığımızda şu altkümeler oluşmaktadır: {},{b},{c},{d},{b,c},{b,d},{c,d},{b,c,d}. Bu altkümeler {b,c,d} kümesi ile oluşturabileceğimiz tüm altkümelerin listesidir. a yı içeren altkümeler oluştururken a yı mutlaka sepete atacağımızdan aslında kalanlarla değişik ne yapabiliriz onu düşünmüş oluyoruz. Demek ki belli bir elemanın olduğu altkümeler oluştururken bu eleman atılır ve kalan kümenin altküme sayısı bulunur.
a nın bulunmadığı altkümeler a elemanı atıldığında kalan kümenin altkümeleridir. {b,c,d} kümesinin altküme sayısı 23=8 olur. Dikkat edelim a nın bulunduğu altküme sayısı ilginç bir şekilde bulunmadığı altküme sayısına eşittir.
İki elemanın da bulunduğu altküme sayısı artık kolaydır. İstenen elemanlar zaten her altkümeye gireceğinden atılır ve kalanlarla değişik ne yapılabilir buna bakılır. Cevap 22=4 tür.
Bu soruyu iki yoldan çözeceğiz.İlk yolda tüm altkümelerden istenmeyen altkümeleri çıkaracağız. a veya b nin olduğu altkümelere yalnız a yı içerenler, a ve b yi içerenler ve yalnız b yi içerenler girer. Bu kümeye girmeyen altkümeler ne a ne de b yi içeren altkümelerdir. Tüm altkümeler 24=16 tane, a yı da b yi de içermeyenler bu elemanları atıp kalan kümenin altküme sayısını bulursak 22 tane. Tüm altkümelerden istenmeyen altkümeleri çıkarırsak 16−4=12 tane.
İkinci yolda a yı içeren altkümelere, ikisini de içerenler a yı içerenler hesaplanırken sayılmış olduğundan b yi içerip a yı içermeyen altkümeleri ekleyeceğiz. a yı içeren altkümeler 23=8tane. a yı içerip b yi içermeyenler 22=4 toplarsak 12 olur.
n elemanlı kümenin r elemanlı altkümeleri sayısı
n elemanlı bir kümenin r elemanlı altkümeleri sayısı kombinasyon konusundan gelen bir formülle bulunur. n in r li kombinasyonu şuna eşittir:
(nr)=n!r!(n−r)!Eleman sayısı belli olan altkümelerin sayısını bulurken bunu kullanacağız.
Örnek A={a,b,c,d,e} kümesinin3 elemanlı altkümeleri sayısı nedir? en az iki elemanlı altküme sayısı nedir? en fazla üç elemanlı altküme sayısı nedir? Çözüm 5 elemanlı bir kümenin 3 elemanlı altkümeleri sayısı 5 in 3 lü kombinasyonudur. (53)=5!2!⋅3!=10 En az iki elemanlı altkümelere 2 ve daha fazla elemanı olan altkümeler girer. (52)+(53)+(54)+(55)=10+10+5+1=26 İki ve daha fazla elemanlı altkümeleri bulacağımıza tüm altküme sayısı olan 25 ten 1 ve 0 elemanlı altkümeleri de çıkarabilirdik. 1 elemanlı altkümeler (51) açıkça 5 tanedirler. 0 elemanlı da 1 tanedir. 32−6=26 bulmuş olduk. En fazla üç elemanlı altkümeler 3 ve daha az eleman içeren altkümelerdir. Bunlar da (53)+(52)+(51)+(50) hesaplanarak 26 bulunur.
(2,3,4,) bunların alt kumesini yazın
(a,b,c,6,7,) alt kumesini yaz
Sertifikada bulunan eleman 3SAT Problemi, Alt Küme Toplamı Problemine Polinom Zamanda İndirgenebilir [değiştir]NP sınıfındaki tüm dillerin polinom zamanda alt küme toplamı diline indirgenebilir olduğunu göstermek için NP-Complete olan 3SAT dili kullanılabilir.
Bu problemin alt küme toplamı problemine polinom zamanda indirgenebilir, , olduğu bir tablo kullanılarak gösterilebilir.[1]
Φ; , ... , değişkenli, , ... , cümleli (clause) Boolean bir formül olsun.
Kullanılacak olan tabloda kolonlar, Φ formülünün değişkenlerini ve cümlelerini; satırlar ise, S kümesinin elemanlarının ve t toplamının ondalık düzende gösterimlerini ifade eder.
Tablodaki çift çizginin üzerinde bulunan , , ... , , ve , , ... , , sayıları S kümesinin elemanlarıdır, çizginin alt kısmında kalan kısımda ise t sayısı yer alır. Kullanılan bu tabloda, Φ formülünde bulunan her bir değişkeni için ve şeklinde 2 sayı yer alır . Bu sayıların ondalık gösterimi iki bölümden oluşur. Tablonun sol tarafı, değişkenin indisine uygun y ve z satırına 1 rakamı, geri kalan kısımlarına ise tabloda görüldüğü gibi l-i tane 0 yerleştirilerek oluşturulur. Tablonun sağ tarafında ise, Φ’de bulunan her bir cümle için bir hane bulunur ve şu şekilde doldurulur:
Eğer ∈ ise sayısının j’inci hanesine 1 konur.Eğer i ∈ ise sayısının j’inci hanesine 1 konur.Değerinin 1 olduğu belirtilmemiş hanelere ise 0 rakamı yerleştirilir.
Yukarıda bahsedilenlere ek olarak S kümesi, Φ’de bulunan her bir cümle için g ve h sayılarını barındırır. Bu iki sayı birbirine eşittir. Bu sayılar, cümlesine uygun düşen haneye 1 rakamı, geri kalan k-j haneye ise 0 yerleştirilerek oluşturulur.
Aşağıdaki tablo Φ = ( 2 ) ( ... ) ( 3 ... ... )için doldurulmuştur.
Bu varsayıma göre S’in bir alt kümesi oluşturulabilir. Bu alt kümeyi oluşturmak için şöyle bir yol izlenebilir:
Φ’yi doğrulayan değişkeninin değeri TRUE ise altkümeye sayısıΦ’yi doğrulayan değişkeninin değeri FALSE ise altkümeye sayısıseçilir.
Oluşturulan bu alt kümenin elemanları toplandığında, tablonun t satırındaki ilk l hanede 1 rakamı elde edilir, çünkü alt kümeye ya ya da sayısı seçilmiştir. Ayrıca son k hanede ise toplamın en fazla 3, en az 1 olduğu görülür. Bunun sebebi, Φ formülü doğrulanabilir olduğundan her cümlede en fazla 3, en az 1 değişkenin TRUE değerini almış olmasıdır. Toplamın 3 olmadığı durumlarda ise uygun indisli g ve/veya h sayıları kullanılarak toplamın 3’e ulaşması sağlanabilir.
Tablodan da görüldüğü gibi, altküme elemanlarının hanelerinde ya 1 ya da 0 rakamı bulunmaktadır, ayrıca her kolonda en fazla 5 adet 1 rakamı bulunduğundan toplama işlemi eldesiz gerçekleşir. İlk l kolonda toplamın 1 olması, ya sayısının ya da sayısının alt küme elemanları arasında yer almakta olduğunu gösterir. İkisi birden alt kümede bulunamaz, çünkü o durumda toplamları 2 olacağından varsayıma aykırı olur. Bu varsayımdan yola çıkılarak, Φ formülünün doğrulanabilirliği şu şekilde sağlanabilir:
Eğer alt kümede sayısı bulunuyorsa değişkenine TRUE değeri,Eğer alt kümede sayısı bulunuyorsa değişkenine FALSE değeriatanır.
Bu atamayla Φ formülünün doğrulanabilirliği sağlanabilir, çünkü son satırdaki t sayısının son k hanesinde 3 rakamı bulunmaktadır. Son k kolonda toplamın 3 olmasını sağlayacak en az 1 tane değer, alt kümeye seçilmiş olan veya sayısından gelmelidir, çünkü alt kümeye seçilebilecek olan g ve h sayılarından en fazla 2 toplamı elde edilebilir.
Bu durumda;
eğer bu 1 rakamı, sayısından geliyorsa ∈ ve = TRUEeğer bu 1 rakamı, sayısından geliyorsa i ∈ ve = FALSEolduğundan dolayı Φ formülünde bulunan her cümlesi doğrulanabilir, dolayısıyla Φ formülü doğrulanabilir olduğu gösterilebilir.
Son olarak da yukarıda bahsedilen tablonun kullanımıyla yapılan bu indirgemenin polinom zamanda gerçekleştirildiğini göstermek için tablonun boyutlarına bakılabilir. Tablonun boyutları kabaca olarak ifade edilebilir, dolayısıyla bu indirgeme için harcanan zamanın O() olduğu söylenebilir.
İlgili bağlantılar ların toplamının t’ye eşit olup olmadığını test et Sertifikada bulunan elemanların S kümesinin elemanı olup olmadığını test et Eğer ikisi de tamamsa, kabul et; değilse reddet."