Санал болгож буй сурах бичиг (2-р хэвлэл, хэвшмэл ойлголт) нь математикийн логик, алгоритмын онолын багцын үндэс суурийг бүрдүүлдэг бөгөөд үүнд асуудлын цуглуулга багтсан болно (Игошин В.И. Математик логик ба алгоритмын онолын даалгавар, дасгалууд) .

Онолын үндэс суурийг нарийвчлан тайлбарлаж, логикийг алгебр, анализ, геометрийн үндэс рүү нэвтрүүлэх чиглэлийг харуулсан, сургуулийн математикийн хичээлийн материалыг логик шинжилгээнд ашигласан, математик логикийн компьютертэй харилцах, мэдээлэл зүй, хиймэл оюун ухааны системүүд тодорхойлогддог.

Танилцуулга. Орчин үеийн боловсролын систем дэх математик логик.
Логик ба зөн совин. Логик уламжлалт ба математик логик. Жаахан түүх. Математик логик - логик эсвэл математик үү? Математик заах математик логик. Математик логик ба орчин үеийн компьютерууд.
Бүлэг I. Тайлбарын алгебр.
§ 1. Тэдэнтэй холбоотой мэдэгдэл, үйл ажиллагаа.
Үг хэлэх тухай ойлголт. Мэдэгдэлийг үгүйсгэх. Хоёр өгүүлбэрийн холбоо. Хоёр мэдэгдлийг салгах. Хоёр мэдэгдлийн утга учир. Хоёр мэдэгдлийн эквивалент. Хэл ба логик үйлдлүүдийн нэгдэл (хэл ба логик). Логик үйлдлүүдийн ерөнхий үзэл бодол.
§2. Санал алгебрийн томъёо.
Нарийн төвөгтэй өгүүлбэр байгуулах. Санал алгебрийн томъёоны тухай ойлголт. Нийлмэл өгүүлбэрийн логик утга. Томъёоны үнэний хүснэгтийн эмхэтгэл. Санал алгебрийн томъёоны ангилал. Сэтгэн бодох чадвар, математик логик
§ 3. Санал алгебрын тавтологи.
Тавтологийн утгын талаар. Үндсэн тавтологи. Тавтологи олж авах үндсэн дүрмүүд.
§ 4. Томъёоны логик тэнцүү байдал.
Томъёоны эквивалентийн тухай ойлголт. Томьёоны тэнцүү байдлын тэмдэг. Ижил томъёоны жишээ. Томъёоны эквивалент хувиргалт. Логик болон алгебр дахь ижил төстэй байдал.
§ 5. Санал алгебрийн томъёоны хэвийн хэлбэрүүд.
Ердийн хэлбэрийн тухай ойлголт. Төгс хэвийн хэлбэрүүд. Санал алгебрийн томъёог төгс салгах хэвийн (CDN) хэлбэрээр дүрслэх. Санал алгебрийн томъёог төгс коньюнктив хэвийн (SKN) хэлбэрээр илэрхийлэх. Санал алгебрийн томьёог төгс хэвийн хэлбэрт оруулах хоёр арга
§ 6. Томъёоны логик дараалал.
Логик үр дагаврын тухай ойлголт. Логик үр дагаврын шинж тэмдэг. Логик үр дагаврын хоёр шинж чанар. Томъёоны дараах ба эквивалент. Логик үндэслэлийн дүрэм. Логик дарааллыг шалгах өөр нэг арга. Эдгээр байрнуудын үр дагаврыг олох. Энэ мөрдөн байцаалтад зориулж байр хайж байна.
§ 7. Логико-математикийн практикт саналын алгебр хэрэглэх.
Шууд ба урвуу теоремууд. Шаардлагатай, хангалттай нөхцөл. Эсрэг теоремын эсрэг ба урвуу. Эсэргүүцлийн хууль. Математикийн теоремийн бүтцийг өөрчлөх. Математикийн теоремыг батлах аргууд. Дедуктив ба индуктив үндэслэл. Зөв ба буруу дедуктив үндэслэл. Логик асуудлуудыг шийдвэрлэх. Бүрэн салгах зарчим. Бүрэн дизюнкцийн зарчмын нэг ерөнхий ойлголт.
II бүлэг. Булийн функцууд.
§8. Олонлогууд, харилцаа холбоо, функцууд.
Олонлогийн тухай ойлголт. Багцуудыг оруулах ба тэгш байдал. Багц дээрх үйлдлүүд. Хоёртын харилцаа ба функцууд. Лар харилцааны тухай ойлголт.
§ 9. Нэг ба хоёр аргументын логик функцууд.
Булийн функцүүдийн гарал үүсэл. Нэг аргументаас логикийн функцууд. Хоёр аргументийн логик функцууд. Дизьюнкц, коньюнкц, үгүйсгэлийн шинж чанарууд. Эквивалент, импликац, үгүйсгэлийн шинж чанарууд. Зарим Булийн функцийг бусад функцээр илэрхийлэх
§ 10. n аргументын логик функцууд.
Булийн функцийн тухай ойлголт. Булийн функцүүдийн тоо. Булийн функцийг коньюнкц, дизъюнкц, үгүйсгэх замаар илэрхийлэх. Боолийн функцууд ба санал алгебрийн томъёо. Булийн функцүүдийн хэвийн хэлбэрүүд.
§ 11. Булийн функцын системүүд.
Булийн функцүүдийн бүрэн системүүд. Булийн функцүүдийн тусгай ангиуд. Булийн функцүүдийн системийн бүрэн байдлын тухай Пост теорем
§ 12. Булийн функцийг реле-контакт хэлхээнд хэрэглэх.
Хэрэглээний санаа. Реле-контакт хэлхээний онолын хоёр үндсэн ажил.
§ 13. Компьютерийн реле контактын хэлхээ.
Хоёртын хагас нэмэгч. Нэг битийн хоёртын нэмэгч. кодлогч ба декодер.
§ 14. Булийн функцийн онолын бусад хэрэглээний талаар.
Өвчний оношлогоо (хүлээн зөвшөөрөх). Загвар таних.
III бүлэг. Албан ёсны саналын тооцоо.
§ 15. Аксиомын систем ба албан ёсны дүгнэлтийн онол.
Аксиоматик саналын онолын эхлэл: анхны ойлголт, аксиомын систем, дүгнэлтийн дүрэм. Дүгнэлтийн тухай ойлголт ба түүний шинж чанарууд. Дедукцийн теорем ба түүний үр дагавар. Дедукцийн теоремын хэрэглээ. Гаргасан дүгнэлтийн дүрэм
§ 16. Албан ёсны саналын тооцооны бүрэн байдал болон бусад шинж чанарууд
Томьёоны нотлох чадвар ба түүний ижил үнэн (синтакс ба семантик). Үүсгэх чадвар Лемма. Албан ёсны саналын тооцооны бүрэн байдал. Хангалттай байдлын теорем. Албан ёсны саналын тооцооны уялдаа холбоо. Албан ёсны тооцооллын шийдвэр гаргах чадвар
§ 17. Албан ёсны саналын тооцооны аксиомын системийн бие даасан байдал.
Тусгаар тогтнолын тухай ойлголт. Аксиомын бие даасан байдал (A1). Аксиомын бие даасан байдал (A2). Аксиомын бие даасан байдал (A3). Аксиомын системийн бие даасан байдал
IV бүлэг. Предикат логик.
§ 18. Предикаттай холбоотой үндсэн ойлголтууд.
Предикатын тухай ойлголт. Предикатуудын ангилал. Предикатын үнэний багц. Эквивалент ба дараах предикатууд
§ 19. Предикат дээрх логик үйлдлүүд.
Предикат үгүйсгэх. Хоёр предикатын холбоо. Дикат хуудас руу орохын тулд дизайн хийх. Үгүйсгэх, холбогч, салгах шинж чанарууд. Хоёр предикатын далд утга ба эквивалент.
§ 20. Предикат дээрх тоон үзүүлэлтийн үйлдлүүд.
Ерөнхий хэмжигч. Оршихуйн хэмжигч. Тоон хэмжигч. Хязгаарлагдмал тоологч. Логик квадрат
§ 21. Предикатын логикийн томьёо.
Предикатын логик томъёоны тухай ойлголт. Предикатын логик томъёоны ангилал. Предикатын логикийн тавтологи
§ 22. Томъёоны эквивалент хувиргалт ба предикатын логикийн томъёоны логик үр дагавар
Томъёоны эквивалентийн тухай ойлголт. Предикатын логик томьёоны багасгасан хэлбэр. Предикатын логик томьёоны өмнөх хэвийн хэлбэр. Предикатын логик томъёоны логик дараалал
§ 23. Томъёоны хүчинтэй байдал, хангалтыг шийдвэрлэх асуудлууд.
Асуудлын мэдэгдэл ба түүнийг шийдвэрлэх боломжгүй байдал ерөнхий үзэл. Төгсгөлтэй олонлог дээрх томьёоны асуудлын шийдэл. Хязгааргүй олонлогт хэрэгжих боломжтой, ямар ч төгсгөлтэй олонлогт боломжгүй томьёоны жишээ. Сэтгэл ханамжийг шийдвэрлэх асуудал: багцын үндсэн байдал ба томъёоны бүтцэд үзүүлэх нөлөө. Зөвхөн нэг байрлалтай предикат хувьсагчийг агуулсан томъёоны асуудлыг шийдвэрлэх. Томьёог авч үзсэн багцын хүчин төгөлдөр байдал, үндсэн байдлыг шийдвэрлэх асуудал. V-томьёо ба 3-томьёоны бодлого бодох
§ 24. Предикатын логикийг логик-математикийн практикт хэрэглэх.
Янз бүрийн өгүүлбэрийн логикийн хэлээр бичлэг хийх. Предикатын логик ба саналын логикийн харьцуулалт. Математикийн теоремуудын бүтэц. Тайлбарлах аргууд: Аристотелийн силлогистик. Аристотелийн силлогистик ба предикатуудын логик. Аристотелийн силлогистикийн олонлогийн онолын тайлбар. Бусад үндэслэлийн аргуудын талаар. Предикат хэлбэрээр бүрэн салгах зарчим. Математикийн индукцийн (бүрэн) арга Шаардлагатай ба хангалттай нөхцөл. Логикийг таамаглах, алгебр тогтоох.
§ 25. Албан ёсны предикатын тооцоо.
Анхдагч ойлголтууд (албан ёсны предикатын тооцооллын хэл). Предикатын тооцооны аксиомын систем. татах дүрэм. Албан ёсны дүгнэлтийн онол.
Бүлэг V. Албан бус аксиоматик онолууд.
§ 26. Математик, аксиоматик онол дахь аксиоматик арга.
Аксиоматик онолын тухай ойлголт. Аксиоматик онолууд хэрхэн үүсдэг. Аксиоматик онолын жишээ. Аксиоматик онолын тайлбар ба загварууд.
§ 27. Аксиоматик онолын шинж чанарууд.
Тогтвортой байдал. Ангилал. Аксиомын системийн бие даасан байдал. Бүрэн байдал.
VI бүлэг. Албан ёсны аксиоматик онолууд.
§ 28. Албан ёсны аксиоматик онолуудын тухай.
Албан ёсны аксиоматик онолын санааны түүхийн тухай. Албан ёсны аксиоматик онолын тухай ойлголт. Хэл ба металл хэл, албан ёсны онолын теорем ба метатеоремууд. Албан ёсны онолын тайлбар ба загварууд. семантик гаралт. Метаматематик (албан ёсны аксиоматик онолын шинж чанарууд). Албан ёсны аксиоматик онол болох албан ёсны саналын тооцоо.Аристотелийн силлогизмын онолыг албан ёсны болгох.
§ 29. Албан ёсны предикатын тооцооллын шинж чанарууд.
Аксиоматжуулалтын үндэслэл.Албанжуулсан предикатын тооцооны уялдаа холбоо. Загвар оршин тогтнох тухай Годелийн теорем. Албан ёсны предикатын тооцооны бүрэн ба хүрэлцээтэй байдал. Үнэмлэхүй ба явцуу утгаараа албан ёсны предикатын тооцооны бүрэн бус байдал Авсаархан байдлын теорем.
§ 30. Нэгдүгээр эрэмбийн албан ёсны онолууд.
Нэгдүгээр эрэмбийн онолууд тэгш эрхтэй. Албан ёсны олонлогийн онолууд дээр. Албан ёсны арифметик дээр. Тооны системийн албан ёсны онолын тухай.Албан ёсны геометрийн тухай. Албан ёсны тухай математик шинжилгээ. Математикийн онолыг албан ёсны болгох үйл явцын ерөнхий үзэл баримтлал.Аксиоматик аргын хил хязгаар, хэлбэржүүлэх арга, логик.
VII бүлэг. Алгоритмын онолын элементүүд.
§31. Алгоритмуудын талаархи зөн совингийн ойлголт.
Бидний эргэн тойрон дахь алгоритмууд. Алгоритмын тухай албан бус ойлголт. Алгоритм гэдэг ойлголтыг тодруулах хэрэгцээ.
§ 32. Тьюрингийн машин.
Тьюрингийн машины тодорхойлолт Тьюрингийн машиныг үгэнд хэрэглэх. Тюринг машины загвар. Тюринг-тооцоолох функцууд. Тюринг машин дээрх функцүүдийн зөв тооцоолол. Тюринг машинуудын найрлага. Тьюрингийн дипломын ажил (алгоритмын онолын үндсэн таамаглал). Тюринг машин ба орчин үеийн электрон компьютер.
§ 33. Рекурсив функцууд.
Рекурсив функцүүдийн гарал үүсэл. Рекурсив функцийн онолын үндсэн ойлголтууд ба Черчийн дипломын ажил. Анхдагч рекурсив функцууд. Предикатуудын команд рекурсив байдал. Команд рекурсив функцүүдийн Туринг тооцоолох чадвар. Акерман функцууд. багасгах оператор. Ерөнхий рекурсив ба хэсэгчилсэн рекурсив функцууд. Хэсэгчилсэн рекурсив функцүүдийн Туринг тооцоолох чадвар. Тюринг-тооцоолох функцүүдийн хэсэгчилсэн рекурсив байдал.
§34. Ердийн Марков алгоритмууд.
Марковын сэлгээ. Ердийн алгоритмууд ба тэдгээрийг үгэнд хэрэглэх. Ердийн тооцоолж болох функцууд ба Марковын хэвийн болгох зарчим. Бүх ердийн тооцоолдог функцуудын ангилал Тьюрингийн бүх тооцоологдох функцүүдийн ангилалтай давхцах. Алгоритмуудын янз бүрийн онолуудын тэнцүү байдал.
§ 35. Багцыг шийдвэрлэх, тоолох чадвар.
§ 36. Шийдэгдэхгүй алгоритмын бодлого.
Алгоритм дугаарлалт. Тюринг машины дугаарлалт. Тьюрингийн тооцоолоогүй функцүүд байгаа эсэх. Өөрийгөө хэрэглэх, хэрэглэх чадварыг хүлээн зөвшөөрөх асуудал. Алгоритмын ерөнхий онолын алгоритмын хувьд шийдэгдээгүй асуудлууд. Райсын теорем. Алгоритмийн шийдвэр гаргах боломжгүй байдлын бусад жишээнүүд.
§ 37. Албан ёсны арифметикийн бүрэн бус байдлын тухай Годелийн теорем.
Албан ёсны аксиоматик онол ба бүхэл тоо. Албан ёсны арифметик ба түүний шинж чанарууд. Годелийн бүрэн бус байдлын теорем. Годель ба түүний 20-р зууны математик логик дахь үүрэг. .
VIII бүлэг. Математик логик ба компьютер, мэдээлэл зүй, хиймэл оюун ухаан.
* § 38. Математик логик ба програм хангамжкомпьютерууд.
Алгоритм ба математик логикийн онол - үндсэн суурьпрограмчлал. Тодорхойлолт компьютерийн програмуудматематик логик ашиглан. Програмчлалын тодорхойлолт, математик логик ашиглан түүний үзэл баримтлалд дүн шинжилгээ хийх. Математик логик ашиглан програмын баталгаажуулалт (зөв байдлын баталгаа).
§ 39. Математик логикийн теоремуудыг батлахад компьютер ашиглах.
"Логик-онолч" нэвтрүүлэг, түүнд ойртсон хөтөлбөрүүд. Бодолт ба предикатын тооцоонд теоремыг батлах арга.
§ 40. Математик логикоос логик програмчлал хүртэл.
PROLOG хэлний үүсэл, түүний хөгжил. ерөнхий шинж чанархэлний ПРОЛОГ. Товч тодорхойлолтхэлний PROLOGUE ба жишээнүүд. PROLOG хэлний хэрэглээний хүрээ.
§41. Математик логик ба мэдээлэл зүй.
Ерөнхий ойлголтмэдээллийн сангийн тухай. Харьцааны мэдээллийн сан ба асуулгын логик.
§ 42. Математик логик ба хиймэл оюун ухааны систем Хиймэл оюун ухааны хөгжлийн түүх, шинжлэх ухаан болох сэдэв. Хиймэл оюун ухааны систем дэх мэдлэгийн төлөөлөл. Мэргэшсэн системүүд. Хиймэл оюун ухааны систем дэх PROLOG хэл. Машин бодож чадах уу.
Дүгнэлт: Сэтгэлгээний хуулиудын мэдлэгт логик нь бүхнийг чадагч уу?
Ном зүй.

