Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Обнинский институт атомной энергетики НИЯУ МИФИ

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Метода

.pdf

Скачиваний:

Добавлен:

11.06.2015

Размер:

608.11 Кб

Скачать

☆

<<< < Предыдущая 1 23 / 83 4 5 6 7 8 > Следующая >>>

EE \RBRANOWOJ OBLASTI H WNA^ALE PRIWODQT FORMULU P(x1; : : : ; xn) K KON_@NKTIWNOJ NORMALXNOJ FORME I POLU^A@T REZOLXWENTY PO PRAWILU (A _ B)(A _ C) = (A_ B)(A_ C)(B _ C) S CELX@ POLU^ITX DIZ_@NKTY WIDA Q I Q .

dLQ UNIFIKACII IME@]IHSQ \LEMENTARNYH KON_@NKCIJ MOVNO

ISPOLXZOWATX PODSTANOWKI WIDA (x1jjt1; x2jjt2; : : : ; xnjjtn) , GDE PERE-

MENNYE xi

I TERMY ti BERUTSQ IZ PREOBRAZUEMOJ FORMULY.

pRIMER 4. dOKAZATX F1; F2 ` F , GDE F1 = 8x (P (x)

! Q(x)) ,

F2 = 8x (Q(x) ! R(x)) , F = 8x (P (x)

! R(x)) .

K SKOLEMOWSKOJ

rE[ENIE. pREOBRAZUEM FORMULU

G = F1F2F

FORME: G = 8x (P (x) _Q(x))

^8x (

Q(x) _R(x)) ^9x (P (x) ^ R(x)) =

= 9y 8

x ((P

(x) _ Q(x))

(x) _ R(x)) ^ P(y

) ^ R

(y)) =

= 8x((P (x) _ Q(x)) ^ (Q(x) _ R(x)) ^ P

(a) ^ R(a)) .

dALEE NAHODIM REZOLXWENTY POLU^ENNYH ^ETYREH DIZ_@NKTOW

G1 = P (x)

_ Q(x) , G2 = Q(x) _ R(x) , G3 = P (a) I G4 = R(a) :

G5 = Q(a)

{ REZOLXWENTA G1(xjja) I G3 ,

G6 = Q(a)

{ REZOLXWENTA G2(xjja) I G4 .

w REZULXTATE POLU^ILOSX, ^TO G5 G6 = Q(a) Q(a) = 0 . oTS@DA

SLEDUET, ^TO G = 0 W \RBRANOWOJ OBLASTI H = fag .

pRIMER 5. dOKAZATX, ^TO F1; F2 `

F , ESLI F1 = 8x 9y P (x; y) ,

F2 = 8x 8y (P (x; y) ! P (y; x)) , F = 8y 9x P(x; y) .

rE[ENIE. w \TOM PRIMERE IZ FORMULY G = F1F2F

POSLE PE-

REIMENOWANIQ SWQZANNYH PEREMENNYH I PRIWEDENIQ K SKOLEMOWSKOJ

FORME POLU^A@TSQ SLEDU@]IE DIZ_@NKTY:

G1 = P(x; f(x)) , G2 = q P (u; v) P (v; u) I G3 = q P (w; a) .

nAJDEM REZOLXWENTU G4 = q P(a; w)_ FORMUL G2(v

w; u

a) I G3 .

pOSKOLXKU

G1(x a) = P (a; f(a)) , A G4(w

f(a)) =

q P(a; f(a)) , TO

FORMULA G LOVNA W \RBRANOWOJ OBLASTI H = fa; f(a); f(f(a)); : : : g .

x15. iS^ISLENIE S RAWENSTWOM

kONKRETNYE AKSIOMATI^ESKIE TEORII POLU^A@TSQ IZ IS^ISLENIQ PREDIKATOW DOBAWLENIEM SOBSTWENNYH AKSIOM, PREDMETNYH KONSTANT, PREDIKATNYH I FUNKCIONALXNYH SIMWOLOW.

w KA^ESTWE PRIMERA RASSMOTRIM AKSIOMATI^ESKU@ TEORI@ S RAWENSTWOM (EQ).

k IS^ISLENI@ PREDIKATOW DOBAWIM KONKRETNYJ PREDIKAT P (x; y) , KOTORYJ OBOZNA^IM ^EREZ x = y I DWE NOWYE AKSIOMY:

Eq1 8x (x = x) ,

Eq2 (x = y) ! (F (x) ! F (x==y)) ,

GDE ^ASTI^NAQ PODSTANOWKA F(x==y)) OZNA^AET PRAWILXNU@ ZAMENU W FORMULE NEKOTORYH WHOVDENIJ PEREMENNOJ x NA PEREMENNU@ y .

sWOJSTWO 1. w TEORII S RAWENSTWOM ` t = t , GDE t { TERM. dOKAZATELXSTWO SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1)	` 8x (x = x)	{ AKSIOMA Eq1 ;
2)	` 8x (x = x)	! (t = t) { AKSIOMA P 1 IS^ISLENIQ PREDIKATOW;
3)	` (t = t) { IZ 1) I 2) PO PRAWILU modus ponens.

sWOJSTWO 2. w TEORII EQ IMEET MESTO SIMMETRI^NOSTX RAWENSTWA, T.E. x = y ` y = x .

dOKAZATELXSTWO SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1) ` (x = y) ! ((x = x) ! (y = x)) { AKSIOMA Eq2 , W KOTOROJ W KA^ESTWE F(x) WZQLI FORMULU x = x ;

2) x = y ` (x = x) ! (y = x) { IZ 1) PO TEOREME DEDUKCII; 3) x = y; x = x ` y = x { IZ 2) PO TEOREME DEDUKCII;

4) ` x = x { PO SWOJSTWU 1;

5) x = y ` y = x { IZ 3) UDALENIEM WYWODIMOJ GIPOTEZY x = x .

sWOJSTWO 3. w TEORII EQ IMEET MESTO TRANZITIWNOSTX RAWENST-

WA, T.E. x = y; y = z ` x = z .

dOKAZATELXSTWO SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1) ` (y = x) ! ((y = z) ! (x = z)) { AKSIOMA Eq2 , W KOTOROJ W KA^ESTWE F(y) WZQLI FORMULU y = z ;

2) y = x ` (y = z) ! (x = z) { IZ 1) PO TEOREME DEDUKCII; 3) x = y ` y = x { PO SWOJSTWU 2;

4) x = y ` (y = z) ! (x = z) { IZ 3) I 2) PO TRANZITIWNOSTI WYWODA;

5) x = y; y = z ` x = z { IZ 4) PO TEOREME DEDUKCII.

x16. fORMALXNAQ ARIFMETIKA

fORMALXNAQ ARIFMETIKA POLU^AETSQ IZ TEORII S RAWENSTWOM DOBAWLENIEM KONSTANTY 0, WWEDENIEM FUNKCIONALXNYH SIMWOLOW

f(x; y) = x + y ,					g(x; y) = x y ,	next(x) = x0
I DOBAWLENIEM SLEDU@]IH SOBSTWENNYH AKSIOM:
(Ar1)		F (0) ! (8x (F (x) ! F (x0))				! 8x F(x)) ,
(Ar2) (t10 = t20 ) ! (t1 = t2) ,
(Ar3) (t1 = t2) ! (t10 = t20 ) ,
		6
(Ar4)		t0 = 0 ,
(Ar5)		t + 0 = t0 ,
(Ar6) t1			+ t0	= (t1 + t2)0 ,
			2
