Zagadnienia wyliczenia

1. Aby sprawdzić metodą zero-jedynkową czy jest tautologią schemat zdaniowy, w którym występuje n zmiennych zdaniowych, trzeba wypisać wszystkie możliwe wartościowania tych zmiennych zdaniowych, czyli wszystkie możliwe n-wyrazowe ciągi zer i jedynek. Takich ciagów jest W₂ⁿ = 2ⁿ. Już dla n = 10 jest to pokaźna liczba 1024 sztuk. 2ⁿ parami różnych n-wyrazowych ciągów zer i jedynek stanowią rozwinięcia dwójkowe liczb całkowitych od 0 do 2ⁿ - 1, w których puste miejsca z przodu zapełniono zerami. Dla n = 4 są to:

   0 = 0000	4 = 0100	8 = 1000	12 = 1100
   1 = 0001	5 = 0101	9 = 1001	13 = 1101
   2 = 0010	6 = 0110	10 = 1010	14 = 1110
   3 = 0011	7 = 0111	11 = 1011	15 = 1111

2. Do wypisania wszystkich C_n^k kombinacji po k elementów ze zbioru {1, 2,..., n} można użyć wielomianu n + 1 zmiennych
   (1 + y₁x)(1 + y₂x)...(1 + y_nx).
   Po otwarciu nawiasów i uprządkowaniu według potęg zmiennej x w nawiasie jako współczynnik przy x^k odczytujemy sumę iloczynów po k różnych zmiennych y_i. Numery tych zmiennych w jednym iloczynie tworzą kombinację, a we wszystkich iloczynach - wszystkie kombinacje, np. dla n = 4, k = 2:
   

   = y₁y₂y₃y₄x⁴ + (((y₁ + y₂)y₃ + y₁y₂)y₄ + y₁y₂y₃)x³ +

   + ((y₁ + y₂ + y₃)y₄ + (y₁ + y₂)y₃ + y₁y₂)x² + (y₁ + y₂ + y₃ + y₄)x + 1

   
   ma współczynnik y₃y₄ + y₂y₄ + y₁y₄ + y₂y₃ + y₁y₃ + y₁y₂ przy x², więc szukanymi kombinacjami są:

   34

   24

   14

   23

   13

   12

   .