Логик ба зөн совин.
Хүний оюун санааны үйл ажиллагаа нь ухамсрын болон ухамсаргүй (далд ухамсар) түвшинд хоёуланд нь тохиолддог нарийн төвөгтэй, олон талт үйл явц юм. Энэ бол хүний ​​​​мэдлэгийн хамгийн дээд түвшин, бодит байдлын объект, үзэгдлийг зохих ёсоор тусгах чадвар юм. үнэнийг олохын тулд.

Логик ба зөн совин нь хүний ​​сэтгэлгээний хоёр эсрэг тэсрэг, салшгүй холбоотой шинж чанарууд юм. Логик (дедуктив) сэтгэлгээ нь туршлага, зөн совин болон бусад гадны хүчин зүйлд найдахгүйгээр үргэлж үнэн зөв дүгнэлтэд хүргэдэг гэдгээрээ ялгаатай. Зөн совин (Латин intuitio - "харц" гэсэн үг) гэдэг нь логик хатуу нотолгоог ашиглан үнэнийг ямар ч үндэслэлгүйгээр шууд ажиглах замаар ойлгох чадвар юм. Тиймээс зөн совин нь нэг төрлийн антипод, логик, хатуу ширүүн байдлын эсрэг тэнцвэр юм.

логик хэсэг сэтгэх үйл явцухамсрын түвшинд, зөн совин - далд ухамсрын түвшинд явагддаг.
Шинжлэх ухаан, ялангуяа математикийн хөгжлийг зөн совингүйгээр төсөөлөхийн аргагүй юм. Шинжлэх ухааны мэдлэгт зөн совингийн хоёр төрөл байдаг1: зөн совин-шүүлт, зөн совин-таавар. Зөн совин-шүүлт (эсвэл философийн зөн-шүүлт) нь энэ тохиолдолд үнэний шууд ойлголт, юмсын объектив холболт нь зөвхөн логикийн хувьд хатуу нотлох баримтгүйгээр явагддаг төдийгүй энэ үнэний хувьд ийм нотолгоо байдаггүй гэдгээрээ онцлог юм. зарчмын хувьд оршин тогтнох боломжгүй. Зөн совин-шүүлт нь ерөнхий шинж чанартай нэг (нэг удаагийн) нийлэг цогц үйлдэл хэлбэрээр явагддаг. Алгоритмын онолд авч үзсэн Тьюринг, Черч, Марков нарын диссертаци нь логикийн хувьд нотлогдоогүй мэдэгдлүүдийн ийм шинж чанартай байдаг.

Тохиромжтой форматаар цахим номыг үнэгүй татаж аваад үзээрэй, уншина уу:
Математик логик ба алгоритмын онол, Игошин VI, 2008 он - fileskachat.com номыг хурдан, үнэгүй татаж авах.

Номууд. DJVU ном, PDF үнэгүй татаж авах. Үнэгүй дижитал номын сан
А.К. Гэдэс, Математик логик ба алгоритмын онол

Та чадна (хөтөлбөр тэмдэглэх болно шар)
Та дээд математикийн номнуудын жагсаалтыг цагаан толгойн дарааллаар эрэмбэлэн харж болно.
Та дээд физикийн номнуудын жагсаалтыг цагаан толгойн дарааллаар эрэмбэлэх боломжтой.

• Ном үнэгүй татаж авах, хэмжээ 556 Kb, .djvu формат (орчин үеийн сурах бичиг)

Хадагтай ноёд оо!! Цахим нийтлэлийн файлуудыг "гажиг"гүйгээр татаж авахын тулд файлын хамт доогуур зураасан холбоос дээр дарна уу Хулганы БАРУУН товч, команд сонгоно уу "Зорилтотыг дараах байдлаар хадгалах ..." ("Зорилтотыг дараах байдлаар хадгалах...") болон e-pub файлыг өөрийн дотоод компьютерт хадгална уу. Цахим хэвлэл нь ихэвчлэн Adobe PDF болон DJVU форматтай байдаг.

I. Логик
1. Сонгодог логик
1.1. саналын логик
1.1.1. үгс
1.1.2. Логикийн үндсэн хуулиуд
1.1.3. логик парадоксРассел
1.1.4. Тайлбарын алгебр (логик).
1.1.5. Шатны диаграммууд
1.1.6. Ижил томьёо
1.1.7. Буль алгебр
1.1.8. Үнэн, хүчинтэй томьёо
1.1.9. Шийдвэрлэх чадварын асуудал
1.1.10. логик үр дагавар
1.1.11. Силлогизм
1.2. Предикат логик
1.2.1. Предикат ба томьёо
1.2.2. Тайлбар
1.2.3. Томъёоны үнэн ба сэтгэл ханамж. Загвар, хүчин төгөлдөр байдал, логик үр дагавар
1.2.4. Готлоб Фреж
1.2.5. Skolem функцууд
болон томьёоны склемизаци
1.3. Шийдвэрлэх арга
1.3.1. Саналын логик дахь шийдвэрийн арга
1.3.2. Предикатын логик дахь шийдвэрлэх арга

2. Албан ёсны онолууд (тооцоолол)
2.1. Албан ёсны онол буюу тооцооллын тодорхойлолт
2.1.1. Баталгаа. Онолын тууштай байдал. Онолын бүрэн байдал
2.2. саналын тооцоо
2.2.1. Санал тооцооллын дүгнэлт гаргах хэл ба дүрэм
2.2.2. Теоремыг батлах жишээ
2.2.3. Саналын тооцооны бүрэн байдал, тууштай байдал
2.3. Тооцооллын тооцоо
2.3.1. Предикатын тооцооны хэл, дүгнэлт гаргах дүрэм
2.3.2. Предикатын тооцооны бүрэн байдал, тууштай байдал
2.4. Албан ёсны арифметик
2.4.1. Эгалитийн онолууд
2.4.2. Албан ёсны арифметикийг гаргах хэл ба дүрэм
2.4.3. Албан ёсны арифметикийн тууштай байдал. Гентзений теорем
2.4.4. Годелийн бүрэн бус байдлын теорем
2.4.5. Курт Годел
2.5. Автомат теоремын гаргалт
2.5.1. С.Ю. Маслов
2.6. Логик програмчлал
2.6.1. логик програм
2.6.2. Логик програмчлалын хэлүүд

