ავტორი: Guts A.K.
გამომცემელი: O.: Heritage
გამოცემის წელი: 2003 წ
გვერდები: 108
ISBN 5-8239-0126-7
წაიკითხეთ:
ჩამოტვირთვა: matematicheskayalogika2003.djvu

ომსკის სახელმწიფო უნივერსიტეტის კომპიუტერული მეცნიერებათა ფაკულტეტი
კიბერნეტიკა
ა.კ. გუგები
მათემატიკური ლოგიკა და ალგორითმების თეორია
ომსკი 2003 წ
VVK 60 UDC 53:630.11
გუტსი ა.კ. მათემატიკური ლოგიკა და ალგორითმების თეორია: სახელმძღვანელო. -
ომსკი: Heritage Publishing. დიალოგი-ციმბირი, 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. S.Yu. მასლოვი ................................ 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. ოპერაციები ბუნდოვანზე
ქვეჯგუფები................................ 52
3.2.3. ბუნდოვანი სიმრავლის თვისებები
ქვეჯგუფები................................ 53
3.2.4. ბუნდოვანი წინადადების ლოგიკა...................... 54
3.2.5. ბუნდოვანი კიბეების დიაგრამები ........... 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 >

განათლების ფედერალური სააგენტო

ტომსკის საკონტროლო სისტემების და რადიოელექტრონიკის სახელმწიფო უნივერსიტეტი (ტუსური)

ინფორმაციის დამუშავების ავტომატიზაციის დეპარტამენტი

Ვადასტურებ:

უფროსი კაფე AOI

პროფესორი

Კი. ეხლაკოვი

"__" _____________2007 წ

გაიდლაინები

დისციპლინაზე პრაქტიკული მუშაობის განხორციელებას

"მათემატიკური ლოგიკა და ალგორითმების თეორია"

სპეციალობის სტუდენტებისთვის 230102 -

"ინფორმაციის დამუშავებისა და კონტროლის ავტომატური სისტემები"

დეველოპერები:

Ხელოვნება. განყოფილების ლექტორი AOI

მაშინ. პერემიტინა

ტომსკი - 2007 წ

პრაქტიკული გაკვეთილი No1 „პროპოზიციური ალგებრის ფორმულები“ ​​3

პრაქტიკული გაკვეთილი No2 „პროპოზიციური ალგებრის ფორმულების ეკვივალენტური გარდაქმნები“ 10

პრაქტიკული გაკვეთილი No3 „ფორმულების ნორმალური ფორმები“ 12

პრაქტიკული გაკვეთილი No4 „ლოგიკური მსჯელობა“ 14

პრაქტიკული გაკვეთილი No5 „პრედიკატების ლოგიკის ფორმულები“ ​​18

პრაქტიკა #6 ლოგიკური ფუნქციები 23

პრაქტიკა #7 ნაწილობრივ რეკურსიული ფუნქციები 28

პრაქტიკა #8 ტურინგის მანქანები 34

პრაქტიკული გაკვეთილი No1 „პროპოზიციური ალგებრის ფორმულები“

წინადადებების დოქტრინა - წინადადებების ალგებრა, ან ლოგიკის ალგებრა - უმარტივესი ლოგიკური თეორიაა. წინადადებათა ალგებრის ატომური ცნება არის განცხადება - დეკლარაციული წინადადება, რომლის მიმართაც აზრი აქვს განცხადებას მისი სიმართლის ან სიცრუის შესახებ.

ჭეშმარიტი განცხადების მაგალითი: "დედამიწა ბრუნავს მზის გარშემო". მცდარი განცხადების მაგალითი: "3 > 5". ყველა წინადადება არ არის განცხადება; განცხადებები არ შეიცავს კითხვით და ძახილის წინადადებებს. წინადადება: „ფაფა უგემრიელესი კერძია“ არ არის განცხადება, რადგან არ შეიძლება იყოს კონსენსუსი იმის თაობაზე, არის თუ არა ეს სიმართლე თუ მცდარი. წინადადება „მარსზე სიცოცხლეა“ უნდა ჩაითვალოს განცხადებად, რადგან ობიექტურად ის ან მართალია ან მცდარი, თუმცა ჯერ არავინ იცის რომელი.

ვინაიდან ლოგიკის შესწავლის საგანია მხოლოდ წინადადებების ჭეშმარიტების მნიშვნელობები, მათთვის შემოტანილია ასოების აღნიშვნები A, B, ... ან X, Y ....

თითოეული განცხადება ითვლება ჭეშმარიტად ან მცდარად. მოკლედ დავწერთ 1-ს ჭეშმარიტი მნიშვნელობის ნაცვლად, ხოლო 0-ს მცდარი მნიშვნელობის ნაცვლად. მაგალითად, X= "დედამიწა ბრუნავს მზის გარშემო" და Y= "3\u003e 5" და X=1 და Y. = 0. განცხადება არ შეიძლება იყოს ჭეშმარიტი და მცდარი.

განცხადებები შეიძლება იყოს მარტივი ან რთული. განცხადებები "დედამიწა ბრუნავს მზის გარშემო" და "3 > 5" მარტივია. რთული განცხადებები წარმოიქმნება მარტივიდან ბუნებრივი (რუსული) ენობრივი კავშირების NOT, AND, OR, IF-მაშინ, მაშინ-და-მხოლოდ-მაშინ. განცხადებებისთვის ანბანური აღნიშვნების გამოყენებისას, ეს კავშირები იცვლება სპეციალური მათემატიკური სიმბოლოებით, რომლებიც შეიძლება ჩაითვალოს ლოგიკური მოქმედებების სიმბოლოებად.

ქვემოთ, ცხრილში 1, არის სიმბოლოების ვარიანტები დამაკავშირებლების აღსანიშნავად და შესაბამისი ლოგიკური ოპერაციების სახელები.

უარყოფა (ინვერსია) განცხადებები Xარის განცხადება, რომელიც მართალია თუ და მხოლოდ იმ შემთხვევაში Xყალბი (აღნიშნეს ან , ნათქვამია „არა X” ან ”ეს არ არის სიმართლე X”).

შეერთება
ორი წინადადებას ეწოდება წინადადება, რომელიც ჭეშმარიტია, თუ და მხოლოდ იმ შემთხვევაში, თუ ორივე წინადადება ჭეშმარიტია Xდა ი. ეს ლოგიკური ოპერაცია შეესაბამება განცხადებების კავშირს კავშირთან „და“.

დისიუნქცია
ორი წინადადება Xდა იგანცხადება ნათქვამია, რომ მცდარია, თუ და მხოლოდ იმ შემთხვევაში, თუ ორივე განცხადება Xდა იყალბი. სასაუბრო მეტყველებაში ეს ლოგიკური ოპერაცია შეესაბამება კავშირს "ან" (არა ექსკლუზიური "ან").