(Ar7)		t	0 = 0 ,
(Ar8) t1			t20 = t1		t2 + t1 .
aKSIOMU			Ar1	NAZYWA@T PRINCIPOM MATEMATI^ESKOJ INDUKCII.
pRIWEDEM DRUGU@ FORMULIROWKU \TOGO PRINCIPA.
sWOJSTWO 1. eSLI					` F(0) I ` F (x) ! F(x0) , TO ` 8x F (x) .
dOKAZATELXSTWO SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:
1)	` F (x) ! F (x0)				{ DANO PO USLOWI@;
2)	` 8x(F(x)			! F(x0)) { IZ 1) PO PRAWILU OBOB]ENIQ;
3)	` F (0)		{ DANO PO USLOWI@;
4)	` F (0)		! (8x (F (x) ! F (x0)) ! 8x F(x)) { AKSIOMA Ar1 ,
5)	` 8x(F(x)			! F (x0)) ! 8x F (x)		{ IZ 3) I 4) PO PRAWILU MP ,
6)	` 8x F (x)			{ IZ 2) I 5) PO PRAWILU MP .
sWOJSTWO 1 DOKAZANO.

mODELX@ DLQ FORMALXNOJ ARIFMETIKI QWLQETSQ MNOVESTWO N0 S OBY^NYMI OPERACIQMI SLOVENIQ I UMNOVENIQ, A next(x) = x + 1 . w OTLI^IE OT IS^ISLENIQ WYSKAZYWANIJ I IS^ISLENIQ PREDIKATOW FORMALXNAQ ARIFMETIKA NE QWLQETSQ POLNOJ. mY PRIWEDEM BEZ

DOKAZATELXSTWA FORMULIROWKU TEOREMY O EE NEPOLNOTE.

tEOREMA gEDELQ O NEPOLNOTE. sU]ESTWUET ZAMKNUTAQ FOR-

MULA F TAKAQ, ^TO W FORMALXNOJ ARIFMETIKE NE WYWODITSQ KAK FORMULA F , TAK I EE OTRICANIE F .

x17. nE^ETKAQ LOGIKA, OPERACII DIZ_@NKCII,

KON_@NKCII I OTRICANIQ

w NE^ETKOJ LOGIKE RASSMATRIWA@TSQ FUNKCII y = f(x1; : : : ; xn) ,

GDE xi 2 [0; 1] PRI i = 1; 2; : : : ; n I y 2 [0; 1] .

oPREDELENIE 1. zNA^ENIQ NE^ETKOJ DIZ_@NKCII I KON_@NKCII OPREDELQ@TSQ PO FORMULAM y = x1_x2 = max(x1; x2) I y = x1^x2 = = min(x1; x2) .

sLEDU@]IE SWOJSTWA NE^ETKOJ DIZ_@NKCII I KON_@NKCII TAKIE VE, KAK I DLQ DWUZNA^NOJ LOGIKI:

1) a _ 0 = a,		1') a ^ 0 = 0,
2) a _ 1 = 1,		2') a ^ 1 = a,
3) a _ a = a,		3') a ^ a = a,
4) a _ b = b _ a,		4') a ^ b = b ^ a,
5)	a _ (b _ c) = (a _ b) _ c,	5') a ^ (b ^ c) = (a ^ b) ^ c,	^ c,
6)	ESLI a 6 b, TO a _ c 6 b _ c,	6') ESLI a 6 b, TO a ^ c 6 b
7)	a ^ (b _ c) = (a ^ b) _ (a ^ c),	7') a_(b ^c) = (a _b) ^(a^c).
sWOJSTWA 1 { 6 I 1' { 6' NEPOSREDSTWENNO WYTEKA@T IZ OPREDE-

LENIQ;

PRIWEDEM DOKAZATELXSTWO SWOJSTWA 7. pUSTX b 6 c ,

TOGDA

a ^ (b _ c) = a ^ c I (a ^ b) _ (a ^ c) = a ^ c , T.K. a ^ b 6 a

^ c PO

SWOJSTWU 6'. sWOJSTWO 7' DOKAZYWAETSQ ANALOGI^NO.

oPREDELENIE 2. zNA^ENIE NE^ETKOGO OTRICANIQ OPREDELQETSQ

PO FORMULE y =

= 1

; x .

sLEDU@]IE SWOJSTWA NE^ETKOGO OTRICANIQ SOWPADA@T SO SWOJ-

STWAMI OTRICANIQ W DWUZNA^NOJ LOGIKE:

11) ESLI a 6 b, TO

> b,

0 = 1,

1 = 0,

12) a ^ b =

_ b,

10)

= a,

13) a _ b =

^ b.

dOKAZATELXSTWO SWOJSTW 8 { 11 O^EWIDNO; DOKAVEM SWOJSTWO 12. pUSTX a 6 b , TOGDA a ^ b = a , T.K. a ^ b = a ; A a _ b = a POTOMU, ^TO a > b . sWOJSTWO 13 DOKAZYWAETSQ ANALOGI^NO.

oPREDELENIE 3. fUNKCIQ y

= x

NAZYWAETSQ PROTIWORE^IEM,

OBOZNA^AETSQ

y = x.

iZ \TOGO OPREDELENIQ WYTEKA@T SLEDU@]IE SWOJSTWA:

x; ESLI 0

6 x 6

;

14) x =

15) x 6

PRI WSEH x

[0; 1].

x; ESLI

6 x 6 1;

nE^ETKAQ IMPLIKACIQ I \KWIWALENCIQ

oPREDELENIE 4. fUNKCIQ y = x _

NAZYWAETSQ TAWTOLOGIEJ,

OBOZNA^AETSQ

y = x_ .

iZ \TOGO OPREDELENIQ WYTEKA@T SLEDU@]IE SWOJSTWA:

x; ESLI 0

6 x 6

;

16) x_ =

x; ESLI

17)

x_ >

PRI WSEH x

[0; 1].

6 x 6 1;

zAMETIM, ^TO W DWUHZNA^NOJ LOGIKE x ^

0 , A x _

1 , ^TO

NE IMEET MESTA W NE^ETKOJ LOGIKE.

oPREDELENIE 5. fUNKCIQ y = f(x)

NAZYWAETSQ PROTIWORE^I-

WOJ, ESLI f(x) 6

DLQ WSEH x

[0; 1] .

pRIMEROM PROTIWORE^IWOJ FUNKCII QWLQETSQ y = x.

oPREDELENIE 6. fUNKCIQ y = f(x)

NAZYWAETSQ OB]EZNA^IMOJ,

ESLI f(x) >

DLQ WSEH x 2 [0; 1] .

w KA^ESTWE PRIMERA OB]EZNA^IMOJ FUNKCII MOVNO PRIWESTI TAWTOLOGI@ y = x_ .

x18.

oPREDELENIE 1. nE^ETKAQ IMPLIKACIQ OPREDELQETSQ PO FOR-

MULE a ! b =

_ b .

iZ \TOGO OPREDELENIQ WYTEKA@T SLEDU@]IE SWOJSTWA:

! a = 1 ,

! 1 =

3) a

! a = a

_ a = a.

oPREDELENIE 2. nE^ETKU@ \KWIWALENCI@ MOVNO OPREDELITX PO

FORMULE a b = (a ! b)

(b ! a) .

oTMETIM SLEDU@]IE SWOJSTWA NE^ETKOJ \KWIWALENCII:

b = (

a) ,

5) a

a =

_ a = a,

b = (a

^ b)

_ (

^ b) .

dOKAVEM SWOJSTWO 6. dLQ \TOGO RAZBEREM DWA SLU^AQ.

1. pUSTX a 6 b , TOGDA

> b , A IZ NIH WYWODITSQ, ^TO

aa _ bb ==

=) (

_ b) ^ (a _ b) =

^ b =) a b =

^ b .

s DRUGOJ STORONY,

a 6 b

=) a^b 6 a^b =) (a^b)_(a^b) = a^b ,

> b

SLEDOWATELXNO, a b = (a ^ b) _ (a ^ b) . 25

2. sLU^AJ a > b RAZBIRAETSQ ANALOGI^NO.

zAME^ANIE. mOVNO WWESTI W NE^ETKOJ LOGIKE I OSTALXNYE LOGI- ^ESKIE OPERACII PO FORMULAM

xy = x y { "ISKL@^A@]EE ILI",

xj y = x _ y { [TRIH {EFFERA,

x# y = x ^ y { STRELKA pIRSA.

x19. nE^ETKIE MNOVESTWA

nE^ETKOE ZNA^ENIE WYSKAZYWANIQ P BUDEM OBOZNA^ATX (P) . oPREDELENIE 1. mNOVESTWO A NAZYWAETSQ NE^ETKIM, ESLI ZA-

DANA FUNKCIQ PRINADLEVNOSTI, KOTORAQ PO L@BOMU EGO \LEMENTU x

OPREDELQET ^ISLO A (x)

[0; 1] , RAWNOE NE^ETKOMU ZNA^ENI@ PRE-

DIKATA x

A , T.E.

(x)2= (x

A) . dLQ WSEH OSTALXNYH \LEMEN-

TOW x 2

U n A , GDE

U {

UNIWERSUM, S^ITAETSQ PO UMOL^ANI@, ^TO

A (x) = 0 .

zAME^ANIE. oBY^NOE (^ETKOE) MNOVESTWO A MOVNO S^ITATX NE-

^ETKIM S FUNKCIEJ PRINADLEVNOSTI A (x) = 1 , ESLI x

A I

A (x) = 0 ,

ESLI x = A .

pRIMER

1. zADADIM NE^ETKIE MNOVESTWA A I B TAKIM OBRAZOM:

A = f0:3=x1 ; 1=x2; 0:8=x3; 0=x4g

, B = f0=x1; 0:7=x2; 0:9=x3; 0:5=x4g;

IZ \TOJ ZAPISI SLEDUET, ^TO A (x1) = 0:3 , A (x2) = 1 , B (x1) = 0

I T.D.

oPREDELENIE 2. dLQ NE^ETKIH MNOVESTW MOVNO OPREDELITX OT-

NO[ENIQ RAWENSTWA I PODMNOVESTWA:

A = B , ESLI

x( A (x) = B (x)) ;

B , ESLI

8x(

(x) 6 (x)) .

x( A (x) = 0) , TO MNOVESTWO A S^ITAETSQ

zAMETIM, ^TO, ESLI

PUSTYM, A = ? .

oPREDELENIE 3. fUNKCII PRINADLEVNOSTI DLQ DOPOLNENIQ, PE-

RESE^ENIQ I OB_EDINENIQ NE^ETKIH MNOVESTW OPREDELQ@TSQ TAK:

(x) = A (x) = 1 A (x) ,

;

A\B (x) = A (x)

B (x) = min( A (x); B (x)) ,

A[B (x) = A (x) _ B (x) = max( A (x); B (x)) .

iZ OPREDELENIJ 2, 3 I SWOJSTW OTRICANIQ, KON_@NKCII I DIZ_- @NKCII SLEDUET, ^TO NA NE^ETKIE MNOVESTWA PERENOSQTSQ OBY^NYE

SWOJSTWA OPERACIJ DOPOLNENIQ, PERESE^ENIQ I OB_EDINENIQ. oTMETIM NEKOTORYE IZ \TIH SWOJSTW.

1) A \ A = A.

1') A [ A = A.

2) A\(B[C

)

= (A\B)[(A\C).

2') A[(B\C) = (A[B)\(A[C).

3) A \ B

= A [ B.

3') A [ B = A \ B.

oPREDELENIE 4. wWEDEM OPERACII WOZWEDENIQ W STEPENX, UMNO-

VENIQ I SLOVENIQ NE^ETKIH MNOVESTW, ZADAWAQ IH FUNKCII PRINAD-

LEVNOSTI TAKIM OBRAZOM:

n (x) = n (x)

PRI n > 0 ,

B (x) ,

A B (x) = A (x)

A+B (x) = A (x) + B (x) ; A (x) B (x) .

oTMETIM NEKOTORYE SWOJSTWA WWEDENNYH OPERACIJ.

A PRI n > 1.

1') A

An PRI n 6 1.

B A \ B.

2') A

[ B A +

B = A + B.

4') A + B = A B.

pRIMER 2. eSLI A I B { MNOVESTWA, DANNYE W PRIMERE 1, TO

\ B = f0=x1; 0:7=x2; 0:8=x3; 0=x4g ,

[ B = f0:3=x1; 1=x2; 0:9=x3; 0:5=x4g ,

A2 = f0:09=x1 ; 1=x2; 0:64=x3 ; 0=x4g ,

B = f0=x1; 0:7=x2 ; 0:72=x3; 0=x4g ,

A + B = f0:3=x1 ; 1=x2; 0:98=x3 ; 0:5=x4g .

pRIMER 3. pUSTX NE^ETKIE ZNA^ENIQ PREDIKATOW p = (x 2 A) ,

q = (x 2 B) I r = (x 2 C) SLEDU@]IE: p = 0; 2 ,

q = 0; 4 I r = 0; 7 .

nAJTI NE^ETKOE ZNA^ENIE PREDIKATA s = (x 2 A \ (B [ C)) .

rE[ENIE. pOSKOLXKU s =

^ (q _ r) , TO PODSTAWLQQ ZNA^ENIQ

p; q; r , POLU^AEM, ^TO s = 0; 8 ^

(0; 4 _ 0; 7) = 0; 8 ^ 0; 7 = 0; 7 .

oTWET. nE^ETKOE ZNA^ENIE PREDIKATA s RAWNO 0; 7 .

ti , TO

xi , xi .

g l a w a 2 rekursiwnye funkcii

x1. iNTUITIWNOE PONQTIE ALGORITMA

iNTUITIWNO POD ALGORITMOM PONIMA@T INSTRUKCI@, POZWOLQ@- ]U@ IZ NA^ALXNYH DANNYH ^EREZ KONE^NOE ^ISLO WPOLNE OPREDELENNYH [AGOW POLU^ITX WYHODNYE DANNYE (REZULXTAT).

eSLI PRIMENITX ALGORITM A K NA^ALXNYM DANNYM x0 , TO POSLE WYPOLNENIQ i -TOGO [AGA POLU^A@TSQ PROMEVUTO^NYE DANNYE ^TO OBOZNA^A@T TAK: A : x0 ! x1 ! : : : ! xi ILI A : x0 ) pRI \TOM IME@TSQ DWE WOZMOVNOSTI.

1. eSLI ALGORITM OSTANAWLIWAETSQ ^EREZ n [AGOW, TO GOWORQT, ^TO A PRIMENIM K x0 , REZULXTATOM PRIMENENIQ QWLQETSQ xn I PI[UT TAK: A : x0 ` xn ILI A(x0) = xn .

