- •І. Математикалық логиканың элементтері
- •1.1. Сөйлемдер мен пікірлер
- •1.2. Пікірлер конъюнкциясы мен дизъюнкциясы
- •1.3. Пікірлер импликациясы және эквиваленциясы
- •1.4. Тұжырымдар логикасы
- •Пропозиционалдық формулалар. Тавтологиялар.
- •Іі. Предикаттар мен кванторлар
- •2.1. Предикаттарды терістеу, олардың конъюнкциясы, дизъюнкциясы және имплекациясы
- •2.2. Қажетті және жеткілікті шарт. Кванторлар
- •2.3. Теоремалар
- •Алгоритмдер теориясының элементтері
- •Примитивті – рекурсивті функциялар
- •Тьюринг машинасы
- •Тьюринг машинасының композициясы
- •Алгоритмдік шешілмейтін проблемалар
- •Күрделілік функциясының асимптотикалық бағалаулары
- •Қорытынды
- •Пайдаланылған әдебиеттер
Пропозиционалдық формулалар. Тавтологиялар.
Пропозиционалдық формула ұғымы (қысқаша пф) алгебралық өрнек анықтамасына ұқсас.
Келесі символдар тізімінен шектелген тізбектер құрастырамыз:
0,1 –– ақиқат мәндерінің символдары, оларды тұрақтылар деп атаймыз;
––
логикалық
амалдар символдары (немесе пропозиционалдық
байланыстар);
––
әріптердің
шексіз тізімі (пропозиционалдық
айнымалылар немесе жай айнымалылар);(,) –– жақшалар.
Осы шектелген тізбектердің кейбіреулерін пф деп атаймыз. Пропозиционалдық формула ұғымы индуктивті түрде енгізіледі.
1. 0, 1 тұрақты символдары пф болып табылады.
2. Әрбір айнымалы пф болып табылады.
3-7.
Егер A
мен В пф болса, онда
–– пф.
Анықтамада 1 және 2 пунктері бастапқы пф анықтайды, ал 3-7 пунктері жаңа пф құру ережелері деп аталады. Мұндай пф { , 0, 1 } тіліндегі пф деп атаймыз.
Мысалдар.
0, 1, p, r, q, s,
p1,
q10 –
бастапқы пф;
Айнымалының кез келген мәндер жиынында тек қана 1 мәнін қабылдайтын пф (сәйкес 0) тепе-тең–ақиқат пропозиционалдық формула немесе тавтология (сәйкес тепе-тең-жалған пропозиционалдық формула немесе қарама-қайшылық) деп аталады.
Кейбір негізгі тавтологияларды келтірейік. ╞А белгілеуі А пф тавтология екенін көрсетеді.
I.
╞
(үшіншіні жою заңы);
II.╞
(екі рет терістеу заңы);
III.╞
;
IV. ╞
(идемпотенттілік заңы);
V.
╞
VI.
╞
VII.╞
VIII. ╞
(коммутативтілік заңы) ;
IX.╞
;X.
╞
(ассоциативтілік заңы);
XI.╞
;
XII
╞
(дистрибутивтілік заңы);
XIII.
╞
;
XIV.
╞
(де Моргана заңдары);
XV.
╞
(контрапозиция заңы);
XVI.╞
(импликацияның транзитивтілік заңы);
XVII.╞
(жанама дәлелдеу заңы);
XVIII.╞
(кездейсоқтық заңы);
XIX.╞
(эквиваленцияның транзитивтілігі заңы);
XX
╞
(қарама-қайшылық заңы);
XXI.
╞
╞
(1 – ң
және
арқылы өрнектелуі);
XXII.╞
╞
(0 – ң
және
арқылы өрнектелуі);
XXIII.╞
(
- ң
арқылы өрнектелуі);
XXIV.╞
(
- ң
арқылы өрнектелуі);
XXV.
╞
(
- ң
арқылы өрнектелуі);
XXVI.
╞
(
-ң
арқылы өрнектелуі).
Іі. Предикаттар мен кванторлар
2.1. Предикаттарды терістеу, олардың конъюнкциясы, дизъюнкциясы және имплекациясы
жиынында
предикаты берілген болсын. Оның кері
предикаты дәл сол
жиынында анықталған және берілген
предикат
жиынының жалған болатын мәндерінде
ғана ақиқат болатын предикатты айтады.
Оны
деп белгілеп,
предикатының терістеу деп атайды.
Мысалы, “
”
предикаты
жиынында берілсін. Оның ақиқаттық жиыны
болады. Сонда, оның кері предикаты
“
”.
Оның ақиқаттық жиыны
болады. Бұл жиын
жиынының
жиынына дейінгі толықтырылуы болады
(1 - сызба).
1 - сызба
жиынында
және
екі предикаты берілсін.
элементар
,
предикаттарының конъюнкциясы
деп
жиынының
және
предикаттарының екеуі де ақиқат болатын
түрдегі күрделі предикатын айтады.
Мысалы,
жиынында
“
”
және
:
“
жұп сан” деген екі предикат берілсе,
онда олардың конъюнкциясы
:
“
саны 8 – ден кем және жұп сан” предикаты
болады.
предикатының ақиқаттық жиыны
ал
предикатының ақиқаттық жиыны
.
“
саны 8 – ден кем және жұп сан” предикатының
ақиқаттық мәндері
болады. Олай болса
ақиқаттық жиыны
мен
жиындарының қиылысуына тең, яғни
(2
- сызба).
2 - сызба
жиынындағы
күрделі предикаты
және
предикаттарының дизъюнкциясы
деп аталады. Ол
жиынының
және
предикаттарының, ең болмағанда, біреуі
ақиқат болатын мәндерінде ақиқат болады.
Мысалы,
жиынында
:
“
саны 8 – ден кем”
:
“
жұп сан” предикаттарының
дизъюнкциясы “
саны 8 – ден кем немесе жұп сан” болады.
Сонда оның ақиқаттық жиыны
яғни
болады (3 - сызба).
3 - сызба
Теріске
шығару, конъюнкция, дизъюнкция амалдарын
пайдаланып берілген предикаттар арқылы
күрделі предикаттар құруға болады.
Мысалы
тағы сол сияқты. Жоғарыдағы қарастырылған
мысалдағы
жиынындағы
:
“
саны 8 – ден кем” және
:
“
жұп сан” предикаттарының
күрделі предикаттарының ақиқаттық
жиынын табайық.
предикаты “
саны 8 – ден кем және жұп емес” деп
оқылады.
предикатының ақиқаттық жиыны
екенін анықтағанбыз. Ол предикаттың
терістеуінің анықтамасы бойынша
жиынының
жиынына дейінгі толықтырылуы, яғни
болады.
жиынында және предикаттары берілсін. предикаты ақиқат, ал предикаты жалған пікірлер болатын деп -тің мәндерінде жалған болатын күрделі предикатты және предикаттарының импликациясы деп атайды.
Екі
предикаттың импликациясы
белгіленеді.
жиынындағы
– тің басқа мәндерінде
предикаты ақиқат болады.
1
– мысал.
жиынында
:
“
саны 5 – ке еселі”,
:
“
саны тақ” деген екі предикатты алайық.
Сонда
предикаты “Егер
саны 5 – ке еселі болса, онда ол тақ сан
болады”
деген сөйлем болады. Осы предикаттың
ақиқаттық жиынын табайық.
жиыны
предикатының
жиыны
предикатының ақиқаттық жиындары болсын.
Сонда
,
болады. Эйлер – Венн диаграммасы арқылы
осы жиындарды кескіндейік (4 - сызба).
4 - сызба
Импликацияның
анықтамасы бойынша “егер
саны 5 – ке еселі болса, онда ол тақ сан
болады” деген предикат
болғанда ғана жалған пікірге айналады.
жиынының басқа элементтер үшін бұл
импликация ақиқат болады.
предикатының ақиқаттық жиыны
.
4 - сызбада
жиыны штрихталып көрсетілген, сонымен
қатар
жиыны
жиынынан және
жиынының
жиынына дейінгі толықтырылуынан тұрады,
сонда
.
Жалпы предикатының ақиқаттық жиыны предикатының ақиқаттық жиыны мен предикатының ақиқаттық жиынының жиынына дейінгі толықтырылуының бірігуінен тұрады.
2
– мысал.
жиынында
:
“
саны 4 – ке еселі”,
:
“
саны жұп” деген предикаттарды
қарастырайық.
импликациясы “Егер
саны 4 – ке еселі болса, онда ол жұп сан
болады” деген предикатты береді.
предикатының ақиқаттық жиыны
,
предикатының ақиқаттық жиыны
.
Бұл жағдайда
яғни
предикатының ақиқат болатын жағдайларының
барлығында
предикаты да ақиқат болады.
жиынының кез келген мәнінде
предикатының ақиқат болатынын көреміз.
Олай болса,
.
Демек, “егер
саны 4 – ке еселі болса, ол жұп сан болады”
деген предикат
жиынындағы
кез келген
-тің мәнінде ақиқат пікірге айналады.
жиыны 5 – сызбада штрихталып көрсетілген.
8
6
5 - сызба
Жалпы, жиынында берілген предикаты тек предикатының ақиқаттық жиыны предикатының ақиқаттық жиыны –нің ішкі жиыны болатын, яғни , жиынындағы –тің мәндерінде ғана ақиқат болуы мүмкін. Егер импликациясы оның анықталу облысындағы –тің барлық мәндерінде ақиқат пікірге айналатын болса, онда предикатын предикатының логикалық салдары деп атайды.
Сондықтан “Егер саны 4 – ке еселі болса, онда ол жұп сан болады ” деген импликацияны “ санының 4 – ке еселі болатындығынан оның жұп сан болатындығы шығады” деп айтуға болады. Егер жиыны жиынының ішкі жиыны болмаса, бұлай тұжырым жасауға болмайды.
Мектептің математика курсында анықталу облысындағы –тің барлық мәндерінде ақиқат болатын импликациялар жиі кездеседі. Мысалы: “Егер санның жазылуындағы цифрлардың қосындысы 3 – ке бөлінсе, онда берілген сан 3 – ке бөлінеді” деген белгіні алайық. Бұл импликацияда “берілген сан 3 – ке бөлінеді” деген предикат “санның жазылуындағы цифрлардың қосындысы 3 – ке бөлінеді”деген предикат “санның жазылуындағы цифрлардың қосындысы 3 – ке бөлінеді” предикаттың логикалық салдар болады.
Бастауыш
мектепте натурал сандар жиынында
анықталған “Егер
болса,
”,
“Егер
болса, онда
”
тағы сол сияқты импликациялар көптеп
қарастырылады.
