Множество от стрингове

[drago]

Нека с [tex]S_n[/tex] означим множеството от стрингове от [tex]0[/tex] и [tex]1[/tex] с дължина [tex]n[/tex], т.е. [tex]S = \left\{(a_1, a_2,\cdots,a_n)|\, a_i \in \{0,1\}\,\right\}[/tex].
Дефинираме следните операции върху S:

- AND [tex](a_1,a_2,\cdots,a_n) \wedge (b_1,b_2,\cdots,b_n) = (a_1\wedge b_1,\cdots, a_n \wedge\ b_n)[/tex].

-OR [tex](a_1,a_2,\cdots,a_n) \vee (b_1,b_2,\cdots,b_n) = (a_1\vee b_1,\cdots, a_n \vee\ b_n)[/tex].

-NOT [tex]\neg (a_1,a_2,\cdots,a_n) = (\neg a_1, \neg a_2,\cdots, \neg a_n)[/tex].


Нека [tex]S \subset S_n[/tex], а [tex]\bar S[/tex] са всички стрингове, които могат да се получат от [tex]S[/tex] с прилагането по всевъзможен начин горните три операции.

Докажете, че [tex]|\bar S | = 2^k,\, k \leq n[/tex].

[drago]

Сега като гледам съм изпуснал два индекса, които биха могли да доведат до някаква двусмислица. Задачата трябва да се чете така:

Нека с [tex]S_n[/tex] означим множеството от стрингове от [tex]0[/tex] и [tex]1[/tex] с дължина [tex]n[/tex], т.е. S_n [tex]= \left\{(a_1, a_2,\cdots,a_n)|\, a_i \in \{0,1\}\,\right\}[/tex].
Дефинираме следните операции върху S_n:

- AND [tex](a_1,a_2,\cdots,a_n) \wedge (b_1,b_2,\cdots,b_n) = (a_1\wedge b_1,\cdots, a_n \wedge\ b_n)[/tex].

-OR [tex](a_1,a_2,\cdots,a_n) \vee (b_1,b_2,\cdots,b_n) = (a_1\vee b_1,\cdots, a_n \vee\ b_n)[/tex].

-NOT [tex]\neg (a_1,a_2,\cdots,a_n) = (\neg a_1, \neg a_2,\cdots, \neg a_n)[/tex].


Нека [tex]S \subset S_n[/tex], а [tex]\bar S[/tex] са всички стрингове, които могат да се получат от [tex]S[/tex] с прилагането по всевъзможен начин горните три операции.

Докажете, че [tex]|\bar S | = 2^k,\, k \leq n[/tex].

[drago]

Събирането по модул 2 или операцията XOR(0+0=0, 0+1=1, 1+1=0) се изразява чрез [tex]\vee, \wedge, \neg[/tex]:

[tex]p+q = (p\wedge \neg q)\vee(\neg p \wedge q)[/tex].

С тази операция и стандартното умножение по 0 и 1, [tex]S_n[/tex] става линейно пространство над [tex]\mathbb{F}_2[/tex].

Тъй като [tex]S[/tex] е затворено относно трите операции [tex]\vee, \wedge,\neg[/tex], то ще е затворено относно [tex]+[/tex] и значи ще е линейно подпространство на [tex]S_n[/tex] и тогава всеки негов елемент ще се представя еднозначно спрямо някакъв базис [tex]s_1, s_2,\cdots, s_k \in S[/tex].

[tex]s \in S , \, s= \lambda_1.s_1+\lambda_2.s_2+\cdots+\lambda_k.s_k,\, \lambda_i \in \{0,1\}[/tex].

От тук [tex]|S|=2^k[/tex].