2. eSLI ALGORITM A PRI PRIMENENII K x0 RABOTAET BESKONE^NO DOLGO, T.E. A : x0 ! x1 ! x2 ! : : : , TO GOWORQT, ^TO A NE PRIMENIM

K x0 I PI[UT TAK: A : x0 ` .

oBY^NO K ALGORITMAM PRED_QWLQ@T SLEDU@]IE TREBOWANIQ. 1. dISKRETNOSTX ALGORITMA OZNA^AET, ^TO ON RABOTAET POSLE-

DOWATELXNO; ESLI ZNA^ENIE xi POLU^AETSQ W MOMENT WREMENI

t0 < t1 < : : : < ti .

2.dETERMINIROWANNOSTX ALGORITMA OZNA^AET, ^TO ZNA^ENIE xi+1 ODNOZNA^NO OPREDELQETSQ ZNA^ENIEM xi .

3.|LEMENTARNOSTX [AGOW ALGORITMA OZNA^AET, ^TO NA KAVDOM [AGE WYPOLNQETSQ NEKOTOROE PROSTOE DEJSTWIE.

4.rEZULXTATIWNOSTX ALGORITMA NE DOPUSKAET OSTANOWKI EGO RABOTY BEZ POLU^ENIQ REZULXTATA.

5.mASSOWOSTX ALGORITMA PREDPOLAGAET, ^TO OBLASTX NA^ALXNYH DANNYH DOLVNA BYTX POTENCIALXNO BESKONE^NOJ.

x1; : : : ; xn; y

pRIMER. aLGORITM eWKLIDA NAHOVDENIQ NAIBOLX[EGO OB]EGO DELITELQ NATURALXNYH ^ISEL m I n SOSTOIT IZ SLEDU@]IH [AGOW.

1.nAHODIM OSTATOK r OT DELENIQ m NA n . eSLI r 6= 0 , TO PEREHODIM K [AGU 2; ESLI r = 0 , TO PEREHODIM K [AGU 3.

2.m := n , n := r I PEREHODIM K [AGU 1.

3.aLGORITM OSTANAWLIWAETSQ, TEKU]EE ZNA^ENIE n QWLQETSQ ISKOMYM REZULXTATOM.

zADA^A (PROBLEMA) NAZYWAETSQ ALGORITMI^ESKI RAZRE[IMOJ, ESLI SU]ESTWUET ALGORITM, KOTORYJ RE[AET \TU ZADA^U.

zADA^A NAHOVDENIQ NAIBOLX[EGO OB]EGO DELITELQ NATURALXNYH ^ISEL QWLQETSQ ALGORITMI^ESKI RAZRE[IMOJ; SOOTWETSTWU@]IJ ALGORITM PRIWEDEN W PRIMERE.

dESQTAQ PROBLEMA gILXBERTA. sU]ESTWUET LI ALGORITM, POZWOLQ@]IJ OPREDELITX DLQ L@BOGO MNOGO^LENA S CELYMI KO\FFICIENTAMI OT NESKOLXKIH PEREMENNYH NALI^IE U NEGO CELO^ISLENNYH KORNEJ?

`.w. mATIQSEWI^ W 1970 G. DOKAZAL, ^TO \TA PROBLEMA QWLQETSQ ALGORITMI^ESKI NERAZRE[IMOJ.

dLQ DOKAZATELXSTWA ALGORITMI^ESKOJ NERAZRE[IMOSTI PROBLEM TREBUETSQ UTO^NENIE PONQTIQ ALGORITMA. iSTORI^ESKI SLOVILISX TRI OSNOWNYH MODELI ALGORITMA: REKURSIWNYE FUNKCII, MA[INY tX@RINGA I NORMALXNYE ALGORIFMY mARKOWA.

x2. pONQTIE PRIMITIWNO REKURSIWNOJ FUNKCII

bUDEM RASSMATRIWATX FUNKCII y = fn(x1 ; : : : ; xn) TAKIE, ^TO 2 N0 , ZDESX N0 = f0; 1; 2; : : : ; g | MNOVESTWO CELYH

NEOTRICATELXNYH ^ISEL, INDEKS n W OBOZNA^ENII fn BUDEM ^ASTO OPUSKATX.

pRI \TOM, FUNKCIQ f NAZYWAETSQ WS@DU OPREDELENNOJ, ESLI D(f) = N0 N0 : : : N0 , T.E. ONA OPREDELENA DLQ L@BYH ZNA^E- NIJ SWOIH ARGUMENTOW; W PROTIWNOM SLU^AE FUNKCIQ f NAZYWAETSQ ^ASTI^NOJ.

oPREDELENIE 1. sLEDU@]IE FUNKCII NAZYWA@TSQ ISHODNYMI: 1) Z1(x) 0 | NULX-FUNKCIQ,

2)N1(x) = x + 1 | FUNKCIQ SLEDOWANIQ (next),

3)Ikn(x1; x2 ; : : : ; xn) = xk | SELEKTORNYE FUNKCII, 1 6 k 6 n .

