3. Предикаттар логикасының формулалары

Логикалық амалдардың таңбаларын және кванторлардың көмегімен предикаттық символдардан предикаттар логикасының формулалары құрылады, олар заттық облысты сипаттау үшін ақпараттық есептерде қолданылады. Сонымен қатар М заттық айнымалылардың жиынының мазмұны анықталады, ал әрбір предикаттық символға маңына беріледі – осы предикатты сипаттайтын қасиет беріледі. Осылайша, формулаларға қандай да бір интерпретация беріледі. Әр түрлі интерпретациядағы бір формула әр түрлі мән қабылдайды.

Мысал. Айталық формуласы берілсін. Оның екі интерпретациясын қарастырайық:

I₁: M=N, ;

I₂: M=Z, .

Бірінші жағдайда F=А – бұл ең кіші натурал санның бар болуы туралы тұжырым. Екінші жағдайда F=Ж.

Егер F формуласы қандай да бір интерпретацияда өзінің аргументтерінің кез келген мәнінде ақиқат болса, онда ол берілген интерпретацияда ақиқат болады. Кез келген интерпретацияда ақиқат болатын формула жалпы мәнді деп аталады. Мысалы, формуласы жалпы мәнді болады. Осыған сәйкес берілген интерпретациядағы тепе – тең формулалар және жай тепе –теңдіктер жайлы да айтуға болады.

Пікірлер логикасында біз ақиқаттылық кестесінің көмегімен әрқашанда формуланың тавтология болатындығын анықтауға болады. Предикаттар логикасында формула жалпы мәнді болатындығын анықтаудың біріңғай процедурасы жоқ: өйткені әрбір формулаға интерпретацияның шексіз санын беруге болады.

3. Формулаларды тепе – тең түрлендіру

Предикаттар логикасының екі формуласы мәндес деп аталады, егер олар кез келген интерпретацияда айнымалылардың кез келген мәнінде біріңғай ақиқат мәнін қабылдаса. Пікірлер логикасының барлық мәндестігі (2.5 кесте) предикаттар логикасында да орындалады. Предикаттар логикасында, сонымен қатар құрамында кванторлары бар формулаларды түрлендірумен байланысты мәндестіктер кездеседі (2.13 кесте).

2.13 кесте

Предикаттар логикасының негізгі мәндестіктері

№	Формула
1
2
3
4
5
6

Мұндағы бірінші формуланы дәлелдейік: .

Бұл формуланың М жиынындағы кез келген I интерпретациясын берейік. Заттық айнымалының кез келген мәнінде формуланың оң және сол жағы біріңғай екендігін көрсетейік.

Айталық,берілген интерпретацияда А болсын, онда Ж. Квантордың анықтамасы бойынша бар болу дегеніміз М жиынында «ақиқат» мәнін қабылдайтындай x элементі жоқ. Бұдан, барлық x заттық айнымалылардың мәнінде предикат Ж, ал А болады. Квантордың жалпылығының анықтамасы бойынша формуласы берілген интерпретацияда ақиқат болады.

Егер формуласы берілген интерпретацияда жалған болса, онда ақиқат. Бұл дегеніміз, болатындай ең болмағанда бір элементі табылады, яғни Ж. Ал ендеше берілген интерпретацияда жалған болады. Бұдан, және берілген иетерпретацияда мәндес болады, ал оның кез келгендігінен, мәндес.

Предикаттар логикасының қалған мәндестіктері осыған ұқсас дәлелденеді (2.7 кесте). 3,4 және 5,6 формулалар жұптарының арасындағы айырмашылықты ескеріңіздер. 3, 4 формулаларда «туысқан» амалдар қолданылады: конъюнкция және жалпыға бірдей квантор, дизъюнкция және бар болу кванторы. 5, 6 формулаларда кванторды жақшаның сыртына шығармастан бұрын, бар болу кванторлардың әрекет етуінің әр түрлі облысын бөліп көрсету үшін, айнымалыны алмастыру қажет: .

Расында да, егер «х математикадан бес алды» дегенді білдірсе, ал – “x физикадан бес алды” дегенді білдірсе, онда А, ал Ж болуы мүмкін (егер бесті әр түрлі адамдар алса).

Ұсынылған әдебиеттер:

1. Нұрсұлтанов Қ.Н., Дискретті математика және математикалық логика. – Семей 2002.

2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. –М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.

3. Смыслова З.А.. Дискретная математика (Учебное пособие), Томск, 2000.

4. Қ.Жетпісов., Математикалық логика және дискретті математика. Алматы, 2011.

5. Шапорев С.Д. Математическая логика. Курс лекций и практических заниятий.- СПБ.: БХВ-Петербург 2005. - 416стр.

6. Тишин В.В. Дискретная математика в задачах и примерах. БХВ-Петербург 2008.

Дәріс 11

Дәріс сабақтың құрылымы: