V. Кванторлардың орнын ауыстыру заңдары

Аңғартпа: Осының алдыңғы пунктте теңмағыналы және теңмәндә формулалар арасында біреуін екіншісінің салдары деп қарауға болатын байланыс барлығын атап көрсеткенбіз. Сол байланысқа сүйену арқылы пердикаттар алгебрасындағы « негізгі теңмағыналы формулалардың тізіміндегі 1 – 5 формулалардың «негізгі жалпымәнділік» тавтология жәнеэквиваленттілік белгілерін пайдаланып «негізгі жалпымәнділік» формулалардың мынадай 1 – 5 жүйесін жазуға болады.

Негізгі жалпымәнділік формулалар тізімі.

1. Кванторларды терістеу заңдары.

2. Кванторларды коньюнкция мен диэьнкция арқылы көшіру заңдары.

3. Кванторларды имплакация арқылы көшіру заңдары

Мұндағы Q – нөл орынды предикат

4. Жалпылық кванторын шеткерілеу бармыстық

кванторын енгізу заңдары.

5. Кванторлардың орнын ауыстыру заңдары

Аңғартпа: НТМ және НЖМ формулалардың әрқайсысын жеке – жеке алғанда теорема деп қарап дәлелдеуге болады. Олардың кейбіреулерінің дәлелдеулері бұрын мысал ретінде қарастырылыпта өтті. Біз енді үлгі ретінде 1 – 5 формулалардың кейбіреулерін ғана дәлелдеп көрсетеміз.

1 – НТМ.

Дәлелдеуі: айталық болсын. Онда мына пікір болады. Демек, Р(х) предикаттың А – анықталу облысында Р қасиетке иелі болатындай бір х бар болуы тиіс. Яғни .

1 және 2 өрнектерден д.с.о.е.

Егер 1₁ – НТМ формула тура болса, онда 1₁ – НЖМ формула да сөзсіз тура болады. Сондақтан, мынадай формула да дәлелденді деуге болады:

1₃ –НТМ.

Дәлелдеуі: дәлелденетін қатынастың оң жағындағы формуланы алып, оған 1₂ – заңды қолданамыз.

≡(қос терістеу заңы бойынша )≡ . Осыдан 1₃ формуланың тура екендігі шығады. Демек, 1₃ –НЖМ формуласы да тура болады:

ІІ₂ – НТМ. (бармыстық кванторы дизьюнкция амалына қарағанда үлесімтірімді болады.)

Дәлелдеу: Айталық Р(х)және Q(х) предикаттар ақырлы жиынды берілген болсын. Сонда бармыстық кванторының анықтамасына сүйеніп былайша жазуға болады:

Осы дәлелденген формуладан ІІ₂ НЖМ формуласының тура болатындығы шығады:

ІІІ₁ – НЖМ формуланың тура болатынын дәлелдеу керек.

Дәлелдеу: Бұл формуладағы Q – нөл орынды предикат болатындығы айтылғанды. Сондай-ақ Q- ды х тен басқа кез келген у айнымалының п – орынды предикаты деп қарауға да болады. Біз қолайлы болуы үшін Q(у) – бір орынды предикат деп аламыз. Мұндағы у квантормен байланбаған кез келген (х тен басқаша) ерікті айнымалы. Осындай алғы шарттардан кейін формуланы жалпымәнді болмасын деп ұйғарамыз. Онда А, А₁ жиыгдары анықталған Р₁(х) және Q(х) екі айқындық функция болып табылып, оларды формуладағы Р(х) және Q(х) тың орнына қойсақ, бекермелік болатын мынадай формула шығуы тиіс:

Бұл формула бекермелік болғандықтан, мұндағы у-тің орнына А₁ жиыннан айқындалып алынған в нәрсені қояр болсақ, онда мынадай жалған формула шығады:

Екі предикаттан құрылған теңгермелік формуланың анықтамасы бойынша қатынас орындалуы үшін құраушы формулалар әртүрлі ақиқаттық мәндерге иелі болуы тиіс. Сондықтан, теңмағыналы формуладан мүмкін болатын екі жағдайда айырып қарауға болады:

Алдымен 1 жағдайды жеке алып қарастырайық. Сондағ формуладан сабақтасым амалының анықтамасы бойынша мыналар шығады:

, мұндағы дан бар болу кванторының анықтамасы бойынша Р₁(х) орындалатын формула деген қорытынды айткымызға болады. Яғни А жиыннан қандай да бір а_к деген мән табылып, Р₁(а_к)=а деп қарай аламыз. а_к =А.

Енді І жағдайдағы формуласына оралайық. Жалпы кванторының анықтамасы бойынша осы формуладан мына формуланы: теңбе – тең ақиқат деп қарауға да болады. Олай болса А жиындағы кез келген а_к үшін былайша жаза аламыз: ал, бен Р₁(а_к)=а ден сабақтасым амалының анықтамасы бойынша мынау шығады:

Сөйтіп, бен - дан қайшылық келіп шықты. Осы қайшылық І жағдай орындалғанда біздің ұйғаруымыздың қате екендігін көрсетеді. Ендеше осы жағдай ауқымында алып қарағанда ІІІ₁ – НЖМ формуланың тавтология болатыны дәлелденді дейміз.

ІІ жағдайға жекелеп қарастырамыз. Сондағы қатынасқа сүйенсек және жалпылық кванторын анықтамасын басшылылыққа алсақ, онда формуланы бекерлемдік формула деп қарауға да болады. Яғни Ғ жиындағы қандай да бір а_к үшін былайша жазуға болады: Сабақтасым амалының анықтамасы бойынша формуладан мыналар шығады: осы а_к үшін

ІІ жағдайдағы формуладан болғандықтан, болатындығы кеп шығады.

Мына қатынас Р₁(х) предикаттың теңбе – тең жалған болатындығын көрсетеді. Ендеше А жиындағы қандай да бір а_к үшін болуы тиіс. Бұл қорытынды қатынастардың біріншісімен үлеспейді. Осы қайшылық ІІ – жағдайдағы ұйғарудың қате екендігіне негіз болады.

Сөйтіп, І және ІІ жағдайда да қайшылыққа тап боламыз. Бұл жалпымәнділіктің тура екендігін көрсетеді. ІІІ₁ – НЖМ формуланың туралығынан ІІІ₁ –НТМ –нің орындалатыны кеп шығады.

ІV₁ – НЖМ формуланың тура болатындығын дәлелдеуге тоқталамыз.

Дәлелдеу: бұл формуланы А жиында анықталған Р предикаттық айнымалы мен у – еркін айнымалының функциясы деп қарауға болады. Р(х) предикаттық ақиқаттық облысын Т_р деп белгілейік. Егер болса, онда мына пікір болады. Демек, сабақтасым анықтамасы бойынша болады.

Ал егер болса, онда болатыны анық. Бұдан болса, онда болады. Демек, пен -ден .

Сонымен, және формуладан мынау шығады:

ІV₂ –НЖМ формуласын дәлелдейік:

Дәлелдеу: мына формуланың тура болатындығын дәлелдеуді екі жағдайға бөліп қарайық.

1 – жайдай: Айталық Ø – құр жиын болсын. Онда А жиындағы кез келген у үшін болады. Осыған қарап сабақтасымдық амалдың анықтамасынан 1 – жағдайда әрқашан деп тұжырым жасауға болады.

2 – жағдай: Айталық Ø құр жиын болмасын. Онда болатын қандай да бір х бар болады. Ендеше сабақтасымның анықтамасы бойынша бұл жағдай да:

болады.

1-ші және 2-ші жағдайды біріктіріп айтар болсақ, онда мына қатынас тура болады дей аламыз.

V₁ –НЖМ формуласын дәлелдейік:

Дәлелдеу: Кері ұйғару әдісімен пайымдап, дәлелдейміз. Айталық мына формула тавталогия болмасын. Онда А жиында анықталған айқынды предикат табылып, оны бірінші формуладағы -тің орнына қойғанда, бұл формула «ж» деген мән қабылдайтын болады.

Бұдан сабақтасым амалының негізінде мынадай қатынастардың тура болатындығы шығады: және

Мұндағы қатынастан бармыстық кванторының анықтамасы бойынша у-ке тәуелді предикатты орындалатын предикат болатындығы шығады. Демек, у=в десек, болады. Соңғы мына қатынастың пердикаттың А жиында х айымалыға қарағанда теңбе – тең ақиқат ьолатынын көреміз. Сол себепті А жиында х-тің предикаты болатын - бір орынды предикат осы А жиында «ақиқат» деген мән қабылдайды. Яғни

мен -дан мынаны жазуға болады:

Бұл өатынасқа қайшы келеді. Демек, біздің ұйғаруымыз қате. Ендеше бастапқы тұжырым тура болады.

ІV Модуль КОДТАУ ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

11. Дәрістің тақырыбы: Кодтаудың негізгі есептері.

Жаспары:

1. Кодтаудың есептері, қағидалары және қолданулары. Декодтау. Алфавитті және біркелкі кодтау.

2. Декодтаудың бір мәнділігінің критерийі.

3. Кодтағы кедергілерге қарсы орнықтылығы туралы есеп.

4. Хэмминг кодтары. Хэмминг кодтарындағы қателерді байқау.

12- Дәрістің тақырыбы: Минимальді арықшылығы бар кодтарды есептеу.

Жаспары:

1.Ақпараттарды құпиялаудың есептері мен қағидалары. Ақпараттарды қорғауды қамтамасыз етуде құпиялаудың негізгі функциялары. Құпиялаудың даму тарихынан.

2. Ақпараттарды компьютерлік құпиялаудың қағидалары.

3. Ашық және жабық кілтті шифрқұпиялар ұғымы.

Негізгі сұрақтар: Модулярлық арифметикадағы есептеулер және олардың криптографияда қолданылуы

Модульді арифметикадағы есептеу қорын және оның криптографияда қолданылуын қарастырайық.

1. Жылдам дәрежеге шығару алгоритмі.

Мысал қарастырайық

Осылайша

3¹⁵mod7=(3*3¹⁴)mod7=(3*3⁶*3⁸)mod7=3*(3²*3)²*((3²)²)²mod7=(((3²*3)²)²*3²*3)mod7= 6.

3¹⁵≡6(mod 7)

Келесі теңдеуді шешіңіздер:

(1) mod 17 (ответ 10)

(2) 2³⁰ mod 5 (ответ 4)

(3) 5¹⁶ mod 13 (ответ 1)

(4) 5³⁵ mod 33 (ответ 23)

(5) 7²³ mod 13 (ответ 2)

(6) 4³⁷ mod 26 (ответ 4)

2. Кері мәнді табу.

(1), салыстырымы берілсін.

Мұнда a, n- белгілі сандар. : - табу қажет, мұндағы - а санының кері мағынасы. х- белгісізін үш жолмен табуға болады.

• Тура іріктеу әдісімен.

• Эйлер функциясы арқылы.

• Евклид алгоритмі арқылы.

Мысал:

: . Түріндегі салыстырым берілсін.

Тура іріктеу әдісін қолданайық.

1	4	4
2	8	8
3	12	12
4	16	3
5	20	7
6	24	11
7	28	2
8	32	6
9	36	10
10	40	1

Жауабы: 10

Тексерейік:

Эйлер функциясын қолданып есептейік. - Эйлер функциясы деп аталады, оның мағынасы n- кіші сандарға тең, ал қарапайым сандар n-ге тең.

Егер n жай сан болса онда

Егер , мұндағы p,q- жай сандар, онда .

Егер , онда .

Онда теңдеу (1) Эйлер функциясы арқылы мына формуламен анықталады.

Онда алдынғы мысал келесі түрде шешіледі

