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

UptoLike

ВУЗ: 

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

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

Рубрика: 

úÁÄÁÞÉ
§1. áÌÇÅÂÒÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
1.1. ôÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ
ëÁÖÄÁÑ ÆÏÒÍÕÌÁ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÏÂÌÁÄÁÅÔ Ó×ÏÊÓÔ×ÏÍ ÐÒÅ×ÒÁ-
ÝÁÔØÓÑ × ×ÙÓËÁÚÙ×ÁÎÉÅ ÐÒÉ ÆÉËÓÁÃÉÉ × ÎÅÊ ÚÎÁÞÅÎÉÊ ×ÓÅÈ ×ÙÓËÁÚÙ×ÁÔÅÌØ-
ÎÙÈ ÐÅÒÅÍÅÎÎÙÈ, ÔÏ ÅÓÔØ ÅÓÌÉ ÍÙ ÚÁÆÉËÓÉÒÕÅÍ × ÆÏÒÍÕÌÅ ÚÎÁÞÅÎÉÑ ×ÓÅÈ
×ÙÓËÁÚÙ×ÁÔÅÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ, ÔÏ, ÐÏÌØÚÕÑÓØ ÏÐÒÅÄÅÌÅÎÉÑÍÉ ÌÏÇÉÞÅÓËÉÈ
ÏÐÅÒÁÃÉÊ, ÍÙ ÍÏÖÅÍ ×ÙÞÉÓÌÉÔØ ÚÎÁÞÅÎÉÅ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ.
ôÁÂÌÉÃÁ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÓÏÄÅÒÖÉÔ ÓÔÏÌØ-
ËÏ ÓÔÒÏË, ÓËÏÌØËÏ ×ÓÅ×ÏÚÍÏÖÎÙÈ ÎÁÂÏÒÏ× ÚÎÁÞÅÎÉÊ ÉÓÔÉÎÎÏÓÔÉ ÐÅÒÅÍÅÎÎÙÈ
ÍÏÖÎÏ ÏÂÒÁÚÏ×ÁÔØ. ëÁÖÄÁÑ ×ÙÓËÁÚÙ×ÁÔÅÌØÎÁÑ ÐÅÒÅÍÅÎÎÁÑ ÍÏÖÅÔ ÐÒÉÎÉ-
ÍÁÔØ ÔÏÌØËÏ Ä×Á ÚÎÁÞÅÎÉÑ (0 É 1), ÐÏÜÔÏÍÕ × ÓÌÕÞÁÅ n ÐÅÒÅÍÅÎÎÙÈ ÔÁÂÌÉÃÁ
ÉÓÔÉÎÎÏÓÔÉ ÓÏÄÅÒÖÉÔ 2
n
ÓÔÒÏË.
ðÒÉ ÐÏÓÔÒÏÅÎÉÉ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ ÎÁÂÏÒÙ ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ ÒÁÓ-
ÐÏÌÁÇÁÀÔ Ó×ÅÒÈÕ ×ÎÉÚ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ (ËÁÖÄÙÊ ÎÁÂÏÒ ÐÏÎÉ-
ÍÁÀÔ ËÁË Ä×ÏÉÞÎÕÀ ÚÁÐÉÓØ ÎÅÏÔÒÉÃÁÔÅÌØÎÏÇÏ ÃÅÌÏÇÏ ÞÉÓÌÁ É ÒÁÓÐÏÌÁÇÁÀÔ
× ÐÏÒÑÄËÅ ×ÏÚÒÁÓÔÁÎÉÑ ÏÔ (000 . . . 0) ÄÏ (111 . . . 1).
ðÒÉÍÅÒ 1. ðÏÓÔÒÏÉÔØ ÔÁÂÌÉÃÕ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ:
x
1
x
2
→ (x
1
∨ x
2
)x
3
.
òÅÛÅÎÉÅ. 1. ïÐÒÅÄÅÌÉÍ ÐÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ × ÆÏÒÍÕÌÅ:
x
1
2
·
1
x
2
6
→ (x
1
3
∨ x
2
)
5
·
4
x
3
.
2. ðÏÌØÚÕÑÓØ ÏÐÒÅÄÅÌÅÎÉÑÍÉ ÏÐÅÒÁÃÉÊ ¬, ·, ∨ É →, ÚÁÐÏÌÎÉÍ ÔÁÂÌÉÃÕ.
x
1
x
2
x
3
x
2
x
1
· x
2
x
1
∨ x
2
x
3
(x
1
∨ x
2
)x
3
x
1
x
2
→ (x
1
∨ x
2
)x
3
0 0 0 1 0 0 1 0 1
0 0 1 1 0 0 0 0 1
0 1 0 0 0 1 1 1 1
0 1 1 0 0 1 0 0 1
1 0 0 1 1 1 1 1 1
1 0 1 1 1 1 0 0 0
1 1 0 0 0 1 1 1 1
1 1 1 0 0 1 0 0 1
208
                                  úÁÄÁÞÉ
  §1. áÌÇÅÂÒÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
1.1. ôÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ

   ëÁÖÄÁÑ ÆÏÒÍÕÌÁ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÏÂÌÁÄÁÅÔ Ó×ÏÊÓÔ×ÏÍ ÐÒÅ×ÒÁ-
ÝÁÔØÓÑ × ×ÙÓËÁÚÙ×ÁÎÉÅ ÐÒÉ ÆÉËÓÁÃÉÉ × ÎÅÊ ÚÎÁÞÅÎÉÊ ×ÓÅÈ ×ÙÓËÁÚÙ×ÁÔÅÌØ-
ÎÙÈ ÐÅÒÅÍÅÎÎÙÈ, ÔÏ ÅÓÔØ ÅÓÌÉ ÍÙ ÚÁÆÉËÓÉÒÕÅÍ × ÆÏÒÍÕÌÅ ÚÎÁÞÅÎÉÑ ×ÓÅÈ
×ÙÓËÁÚÙ×ÁÔÅÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ, ÔÏ, ÐÏÌØÚÕÑÓØ ÏÐÒÅÄÅÌÅÎÉÑÍÉ ÌÏÇÉÞÅÓËÉÈ
ÏÐÅÒÁÃÉÊ, ÍÙ ÍÏÖÅÍ ×ÙÞÉÓÌÉÔØ ÚÎÁÞÅÎÉÅ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ.
   ôÁÂÌÉÃÁ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ ÁÌÇÅÂÒÙ ×ÙÓËÁÚÙ×ÁÎÉÊ ÓÏÄÅÒÖÉÔ ÓÔÏÌØ-
ËÏ ÓÔÒÏË, ÓËÏÌØËÏ ×ÓÅ×ÏÚÍÏÖÎÙÈ ÎÁÂÏÒÏ× ÚÎÁÞÅÎÉÊ ÉÓÔÉÎÎÏÓÔÉ ÐÅÒÅÍÅÎÎÙÈ
ÍÏÖÎÏ ÏÂÒÁÚÏ×ÁÔØ. ëÁÖÄÁÑ ×ÙÓËÁÚÙ×ÁÔÅÌØÎÁÑ ÐÅÒÅÍÅÎÎÁÑ ÍÏÖÅÔ ÐÒÉÎÉ-
ÍÁÔØ ÔÏÌØËÏ Ä×Á ÚÎÁÞÅÎÉÑ (0 É 1), ÐÏÜÔÏÍÕ × ÓÌÕÞÁÅ n ÐÅÒÅÍÅÎÎÙÈ ÔÁÂÌÉÃÁ
ÉÓÔÉÎÎÏÓÔÉ ÓÏÄÅÒÖÉÔ 2n ÓÔÒÏË.
   ðÒÉ ÐÏÓÔÒÏÅÎÉÉ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ ÎÁÂÏÒÙ ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ ÒÁÓ-
ÐÏÌÁÇÁÀÔ Ó×ÅÒÈÕ ×ÎÉÚ × ÌÅËÓÉËÏÇÒÁÆÉÞÅÓËÏÍ ÐÏÒÑÄËÅ (ËÁÖÄÙÊ ÎÁÂÏÒ ÐÏÎÉ-
ÍÁÀÔ ËÁË Ä×ÏÉÞÎÕÀ ÚÁÐÉÓØ ÎÅÏÔÒÉÃÁÔÅÌØÎÏÇÏ ÃÅÌÏÇÏ ÞÉÓÌÁ É ÒÁÓÐÏÌÁÇÁÀÔ
× ÐÏÒÑÄËÅ ×ÏÚÒÁÓÔÁÎÉÑ ÏÔ (000 . . . 0) ÄÏ (111 . . . 1).
   ðÒÉÍÅÒ 1. ðÏÓÔÒÏÉÔØ ÔÁÂÌÉÃÕ ÉÓÔÉÎÎÏÓÔÉ ÆÏÒÍÕÌÙ:
                            x1x2 → (x1 ∨ x2)x3 .
  òÅÛÅÎÉÅ. 1. ïÐÒÅÄÅÌÉÍ ÐÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ × ÆÏÒÍÕÌÅ:
                             21   6     3    54
                          x1 · x2→ (x1 ∨ x2) · x3 .
  2. ðÏÌØÚÕÑÓØ   ÏÐÒÅÄÅÌÅÎÉÑÍÉ ÏÐÅÒÁÃÉÊ ¬, ·, ∨ É →, ÚÁÐÏÌÎÉÍ ÔÁÂÌÉÃÕ.
     x1 x2 x3    x2 x1 · x2 x1 ∨ x2 x3 (x1 ∨ x2)x3 x1x2 → (x1 ∨ x2)x3
     0 0 0        1    0       0    1       0              1
     0 0 1        1    0       0    0       0              1
     0 1 0        0    0       1    1       1              1
     0 1 1        0    0       1    0       0              1
     1 0 0        1    1       1    1       1              1
     1 0 1        1    1       1    0       0              0
     1 1 0        0    0       1    1       1              1
     1 1 1        0    0       1    0       0              1
                                      208

Страницы