3. Дәлелдеудің тура және жанама әдістері

Біз математикада теоремаларды дәлелдеген кезде ылғи да логикалық тұжырымдар келтіреміз P D (P – теореманың шарты, D – қорытынды), яғни формуласы тавтология болу, болмайтындығын анықтаймыз. Бұл кезде теореманың дәлелдеуі тура болуы мүмкін, қорытынды ережесінің негізінде P посылкасынан D қорытындысын аламыз. Алайда дәлелдеу жанама да болуы мүмкін, егер біз формуласының орнына оған тепе – тең формуланы қарастырсақ.

Теореманы тура деп атайық. Бұнымен қатар мына теоремаларды қарастыруға болады:

– кері;

– қарама - қарсы;

– кері қарама - қарсы.

Осы формулалардың ішінде алғашқысына тепе – теңі бар ма? Ақиқаттылық кестесін құру арқылы ондай формуланың болатындығына көз жеткіземіз. (2.11 кесте).

2.11 кесте

Ақиқаттылық кестесі

P	D
А	А	А	А	А	А
А	Ж	Ж	А	А	Ж
Ж	А	А	Ж	Ж	А
Ж	Ж	А	А	А	А

Тура теорема кері қарама – қарсыға тепе - тең:

.

Бұл тепе – теңдіктің арнаулы атауы бар – контрапозиция заңы. Сондай – ақ, кері және қарама – қарсы теоремалар да контрапозиция заңымен байланысты екенін ескерейік.

Мысал. Контрапозиция заңы бойынша «Егер тақ сан болса, онда m және n тақ болады» ( ) тұжырымын дәлелдеудің орнына, мына тұжырымды дәлелдеуге болады ( ): “егер m немесе n сандарының ең болмағанда біреуі тақ болса, онда тақ болады”.

Жанама дәлелдеу әдісіне «кері жору арқылы» дәлелдеулер жатады. Мұндай дәлелдеулердің схемасы тепе – теңдіктерге негізделген (олардың дұрыстығын ақиқаттылық кетсесі бойынша тексеруге болады):

;

;

.

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

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

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

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

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

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

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

Дәріс 10

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

Предикаттар логикасы

1. Предикат түсінігі

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

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

1. Предикат түсінігі

Барлық логикалық тұжырымдар логикалық пікірлердің көмегімен беріле бермейді. Кейде бізге сол сөйлемнің өзінің құрылымын зерттеуге тура келеді. Бұны предикаттар логикасы көмегімен жүзеге асыруға болады. “x ақ түсті” сөйлемі пікір емес, бірақ егер x орнына нақты бір мәнді қоятын болсақ, мысалы «қар» немесе «керік», онда біз пікір аламыз. Бұл сөйлем x –ң «ақ түсті болу» қасиетін сипаттайды және ол бір орыны предикат болып табылады. Егер «x ұзындығы бойынша y қарағанда үлкен» сөйлемін қарастырайық, онда нақты мәндер жұбын қоя отырып, «ақиқат» және «жалған» мәндерән қабылдайтын пікірлер аламыз. Бұл сөйлем екі обьектінің қасиетін сипаттап, екі орынды предикат болып табылады.

Жалпы алғанда n- орынды предикат деп аргументтері кез келген бір М жиынының элементтері болып табылатын, ал мәндері {А, Ж} жиынына тиісті функцияны айтады, яғни {А,Ж}. М жиынының элементтерін заттық айнымалылар деп аталады. Заттық айнымалылардың саны предикаттың реті болып табылады. Предикат А мәнін қабылдайтын заттық айнымалылардың мәндерінің жиынын предикаттың ақиқаттылық жиыны деп аталады. Мысалы, M=N жиынында бір орынды предикатын анықтайық – “x 2-ге бөлінеді”. Оның ақиқаттылық жиыны барлық бүтін оң сандар жиыны болады. M=R жиынында екі орынды предикат берейік – “x y-тан кіші”. Оның ақиқаттылық жиынын жазықтығында түзуінің жоғары жағында жатқан нүктелер жиыны түрінде бейнелеуге болады.

Айталық P және Q екі предикаты да бір М жиынында берілсін. Предикаттар тек қана екі (ақиқат және жалған) мән ғана қабылдай алатындықтан, онда оларға пікірлер логикасының амалдарын, жаңа предикаттар құра отырып, қолданамыз, сонымен қатар мұнда предикаттың реті өзгермейді: . Жаттығу ретінде осы предикаттарға өз беттеріңмен анықтама беріңдер.