тура іріктеу әдісіндегідей 10 саны алынды.

Үлкейтілген Евклид алгоритмі. (1) түріндегі теңдеу берілсін. Үлкен Евклид алгоритмінің мағынасы келесідей.

1. орнату.

2. Егер , алгоритм теңдеуінде тоқтатылады, әйтпесе 3 тармақ орындалады.

3.

2 тармаққа ораламыз.

-	0	1	13	1	0	4
3	1	0	4	-3	1	1
4	-3	1	1

Жауабы:

3. ax ≡ b mod n теңдігінің шешімі.

ax ≡ в mod n, в ≠ 1 (2) түріндегі теңдіктің шешімі 2 кезеңге бөлінеді.

1. ax₁ ≡ 1 mod n

2. x = x₁*в mod n

Мысал1: 3x ≡ 6 mod 17

1. 3x₁ ≡ 1 mod 17

x₁ = 6

2. x = 6*6 mod 17 = 2

Тексеру: 3*2 ≡ 6 mod 17 = 6

Мысал2: 2x ≡ 7 mod 9

1. 2x₁ ≡ 1 mod 9

x₁ = 5

2. x = 5*7 mod 9 = 8

Тексеру: 2*8 ≡ 7 mod 9 = 5

Мысал3: 4x ≡ 11 mod 33

1. 4x₁ ≡ 1 mod 17

x₁ = 4^φ(33)-1mod 33 = 4^20-1mod 33 = (4³)⁶ * 4 mod 33 = (31)⁶ * mod 33 = (31²)³ * 4 mod 33 = 4³ * 4 mod 33 = 31 * 4 mod 33 = 25

x₁ = 25

2. x = 25*11 mod 33 = 275 mod 33

x = 11

Тексеру: 25*11 ≡ 11 mod 33 = 25

4. Салыстыру жүйелерін шешу.

(3) жүйе б.э. 1 ғасырында Қытай математигі Сун Це- мен шешілген.

Қалдық туралы Қытай теоремасы: Шегеру модулі белгілі болатын модулінің туындысынан асып кетпейтін кез-келген теріс санды, қалпына келтіруге болады. Бұл теңдік ежелгі қытайда белгілі болған және «Қалдықтар туралы Қытай теоремасы» деген атпен белгілі. Бұл теорема 1 ғасырда Қытай математигі Сун Це- мен ұсынылған. Қалдықтар туралы Қытай теоремасы қуатты криптографиялық құрал болып табылады.

Шешім:

1. N = n₁* n₂ белгілейік, онда

N₁ = N/n₁ = n₂

N₂ = N/n₂ = n₁

2. Келесі теңдікті шешейік:

Теңдікті түрлендірсек ол келесі түрге келеді:

, онда

3. (3) жүйесін шешуге болады:

x ≡ (a₁N₁y₁ + a₂N₂y₂) mod n₁ n₂

Мысал1:

1. N = 91

N₁ = 13

N₂ = 7

2. Теңдікті шешейік:

3. Шешім:

x ≡ (3*13*6 + 8*7*2) mod 91 = (234+112) mod 91 = 346 mod 91 = 73

x = 73

Тексеру:

73 mod 7 = 3

73 mod 13 = 8

Мысал2:

1. N = 91

N₁ = 13

N₂ = 7

2. Теңдікті шешейік:

3. Шешім:

x ≡ (5*13*6 + 8*7*2) mod 91 = (390+112) mod 91 = 502 mod 91 = 47

x = 47

Тексеру:

47 mod 7 = 5

47 mod 13 = 8

Мысал3:

1. N = 66

N₁ = 11

N₂ = 6

2. Теңдікті шешейік:

3. Шешім:

x ≡ (4*11*5 + 3*6*2) mod 66 = (220+36) mod 66 = 256 mod 66 = 58

x = 58

Тексеру:

58 mod 6 = 4

58 mod 11 = 3

Тақырып №5. Криптографиялық қорғау құралдары