3. Сонгодог бус логик
3.1. зөн совингийн логик
3.2. бүдэг логик
3.2.1. Тодорхой бус дэд олонлогууд
3.2.2. Тодорхой бус дэд олонлогууд дээрх үйлдлүүд
3.2.3. Тодорхой бус дэд олонлогийн шинж чанарууд
3.2.4. Тодорхой бус санал логик
3.2.5. Fuzzy Ladder Diagrams
3.3. Модаль логик
3.3.1. Модалийн төрлүүд
3.3.2. Тооцоолол 1 ба Т (Фейс-фон Райт)
3.3.3. Тооцоолол S4, S5 болон Wrouer Тооцоолол
3.3.4. Томъёоны үнэлгээ
3.3.5. Крипкегийн семантик
3.3.6. Модал тэмдгүүдийн бусад тайлбарууд
3.4. Жорж фон Райт
3.5. Түр зуурын логик
3.5.1. Прайорын цаг хугацааны логик
3.5.2. Леммоны түр зуурын логик
3.5.3. Фон Райтын цаг хугацааны логик
3.5.4. Програмчлалд цаг хугацааны логикийг ашиглах
3.5.5. Пнуэлийн түр зуурын логик
3.6. Алгоритм логик
3.6.1. Алгоритм логикийг бий болгох зарчим
3.6.2. Чарльз Хоар
3.6.3. Хоарын алгоритмын логик

II. Алгоритмууд
4. Алгоритмууд
4.1. Алгоритм ба тооцоолох функцийн тухай ойлголт
4.2. Рекурсив функцууд
4.2.1. Анхан шатны рекурсив функцууд
4.2.2. Хэсэгчилсэн рекурсив функцууд
4.2.3. Сүмийн дипломын ажил
4.3. Тюринг-Шуудангийн машин
4.3.1. Тюринг-Пост машин дээрх функцын тооцоолол
4.3.2. Тооцооллын жишээ
4.3.3. Тюрингийн дипломын ажил
4.3.4. Бүх нийтийн Тьюрингийн шуудангийн машин
4.4. Алан Тюринг
4.5. Эмил Пост
4.6. Үр дүнтэй алгоритмууд
4.7. Алгоритмын хувьд шийдэгдээгүй асуудлууд

5. Алгоритмуудын нарийн төвөгтэй байдал
5.1. Алгоритмуудын нарийн төвөгтэй байдлын тухай ойлголт
5.2. Асуудлын ангиуд Р ба NP
5.2.1. Асуудлын анги Р
5.2.2. Асуудлын ангилал NP
5.2.3. Тодорхой бус Тьюрингийн машин
5.3. Нарийн төвөгтэй байдлын тухай ойлголтын тухай
5.3.1. Гурван төрлийн хүндрэл
5.3.2. Колмогоровын дагуу дөрвөн ангиллын тоо
5.3.3. Колмогоровын дипломын ажил
5.4. А.Н. Колмогоров

6. Бодит байдлын алгоритмууд
6.1. Генератор виртуал бодит байдал
6.2. Тьюрингийн зарчим
6.3. Логикийн хувьд боломжтой Кантготу орчин

Номын товч хураангуй

ЗааварМатематик логикийн үндэс ба алгоритмын онолын танилцуулгад зориулагдсан. Уг гарын авлагын үндэс нь Омск хотын Компьютерийн шинжлэх ухааны тэнхимийн 2-р курсын оюутнуудад өгсөн лекцийн тэмдэглэл юм улсын их сургууль 2002 онд. мэргэжлээр суралцаж буй оюутнуудад зориулсан " Компьютерийн аюулгүй байдалмөн "Компьютер, цогцолбор, систем, сүлжээ" мэргэжлээр суралцана.

Логикийн шинжлэх ухаан гэж юу вэ. Энэ нь зөв сэтгэх, дүгнэлт, дүгнэлтийг зөв гаргах, үр дүнд нь зөв (зөв) дүгнэлт гаргахад сургадаг онол юм. Тиймээс логик нь шинжлэх ухааны хувьд зөв мэдэгдлийг олж авах дүрмийн жагсаалтыг агуулсан байх ёстой. Ийм багц дүрэм, дүгнэлтийг силлогизмын жагсаалт гэж нэрлэдэг. Мэдэгдэл гэдэг нь судалж буй объектуудын талаархи хоёрдмол утгагүй, нарийн тодорхойлогдсон утгатай мэдэгдэл юм. Орос хэлээр бол илэрхийлэл юм тунхаг өгүүлбэр, энэ нь бидэнд ямар нэг үнэн эсвэл огт буруу зүйлийг хэлж байна гэж залбирдаг. Тиймээс мэдэгдэл нь үнэн эсвэл худал байж болно.

Ном уншина шилдэг номуудматематик, физик, сонирхолтой номнуудматематик, физик, цахим ном, ном үнэгүй, ном үнэгүй татаж авах, математик, физикийн ном үнэгүй татаж авах, номыг бүрэн үнэгүй татаж авах, онлайн номын сан, ном үнэгүй татаж авах, онлайн ном үнэгүй, бүртгэлгүйгээр унших, математик, физик, Математик, физикийн номыг онлайнаар үнэ төлбөргүй унших, цахим номын сан математик, физик, онлайн математик, физик унших ном, номын ертөнц математик, физик, математик, физикийг үнэ төлбөргүй унших, номын сангийн онлайн математик, физик, математик, физикийн ном унших, онлайн үнэгүй математик, физикийн ном, алдартай математик, физикийн ном, математик, физикийн үнэгүй номын сан, математик, физикийн цахим ном татаж авах, үнэгүй номын сан онлайн математик, физик, цахим ном татаж авах, математик, физикийн онлайн сурах бичиг, цахим номын сан математик, физик, цахим ном үнэгүй татаж авах, бүртгэлгүйгээр математик, физик, математик, физикийн сайн ном, математик, физикийн бүрэн ном татаж авах, цахим номын сан Математик, физикийн хичээлийг үнэгүй унших, цахим номын сан, математик, физикийн хичээлийг үнэгүй татаж авах, математик, физикийн ном татах сайт, математик, физикийн ухаалаг ном, математик, физикийн ном хайх, математик, физикийн цахим ном, математик, физикийн цахим ном татаж авах, математик, цахим ном татаж авах физик, математик, физикийн шилдэг номууд, математик, физикийн цахим номын сан, математик, физикийн онлайн үнэгүй ном унших, математик, физикийн номын сайт, цахим номын сан, унших онлайн ном, электрон математик, физикийн ном, ном татаж авах сайт үнэ төлбөргүй, бүртгэлгүй, үнэгүй онлайн математикийн номын сан, физик, хаана Математик, физикийн ном үнэгүй татаж авах, математик, физикийн номыг үнэ төлбөргүй, бүртгэлгүйгээр унших, математик, физикийн сурах бичиг татаж авах, математик, физикийн цахим ном үнэгүй татаж авах, үнэгүй номыг бүрэн татаж авах, онлайн номын сан үнэгүй, математик, физикийн шилдэг цахим ном , математик, физикийн номын онлайн номын сан, цахим номыг бүртгэлгүйгээр үнэгүй татаж авах, онлайн номын сан үнэгүй татаж авах, хаанаас үнэгүй ном татаж авах, цахим номын сан, цахим ном үнэгүй, цахим номын сан, цахим номын сан үнэгүй , үнэгүй ном унших, онлайн номыг үнэгүй унших, онлайнаар үнэгүй унших, онлайн математик, физик унших сонирхолтой ном, онлайн математик, физикийн ном унших, цахим математик, физикийн онлайн номын сан, математик, физикийн цахим номын үнэгүй номын сан, номын сан Математик, физикийн хичээлийг онлайнаар унших, үнэ төлбөргүй, бүртгэлгүйгээр унших, математик, физикийн ном олох , математик, физикийн номын каталог, математик, физикийн онлайн номыг үнэгүй татаж авах, математик, физикийн онлайн номын сан, математик, физикийн номыг бүртгэлгүйгээр үнэгүй татаж авах, математик, физикийн номуудыг үнэгүй татаж авах боломжтой, эндээс татаж авах боломжтой ном, сайтууд ном үнэгүй татаж авах, онлайнаар унших, унших номын сан, бүртгэлгүйгээр онлайнаар үнэгүй унших ном, номын сан, үнэгүй номын сан, онлайн номын сан ном үнэгүй, онлайнаар үнэгүй унших боломжтой.

,
2017 оноос хойш бид вэбсайтын гар утсанд зориулсан гар утасны хувилбарыг (товчилсон текст дизайн, WAP технологи) - вэб хуудасны зүүн дээд буланд байрлах дээд товчлуурыг сэргээж байна. Хэрэв та хувийн компьютер эсвэл интернет терминалаар интернетэд холбогдох боломжгүй бол гар утсаа ашиглан манай вэб сайтад зочлох боломжтой (товчилсон загвар), шаардлагатай бол вэбсайтаас өгөгдлийг гар утасныхаа санах ойд хадгалах боломжтой. Ном, нийтлэлээ өөртөө хадгалаарай гар утас (Мобайл интернет) болон тэдгээрийг утаснаасаа компьютер дээрээ татаж аваарай. Гар утсаар (утасны санах ойд) болон гар утасны интерфейсээр дамжуулан компьютерт ном татахад тохиромжтой. Хурдан интернетшаардлагагүй шошгогүй, үнэ төлбөргүй (Интернэт үйлчилгээний үнээр), нууц үггүй. Материалыг хянан үзэхээр өгсөн. Вэбсайт дахь ном, нийтлэлийн файлд шууд холбоос оруулах, гуравдагч этгээдээр худалдахыг хориглоно.

Анхаарна уу. Хэлэлцүүлэг, блог, вэбсайтын материалаас иш татахад тохиромжтой текст холбоос болох html кодыг манай вэбсайтын материалаас иш татахдаа хуулж аваад өөрийн вэб хуудсандаа буулгах боломжтой. Материалыг хянан үзэхээр өгсөн. Мөн интернетээр дамжуулан номоо гар утсандаа хадгалаарай (байна гар утасны хувилбарсайт - хуудасны зүүн дээд талд байгаа холбоос) болон тэдгээрийг утаснаасаа компьютер дээрээ татаж аваарай. Номын файлд шууд холбоос оруулахыг хориглоно.

КАЗАНИЙН ТЕХНИКИЙН ИХ СУРГУУЛЬ тэднийг . А.Н.Туполева

Ш.И.Галиев

МАТЕМАТИК ЛОГИК, АЛГОРИТМЫН ОНОЛ

СУРГАЛТ

Казань 2002

Галиев Ш.И. Математик логик ба алгоритмын онол. - Казань: KSTU-ийн хэвлэлийн газар. А.Н.Туполев. 2002. - 270 х.

ISBN 5-93629-031-X

Гарын авлага нь дараах хэсгүүдийг агуулна. Програмтай санал, предикатуудын логик, үүнд шийдвэрлэх арга, PROLOG хэл дээр хэрэгжүүлэх элементүүд орно. Сонгодог тооцоо (боломж ба предикатуудын) ба сонгодог бус логикийн элементүүд: гурван ба олон утгатай логик, модаль, цаг хугацааны болон бүдэг логик. Алгоритмын онол: хэвийн алгоритм, Тьюрингийн машин, рекурсив функц, тэдгээрийн хамаарал. Тооцооллын нарийн төвөгтэй байдлын тухай ойлголт, асуудлын өөр өөр (нарийн төвөгтэй байдлаар) ангиуд, ийм асуудлын жишээ.

Бүх бүлгүүд хяналтын асуулт, дасгалуудаар тоноглогдсон, сонголтуудыг өгсөн болно ердийн даалгавармөн материалыг өөртөө шингээх өөрийгөө хянах туршилтууд.

Энэхүү гарын авлага нь "Мэдээлэл зүй, компьютерийн инженерчлэл" чиглэлийн 2201-р мэргэжлээр техникийн их дээд сургуулийн оюутнуудад зориулагдсан бөгөөд 2202-р мэргэжлээр болон бусад мэргэжлээр ашиглах боломжтой.

ТАНИЛЦУУЛГА
Бүлэг 1. МЭДЭГДЭЛИЙН ЛОГИК
§ 1. Мэдэгдэл. Булийн үйлдлүүд
§ 2. Саналын үсэг, холбогч ба хэлбэрүүд (логикийн томьёо
	мэдэгдэл). Үнэний хүснэгтийг бий болгох
§ 3. Саналын хэлбэрийн тэмдэглэгээг хялбарчлах
§ 4. Таутологи (ерөнхийдөө хүчинтэй томъёо). зөрчилдөөн
§ 5. Саналын хэлбэрийн тэнцүү байдал
	Ижил төстэй саналын хэлбэрийн хамгийн чухал хосууд
	Саналын холбогч хоорондын хамаарал
	хэвийн хэлбэрүүд
	Төгс хэвийн хэлбэрүүд
§ 10. Булийн (шилжих) функц
		Санал алгебрыг анализ, синтезд хэрэглэх
		холбоо барих (солих) хэлхээ
		Санал алгебрыг хэлхээний анализ, синтезд ашиглах
		функциональ элементүүдээс
		Дасгал

Бүлэг 2. ПРЕДИКАТ ЛОГИК
§ 1. Предикатын тухай ойлголт
§ 2. Хэмжигдэхүүн
§ 3. Предикатын логикийн томьёо
§ 4. Тайлбар. Загвар
§ 5. Энэхүү тайлбар дахь томъёоны шинж чанарууд
	Логик хүчин төгөлдөр томьёо. Боломжтой ба
	эквивалент томьёо
	Үгүйдлийг тоон үзүүлэлтээр дамжуулах дүрэм
	Тоон хэмжигчийг солих дүрэм
	Холбоотой хувьсагчдын нэрийг өөрчлөх дүрэм
§ 10. Хэмжигчийг хаалтанд оруулах дүрэм. Урьдчилсан
	хэвийн хэлбэр
§ 11. Өөрийгөө шалгах асуулт, сэдэв
§ 12. Дасгал ажил

Бүлэг 3. ЛОГИК ҮР ДҮН, ШИЙДВЭРЛЭХ АРГА
§ 1. Логик үр дагавар ба логик дахь дедукцийн асуудал
	мэдэгдэл
§ 2. Саналын логикийн дизюнктуудыг шийдвэрлэх
§ 3. Саналын логик дахь шийдвэрлэх арга
§ 4. Түвшингийн ханалтын арга
	Хагарах стратеги
	Түгжих нягтрал
	Horn өгүүлбэрийг шийдвэрлэх арга
	Предикатын логик томъёоны хувиргалт. Сколемовская

