Математическая логика и теория алгоритмов. Самохин А.В. - 11 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

§2. þÉÓÌÏ ÜÌÅÍÅÎÔÏ× 11
úÁÄÁÞÁ 13. äÏËÁÖÉÔÅ, ÞÔÏ |A
1
4 . . . 4 A
n
| ÒÁ×ÎÏ
X
i
|A
i
| − 2
X
i<j
|A
i
∩ A
j
| + 4
X
i<j<k
|A
i
∩ A
j
∩ A
k
| − . . .
(ËÏÜÆÆÉÃÉÅÎÔÙ ¡ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÙÅ ÓÔÅÐÅÎÉ Ä×ÏÊËÉ).
ðÏÄÓÞ¾Ô ËÏÌÉÞÅÓÔ× ÜÌÅÍÅÎÔÏ× × ËÏÎÅÞÎÙÈ ÍÎÏÖÅÓÔ×ÁÈ ÏÔÎÏÓÑÔ Ë ËÏÍ-
ÂÉÎÁÔÏÒÉËÅ. îÅËÏÔÏÒÙÅ ÎÁÞÁÌØÎÙÅ Ó×ÅÄÅÎÉÑ ÉÚ ËÏÍÂÉÎÁÔÏÒÉËÉ ÐÒÉ×ÅÄÅÎÙ
ÄÁÌØÛÅ × ËÁÞÅÓÔ×Å ÚÁÄÁÞ. óÅÊÞÁÓ ÎÁÓ × ÐÅÒ×ÕÀ ÏÞÅÒÅÄØ ÉÎÔÅÒÅÓÕÅÔ ÓÌÅÄÕÀ-
ÝÉÊ ÐÒÉÎÃÉÐ:
ÅÓÌÉ ÍÅÖÄÕ Ä×ÕÍÑ ÍÎÏÖÅÓÔ×ÁÍÉ ÍÏÖÎÏ ÕÓÔÁÎÏ×ÉÔØ ×ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ
ÓÏÏÔ×ÅÔÓÔ×ÉÅ, ÔÏ × ÎÉÈ ÏÄÉÎÁËÏ×ÏÅ ÞÉÓÌÏ ÜÌÅÍÅÎÔÏ×.
(÷ÚÁÉÍÎÁÑ ÏÄÎÏÚÎÁÞÎÏÓÔØ ÔÒÅÂÕÅÔ, ÞÔÏÂÙ ËÁÖÄÏÍÕ ÜÌÅÍÅÎÔÕ ÐÅÒ×ÏÇÏ
ÍÎÏÖÅÓÔ×Á ÓÏÏÔ×ÅÔÓÔ×Ï×ÁÌ ÒÏ×ÎÏ ÏÄÉÎ ÜÌÅÍÅÎÔ ×ÔÏÒÏÇÏ É ÎÁÏÂÏÒÏÔ.)
÷ÏÔ ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ× ÉÓÐÏÌØÚÏ×ÁÎÉÑ ÜÔÏÇÏ ÐÒÉÎÃÉÐÁ.
úÁÄÁÞÁ 14. îÁ ÏËÒÕÖÎÏÓÔÉ ×ÙÂÒÁÎÙ 1000 ÂÅÌÙÈ ÔÏÞÅË É ÏÄÎÁ Þ¾ÒÎÁÑ.
þÅÇÏ ÂÏÌØÛÅ ¡ ÔÒÅÕÇÏÌØÎÉËÏ× Ó ×ÅÒÛÉÎÁÍÉ × ÂÅÌÙÈ ÔÏÞËÁÈ ÉÌÉ ÞÅÔÙÒ¾È-
ÕÇÏÌØÎÉËÏ×, Õ ËÏÔÏÒÙÈ ÏÄÎÁ ×ÅÒÛÉÎÁ Þ¾ÒÎÁÑ, Á ÏÓÔÁÌØÎÙÅ ÔÒÉ ÂÅÌÙÅ? (òÅ-
ÛÅÎÉÅ: ÉÈ ÐÏÒÏ×ÎÕ, ÐÏÓËÏÌØËÕ ËÁÖÄÏÍÕ ÞÅÔÙÒ¾ÈÕÇÏÌØÎÉËÕ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ
ÔÒÅÕÇÏÌØÎÉË, ÏÂÒÁÚÏ×ÁÎÎÙÊ ÔÒÅÍÑ ÅÇÏ ÂÅÌÙÍÉ ×ÅÒÛÉÎÁÍÉ.)
úÁÄÁÞÁ 15. ëÁËÉÈ ÐÏÄÍÎÏÖÅÓÔ× ÂÏÌØÛÅ Õ 100-ÜÌÅÍÅÎÔÎÏÇÏ ÍÎÏÖÅ-
ÓÔ×Á: ÍÏÝÎÏÓÔÉ 57 ÉÌÉ ÍÏÝÎÏÓÔÉ 43? (õËÁÚÁÎÉÅ: 57 + 43 = 100.)
úÁÄÁÞÁ 16. äÏËÁÖÉÔÅ, ÞÔÏ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ ÄÌÉÎÙ n, ÓÏÓÔÁ-
×ÌÅÎÎÙÈ ÉÚ ÎÕÌÅÊ É ÅÄÉÎÉÃ, ÓÔÏÌØËÏ ÖÅ, ÓËÏÌØËÏ ÐÏÄÍÎÏÖÅÓÔ× Õ ÍÎÏÖÅ-
ÓÔ×Á {1, 2, . . . , n}. (õËÁÚÁÎÉÅ: ËÁÖÄÏÍÕ ÐÏÄÍÎÏÖÅÓÔ×Õ X ⊂ {1, 2, . . . , n}
ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ, ÎÁ i-Í ÍÅÓÔÅ
ËÏÔÏÒÏÊ ÓÔÏÉÔ ÅÄÉÎÉÃÁ, ÅÓÌÉ É ÔÏÌØËÏ ÅÓÌÉ i ∈ X.)
úÁÄÁÞÁ 17. äÏËÁÖÉÔÅ, ÞÔÏ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ ÎÕÌÅÊ É ÅÄÉÎÉà ÄÌÉ-
ÎÙ n, × ËÏÔÏÒÙÈ ÞÉÓÌÏ ÅÄÉÎÉà ÒÁ×ÎÏ k, ÒÁ×ÎÏ ÞÉÓÌÕ k-ÜÌÅÍÅÎÔÎÙÈ ÐÏÄÍÎÏ-
ÖÅÓÔ× n-ÜÌÅÍÅÎÔÎÏÇÏ ÍÎÏÖÅÓÔ×Á.
üÔÏ ÞÉÓÌÏ ÎÁÚÙ×ÁÅÔÓÑ ÞÉÓÌÏÍ ÓÏÞÅÔÁÎÉÊ ÉÚ n ÐÏ k É ÏÂÏÚÎÁÞÁÅÔÓÑ C
k
n
×
ÒÕÓÓËÉÈ ËÎÉÖËÁÈ; × ÉÎÏÓÔÒÁÎÎÙÈ ÏÂÙÞÎÏ ÉÓÐÏÌØÚÕÅÔÓÑ ÏÂÏÚÎÁÞÅÎÉÅ
n
k
.
úÁÄÁÞÁ 18. äÏËÁÖÉÔÅ, ÞÔÏ C
k
n
= C
n−k
n
.
úÁÄÁÞÁ 19. äÏËÁÖÉÔÅ, ÞÔÏ C
0
n
+ C
1
n
+ . . . + C
n
n
= 2
n
.
úÁÄÁÞÁ 20. ðÕÓÔØ U ¡ ÎÅÐÕÓÔÏÅ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï. äÏËÁÖÉÔÅ,
ÞÔÏ ÐÏÄÍÎÏÖÅÓÔ× ÍÎÏÖÅÓÔ×Á U, ÉÍÅÀÝÉÈ Þ¾ÔÎÕÀ ÍÏÝÎÏÓÔØ, ÓÔÏÌØËÏ
§2. þÉÓÌÏ ÜÌÅÍÅÎÔÏ×                                                       11

  úÁÄÁÞÁ 13. äÏËÁÖÉÔÅ, ÞÔÏ |A1 4 . . . 4 An| ÒÁ×ÎÏ
         X             X                X
             |Ai | − 2   |Ai ∩ Aj | + 4   |Ai ∩ Aj ∩ Ak | − . . .
             i          i

Страницы