Предикаттар алгебрасы және формалды тілдер теориясы

1 слайд
Предикаттар алгебрасы және формалды тілдер теориясы Формалды тілдер теориясында тілді грамматика көмегімен көрсетуге болады. Грамматиканы жиі Бэкус-Наур қалыпты формасы (БНҚФ) арқылы анықтайды. Бұл презентацияда біз предикаттар алгебрасының негізгі ұғымдарын, формалды тілдердің анықтамаларын және логикалық есептеулердің құрылымын қарастырамыз. GA by Gani Abdumalik

1 слайд

2 слайд
Алфавит және тізбектер Алфавит (Ʃ) - дербес бос емес жиын. Мысалы, орыс немесе ағылшын тілінің алфавиті, сандар жиыны немесе пернетақтадағы барлық символдар жиыны. Алфавиттің символы - оның кез келген элементі. Тізбек - символдардың кез келген тізбегі, мысалы сөздер немесе сөйлемдер. Бос тізбек арнайы символмен белгіленеді. Ʃ* - Ʃ алфавиті бойынша барлық тізбектердің жиыны. Тізбектің ұзындығы - оның құрамындағы символдар саны. 1Алфавит (Ʃ) Дербес бос емес жиын, мысалы тіл әріптері немесе сандар 2Символ Алфавиттің кез келген элементі 3Тізбек Символдардың кез келген тізбегі, мысалы сөздер 4Ұзындық Тізбектегі символдар саны

2 слайд

3 слайд
Конкатенация операциясы Конкатенация - екі тізбекті біріктіру операциясы. Егер x және y екі тізбек болса, онда xy олардың конкатенациясы болады. Бұл операция келесі қасиеттерге ие: Ассоциативтілік (xy)z = x(yz) Бірлік элементі xε = εx = x, мұндағы ε - бос тізбек Дистрибутивтілік x(y + z) = xy + xz, (x + y)z = xz + yz

3 слайд

4 слайд
Формалды тіл анықтамасы Формалды тіл - Ʃ* тізбектерінің жиынының кез келген ішкі жиыны. Егер тілдің соңы бар болса, оның барлық элементтерін санап беруге болады. Шексіз тілдер үшін бұл мүмкін емес. Тілді анықтау үшін жиі грамматика қолданылады. Грамматика - бұл G = (Ʃ, N, P, S) жиыны, мұндағы: Ʃ Терминалды символдар жиыны N Метасимволдар (терминал емес символдар) жиыны P Шығару ережелерінің жиыны S Бастапқы метасимвол

4 слайд

5 слайд
Грамматика және шығару процесі Грамматиканың әрбір ережесі α → β түрінде болады, мұндағы α - метасимвол, ал β - екі алфавиттің бірігуіндегі кез келген тізбек. Шығару процесі бастапқы символдан басталып, ережелерді қолдану арқылы жүзеге асырылады. Егер тізбекте метасимволдар қалмаса, шығару процесі аяқталған болып саналады. Терминалды символдар - Ʃ алфавитынан алынған символдар, ал метасимволдар - N-нан алынған символдар. 1 Бастапқы символ Шығару процесі S бастапқы символдан басталады 2 Ережелерді қолдану Метасимволдар ережелер бойынша ауыстырылады 3 Терминалды тізбек Процесс терминалды символдардан тұратын тізбекке жеткенде аяқталады

5 слайд

6 слайд
Бэкус-Наур қалыпты формасы (БНҚФ) БНҚФ - грамматиканы көрсетудің көрнекі формасы. Ол ережелерді бағыттауыштары бар жиын түрінде береді. Әрбір ереже метасимволдың ауыстырылуы мүмкін барлық тізбектерді көрсетеді. Мысалы, предикаттар тілінің синтаксисін анықтайтын БНҚФ грамматикасы: Предикат ::= ақиқат | жалған | идентификатор | (¬Предикат) | (Предикат ∨ Предикат) | ... Идентификатор ::= әріп | әріп цифр | әріп идентификатор Әріп ::= A | B | C | ... | Z | a | b | c | ... | z Цифр ::= 0 | 1 | 2 | ... | 9

6 слайд

7 слайд
Предикаттар тілінің мысалы Предикаттар тілінің грамматикасынан туындаған тізбектің мысалы: (¬(p ∨ q)). Бұл тізбек p ∨ q теңдеуінің предикат болып табылатынын көрсетеді. Бір предикат үшін бірнеше эквивалентті шығару тізбектері болуы мүмкін. Мысалы: (¬(p ∨ q)) = ((¬p) ∧ (¬q)). Бұл эквивалентті тізбектердің жиынын предикаттың шығыс ағашы арқылы көрсетуге болады. Шығыс ағашы Предикаттың құрылымын көрсетеді Эквиваленттілік Бірдей мағынаны білдіретін тізбектер Логикалық операциялар ¬, ∨, ∧ сияқты символдар

7 слайд

8 слайд
Дедуктивті теориялар Көптеген математикалық теориялар дедуктивті түрде құрылады. Теорияның негізіне аксиомалар алынады. Басқа ұғымдар осы негізгі ұғымдардың негізінде қалыптасады. Дедуктивті теориялардың негізгі мәселелері: Толықтығы Теорияның барлық пайымдауларын дәлелдеуге немесе теріске шығаруға бола ма? Қарама-қайшы еместігі Белгілі-бір пайымдауды дәлелдеуге немесе теріске шығаруға бола ма? Шешілімділігі Теорияның кез-келген формуласының ақиқаттығын анықтауға бола ма?

8 слайд

9 слайд
Логикалық есептеулердің құрылымы Әрбір логикалық есептеу келесі элементтермен сипатталады: 1 Алфавит Символдар жиынтығы 2 Формула құру ережелері Мағыналы пайымдауларды құру ережелері 3 Аксиомалар жүйесі Белгілі бір формулалар жиынтығы 4 Шығару ережелері Жаңа формулаларды алу ережелері Алфавит және формулалар жиынтығы есептеулер тілін құрайды, ал формулалардың жасалуы есептеулер синтаксисын құрайды.

9 слайд

10 слайд
Алгебра предикаты және сигнатура Алгебра предикаты σ сигнатурасының формуласы келесідей анықталады: σ = σ1 ∪ σ2, мұндағы σ1 - операциялар формулаларының жиынтығы, σ2 - М предикатының бос емес символдар жиынтығы. σ0 - σ1 жиынының нуль- арлы операцияларының ішкі жиыны. Формуланы анықтау барысында әр түрлі әріптер қолданылады: σ0 жиынында a, d, c; σ1 жиынында f, φ, ψ; σ2 жиынында p, q. Сонымен қатар, x, y, z, u, v әріптері М жиынынан алынған Х символдар жиынтығын білдіреді. Сигнатура құрылымы σ сигнатурасының құрамдас бөліктері Символдар жүйесі Алгебра предикатында қолданылатын әріптер мен таңбалар

10 слайд