oPREDELENIE 2. gOWORQT, ^TO FUNKCIQ hm POLU^AETSQ PRIMENENIEM OPERATORA SUPERPOZICII S K FUNKCIQM fn , g1m; : : : ; gnm ;

PI[UT h = S(f; g1; : : : ; gn) , ESLI

h(x1; : : : ; xm) = f(g1(x1; : : : ; xm); : : : ; gn(x1; : : : ; xm)) .

zAME^ANIE 1. oGRANI^ENIE, SWQZANNOE S TEM, ^TO WSE FUNKCII gi ZAWISQT OT ODNOGO I TOGO VE ^ISLA ARGUMENTOW, MOVNO SNQTX S POMO]X@ SELEKTORNYH FUNKCIJ. nAPRIMER, NESTANDARTNU@ SUPERPO-

ZICI@ F (t1; t2; t3) = f(t3; t1; g1(t1; t2; t3); g2(t2)) MOVNO PREDSTAWITX

TAK: f(I33(t1; t2; t3); I13(t1; t2; t3); g1(t1; t2; t3); g2(I23(t1; t2; t3))) .

oPREDELENIE 3. gOWORQT, ^TO FUNKCIQ fn+1 POLU^AETSQ PRI-

MENENIEM OPERATORA PRIMITIWNOJ REKURSII R K FUNKCIQM gn I hn+2 ; PI[UT f = R(g; h) , ESLI

1)f(t1; : : : ; tn; 0) = g(t1; : : : ; tn) ;

2)f(t1; : : : ; tn; x + 1) = h(t1; : : : ; tn; x; f(t1; : : : ; tn; x)) DLQ ZNA-

^ENIJ x = 0; 1; 2; : : : .

w ^ASTNOSTI, PRI n = 0 POLU^AEM f1 = R(c; h2) PO SHEME

1) f(0) = c , GDE c 2 N0 , 2) f(x + 1) = h(x; f(x)) . oPREDELENIE 4. fUNKCIQ NAZYWAETSQ PRIMITIWNO REKURSIWNOJ

(P-R), ESLI ONA MOVET BYTX POLU^ENA IZ ISHODNYH PRIMENENIEM KONE^NOGO ^ISLA OPERATOROW SUPERPOZICII I PRIMITIWNOJ REKURSII.

zAME^ANIE 2. iZ OPREDELENIQ 4 SLEDUET, ^TO, ESLI FUNKCIQ POLU- ^ENA IZ PRIMITIWNO REKURSIWNYH FUNKCIJ S POMO]X@ OPERATORA S ILI R , TO ONA MOVET BYTX POLU^ENA I IZ ISHODNYH FUNKCIJ PRIMENENIEM KONE^NOGO ^ISLA OPERATOROW S I R I, SLEDOWATELXNO, QWLQETSQ PRIMITIWNO REKURSIWNOJ.

