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

UptoLike

ВУЗ: 

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

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

Рубрика: 

234 úÁÄÁÞÉ
§7. íÁÛÉÎÁ ôØÀÒÉÎÇÁ
÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÓÏÄÅÒÖÁÔÓÑ ÚÁÄÁÞÉ Ä×ÕÈ ÔÉÐÏ×:
¡ ÐÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ Å¾ ÐÒÉÍÅÎÅÎÉÑ Ë
ÚÁÄÁÎÎÏÍÕ ÓÌÏ×Õ u, ÔÏ ÅÓÔØ ÎÁÊÔÉ T (u);
¡ ÐÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ, ÒÅÛÁÀÝÕÀ ÄÁÎÎÙÊ ËÌÁÓÓ ÚÁÄÁÞ.
ðÒÉ ÒÅÛÅÎÉÉ ÚÁÄÁÞ ×ÔÏÒÏÇÏ ÔÉÐÁ ÒÅËÏÍÅÎÄÕÅÔÓÑ ÄÏ ÓÏÓÔÁ×ÌÅÎÉÑ ÐÒÏÇÒÁÍ-
ÍÙ ÍÁÛÉÎÙ, ÔÏ ÅÓÔØ ÄÏ ÚÁÐÏÌÎÅÎÉÑ ÔÁÂÌÉÃÙ, ÚÁÄÁÀÝÅÊ ÐÒÏÇÒÁÍÍÕ, ÔÝÁ-
ÔÅÌØÎÏ ÐÒÏÄÕÍÁÔØ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÄÏÌÖÅÎ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎ ÐÒÏÇÒÁÍÍÏÊ.
÷ ËÏÎÃÅ ÒÅÛÅÎÉÑ (ËÏÇÄÁ ÐÒÏÇÒÁÍÍÁ ÓÏÓÔÁ×ÌÅÎÁ) ÎÅ ÚÁÂÕÄØÔÅ ÐÒÉÍÅÎÉÔØ Å¾
Ë ÔÅÓÔÏ×ÏÍÕ ÐÒÉÍÅÒÕ.
ðÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ A = {|, ∧} É ÓÌÏ×Õ u ÎÁÊÔÉ
ÓÌÏ×Ï T (u):
453.
q
1
q
2
| ∧q
2
+ 1 | q
2
− 1
∧ | q
0
0 ∧q
1
+ 1
u
1
=||||
u
2
=| ∧∧ |
454.
q
1
q
2
q
3
| | q
3
+ 1 | q
2
0 | q
1
+ 1
∧ | q
2
+ 1 | q
3
+ 1 | q
0
0
u
1
=|||
u
2
=| ∧∧ |
u
3
=|| ∧ ∧ ∧ |
÷ÙÑÓÎÉÔØ, ÐÒÉÍÅÎÉÍÁ ÌÉ ÍÁÛÉÎÁ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ {|, ∧} Ë ÓÌÏ×Õ
u, É × ÓÌÕÞÁÅ ÐÒÉÍÅÎÉÍÏÓÔÉ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ:
455.
q
1
q
2
| ∧q
1
+ 1 ∧q
2
− 1
∧ ∧q
2
− 1 | q
0
+ 1
u
1
=|||
u
2
=|| ∧ |
456.
q
1
q
2
q
3
| ∧q
1
+ 1 | q
1
− 1 | q
2
+ 1
∧ ∧q
2
+ 1 ∧q
3
+ 1 ∧q
0
0
u
1
=|| ∧ |
u
2
=| ∧ ||||
457. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K
2
ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {|}.
458. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K
1
ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {α, β}.
459. ëÁËÕÀ ÆÕÎËÃÉÀ ÎÁÔÕÒÁÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ×ÙÞÉÓÌÑÅÔ ÍÁÛÉÎÁ, ÚÁ-
ÄÁÎÎÁÑ ÐÒÏÇÒÁÍÍÏÊ:
234                                                             úÁÄÁÞÉ

  §7. íÁÛÉÎÁ ôØÀÒÉÎÇÁ
   ÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÓÏÄÅÒÖÁÔÓÑ ÚÁÄÁÞÉ Ä×ÕÈ ÔÉÐÏ×:
    ¡ ÐÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ Å¾ ÐÒÉÍÅÎÅÎÉÑ Ë
