- •І. Математикалық логиканың элементтері
- •1.1. Сөйлемдер мен пікірлер
- •1.2. Пікірлер конъюнкциясы мен дизъюнкциясы
- •1.3. Пікірлер импликациясы және эквиваленциясы
- •1.4. Тұжырымдар логикасы
- •Пропозиционалдық формулалар. Тавтологиялар.
- •Іі. Предикаттар мен кванторлар
- •2.1. Предикаттарды терістеу, олардың конъюнкциясы, дизъюнкциясы және имплекациясы
- •2.2. Қажетті және жеткілікті шарт. Кванторлар
- •2.3. Теоремалар
- •Алгоритмдер теориясының элементтері
- •Примитивті – рекурсивті функциялар
- •Тьюринг машинасы
- •Тьюринг машинасының композициясы
- •Алгоритмдік шешілмейтін проблемалар
- •Күрделілік функциясының асимптотикалық бағалаулары
- •Қорытынды
- •Пайдаланылған әдебиеттер
2.2. Қажетті және жеткілікті шарт. Кванторлар
жиынында : “ саны 4 – ке еселі”, : “ саны жұп” деген предикаттарға оралайық. Онда импликациясы “егер саны 4 – ке бөлінетін болса, онда ол жұп” деген мағынаны береді. жиынындағы қандай да бір санның жұп екенін тұжырымдау үшін оның жұп сан екенін білуіміз қажет, яғни мынаны білуіміз керек:
саны жұп болуы үшін оның 4 – ке бөлінуі жеткілікті;
саны 4 – ке бөлінетін болуы үшін оның жұп болғаны қажетті;
жиынында анықталған және предикаттарынан алынған импликациясында предикаты предикатының логикалық нәтижесі екендігі белгілі болса, онда предикаты предикаты үшін қажетті шарт, ал предикаты предикаты үшін жеткілікті шарт деп аталады.
Жоғарыдағы мысалда : “ саны 4 – ке бөлінеді” предикатының ақиқаттық жиыны ал : “ саны жұп” предикатының ақиқаттық жиыны болады және болғандықтан предикаты логикалық түрде предикатынан келіп шығады. Сондықтан предикаты предикаты үшін қажетті шарты, ал предикаты үшін жеткілікті шарт блып саналады.
Сонымен, : “ саны жұп” деген қажетті шарт предикатының ақиқат болуы үшін міндетті түрде орындалатын шарт екенін көреміз. Бірақ шарты предикатының ақиқат болуына кепіл бола алмайды, ол үшін жеткіліксіз, яғни кез келген жұп сан 4 – ке бөлінбейді. : “ саны 4 – ке еселі” деген жеткілікті шарт предикатының ақиқат болуы үшін қажетті шарттан әлдеқайда артық болып саналады. Мысалы, 10 саны 4 – ке еселі емес, дегенмен жұп сан.
“Қажетті шарт” деген сөздің “тек сонда”, “тек сол жағдайда”, “сонда тек сонда ғана” деген сөздермен жиі алмастырылатынына көңіл бөлу керек, “Егер сан 4 – ке еселі болса, онда ол жұп сан” деген импликацияны “егер сан 4 – ке бөлінсе, тек сонда ол жұп сан болады” деп оқуға болады.
Мынадай сөйлемді қарастырайық: “Төртбұрыш ромб болу үшін оның диагональдарының өзара перпендикуляр болуы қажетті”. Осы сөйлемді басқаша құруға бола ма? “Ромбтың диагоналі өзара перпендикуляр” деген сөйлем “Төртбұрыш – ромб” деген сөйлемнен туады. Сондықтан жоғарыдағы сөйлемді былайша оқуға болады:
Төртбұрыштың ромб болғандығынан оның диагональдарының перпендикулярлығы шығады;
Кез келген ромбтың диагональдары өзара перпендикуляр;
Егер төртбұрыш ромб болса, оның диагональдары өзара перпендикуляр болады;
Төртбұрыштың диагональдары перпендикуляр болу үшін оның ромб болу жеткілікті;
Бастауыш мектептің математика курсында “қажетті”, “жеткілікті” деген сөздер қолданылмайды, бірақ олардың орнына бұл сөздердің синонимдері “керек”, “болады” сөздері қолданылады.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 сандары туралы мынадай ой айтуға болады:
Барлық берілген сандар бір орынды
б) Берілген сандардың кейбіреуі жұп сандар
Бұл сөйлемдердің ақиқат не жалғандығын анықтауға болатындықтан екеуі де пікір болады. Енді “а” сөйлемінен “барлық” деген сөзді алып тастасақ “Берілген сандар бір орынды” деген сөйлем құрылады. Бұл сөйлем пікірлік форма болады. Сонымен, бұл пікірлік форманың алдына қойылған “барлық” сөзі оны пікірге айналдыратын екен.
“б” сөйлеміндегі “кейбіреуі” деген сөз “берілген сандар жұп” деген предикатты пікірге айналдырып тұр. Сонымен қатар “бар болады” деген сөзді қолданып та предикатты пікірге айналдыруға болады.
“Барлық”,
“бар”
“болады”,
“кейбір”
деген сөздер кванторлар
деп аталады. Осындай пікірлерді жазу
үшін
және
символдары пайдаланылады.
символы “барлық”, “әрбір”, “кез
келген”, “әртүрлі” деген сөздердің
орнына қолданылып, жалпылау
кванторы деп аталады.
символын “бар болады”, “қандай
болмасын”, “ең болмағанда бір”,
“табылады” сөздерінің орнына пайдаланып,
оны бар
болу
кванторы деп атайды.
Мысалы:
:
“
,
”
предикаты үшін
,
түріндегі жазба “кез келген
натурал саны үшін
теңсіздігі орындалады” деген пікірді
білдіреді. Бұл – пікір ақиқат, өйткені
қандай да бір
натурал санды алсақ та, үнемі
болады. Ал,
,
жазбасы “
теңсіздігі орындалатын
натурал саны бар болады”
деп оқылады. Бұл пікір де ақиқат. Сонымен,
жиынында берілген қандай да бір предикат
болса, онда
,
деген жазба “
жиынындағы барлық
үшін
орындалады” деген пікір болады. Бұл
пікірдің ақиқаттығын анықтау үшін
жиынынан кез келген а элементін алып,
пікірінің ақиқат екенін көрсету керек.
Егер де,
жиынындағы ең болмағанда бір а элементі
үшін
жалған болса, онда
,
жалған пікір болады.
Мысалы,
барлық жәй сандар жиынында
:
“
тақ сан”
деген предикат берілсін. Сонда
,
жазуы “Барлық жәй сандар тақ” деп
оқылады. Бұл пікір жалған, себебі
саны жәй, бірақ тақ емес, яғни “2 тақ
сан” деген пікір жалған. Егер
жиынында анықталған
предикаты үшін
,
жазуы берілсе, ол “
жиынында
орындалатын
бар болады” деп оқылады. Бұл жазуды “
жиынынан
орындалатын ең болмағанда бір
элементі табылады” деп те оқуға болады.
жиынынан алынған ең болмағанда бір а
элементі үшін
ақиқат болса,
,
пікір ақиқат болады. Егер
ақиқат болатындай
жиынынан бірде бір элемент табылмаса,
ол жалған пікір болады. Мысалы,
жәй сандар жиынында
:
“
саны жұп” деген предикат берілсін.
Сонда
,
пікір ақиқат. Шындығында да жәй сандар
жиынында
саны табылып, “2 саны жұп” деген ақиқат
пікір аламыз.
және
кванторлары екі, үш, тағы сол сияқты
орынды предикаттар үшін де қолданылады.
Мысалы, барлық нақты сандар жиынында
предикаты
:
“
”
берілген болсын. Сонда
,
,
жазылуы “кез келген
,
нақты сандар үшін
”
теңдігі орындалады.
Барлық
нақты сандар жиынында
:
“
”
предикатын қарастырайық. Сонда
,
,
жазылуы “кез келген
нақты саны үшін
теңсіздігі орындалатын
нақты саны бар болады” деген мағына
береді. Бұл пікір ақиқат.