zAME^ANIE 3. wSE ISHODNYE FUNKCII QWLQ@TSQ WS@DU OPREDELENNYMI I \TO SWOJSTWO SOHRANQETSQ PRI PRIMENENII OPERATOROW S I R , PO\TOMU L@BAQ PRIMITIWNO REKURSIWNAQ FUNKCIQ WS@DU OPREDELENA.

pRIMER. pOSTOQNNAQ FUNKCIQ C(x) = c , c 2 N0 QWLQETSQ PRIMITIWNO REKURSIWNOJ, T.K. C(x) = N(: : : N(Z(x)) : : : ) , GDE PRISUTSTWU@T c \KZEMPLQROW N .

<<< < Предыдущая 1 23 / 83 4 5 6 7 8 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
19.11.2019476.16 Кб8Метод.ук. по магистрам.doc
#
14.08.2019357.38 Кб7Метод.указ.для преподавателейc.doc
#
11.06.2015864.26 Кб379Метода по ФК(Маломужев).DOC
#
11.06.2015961.02 Кб121Метода по ФК(Маломужев).DOC
#
11.06.2015418.82 Кб21Метода пролог.doc
#
11.06.2015608.11 Кб16Метода.pdf
#
11.06.2015598.02 Кб34Метода_Организация_ЭВМ.DOC
#
29.08.201933.11 Кб8Методика Тревожность.docx
#
11.06.2015544.77 Кб23Методич. рекомендации.doc
#
11.06.201557.86 Кб119Методические наработки по стоматологии.docx
#
11.06.2015208.38 Кб29Методические указания по выполнению лабораторных работ и расчету доз возможного облучения.doc