Метода

ministerstwo obrazowaniq rossijskoj federacii

obninskij institut atomnoj |nergetiki

a. z. nasyrow, z. h. nasyrow

matemati~eskaq logika

i teoriq algoritmow

u^EBNOE POSOBIE

obninsk 2003

udk 519.4

nASYROW a. z., nASYROW z. h. mATEMATI^ESKAQ LOGIKA I TEORIQ ALGORITMOW. u^EBNOE POSOBIE. { oBNINSK: iat|, 2003, { 80 S.

dANNOE POSOBIE PREDNAZNA^ENO DLQ IZU^ENIQ MATEMATI^ESKOJ LOGIKI I TEORII ALGORITMOW STUDENTAMI DNEWNOJ, ZAO^NOJ I WE^ERNEJ FORM OBU^ENIQ. pOSOBIE SODERVIT U^EBNYJ MATERIAL PO AKSIOMATI^ESKIM SISTEMAM, REKURSIWNYM FUNKCIQM, MA[INAM tX@RINGA, SLOVNOSTI ALGORITMOW, FORMALXNYM QZYKAM I GRAMMATIKAM W W WIDE RAS[IRENNOGO KONSPEKTA LEKCIJ.

iLL. 8, TABL. 6

c nASYROW a.z., nASYROW z.h., 2003 G.

c oBNINSKIJ INSTITUT ATOMNOJ \NERGETIKI, 2003 G.

sodervanie

gLAWA 1. mATEMATI^ESKAQ LOGIKA . . . . . . . . . . . . . . . . . . 5 x1. pONQTIE AKSIOMATI^ESKOJ TEORII . . . . . . . . . . . . . . 5 x2. oPREDELENIE IS^ISLENIQ WYSKAZYWANIJ . . . . . . . . . . 6 x3. tEOREMA DEDUKCII W IS^ISLENII WYSKAZYWANIJ . . . . . . 8 x4. dWOJNOE OTRICANIE W IS^ISLENII WYSKAZYWANIJ . . . . . 9 x5. dOKAZATELXSTWO OT PROTIWNOGO W IS^ISLENII

WYSKAZYWANIJ . . . . . . . . . . . . . . . . . . . . . . . . . 10 x6. wWEDENIE KON_@NKCII W IS^ISLENII WYSKAZYWANIJ. . . . 10 x7. zAKON PROTIWORE^IQ W IS^ISLENII WYSKAZYWANIJ. . . . . 11 x8. iNTERPRETACIQ I NEPROTIWORE^IWOSTX . . . . . . . . . . . 11 x9. pOLNOTA IS^ISLENIQ WYSKAZYWANIJ . . . . . . . . . . . . . 13 x10. mETOD REZOL@CIJ W IS^ISLENII WYSKAZYWANIJ . . . . . . 14 x11. nEKLAUZALXNOE PRAWILO REZOL@CIJ . . . . . . . . . . . . . 15 x12. oPREDELENIE IS^ISLENIQ PREDIKATOW. . . . . . . . . . . . 16 x13. iNTERPRETACIQ I NEPROTIWORE^IWOSTX ip . . . . . . . . 18 x14. mETOD REZOL@CIJ W IS^ISLENII PREDIKATOW. . . . . . . . 19 x15. iS^ISLENIE S RAWENSTWOM . . . . . . . . . . . . . . . . . . 21 x16. fORMALXNAQ ARIFMETIKA. . . . . . . . . . . . . . . . . . . 23 x17. nE^ETKAQ LOGIKA, OPERACII DIZ_@NKCII,

KON_@NKCII I OTRICANIQ . . . . . . . . . . . . . . . . . . 24 x18. nE^ETKAQ IMPLIKACIQ I \KWIWALENCIQ . . . . . . . . . . . 25 x19. nE^ETKIE MNOVESTWA . . . . . . . . . . . . . . . . . . . . . 26

gLAWA 2. rEKURSIWNYE FUNKCII . . . . . . . . . . . . . . . . . . . 28 x1. iNTUITIWNOE PONQTIE ALGORITMA . . . . . . . . . . . . . . 28 x2. pONQTIE PRIMITIWNO REKURSIWNOJ FUNKCII . . . . . . . . 29 x3. oSNOWNYE PRIMITIWNO REKURSIWNYE FUNKCII . . . . . . . 31 x4. pRIMITIWNO REKURSIWNYE PREDIKATY . . . . . . . . . . . 32 x5. oGRANI^ENNYE SUMMY, PROIZWEDENIQ, KWANTORY. . . . . . 33 x6. oGRANI^ENNYJ OPERATOR NAIMENX[EGO ZNA^ENIQ . . . . . 33 x7. nUMERACIQ pEANO . . . . . . . . . . . . . . . . . . . . . . . 35

3

x8. ~ASTI^NO REKURSIWNYE FUNKCII. tEZIS ~ER^A . . . . . . 38

gLAWA 3. mA[INY tX@RINGA. . . . . . . . . . . . . . . . . . . . . 39 x1. pONQTIE MA[INY tX@RINGA, PRIMERY . . . . . . . . . . . 39 x2. wY^ISLENIE FUNKCIJ MA[INAMI tX@RINGA . . . . . . . . 41 x3. kOPIROWANIE ^ISLA MA[INOJ tX@RINGA . . . . . . . . . . 42 x4. pERESTANOWKA ^ISEL MA[INOJ tX@RINGA . . . . . . . . . . 43 x5. kOMPOZICIQ MA[IN tX@RINGA. . . . . . . . . . . . . . . . 44 x6. kOPIROWANIE n ^ISEL MA[INOJ tX@RINGA . . . . . . . . 46 x7. wY^ISLENIE SELEKTORNYH FUNKCIJ I SUPERPOZICII

FUNKCIJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 x8. wY^ISLENIE FUNKCIJ, ZADAWAEMYH OPERATOROM

PRIMITIWNOJ REKURSII . . . . . . . . . . . . . . . . . . . . 48 x9. wY^ISLENIE FUNKCIJ, ZADAWAEMYH -OPERATOROM.

tEOREMA tX@RINGA . . . . . . . . . . . . . . . . . . . . . . 50 x10. fORMULA kLINI . . . . . . . . . . . . . . . . . . . . . . . . 51 x11. uNIWERSALXNAQ MA[INA tX@RINGA . . . . . . . . . . . . . 53 x12. nERAZRE[IMOSTX ZADA^I OSTANOWA . . . . . . . . . . . . . 55

gLAWA 4. fORMALXNYE QZYKI I GRAMMATIKI . . . . . . . . . . . . 56 x1. pONQTIE FORMALXNOGO QZYKA . . . . . . . . . . . . . . . . . 56 x2. pONQTIE FORMALXNOJ GRAMMATIKI. . . . . . . . . . . . . . 57 x3. rEGULQRNYE QZYKI I IH OB_EDINENIE . . . . . . . . . . . . 59 x4. kONKATENACIQ I ITERACIQ REGULQRNYH QZYKOW . . . . . . 60 x5. pONQTIE KONE^NOGO AWTOMATA. . . . . . . . . . . . . . . . . 62 x6. kONE^NYE AWTOMATY I REGULQRNYE QZYKI . . . . . . . . . 63 x7. pREOBRAZOWANIQ KONE^NYH AWTOMATOW . . . . . . . . . . . . 65 x8. mETOD CIKLI^ESKIH KOMPLEKSOW . . . . . . . . . . . . . . . 67 x9. kONTEKSTNO SWOBODNYE QZYKI I GRAMMATIKI. . . . . . . . 69 x10. sTEKOWYE AWTOMATY . . . . . . . . . . . . . . . . . . . . . 70

gLAWA 5. sLOVNOSTX ALGORITMOW. . . . . . . . . . . . . . . . . . . 73 x1. zADA^I, ALGORITMY, SLOVNOSTX . . . . . . . . . . . . . . . 73 x2. zADA^I RASPOZNAWANIQ I IH SLOVNOSTX . . . . . . . . . . . 75 x3. ndmt I KLASS NP. . . . . . . . . . . . . . . . . . . . . . . 78 x4. pOLINOMIALXNAQ SWODIMOSTX I NP-POLNOTA . . . . . . . . 79

4

g l a w a 1 matemati~eskaq logika

x1. pONQTIE AKSIOMATI^ESKOJ TEORII

aKSIOMATI^ESKU@ TEORI@ T PRINQTO OPREDELQTX SLEDU@]IM OBRAZOM.

1.zADAETSQ ALFAWIT A \TOJ TEORII { KONE^NOE ILI BESKONE^NOE MNOVESTWO SIMWOLOW. mNOVESTWO WSEH KONE^NYH SLOW W ALFAWITE A OBOZNA^IM ^EREZ A .

2.wYDELQETSQ PODMNOVESTWO SLOW W A , NAZYWAEMYH FORMULAMI TEORII T . sPOSOB POSTROENIQ FORMUL OBY^NO ZADAETSQ INDUKTIWNO, T.E. OPREDELQ@TSQ \LEMENTARNYE FORMULY I UKAZYWA@TSQ PRAWILA, PO KOTORYM IZ NIH MOVNO POLU^ATX BOLEE SLOVNYE FORMULY.

3.wYDELQETSQ PODMNOVESTWO FORMUL, NAZYWAEMYH AKSIOMAMI TEORII T .

4.zADA@TSQ PRAWILA WYWODA; ONI IME@T WID R(F1; F2 ; : : : ; Fn; F ) I POZWOLQ@T PO DANNYM FORMULAM F1; F2; : : : ; Fn POLU^ATX NOWU@

FORMULU F . oBY^NO \TI PRAWILA ZAPISYWA@T TAK: R : F1; F2 ; : : : ; Fn .

F

fORMULY F1; F2 ; : : : ; Fn NAZYWA@TSQ POSYLKAMI, A FORMULA F S^I- TAETSQ SLEDSTWIEM.

oPREDELENIE 1. wYWODOM W TEORII T NAZYWAETSQ TAKAQ POSLEDOWATELXNOSTX FORMUL F1; F2; : : : ; Fn , W KOTOROJ L@BAQ FORMULA Fi LIBO AKSIOMA, LIBO QWLQETSQ SLEDSTWIEM IZ NEKOTORYH PREDYDU]IH FORMUL F1; F2; : : : ; Fi;1 PO ODNOMU IZ PRAWIL WYWODA.

oPREDELENIE 2. fORMULA F NAZYWAETSQ WYWODIMOJ W TEORII T , OBOZNA^AETSQ ` F , ESLI SU]ESTWUET WYWOD F1 ; F2; : : : ; Fn; F .

wYWODIMAQ FORMULA NAZYWAETSQ TEOREMOJ, W ^ASTNOSTI WSE AKSIOMY QWLQ@TSQ TEOREMAMI.

5

oPREDELENIE 3. fORMULA F NAZYWAETSQ WYWODIMOJ IZ FORMUL G1; G2 ; : : : ; Gm , OBOZNA^AETSQ G1; G2; : : : ; Gm ` F , ESLI SU- ]ESTWUET POSLEDOWATELXNOSTX FORMUL F1; F2; : : : ; Fn; F , W KOTOROJ L@BAQ FORMULA Fi LIBO AKSIOMA, LIBO SOWPADAET S ODNOJ IZ FORMUL Gk , LIBO QWLQETSQ SLEDSTWIEM IZ NEKOTORYH PREDYDU]IH FORMUL

TO G1; : : : ; Gm ` F { PRAWILO UDALENIQ WYWODIMOJ GIPOTEZY. zAMETIM, ^TO PRAWILO UDALENIQ WYWODIMOJ GIPOTEZY QWLQETSQ

^ASTNYM SLU^AEM SWOJSTWA TRANZITIWNOSTI WYWODA.

x2. oPREDELENIE IS^ISLENIQ WYSKAZYWANIJ

aKSIOMATI^ESKAQ TEORIQ, NAZYWAEMAQ IS^ISLENIEM WYSKAZYWANIJ (iw), ZADAETSQ SLEDU@]IM OBRAZOM.

1.aLFAWIT iw SOSTOIT IZ LOGI^ESKIH SWQZOK q I ! , DWUH SKOBOK ( I ), A TAKVE SIMWOLOW a1; a2; : : : ; an; : : : , SLUVA]IH W KA^ESTWE BUKW.

mY BUDEM ^ASTO WMESTO BUKW ai UPOTREBLQTX MALYE LATINSKIE BUKWY BEZ INDEKSOW.

2.fORMULY iw OPREDELQ@TSQ INDUKTIWNO SLEDU@]IM OBRAZOM: A) L@BAQ BUKWA QWLQETSQ FORMULOJ;

B) ESLI A { FORMULA, TO ( q A) TAKVE QWLQETSQ FORMULOJ; W) ESLI A I B { FORMULY, TO (A ! B) { TOVE FORMULA; G) DRUGIH FORMUL NET.

wMESTO ( q A) BUDEM ^ASTO PISATX LAH OBY^NO OPUSKA@T.

3. aKSIOMAMI iw QWLQ@TSQ TRI FORMULY A1 , A2 I A3 , W KOTORYH { BUKWY:

6

A1 = a ! (b ! a) ;

A2 = (a ! (b ! c)) ! ((a ! b) ! (a ! c)) ; A3 = (b ! a) ! ((b ! a) ! b) .

4. iME@TSQ DWA SLEDU@]IH PRAWILA WYWODA iw:

rEZULXTAT ODNOWREMENNOJ PODSTANOWKI BUDEM OBOZNA^ATX ^EREZ

F (a1; : : : ; an jj A1; : : : ; An) , A PRAWILO ZAKL@^ENIQ BUDEM PISATX W

WIDE B = MP (A; A ! B)

zAME^ANIE 1. ~ASTO AKSIOMY A1 , A2 I A3 ZAMENQ@T NA

A10 = A ! (B ! A) ,

A20 = (A ! (B ! C)) ! ((A ! B) ! (A ! C)) , A30 = (B ! A) ! ((B ! A) ! B) ,

POLU^AEMYE IZ AKSIOM A1 , A2 I A3 PODSTANOWKOJ FORMUL A; B; C WMESTO BUKW a; b; c . w \TOM SLU^AE MOVNO OBOJTISX BEZ PRAWILA ODNOWREMENNOJ PODSTANOWKI.

zAME^ANIE 2. iME@TSQ I DRUGIE SISTEMY AKSIOM DLQ iw. zAME^ANIE 3. mOVNO WWESTI W iw I DRUGIE LOGI^ESKIE SWQZKI

x3. tEOREMA DEDUKCII W IS^ISLENII WYSKAZYWANIJ

nA^INAQ S \TOGO PARAGRAFA MY BUDEM POLXZOWATXSQ SISTEMOJ AKSIOM A10; A20; A30 , ^TO POZWOLIT NAM OBHODITXSQ BEZ PRAWILA ODNOWREMENNOJ PODSTANOWKI.

tEOREMA DEDUKCII. pUSTX ; { MNOVESTWO FORMUL (GIPOTEZ);

A , B { FORMULY, TOGDA ; ` A ! B () ;; A ` B . dOKAZATELXSTWO. pUSTX ; ` A ! B , TOGDA ;; A ` A ! B PO

PRAWILU OSLABLENIQ. kROME TOGO, O^EWIDNO, ^TO ;; A ` A . pOSKOLXKU A; A ! B ` B PO PRAWILU ZAKL@^ENIQ, TO ;; A ` B PO SWOJSTWU TRANZITIWNOSTI WYWODA, ^TO I TREBOWALOSX DOKAZATX.

dOKAZATELXSTWO W OBRATNU@ STORONU. pUSTX ;; A ` B , T.E. SU- ]ESTWUET WYWOD F1; F2; : : : ; Fn IZ GIPOTEZ ;; A , W KOTOROM Fn = B . dOKAVEM INDUKTIWNO, ^TO ; ` A ! Fm DLQ

1. pUSTX m = 1 . fORMULA F1 MOVET BYTX LIBO AKSIOMOJ, LIBO F1 2 ; , LIBO F1 = A . rAZBEREM \TI SLU^AI OTDELXNO.

1A. pUSTX F1 { AKSIOMA. pOSTROIM SLEDU@]IJ WYWOD:

G1 = F1

G2 = F1 ! (A ! F1) = A10 { AKSIOMA,

G3 = A ! F1 = MP (G1; G2) .

tAKIM OBRAZOM, ; ` A ! F1 .

1B. pUSTX F1 2 ; , TOGDA WYWODOM A ! F1 QWLQETSQ TA VE POSLEDOWATELXNOSTX G1; G2; G3 , ^TO I W PREDYDU]EM SLU^AE, TOLXKO W \TOM SLU^AE G1 { NE AKSIOMA, A ODNA IZ GIPOTEZ MNOVESTWA ; .

1W. pUSTX F1 = A I POSKOLXKU PO UTWERVDENI@ 1 PREDYDU]EGO PARAGRAFA ` A ! A , TO PO PRAWILU OSLABLENIQ IMEEM ; ` A ! A I, ZNA^IT, ; ` A ! F1 , T.K. A = F1 .

sLU^AJ m = 1 POLNOSTX@ RAZOBRAN.

2.iNDUKCIONNOE PREDPOLOVENIE. pUSTX ; ` A ! Fi DLQ ZNA^E-

NIJ i = 1;2; : : : ; m ; 1 .

3.{AG INDUKCII. dOKAVEM, ^TO ; ` A ! Fm . fORMULA Fm MOVET BYTX LIBO AKSIOMOJ, LIBO Fm 2 ; , LIBO Fm = A , LIBO Fm MOVET POLU^ITXSQ PO PRAWILU ZAKL@^ENIQ IZ FORMUL Fi I Fj , GDE

i < j < m . w PERWYH TREH SLU^AQH DOKAZATELXSTWO PROWODITSQ KAK I DLQ m = 1 . w POSLEDNEM SLU^AE Fj = Fi ! Fm , I PO INDUKCION-

8

NOMU PREDPOLOVENI@ MY IMEEM ; ` A ! Fi I ; ` A ! (Fi ! Fm) . iSKOMYJ WYWOD ; ` A ! Fm SOSTOIT IZ SLEDU@]IH FORMUL:

G1 = A ! Fi { INDUKCIONNOE PREDPOLOVENIE,

G2 = A ! (Fi ! Fm) { INDUKCIONNOE PREDPOLOVENIE,

G3 = (A ! (Fi ! Fm)) ! ((A ! Fi) ! (A ! Fm)) = A30 , G4 = ((A ! Fi) ! (A ! Fm)) = MP (G2; G3) ,

G5 = (A ! Fm) = MP (G1; G4) .

iTAK, MY DOKAZALI, ^TO ; ` A ! Fm DLQ m = 1; 2; : : : ; n , I W ^ASTNOSTI ; ` A ! Fn , A POSKOLXKU Fn = B , TO ; ` A ! B .

tEOREMA DEDUKCII POLNOSTX@ DOKAZANA.

x4. dWOJNOE OTRICANIE W IS^ISLENII WYSKAZYWANIJ

tEOREMA 1. w IS^ISLENII WYSKAZYWANIJ A ` A . dOKAZATELXSTWO TEOREMY SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1)` A ! (A ! A) { AKSIOMA A10 ,

2)A ` A ! A { IZ 1 PO TEOREME DEDUKCII,

3)` (A ! A) ! ((A ! A) ! A) { AKSIOMA A30 ,

4)A ! A ` (A ! A) ! A { IZ 3 PO TEOREME DEDUKCII,

5)A ` (A ! A) ! A { IZ 2 I 4 PO TRANZITIWNOSTI WYWODA,

6)A; A ! A ` A { IZ 5 PO TEOREME DEDUKCII,

7)` A ! A { UTWERVDENIE 1 IZ x2,

8)A ` A { UDALENIE WYWODIMOJ GIPOTEZY 7 IZ 6.

tEOREMA 2. w IS^ISLENII WYSKAZYWANIJ A ` A . dOKAZATELXSTWO TEOREMY SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1)` A ! A { TEOREMA 1,

2)` (A ! A) ! ((A ! A) ! A) { AKSIOMA A30 ,

3)` (A ! A) ! A { PO PRAWILU MP IZ 1 I 2,

4)A ! A ` A { IZ 3 PO TEOREME DEDUKCII,

5)` A ! (A ! A) { AKSIOMA A10 ,

6)A ` A ! A { IZ 5 PO TEOREME DEDUKCII,

7)A ` A { IZ 6 I 4 PO TRANZITIWNOSTI WYWODA.

9

x5. dOKAZATELXSTWO OT PROTIWNOGO W IS^ISLENII

WYSKAZYWANIJ

tEOREMA 1. w IS^ISLENII WYSKAZYWANIJ B ! A ` A ! B . dOKAZATELXSTWO TEOREMY SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1)` A ! (B ! A) { AKSIOMA A10 ,

2)A ` B ! A { IZ 1 PO TEOREME DEDUKCII,

3)` (B ! A) ! ((B ! A) ! B) { AKSIOMA A30 ,

4)B ! A ` (B ! A) ! B { IZ 3 PO TEOREME DEDUKCII,

5)B ! A; (B ! A) ! B ` B { PRAWILO ZAKL@^ENIQ,

6)B ! A; A ` B { IZ 2, 4 I 5 PO TRANZITIWNOSTI WYWODA,

7)B ! A ` A ! B { IZ 6 PO TEOREME DEDUKCII.

tEOREMA 2. w IS^ISLENII WYSKAZYWANIJ A ! B ` B ! A . dOKAZATELXSTWO TEOREMY SOSTOIT IZ SLEDU@]IH UTWERVDENIJ:

1)A ` A { PO TEOREME 1 O DWOJNOM OTRICANII,

2)A ! B; A ` B { PRAWILO ZAKL@^ENIQ,

3)A ! B;A ` B { IZ 1 I 2 PO TRANZITIWNOSTI WYWODA,

4)B ` B { PO TEOREME 2 O DWOJNOM OTRICANII,

5)A ! B;A ` B { IZ 3 I 4 PO TRANZITIWNOSTI WYWODA,

6)A ! B ` A ! B { IZ 5 PO TEOREME DEDUKCII,

7)A ! B ` B ! A { PO TEOREME 1 O DOKAZATELXSTWE OT PROTIWNOGO,

8)A ! B ` B ! A { IZ 6 I 7 PO TRANZITIWNOSTI WYWODA.

x6. wWEDENIE KON_@NKCII W IS^ISLENII WYSKAZYWANIJ