Негізгі сұрақтар: Қазіргі заманғы шифрлеу жүйелері. Салыстырмалы талдау

Шифрлеу жүйелерінің классификациясы

- дәстүрлі:

блоктық (ауысымдық, аналогтық түрлену)

ағымдық (алмастыру, жылжыту)

- қазіргі заманғы:

симметриялы (DES, IDEA, ГОСТ 28147-89)

асимметриялы (ашық кілтті криптожүйелер) (RSA, Diffie-Hellman, EL-Gamal).

Ағымдық шифрлеу.

Мысал:

Ағылшын тілінде m_a=26

Қазақ тілінде m_k=42

Орыс тілінде m_o=33

-алмастыру функциясы. 1) pt= I am fine.

ct= bhgebir

2) pt = Everybody dance

ct = rsrvojav

3) ct = npqaripgiarmnphian

pt = student understands

Полибий квадраты

	1	2	3	4	5	6
1	а	б	в	г	д	Е
2	е	ж	з	и	й	К
3	л	м	н	о	п	Р
4	с	т	у	ф	х	Ц
5	ч	ш	щ	ъ	ы	Ь
6	э	ю	я		.	?

pt = криптография

26 36 24 35 42 34 14 36 11 44 24 63

к р и п т о г р а ф и я

Мысал: pt = қауіпсіздік

ct = 31 11 45 63 41 43 63 24 17 63 27

Плейфейердің биграмдық шифрі.

1854 жылы жасалған Плефейердің шифрі алмастырудың биграмдық шифрлерінің ең танымалысы. Ол бірінші дүние жүзілік соғыста Ұлыбритания қолданған. Плефейер шифрінің негізгі болып бастапқы мәліметтер алфавитінің әріптері кездейсоқ орналасқан шифлеуші кесте болып табылады. Шифрлеуші таблицаны оңай есте сақтау үшін кестенің бастапқы жолдарын толтыру негізінде жіберуші мен қабылдаушы кілттік сөзді қолданады. Жалпы алғанда Плефейердің шифрлеуші кестесінің құрылымы Трисемус кестесінің құрылымына ұқсас. Сондықтан Плефейер жүйесінің шифрлеу және шифрды ашу процедураларын түсіну үшін өзіміз білетін Трисемус шифрлеуші кестесін қолданамыз.

Б	А	Н	Д	Е	Р	О	Л
Ь	В	Г	Ж	З	И	Й	К
М	П	С	Т	У	Ф	Х	Ц
Ч	Ш	Щ	Ы	Ъ	Э	Ю	Я

Шифрлеу үрдісі келесі қадамдардан тұрады:

1. Ашық мәтін биграммаларға бөлінеді. Мәтінде әріптер саны жұп болуы керек және онда екі бірдей биграмма болмауы керек. Егер бұл шарттар орындалмаса мәтін маңызды емес орфографиялық қателер үшін де мәтін өзгерістерге ұшырайды.

2. Ашық мәтіннің биграммалар тізбегі шифрлеуші кестенің көмегімен келесі ережелерге сай шифрмәтіннің биграммалар тізбегіне өзгертіледі.

2.а) Егер ашық мәтіннің биграммасының екі әрпі бір жолда немесе бағанада орналаспаса, онда кестедегі а мен й әріптері, онда бұл екі әріп арқылы анықталған тік төртбұрыштың басқа екі бұрышындағы әріптер алынады (біздің мысалы бұл а, й, о, в әріптері а, й әріптер жұбы О, В әріптер жұбына түрленеді).

Шифрмәтіннің биграммасындағы әріптер тізбегіне қарағанда түра шағылып орналасу керек (зеркально расположены).

2.б) Егер ашық мәтіннің биграммасының екі әрпі де бір бағанада орналасса, онда шифрмәтіннің әріптері берілген әріптердің тура астында орналасқан әріптер болады. (Мысалы, н мен с, г мен щ әріптеріне түрленеді). Егер ашық мәтіннің әрпі ең соңғы жолда орналасса, шифрмәтіннің әрпі ең жоғары жолдың сәйкес әрпі болады, Мысалы,

2.в) Егер ашық мәтіннің биграммасының екі әрпі де бір жолда орналасса, онда шифрмәтіннің әріптері сол әріптердің оң жағында орналасқан әріптер болып табылады. (н,о-д,л)

Егер ашық мәтіннің әрпі оң жақ шеткі бағанда орналасса шифр үшін сол жолдың сол жақ шеткі бағанасындағы сәйкес әрппті аламаыз (Ф,Х – Х,М).

Келесі мәтіннің шифрін қарастырайық:

ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ

ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ

Кестеге сай ашық мәтіннің биграммалар тізбегі келесі биграммалар тізбегіне бөлінеді.

ГП ДУ ОВ ДЛ НУ ГД ДР ЦЫ ГА ЧТ

Шифрді ашуда осы амалдар кері бағытта орындалады. Биграммалар арқылы шифрлеу шифрдің ашу төзімділігін арттырады.

Мысал:

Қ	Ұ	П	И	Я	А	Ә	Б
В	Г	Ғ	Д	Е	Е	Ж	З
Й	К	Л	М	Н	Ң	О	Ө
Р	С	Т	У	Ү	Ф	Х	Һ
Ц	Ч	Ш	Щ	Ъ	Ы	І	Ь
Э	Ю

pt = Келдім, Көрдім, Жеңдім

ct = ңгмғщолйувщоземещо

Трисемус кестесі

к – кілттік сөз. к = Бандероль

Б	А	Н	Д	Е	Р	О	Л
Ь	В	Г	Ж	З	И	Й	К
М	П	С	Т	У	Ф	Х	Ц
Ч	Ш	Щ	Ы	Ъ	Э	Ю	Я

pt = ВЫЛЕТАЕМ ПЯТОГО

ct = ПДКЗЫВЗЧ_ШЛЫЙСЙ

к = құпия

Қ	Ұ	П	И	Я	А	Ә	Б
В	Г	Ғ	Д	Е	Е	Ж	З
Й	К	Л	М	Н	Ң	О	Ө
Р	С	Т	У	Ү	Ф	Х	Һ
Ц	Ч	Ш	Щ	Ъ	Ы	І	Ь
Э	Ю

pt = күтіп алыңдар

ct = съшәғетафмец

Виженер кестесі.

ашық мәтін әріптері

	А	Б	В	Г	Д	Е	. .
А	А	Б	В	Г	Д	Е	. ..
Б	Я	А	Б	В	Г	Д	...
В	Ю	Я	А	Б	В	Г	. құпиялы сөздің әріптері ..
Г	Э	Ю	Я	А	Б	В	...
Д	Ь	Э	Ю	Я	А	Б	...
Е	Ы	Ь	Э	Ю	Я	А	...
...	...	...	...	...	...	...	...

кілттік сөз әріптері

pt = ГДЕ АББА

k = ДЕВА

ct = ЯЯГАЭЬЮ

Вернам шифрі немесе афиндік түрлендіру.

А В С D E F G H I J K L M N O P Q R S T U V W X Y Z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 – алфавитті цифрлеу.

pt = h i d d e n n u m b e r i s a k e y

7 8 3 3 4 13 13 20 12 1 4 17 8 18 0 10 4 24

k = Y E 2 P K P Y M 4 7 R W F 0 0 1

9 4 2 15 10 15 9 12 4 7 17 22 5 0 0 1

Мысал:

А Ә Б В Г Ғ Д Е Е Ж З И Й К Қ Л М Н Ң О Ө П Р С Т У Ұ Ү Ф

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Х Һ Ц Ч Ш Щ Ъ Ы І Ь Э Ю Я

29 30 31 32 33 34 35 36 37 38 39 40 41

pt = С а л а у а т т ы ө м і р с а л т ы

23 0 15 0 25 0 24 24 36 20 16 37 22 23 0 15 24 36

k = м е м л е к е т

16 7 16 15 7 13 7 24

10111