ÚÁÄÁÎÎÏÍÕ ÓÌÏ×Õ u, ÔÏ ÅÓÔØ ÎÁÊÔÉ T (u);
   ¡ ÐÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ, ÒÅÛÁÀÝÕÀ ÄÁÎÎÙÊ ËÌÁÓÓ ÚÁÄÁÞ.
   ðÒÉ ÒÅÛÅÎÉÉ ÚÁÄÁÞ ×ÔÏÒÏÇÏ ÔÉÐÁ ÒÅËÏÍÅÎÄÕÅÔÓÑ ÄÏ ÓÏÓÔÁ×ÌÅÎÉÑ ÐÒÏÇÒÁÍ-
ÍÙ ÍÁÛÉÎÙ, ÔÏ ÅÓÔØ ÄÏ ÚÁÐÏÌÎÅÎÉÑ ÔÁÂÌÉÃÙ, ÚÁÄÁÀÝÅÊ ÐÒÏÇÒÁÍÍÕ, ÔÝÁ-
ÔÅÌØÎÏ ÐÒÏÄÕÍÁÔØ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÄÏÌÖÅÎ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎ ÐÒÏÇÒÁÍÍÏÊ.
÷ ËÏÎÃÅ ÒÅÛÅÎÉÑ (ËÏÇÄÁ ÐÒÏÇÒÁÍÍÁ ÓÏÓÔÁ×ÌÅÎÁ) ÎÅ ÚÁÂÕÄØÔÅ ÐÒÉÍÅÎÉÔØ Å¾
Ë ÔÅÓÔÏ×ÏÍÕ ÐÒÉÍÅÒÕ.
   ðÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ A = {|, ∧} É ÓÌÏ×Õ u ÎÁÊÔÉ
ÓÌÏ×Ï T (u):

  453.
                      q1       q2
                                            u1 =||||
                  | ∧q2 + 1 | q2 − 1
                                            u2 =| ∧∧ |
                  ∧ | q0 0 ∧q1 + 1
  454.
                  q1        q2      q3        u1 =|||
             | | q3 + 1 | q 2 0 | q 1 + 1     u2 =| ∧∧ |
             ∧ | q2 + 1 | q 3 + 1 | q 0 0     u3 =|| ∧ ∧ ∧ |

   ÷ÙÑÓÎÉÔØ, ÐÒÉÍÅÎÉÍÁ ÌÉ ÍÁÛÉÎÁ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ {|, ∧} Ë ÓÌÏ×Õ
u, É × ÓÌÕÞÁÅ ÐÒÉÍÅÎÉÍÏÓÔÉ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ:
  455.
                       q1       q2
                                            u1 =|||
                   | ∧q1 + 1 ∧q2 − 1
                                            u2 =|| ∧ |
                   ∧ ∧q2 − 1 | q0 + 1
  456.
                  q1       q2       q3
                                                u1 =|| ∧ |
              | ∧q1 + 1 | q1 − 1 | q2 + 1
                                                u2 =| ∧ ||||
              ∧ ∧q2 + 1 ∧q3 + 1 ∧q0 0
  457. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K2 ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {|}.
  458. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K1 ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {α, β}.
  459. ëÁËÕÀ ÆÕÎËÃÉÀ ÎÁÔÕÒÁÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ×ÙÞÉÓÌÑÅÔ ÍÁÛÉÎÁ, ÚÁ-
ÄÁÎÎÁÑ ÐÒÏÇÒÁÍÍÏÊ:

Страницы