იმპლიკამენტი ორი წინადადება X და იარის განცხადება, რომელიც მცდარია თუ და მხოლოდ იმ შემთხვევაში Xმართალია და ი- ყალბი (აღნიშნეს
; კითხულობს " Xიწვევს ი“, „თუ X, მაშინ ი”). ამ ოპერაციის ოპერატორებს აქვთ სპეციალური სახელები: X- პაკეტი, ი- დასკვნა.

ეკვივალენტობა ორი წინადადება Xდა იეწოდება განცხადება, რომელიც არის ჭეშმარიტი, თუ და მხოლოდ იმ შემთხვევაში, თუ სიმართლე ფასდება Xდა იიგივეა (სიმბოლო:
).

ცხრილი 1. ლოგიკური ოპერაციები

ლოგიკური ოპერაციების ოპერანდებს შეუძლიათ მიიღონ მხოლოდ ორი მნიშვნელობა: 1 ან 0. აქედან გამომდინარე, თითოეული ლოგიკური ოპერაცია , &, , ,  შეიძლება მარტივად იყოს მითითებული ცხრილის გამოყენებით, რაც მიუთითებს ოპერაციის შედეგის მნიშვნელობას მნიშვნელობებზე დაყრდნობით. ოპერანდებიდან. ასეთ მაგიდას ე.წ სიმართლის ცხრილი (ცხრილი 2).

ცხრილი 2. ლოგიკური მოქმედებების სიმართლის ცხრილი

ზემოთ განსაზღვრული ლოგიკური ოპერაციების დახმარებით შესაძლებელია მარტივი წინადადებების აგება წინადადების ლოგიკური ფორმულები წარმოადგენს სხვადასხვა შედგენილ განცხადებებს. რთული განცხადების ლოგიკური მნიშვნელობა დამოკიდებულია განცხადების სტრუქტურაზე, რომელიც გამოხატულია ფორმულით და მისი შემადგენელი ელემენტარული განცხადებების ლოგიკურ მნიშვნელობებზე.

განცხადებების გამომხატველი ფორმულების სისტემატური შესწავლისთვის შემოღებულია ცვლადი განცხადებები პ, პ 1 , პ 2 , ..., პ ნმნიშვნელობების აღება კომპლექტიდან (0, 1).

წინადადების ლოგიკის ფორმულა ფ (პ 1 , პ 2 ,..., პ ნ) ეწოდება ტავტოლოგია ან იგივე სიმართლეა თუ მისი მნიშვნელობა რომელიმე მნიშვნელობისთვის პ 1 , პ 2 ,..., პ ნარის 1 (მართალია). ფორმულები, რომლებიც ფასდება ჭეშმარიტად ცვლადების სიების მინიმუმ ერთი ნაკრებისთვის, ეწოდება შესასრულებელი . ფორმულები, რომლებიც იღებენ მნიშვნელობას "false" ცვლადის ნებისმიერი მნიშვნელობისთვის, ეწოდება წინააღმდეგობები (იდენტური ყალბი, შეუძლებელია).

შემოთავაზებული სახელმძღვანელო (მე-2 გამოცემა, სტერეოტიპი) ქმნის კომპლექტს მათემატიკური ლოგიკის კურსისა და ალგორითმების თეორიისთვის, რომელიც ასევე მოიცავს ამოცანების კრებულს (Igoshin V.I. ამოცანები და სავარჯიშოები მათემატიკური ლოგიკაში და ალგორითმების თეორია) .

დეტალურად არის აღწერილი თეორიის საფუძვლები, ნაჩვენებია ლოგიკის შეღწევის მიმართულებები ალგებრის საფუძვლებში, ანალიზი, გეომეტრია, მისი ლოგიკური ანალიზისთვის გამოყენებულია სასკოლო მათემატიკის კურსის მასალა, მათემატიკური ლოგიკის ურთიერთობა კომპიუტერებთან, ინფორმატიკისა და ხელოვნური ინტელექტის სისტემები ხასიათდება.

შესავალი. მათემატიკური ლოგიკა თანამედროვე განათლების სისტემაში.
ლოგიკა და ინტუიცია. ლოგიკა ტრადიციული და მათემატიკური ლოგიკა. ცოტა ისტორია. მათემატიკური ლოგიკა - ლოგიკა თუ მათემატიკა? მათემატიკური ლოგიკა მათემატიკის სწავლებაში. მათემატიკური ლოგიკა და თანამედროვე კომპიუტერები.
თავი I. განცხადებების ალგებრა.
§ 1. განცხადებები და ოპერაციები მათზე.
გამოთქმის ცნება. განცხადების უარყოფა. ორი წინადადების შეერთება. ორი განცხადების განცალკევება. ორი განცხადების მნიშვნელობა. ორი განცხადების ეკვივალენტობა. ენისა და ლოგიკური ოპერაციების გაერთიანებები (ენა და ლოგიკა). ლოგიკური ოპერაციების ზოგადი ხედვა.
§2. წინადადების ალგებრის ფორმულები.
რთული წინადადებების აგება. წინადადების ალგებრის ფორმულის კონცეფცია. რთული განცხადების ლოგიკური მნიშვნელობა. ფორმულებისთვის სიმართლის ცხრილების შედგენა. წინადადებების ალგებრის ფორმულების კლასიფიკაცია. აზროვნება და მათემატიკური ლოგიკა
§ 3. პროპოზიციური ალგებრის ტავტოლოგიები.
ტავტოლოგიების მნიშვნელობის შესახებ. ძირითადი ტავტოლოგიები. ტავტოლოგიის მიღების ძირითადი წესები.
§ 4. ფორმულების ლოგიკური ეკვივალენტობა.
ფორმულების ეკვივალენტობის ცნება. ფორმულების ეკვივალენტობის ნიშანი. ეკვივალენტური ფორმულების მაგალითები. ფორმულების ეკვივალენტური გარდაქმნები. ეკვივალენტები ლოგიკაში და იდენტობები ალგებრაში.
§ 5. წინადადების ალგებრის ფორმულების ნორმალური ფორმები.
ნორმალური ფორმების კონცეფცია. იდეალური ნორმალური ფორმები. პროპოზიციური ალგებრის ფორმულების წარმოდგენა სრულყოფილი დისუნქციური ნორმალური (CDN) ფორმებით. წინადადებათა ალგებრის ფორმულების წარმოდგენა სრულყოფილი შეერთების ნორმალური (SKN) ფორმებით. ორი გზა წინადადებული ალგებრის ფორმულის სრულყოფილ ნორმალურ ფორმამდე დასაყვანად
§ 6. ფორმულების ლოგიკური მიმდევრობა.
ლოგიკური შედეგის კონცეფცია. ლოგიკური შედეგის ნიშნები. ლოგიკური შედეგის ორი თვისება. ფორმულების დაცვა და ეკვივალენტობა. ლოგიკური მსჯელობის წესები. კიდევ ერთი გზა ლოგიკური შემდეგის შესამოწმებლად. შედეგების პოვნა ამ შენობიდან. ამ გამოძიების საშუალების მოძიება.
§ 7. პროპოზიციური ალგებრის გამოყენება ლოგიკურ-მათემატიკურ პრაქტიკაში.
პირდაპირი და შებრუნებული თეორემები. აუცილებელი და საკმარისი პირობები. საპირისპირო თეორემის საპირისპირო და შებრუნებული. კონტრაპოზიციის კანონი. მათემატიკური თეორემის სტრუქტურის მოდიფიკაცია. მათემატიკური თეორემების დამტკიცების მეთოდები. დედუქციური და ინდუქციური მსჯელობა. სწორი და არასწორი დედუქციური მსჯელობა. ლოგიკური პრობლემების გადაჭრა. სრული განცალკევების პრინციპი. სრული განშორების პრინციპის ერთი განზოგადება.
თავი II. ლოგიკური ფუნქციები.
§რვა. კომპლექტები, მიმართებები, ფუნქციები.
კომპლექტის კონცეფცია. კომპლექტების ჩართვა და თანასწორობა. ოპერაციები კომპლექტებზე. ორობითი ურთიერთობები და ფუნქციები. lar ურთიერთობის კონცეფცია.
§ 9. ერთი და ორი არგუმენტის ლოგიკური ფუნქციები.
ლოგიკური ფუნქციების წარმოშობა. ლოგიკური ფუნქციები ერთი არგუმენტიდან. ორი არგუმენტის ლოგიკური ფუნქციები. დისიუნქციის, შეერთების და უარყოფის თვისებები. ეკვივალენტობის, მნიშვნელობისა და უარყოფის თვისებები. ზოგიერთი ლოგიკური ფუნქციის გამოხატვა სხვების თვალსაზრისით
§ 10. n არგუმენტების ლოგიკური ფუნქციები.
ლოგიკური ფუნქციის კონცეფცია. ლოგიკური ფუნქციების რაოდენობა. ლოგიკური ფუნქციების გამოხატვა შეერთების, დისიუნქციისა და უარყოფის გზით. წინადადებების ალგებრის ლოგიკური ფუნქციები და ფორმულები. ლოგიკური ფუნქციების ნორმალური ფორმები.
§ 11. ლოგიკური ფუნქციების სისტემები.
ლოგიკური ფუნქციების სრული სისტემები. ლოგიკური ფუნქციების სპეციალური კლასები. პოსტის თეორემა ლოგიკური ფუნქციების სისტემის სისრულის შესახებ
§ 12. ლოგიკური ფუნქციების გამოყენება სარელეო-კონტაქტურ სქემებზე.
განაცხადის იდეა. სარელეო-კონტაქტური სქემების თეორიის ორი ძირითადი ამოცანა.
§ 13. სარელეო-კონტაქტური სქემები კომპიუტერებში.
ორობითი ნახევარი შემკრები. ერთბიტიანი ორობითი დამმატებელი. შიფრატორი და დეკოდერი.
§ 14. ლოგიკური ფუნქციების თეორიის ზოგიერთი სხვა გამოყენების შესახებ.
დაავადებათა დიაგნოსტიკა (აღიარება). ნიმუშის ამოცნობა.
თავი III. ფორმალიზებული წინადადების გაანგარიშება.
§ 15. აქსიომების სისტემა და ფორმალური დასკვნის თეორია.
აქსიომური წინადადებების თეორიის დასაწყისი: საწყისი ცნებები, აქსიომების სისტემა, დასკვნის წესი. დასკვნის ცნება და მისი თვისებები. დედუქციის თეორემა და მისი შედეგები. დედუქციის თეორემის გამოყენება. მიღებული დასკვნის წესები
§ 16. ფორმალიზებული წინადადებების კალკულუსის სისრულე და სხვა თვისებები
ფორმულის და მისი იდენტური ჭეშმარიტების დადასტურება (სინტაქსი და სემანტიკა). წარმოშობის ლემა. ფორმალიზებული წინადადების გაანგარიშების სისრულე. ადეკვატურობის თეორემა. ფორმალიზებული წინადადების გაანგარიშების თანმიმდევრულობა. ფორმალიზებული წინადადების გაანგარიშების გადაწყვეტადობა
§ 17. ფორმალიზებული წინადადებების კალკულუსის აქსიომების სისტემის დამოუკიდებლობა.
დამოუკიდებლობის კონცეფცია. აქსიომის დამოუკიდებლობა (A1). აქსიომის დამოუკიდებლობა (A2). აქსიომა დამოუკიდებლობა (A3). აქსიომური სისტემის დამოუკიდებლობა
თავი IV. პრედიკატის ლოგიკა.
§ 18. პრედიკატებთან დაკავშირებული ძირითადი ცნებები.
პრედიკატის ცნება. პრედიკატების კლასიფიკაცია. პრედიკატის ჭეშმარიტების ნაკრები. ეკვივალენტობა და შემდეგი პრედიკატები
§ 19. ლოგიკური მოქმედებები პრედიკატებზე.
პრედიკატის უარყოფა. ორი პრედიკატის შეერთება. დიზაინი დიკატის გვერდზე გადასასვლელად. უარყოფის, შეერთების და დისიუნქციის თვისებები. ორი პრედიკატის მნიშვნელობა და ეკვივალენტობა.
§ 20. რაოდენობრივი ოპერაციები პრედიკატებზე.
ზოგადი კვანტიფიკატორი. არსებობის რაოდენობრივი მაჩვენებელი. რიცხვითი რაოდენობები. შეზღუდული რაოდენობები. ლოგიკის კვადრატი
§ 21. პრედიკატების ლოგიკის ფორმულები.
პრედიკატის ლოგიკური ფორმულის კონცეფცია. პრედიკატების ლოგიკური ფორმულების კლასიფიკაცია. პრედიკატების ლოგიკის ტავტოლოგია
§ 22. ფორმულების ეკვივალენტური გარდაქმნები და პრედიკატების ლოგიკის ფორმულების ლოგიკური შედეგი
ფორმულების ეკვივალენტობის ცნება. შემცირებული ფორმა პრედიკატების ლოგიკური ფორმულებისთვის. Prenex ნორმალური ფორმა პრედიკატების ლოგიკური ფორმულებისთვის. პრედიკატების ლოგიკური ფორმულების ლოგიკური მიდევნება
§ 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 ენის გაჩენა და მისი განვითარება. PROLOG ენის ზოგადი მახასიათებლები. PROLOG ენის მოკლე აღწერა და მაგალითები. PROLOG ენის გამოყენების სფეროები.
§41. მათემატიკური ლოგიკა და ინფორმატიკა.
მონაცემთა ბაზის ზოგადი კონცეფცია. რელატიური მონაცემთა ბაზა და შეკითხვის ლოგიკა მასში.
§ 42. მათემატიკური ლოგიკა და ხელოვნური ინტელექტის სისტემები განვითარების ისტორია და ხელოვნური ინტელექტის საგანი, როგორც მეცნიერება. ცოდნის წარმოდგენა ხელოვნური ინტელექტის სისტემებში. საექსპერტო სისტემები. PROLOG ენა ხელოვნური ინტელექტის სისტემებში. შეუძლია თუ არა მანქანას ფიქრი.
დასკვნა: არის თუ არა ლოგიკა ყოვლისშემძლე აზროვნების კანონების ცოდნაში?
ბიბლიოგრაფია.

ლოგიკა და ინტუიცია.
ადამიანის გონებრივი აქტივობა რთული და მრავალმხრივი პროცესია, რომელიც ხდება როგორც ცნობიერ, ასევე არაცნობიერ (ქვეცნობიერ) დონეზე. ეს არის ადამიანის ცოდნის უმაღლესი დონე, რეალობის ობიექტებისა და ფენომენების ადეკვატურად ასახვის უნარი, ე.ი. სიმართლის საპოვნელად.

ლოგიკა და ინტუიცია ადამიანის აზროვნების ორი საპირისპირო და განუყოფლად დაკავშირებული თვისებაა. ლოგიკური (დედუქციური) აზროვნება განსხვავდება იმით, რომ მას ყოველთვის მივყავართ ჭეშმარიტ დასკვნამდე ჭეშმარიტი წინაპირობიდან, გამოცდილებაზე, ინტუიციაზე და სხვა გარე ფაქტორებზე დაყრდნობის გარეშე. ინტუიცია (ლათინური intuitio-დან - „მჭიდროდ დაკვირვება“) არის ჭეშმარიტების გაგების უნარი მასზე პირდაპირი დაკვირვებით, დასაბუთების გარეშე, ლოგიკურად მკაცრი მტკიცებულების დახმარებით. ამრიგად, ინტუიცია არის ერთგვარი ანტიპოდი, ლოგიკისა და სიმკაცრის საპირწონე.

აზროვნების პროცესის ლოგიკური ნაწილი ცნობიერების დონეზე მიმდინარეობს, ინტუიციური ნაწილი – ქვეცნობიერის დონეზე.
მეცნიერების და განსაკუთრებით მათემატიკის განვითარება წარმოუდგენელია ინტუიციის გარეშე. მეცნიერულ ცოდნაში არსებობს ორი სახის ინტუიცია: ინტუიცია-განსჯა და ინტუიცია-გამოცნობა. ინტუიცია-განსჯა (ან ფილოსოფიური ინტუიცია-განსჯა) ხასიათდება იმით, რომ ამ შემთხვევაში ჭეშმარიტების პირდაპირი აღქმა, საგნების ობიექტური კავშირი ხორციელდება არა მხოლოდ ლოგიკურად მკაცრი მტკიცებულების გარეშე, არამედ ასეთი მტკიცებულება არ არსებობს ამ ჭეშმარიტებისა და. პრინციპში ვერ იარსებებს. ინტუიცია-განსჯა ხორციელდება როგორც განზოგადებული ხასიათის ერთჯერადი (ერთჯერადი) სინთეზური ჰოლისტიკური აქტი. ლოგიკურად დაუმტკიცებელი დებულებების ასეთი ბუნება აქვთ ალგორითმების თეორიაში განხილულ ტურინგის, ჩერჩისა და მარკოვის თეზისებს.

უფასო ჩამოტვირთვა ელექტრონული წიგნი მოსახერხებელ ფორმატში, უყურეთ და წაიკითხეთ:
ჩამოტვირთეთ წიგნი Mathematical Logic and Theory of Algorithms, Igoshin VI, 2008 - fileskachat.com, სწრაფი და უფასო ჩამოტვირთვა.

11.1. ალგორითმის კონცეფცია და ალგორითმების თეორია

ინტუიციურად, ალგორითმი გაგებულია, როგორც პრობლემის თანმიმდევრული გადაჭრის პროცესი, რომელიც მიმდინარეობს დისკრეტულ დროს ისე, რომ დროის ყოველ მომდევნო მომენტში, ალგორითმის ობიექტების სისტემა მიიღება გარკვეული კანონის მიხედვით, ობიექტების სისტემიდან, რომლებიც ხელმისაწვდომი იყო. დროის წინა მომენტში. ინტუიციური, რადგან, მკაცრად რომ ვთქვათ, ალგორითმის კონცეფცია წააგავს კომპლექტის კონცეფციას, რომელიც განუსაზღვრელია.

GOST 19781-74 შესაბამისად ”გამოთვლითი მანქანები. პროგრამული უზრუნველყოფა. ტერმინები და განმარტებები" ალგორითმიარის ზუსტი რეცეპტი, რომელიც განსაზღვრავს გამოთვლით პროცესს, რომელიც მიდის ცვლადი საწყისი მონაცემებიდან სასურველ შედეგამდე. ეს ითვალისწინებს ალგორითმის შემსრულებელის არსებობას - ობიექტი, რომელმაც "იცის როგორ" შეასრულოს ეს მოქმედებები.

სიტყვა "ალგორითმი" სავარაუდოდ მომდინარეობს XIII საუკუნის შუააზიელი (უზბეკი) მათემატიკოსის ალ ხორეზმის (აბუ აბდალა მუჰამედ იბნ მუსა ალ ხორეზმი ალ მეჯუსის) სახელიდან - "ალგორითმი" ლათინური ტრანსკრიფციით, რომელიც პირველად ჩამოაყალიბა ათწილადი რიცხვების სისტემაში ოთხი არითმეტიკული მოქმედების შესრულების წესები (პროცედურა).

სანამ გამოთვლები მარტივი იყო, ალგორითმების განსაკუთრებული საჭიროება არ არსებობდა. როცა საჭირო იყო მრავალი ეტაპობრივი პროცედურა, მაშინ გაჩნდა ალგორითმების თეორია. მაგრამ ამოცანების კიდევ უფრო დიდი გართულებით, აღმოჩნდა, რომ ზოგიერთი მათგანის ალგორითმულად გადაჭრა შეუძლებელია. ასეთია, მაგალითად, ბევრი ამოცანა, რომელსაც წყვეტს ადამიანის „ბორტ კომპიუტერი“ – ტვინი. ასეთი პრობლემების გადაჭრა ეფუძნება სხვა პრინციპებს - ამ პრინციპებს იყენებს ახალი მეცნიერება - ნეირომათემატიკა და შესაბამისი ტექნიკური საშუალებები - ნეიროკომპიუტერები. ამ შემთხვევაში გამოიყენება სწავლის, ცდისა და შეცდომის პროცესები – ანუ რასაც ამჟამად ვაკეთებთ.

ალგორითმის ხარისხი განისაზღვრება მისი თვისებებით (მახასიათებლებით). ალგორითმის ძირითადი თვისებებია:

1. მასობრივი ხასიათი. ვარაუდობენ, რომ ალგორითმი შეიძლება იყოს შესაფერისი ამ ტიპის ყველა პრობლემის გადასაჭრელად. მაგალითად, წრფივი ალგებრული განტოლებათა სისტემის ამოხსნის ალგორითმი გამოყენებული უნდა იყოს განტოლებათა თვითნებური რაოდენობისგან შემდგარ სისტემაზე.

2. ეფექტურობა. ეს თვისება ნიშნავს, რომ ალგორითმმა უნდა გამოიწვიოს შედეგი სასრული რაოდენობის ნაბიჯებით.

3. გარკვეულობა. ალგორითმში შეტანილი ინსტრუქციები უნდა იყოს ზუსტი და გასაგები. ეს მახასიათებელი უზრუნველყოფს გამოთვლითი პროცესის შედეგის უნიკალურობას მოცემული საწყისი მონაცემებისთვის.

4. დისკრეტულობა. ეს თვისება ნიშნავს, რომ ალგორითმის მიერ აღწერილი პროცესი და თავად ალგორითმი შეიძლება დაიყოს ცალკეულ ელემენტარულ ეტაპებად, რომლის შესაძლებლობაც მომხმარებელს შეუძლია შეასრულოს კომპიუტერზე ეჭვგარეშეა.

დღეს „ციფრული ათასწლეული“ ეზოშია და შეიძლება გქონდეთ შთაბეჭდილება, რომ ნებისმიერი დავალება ექვემდებარება ალგორითმებს. გამოდის, რომ ბევრი პრობლემის ალგორითმულად გადაჭრა შეუძლებელია. ეს არის ეგრეთ წოდებული ალგორითმულად გადაუჭრელი პრობლემები.

პრობლემების ალგორითმული ამოხსნადობის ან გადაუჭრელობის დასამტკიცებლად საჭიროა მათემატიკურად მკაცრი და ზუსტი საშუალებები. გასული საუკუნის 30-იანი წლების შუა ხანებში განხორციელდა მცდელობები ალგორითმის კონცეფციის ფორმალიზებაზე და შემოთავაზებული იქნა ალგორითმების სხვადასხვა მოდელები: რეკურსიული ფუნქციები; "მანქანები" - Turing, Post; ნორმალური მარკოვის ალგორითმები.

შემდგომში გაირკვა, რომ ეს და სხვა მოდელები ეკვივალენტურია იმ გაგებით, რომ მათ მიერ გადაწყვეტილი პრობლემების კლასები ემთხვევა. ამ ფაქტს ეკლესიის თეზისი ჰქვია. ახლა ეს ზოგადად მიღებულია. ალგორითმის ცნების ოფიციალურმა განმარტებამ შექმნა წინაპირობები ალგორითმის თეორიის განვითარებისთვის ჯერ კიდევ პირველი კომპიუტერების განვითარებამდე. კომპიუტერული ტექნოლოგიების პროგრესმა ხელი შეუწყო ალგორითმების თეორიის შემდგომ განვითარებას. პრობლემების ალგორითმული გადაწყვეტის დადგენის გარდა, ალგორითმების თეორია ასევე ეხება ალგორითმების სირთულის შეფასებას ნაბიჯების რაოდენობის (დროის სირთულე) და საჭირო მეხსიერების (სივრცის სირთულე) და ასევე ავითარებს ეფექტურ ალგორითმებს. ეს გრძნობა.

ზოგიერთი ალგორითმის განხორციელებას, ფიზიკის თვალსაზრისით რაიმე გონივრული ვარაუდით ელემენტარული ნაბიჯების შესრულების სიჩქარის შესახებ, შეიძლება დასჭირდეს უფრო მეტი დრო, ვიდრე, თანამედროვე შეხედულებების თანახმად, არსებობს სამყარო, ან მეტი მეხსიერების უჯრედი, ვიდრე ატომები. შეადგინოს პლანეტა დედამიწა.

მაშასადამე, ალგორითმების თეორიის კიდევ ერთი ამოცანაა კომბინატორულ ალგორითმებში ვარიანტების ჩამოთვლის აღმოფხვრის პრობლემის გადაჭრა. ალგორითმების სირთულის შეფასება და ე.წ ეფექტური ალგორითმების შექმნა თანამედროვე ალგორითმების თეორიის ერთ-ერთი ყველაზე მნიშვნელოვანი ამოცანაა.