стандарт хэлбэр
§ 9. Нэгдмэл байдал
§ 10. Предикатын логик дахь шийдвэрлэх арга
§ 11. Силлогизмд дүн шинжилгээ хийх тогтоолын аргыг хэрэглэх
Аристотель
§ 12. ПРОЛОГ хэлээр тогтоолын аргыг ашиглах
§ 13. ПРОЛОГ дахь дүрмийн танилцуулга, хэрэглээ
§ 14. PROLOG дахь дүрмийн рекурсив тодорхойлолт
§ 15. PROLOGUE-ийн онцлог
§ 16. Өөрийгөө шалгах асуулт, сэдэв
§ 17. Дасгал ажил
Бүлэг 4. Дедуктив онолууд
§ 1. Үр ашигтай ба хагас үр ашигтай үйл явцын тухай ойлголт
(арга)
§ 2. Дедуктив онолууд
§ 3. Дедуктив онолын шинж чанарууд
§ 4. Хагас албан ёсны аксиоматик онолын жишээ - геометр
§ 5. Албан ёсны аксиоматик онолууд
§ 6. Үүсгэх чадварын шинж чанарууд
§ 7. Саналын тооцоо
§ 8. Саналын тооцооны зарим теоремууд
§ 9. Тууштай байдлын хоёр тодорхойлолтын дүйцэх байдал
§ 10. Тооцооллын дүгнэлт гаргах үүсмэл (нотлох) дүрэм
мэдэгдэл
§ 11. Саналын тооцооны шинж чанарууд
§ 12. Саналын тооцооны бусад аксиоматжуулалт
§ 13. Нэгдүгээр эрэмбийн онолууд
§ 14. Албан ёсны арифметик (S онол)
§ 15. Нэгдүгээр эрэмбийн онолын шинж чанарууд
§ 16. Аксиоматик аргын ач холбогдол
§ 17. Байгалийн дүгнэлтийн онол
§ 18. Өөрийгөө шалгах асуулт, сэдэв
§ 19. Дасгал ажил
Бүлэг 5. СОНГОГДОГ БУС ЛОГИК
§ 1. Гурван үнэ цэнэтэй логик
§ 2. Олон үнэ цэнэтэй логик
§ 3. Тодорхой бус олонлогийн тухай ойлголт
§ 4. Бүрхэг илэрхийллүүд ба тэдгээрт хийх максимин үйлдлүүд
§ 5. Хэлний бүдэг логикийн тухай ойлголт
§ 6. Модаль логик
§ 7. Түр зуурын (цаг хугацааны) логик
§ 9. Дасгал ажил
Бүлэг 6. АЛГОРИТМЫН ОНОЛ
§ 1. Алгоритмын тухай албан бус ойлголт
§ 2. Цагаан толгойн үсгийн үсэг, үг, алгоритм. Нэлээд тэнцүү
алгоритмууд
§ 3. Хэвийн алгоритм (А.А.Марковын алгоритм)
§ 4. Марковын утгаараа хэсэгчлэн тооцоолох боломжтой функцууд

§ 5. Хэвийн алгоритмыг хаах, өргөтгөх
§ 6. Ердийн алгоритм дээрх үйлдлүүд
§ 7. Тьюрингийн машин
§ 8. Тьюрингийн машины даалгавар
§ 9. Тьюрингийн алгоритм. Туринг тооцоолох чадвар
	Тюринг машин ба ердийн алгоритмуудын хоорондын хамаарал
	Алгоритмын онолын үндсэн таамаглал (хэвийн болгох зарчим
	эсвэл Сүмийн дипломын ажил)
	Алгоритмийн шийдвэр гаргах боломжгүй байдлын асуудал
	Алгоритмын хувьд шийдэгдээгүй бөөн бодлогын жишээ
	Цагаан толгойн үсгийн аливаа өөрчлөлтийн мэдээлэл
бүхэл тоон функцүүдийн утгыг тооцоолох
	Анхан шатны рекурсив ба ерөнхий рекурсив функцууд
	Зарим функцүүдийн анхдагч рекурсив байдал. Хэсэгчилсэн
	рекурсив функцууд
	ламбда тооцоо
	Гол үр дүн
	Өөрийгөө шалгах асуулт, сэдэв
	Дасгал
7-р бүлэг
АЛГОРИТМ
§ 1. Тооцооллын нарийн төвөгтэй байдлын тухай ойлголт
§ 2. Тооцооллын цаг хугацааны нарийн төвөгтэй байдал (алгоритм)
§ 3. Олон гишүүнт алгоритм ба бодлого. R анги
§ 4. NP анги
§ 5. NP-бүрэн ба NP-хэцүү бодлого
§ 6. Е анги
§ 7. Алгоритмын багтаамж (соронзон хальс) нарийн төвөгтэй байдал
§ 8. Өөрийгөө шалгах асуулт, сэдэв
§ 9. Дасгал ажил
Уран зохиол
APPS
Ажлын ердийн сонголтууд
Өөрийгөө хянах тестүүд
Саналын логик тест (Тест №1)
Предикат логик тест (Тест №2)
Логик үр дагавар, шийдвэрлэх аргын талаархи тест (Тест No3)
Дедуктив онолын тест (Тест No4)
Алгоритмын онолын тест (тестийн дугаар 5)
Сонгодог бус логик ба тооцооллын нарийн төвөгтэй байдлын тест (тест
Өөрийгөө хянах тестийн хариултууд

ТАНИЛЦУУЛГА

Логикийг ихэвчлэн нотлох, няцаах аргын шинжлэх ухаан гэж ойлгодог. Математик логик нь математик аргуудын тусламжтайгаар боловсруулсан логик юм.

Нотлох, няцаах аргуудыг судлахдаа логик нь үндсэндээ энэ эсвэл өөр үндэслэл дэх байр суурь, дүгнэлтийн агуулгыг бус харин үнэн дүгнэлтийг олж авах хэлбэрийг сонирхдог. Жишээлбэл, дараах хоёр гаралтыг авч үзье.

1. Бүх хүмүүс мөнх бус байдаг. Сократ бол эр хүн. Тиймээс Сократ мөнх бус мөнх юм.

2. Бүх зулзага тоглох дуртай. Моура бол зулзага. Тиймээс Моура тоглох дуртай.

Эдгээр хоёр дүгнэлт нь ижил хэлбэртэй байна: Бүх A нь B, C нь А; тиймээс C нь В. Эдгээр дүгнэлт нь агуулгаас үл хамааран хэлбэрийн хувьд үнэн, өөрийн хийсэн байр суурь, дүгнэлт нь үнэн эсвэл худал эсэхээс үл хамааран үнэн юм. Системтэй албан ёсны болгох, каталогжуулах зөв арга замуудсэтгэх нь логикийн үндсэн ажлуудын нэг юм. Хэрэв энэ тохиолдолд математикийн төхөөрөмжийг ашигладаг бөгөөд судалгаа нь үндсэндээ математикийн үндэслэлийг судлахад зориулагдсан бол энэ логик нь математик логик юм ( албан ёсны логик). Энэ тодорхойлолтгэдэг нь хатуу (яг) тодорхойлолт биш юм. Математик логикийн сэдэв, аргыг ойлгохын тулд үүнийг судалж эхлэх нь дээр.

Математик логик нь нэлээд эртнээс бүрэлдэж эхэлсэн. Түүний үзэл санаа, арга барилын гарал үүсэл нь онд болсон Эртний Грек, эртний Энэтхэгболон Эртний Хятад 6-р зууны орчим. МЭӨ д. Энэ үед аль хэдийн эрдэмтэд математикийн баталгааны гинжин хэлхээг нэг холбоосоос нөгөө холбоос руу шилжих нь эргэлзээ төрүүлэхгүй байхын тулд бүх нийтээр хүлээн зөвшөөрүүлэхээр оролдсон. Бидэнд хүрч ирсэн хамгийн эртний гар бичмэлүүдэд математикийн илтгэлийн хэв маягийн "канон" нь баттай тогтоогдсон байдаг. Үүний дараа тэрээр Аристотель, Евклид, Архимед зэрэг агуу сонгодог бүтээлүүдийн эцсийн төгсөлтийг хүлээн авдаг. Эдгээр зохиогчдын нотолгоо гэсэн ойлголт манайхаас ялгаагүй.

Логик нь бие даасан шинжлэх ухаан болох Аристотелийн (МЭӨ 384 - 322) судалгаанаас гаралтай. Эртний агуу гүн ухаантан Аристотель тухайн үеийн шинжлэх ухааны бүхий л салбарт эртний мэдлэгийг нэвтэрхий толь бичгийн системчилсэн системчилсэн. Аристотелийн логик судалгааг голчлон "Органон" (Мэдлэгийн хэрэгсэл) гэсэн ерөнхий нэрийн дор нэгтгэсэн "Анхны аналитик" ба "Хоёр дахь аналитик" гэсэн хоёр бүтээлдээ тусгасан болно.

Онцлон тэмдэглэх нь зүйтэй их ач холбогдолХүн төрөлхтний түүхэн дэх хамгийн гайхалтай ололтуудын нэг болох математикийн логикийг бий болгох, хөгжүүлэх, тухайлбал Евклидийн (МЭӨ 330 - 275 он) "Эхлэл" бүтээл дэх геометрийг яг дедуктив систем болгон хувиргах. Чухамхүү зорилго, аргуудыг тодорхой ухамсарласан энэхүү дедуктив хандлага нь дараагийн зуунд философи, математикийн сэтгэлгээг хөгжүүлэх үндэс суурь болсон юм.

Алгебр (Буле алгебр) болон бусад математикийн салбаруудад, тэр дундаа дахин геометрийн (Евклидийн бус геометрийг бүтээх - Лобачевский-Гаусс-Боляй геометр) ололт амжилт нь логикийг бүрдүүлэх, хөгжүүлэхэд чухал ач холбогдолтой байв. Богино тоймматематик логик үүсэхийг олж болно.

Эрт дээр үед ч, дундад зууны үед ч, түүнээс хойшхи үед ч математик логикийг бий болгох, хөгжүүлэхэд олон, олон эрдэмтэд оролцсон.

Математик логикийн үндсэн ба хэрэглээний ач холбогдол

Математик логикийн үндсэн ач холбогдол нь математикийн үндэслэл (математикийн үндэс суурийг шинжлэх) юм.

Математик логикийн хэрэглээний утга одоогоор маш өндөр байна. Математик логикийг дараахь зорилгоор ашигладаг.

дижитал компьютер болон бусад салангид автомат, түүний дотор ухаалаг системийг шинжлэх, нэгтгэх (барилга барих);

байгалийн хэлэнд дүн шинжилгээ хийх албан ёсны болон машин хэлний анализ, синтез;

тооцоолох чадварын зөн совингийн үзэл баримтлалд дүн шинжилгээ хийх, албан ёсны болгох;

тодорхой төрлийн асуудлыг шийдвэрлэх механик журам байгаа эсэхийг олж мэдэх;

тооцооллын нарийн төвөгтэй асуудлуудын шинжилгээ.

Мөн математик логик нь хэл шинжлэл, эдийн засаг, сэтгэл судлал, гүн ухааны хэд хэдэн асуудалтай нягт холбоотой байв.

Энэхүү гарын авлагад математик логик, алгоритмын онолын үндсэн ойлголтуудыг тусгасан болно. Гарын авлагад танилцуулсан материал

мужтай тохирч байна боловсролын стандарт"Компьютерийн шинжлэх ухаан ба компьютерийн технологи" чиглэлд зориулагдсан бөгөөд энэ чиглэлээр янз бүрийн мэргэжлээр суралцаж буй оюутнуудад ашиглаж болно.

Гарын авлагыг бичихдээ уран зохиол ашигласан бөгөөд мэдээжийн хэрэг бусад эх сурвалжийг ашигласан. Ашигласан материалын жагсаалтад сониуч, эрэлт хэрэгцээтэй оюутны үзэхийг хүсч буй номууд багтсан болно.

Бүлэг бүрийн гарын авлагад өөрийгөө шалгах асуултууд байдаг онолын материалАсуудлыг шийдвэрлэх чадварыг хөгжүүлэх, танилцуулж буй сэдвийн талаархи мэдлэгийг гүнзгийрүүлэх зорилготой дасгалууд. Нэмж дурдахад энэхүү гарын авлагад ердийн даалгавар, материалыг өөртөө шингээх чадварыг хянах тестийн сонголтуудыг багтаасан болно.

11.1. Алгоритмын тухай ойлголт ба алгоритмын онол

Зөн совингийн хувьд алгоритм гэдэг нь тодорхой хугацаанд үргэлжилдэг асуудлыг дараалан шийдвэрлэх үйл явц гэж ойлгогддог бөгөөд ингэснээр дараагийн цаг мөч бүрт алгоритмын объектын системийг дараах байдлаар олж авдаг. тодорхой хуульөмнөх агшинд байгаа объектуудын системээс . Зөн совинтой, учир нь хатуухан хэлэхэд алгоритм гэдэг ойлголт нь олонлогийн тухай ойлголттой төстэй бөгөөд үүнийг тодорхойлох боломжгүй юм.

ГОСТ 19781-74 стандартын дагуу "Тооцоолох машин. Програм хангамж. Нэр томъёо, тодорхойлолт" алгоритмхувьсагчийн анхны өгөгдлөөс хүссэн үр дүнд хүрэх тооцооллын процессыг тодорхойлдог нарийн жор юм. Энэ нь алгоритм гүйцэтгэгч - эдгээр үйлдлийг хэрхэн гүйцэтгэхийг мэддэг объект байгаа гэж үздэг.

"Алгоритм" гэдэг үг нь 13-р зууны Төв Азийн (Узбек) математикчийн нэрнээс гаралтай гэж үздэг. Аль Хорезми(Абу Абдалла Мухаммад ибн Муса аль Хорезми аль Межуси) - Латин хэл дээрх "Алгоритми" бөгөөд тэрээр анх удаа арифметикийн дөрвөн үйлдлийг гүйцэтгэх дүрмийг (процедур) томъёолжээ. аравтын системтооцоо.

Тооцоолол нь энгийн байсан бол алгоритмын онцгой шаардлага байгаагүй. Хэд хэдэн алхам алхмаар процедур шаардлагатай болсон үед алгоритмын онол гарч ирэв. Гэвч даалгаврууд улам бүр төвөгтэй болсон тул заримыг нь алгоритмаар шийдвэрлэх боломжгүй болсон. Жишээлбэл, хүний ​​​​тархины "самбар дээрх компьютер" -ээр шийдэгддэг олон ажил байдаг. Ийм асуудлыг шийдэх нь бусад зарчмууд дээр суурилдаг - эдгээр зарчмуудыг шинэ шинжлэх ухаан - нейроматематик ба холбогдох техникийн хэрэгсэл - нейрокомпьютер ашигладаг. Энэ тохиолдолд суралцах, турших, алдаа гаргах үйл явцыг ашигладаг - өөрөөр хэлбэл бидний одоо хийж байгаа зүйл.

Алгоритмын чанар нь түүний шинж чанар (шинж чанар) -аар тодорхойлогддог. Алгоритмын үндсэн шинж чанарууд нь:

1. массын дүр. Алгоритм нь энэ төрлийн бүх асуудлыг шийдвэрлэхэд тохиромжтой гэж үздэг. Жишээлбэл, шугаман алгебрийн тэгшитгэлийн системийг шийдэх алгоритм нь дурын тооны тэгшитгэлээс бүрдэх системд хэрэглэгдэх ёстой.

2. Үр ашиг. Энэ шинж чанар нь алгоритм нь хязгаарлагдмал тооны алхмуудын үр дүнд хүргэх ёстой гэсэн үг юм.

3. Баталгаатай. Алгоритмд орсон зааварчилгаа нь нарийн бөгөөд ойлгомжтой байх ёстой. Энэ шинж чанар нь өгөгдсөн анхны өгөгдлийн тооцооллын үйл явцын үр дүнгийн өвөрмөц байдлыг баталгаажуулдаг.

4. салангид байдал. Энэ шинж чанар нь алгоритм болон алгоритмаар тодорхойлсон процессыг тусдаа үндсэн үе шатуудад хувааж болох бөгөөд хэрэглэгч компьютер дээр гүйцэтгэх боломж нь эргэлзээгүй гэсэн үг юм.

Өнөөдөр "дижитал мянган" хашаанд байгаа бөгөөд та аливаа ажлыг алгоритмд захирагддаг мэт сэтгэгдэл төрүүлж магадгүй юм. Олон асуудлыг алгоритмаар шийдэж чадахгүй нь харагдаж байна. Эдгээр нь алгоритмын хувьд шийдэгдээгүй гэж нэрлэгддэг асуудлууд юм.

Асуудлын алгоритмаар шийдэгдэх эсвэл шийдэгдэхгүй байхыг батлахын тулд математикийн нарийн, нарийн арга хэрэгсэл хэрэгтэй. Өнгөрсөн зууны 30-аад оны дундуур алгоритмын тухай ойлголтыг албан ёсны болгох оролдлого хийж, санал болгосон. янз бүрийн загваруудалгоритмууд: рекурсив функцууд; "машин" - Тюринг, Пост; ердийн Марков алгоритмууд.

Дараа нь эдгээр болон бусад загварууд нь шийдэж буй асуудлын ангиуд нь давхцаж байгаагаараа ижил төстэй болохыг олж мэдсэн. Энэ баримтыг Сүмийн дипломын ажил гэж нэрлэдэг. Одоо үүнийг нийтээр хүлээн зөвшөөрч байна. Алгоритмын тухай ойлголтын албан ёсны тодорхойлолт нь анхны компьютер үүсэхээс өмнө алгоритмын онолыг хөгжүүлэх урьдчилсан нөхцөлийг бүрдүүлсэн. Компьютерийн технологийн дэвшил нь алгоритмын онолын цаашдын хөгжилд түлхэц өгсөн. Алгоритмын онол нь асуудлын алгоритмын шийдлийг тогтоохоос гадна алгоритмын нарийн төвөгтэй байдлыг алхамын тоо (цаг хугацааны нарийн төвөгтэй байдал) болон шаардагдах санах ой (орон зайн нарийн төвөгтэй байдал) зэргээр тооцох, мөн үр ашигтай алгоритмуудыг боловсруулдаг. энэ мэдрэмж.

Зарим алгоритмыг хэрэгжүүлэхийн тулд физикийн үүднээс авч үзвэл энгийн алхамуудыг гүйцэтгэх хурд нь орчин үеийн үзэл баримтлалын дагуу орчлон ертөнц оршин тогтнохоос ч илүү цаг хугацаа, эсхүл атомуудаас илүү санах ойн эсүүдийг авч болно. Дэлхий гарагийг бүрдүүлдэг.

Иймээс алгоритмын онолын өөр нэг ажил бол комбинатор алгоритм дахь сонголтуудын тооллогыг арилгах асуудлыг шийдвэрлэх явдал юм. Алгоритмуудын нарийн төвөгтэй байдлыг тооцоолох, үр ашигтай гэж нэрлэгддэг алгоритмуудыг бий болгох нь орчин үеийн алгоритмын онолын хамгийн чухал ажлуудын нэг юм.

Зохиогч: Guts A.K.
Нийтлэгч: О.: Өв
Хэвлэгдсэн он: 2003 он
Хуудас: 108
ISBN 5-8239-0126-7
Унших:
Татаж авах: matematicheskayalogika2003.djvu

ОМСК УЛСЫН ИХ СУРГУУЛИЙН КОМПЬЮТЕРИЙН ШИНЖЛЭХ УХААНЫ ФАКУЛЬТЕТИЙН ТЭНХИМ
КИБЕРНЕТИК
А.К. Гэдэс
Математик логик ба алгоритмын онол
Омск 2003
VVK 60 UDC 53:630.11
Guts A.K. Математик логик ба алгоритмын онол: Сурах бичиг. -
Омск: Өв хэвлэл. Диалог-Сибирь, 2003. - 108 х.
ISBN 5-8239-0126-7
Сурах бичиг нь математик логик, онолын үндэс суурийг танилцуулахад зориулагдсан болно
алгоритмууд. Гарын авлагын үндэс нь уншсан лекцийн хураангуй юм
Омскийн компьютерийн тэнхимийн хоёрдугаар курсын оюутнууд
2002 онд Улсын их сургууль.
075200 - "Компьютер" мэргэжлээр суралцаж буй оюутнуудад зориулсан
аюулгүй байдал" ба 220100 - "Компьютер,
цогцолбор, систем, сүлжээ".
ISBN 5-8239-0126-7
(в) Омскийн улсын их сургууль, 2003 он
Агуулгын хүснэгт
I Логик 7
1 Сонгодог логик 8
1.1. Саналын логик.................................. 8
1.1.1. Үг хэллэг........................... 8
1.1.2. Логикийн үндсэн хуулиуд ................................. 9
1.1.3. Расселын логик парадокс .............. 10
1.1.4. Саналын алгебр (логик) .............. 11
1.1.5. Шатны диаграмм ................................. 12
1.1.6. Тэнцүү томьёо ....................... 14
1.1.7. Буль алгебр.................................. 15
1.1.8. Үнэн, хүчинтэй томьёо ............ 15
1.1.9. Шийдвэрлэх чадварын асуудал ................... 15
1.1.10. Логик үр дагавар............................... 16
1.1.11. Силлогизм.................................. 17
1.2. Предикатын логик.................................. 17
1.2.1. Предикат ба томьёо............... 18
1.2.2. Тайлбар.................................. 19
1.2.3. Томъёоны үнэн ба сэтгэл ханамж. загварууд,
хүчин төгөлдөр байдал, логик үр дагавар....... 20
1.2.4. Готлоб Фреге................................. 21
1.2.5. Skolem функцууд
томъёоны сколемизаци....................... 22
1.3. Шийдвэрлэх арга.................................. 25
1.3.1. Логик дахь шийдвэрлэх арга
хэлсэн үг.................................. 25
1.3.2. Логик дахь шийдвэрлэх арга
предикат................................. 29
3
4
Агуулгын хүснэгт
2 Албан ёсны онолууд (тооцоолол) 31
2.1. Албан ёсны онол буюу тооцооллын тодорхойлолт. . 32
2.1.1. Баталгаа. Онолын тууштай байдал.
Онолын бүрэн байдал........................... 32
2.2. Саналын тооцоо................................. 33
2.2.1. Санал тооцооллын дүгнэлт гаргах хэл ба дүрэм
............................................. 33
2.2.2. Теоремын баталгааны жишээ.............. 35
2.2.3. Бүрэн байдал ба тууштай байдал
саналын тооцоо ........................... 36
2.3. Урьдчилан тооцоолол.................................. 37
2.3.1. Предикатын тооцооны хэл, дүгнэлт гаргах дүрэм 37
2.3.2. Бүрэн байдал ба тууштай байдал
предикатын тооцоо............................. 39
2.4. Албан ёсны арифметик........................... 39
2.4.1. Эгалитийн онолууд........................... 39
2.4.2. Албан ёсны арифметикийг гаргах хэл ба дүрэм
.............................................. 39
2.4.3. Албан ёсны тууштай байдал
арифметик. Гэнцэний теорем.............. 40
2.4.4. Годелийн бүрэн бус байдлын теорем................................. 41
2.4.5. Курт Годел................. 42
2.5. Автомат теоремын гаргалт ........................... 43
2.5.1. С.Ю. Маслов................................. 43
2.6. Логик програмчлал.................. 45
2.6.1. Логик програм ................................. 46
2.6.2. Логик програмчлалын хэлүүд.... 49
3 Сонгодог бус логик 50
3.1. Зөн совингийн логик.................................. 50
3.2. Тодорхой бус логик.................................. 51
3.2.1. Бүдэг дэд олонлогууд ........................... 51
3.2.2. fuzzy дээрх үйлдлүүд
дэд олонлогууд........................... 52
3.2.3. Тодорхой бус олонлогийн шинж чанарууд
дэд олонлогууд................................. 53
3.2.4. Тодорхой бус санал логик....................... 54
3.2.5. Fuzzy Ladder Diagrams ............ 56
3.3. Модаль логик.................................. 56
3.3.1. Модал хэлбэрийн төрлүүд.................................. 57
Агуулгын хүснэгт
5
3.3.2. Тооцоолол 1 ба Т (Фейс-фон Райт) ........ 57
3.3.3. Тооцоолол S4, S5
ба Брауверын тооцоо................................ 58
3.3.4. Томъёоны үнэлгээ ........................... 59
3.3.5. Крипкегийн семантик ................................. 60
3.3.6. Модалуудын бусад тайлбарууд
тэмдэг................................. 62
3.4. Георг фон Райт ................................ 62
3.5. Түр логик ........................... 62
3.5.1. Прайорын цаг хугацааны логик............................. 63
3.5.2. Леммоны цаг хугацааны логик................. 64
3.5.3. Фон Райтын цаг хугацааны логик...................... 64
3.5.4. Цагийн логикийн хэрэглээ
програмчлалд ........................... 65
3.5.5. Пнуэли түр зуурын логик ................................ 67
3.6. Алгоритм логик............................ 70
3.6.1. Барилгын зарчим
1 >