Zaxarova Riyazi məntiqin əsasları və alqoritmlər nəzəriyyəsi. «Riyazi məntiq və alqoritmlər nəzəriyyəsi

Kitablar. DJVU kitablarını, PDF-i pulsuz yükləyin. Pulsuz elektron kitabxana
A.K. Quts, Riyazi məntiq və alqoritmlər nəzəriyyəsi

Siz edə bilərsiniz (proqram onu ​​sarı rənglə qeyd edəcək)
Siz ali riyaziyyat üzrə kitabların əlifba sırası ilə sıralanmış siyahısını görə bilərsiniz.
Ali fizika üzrə kitabların siyahısını əlifba sırası ilə görə bilərsiniz.

• Pulsuz kitab yükləmək, həcmi 556 Kb, .djvu formatı (müasir dərslik)

Xanımlar və cənablar!! Elektron nəşrlərin fayllarını "qüsursuz" yükləmək üçün faylın altından xətt çəkilmiş keçidə klikləyin SAĞ siçan düyməsini, əmr seçin "Hədəf kimi saxla..." ("Hədəf kimi yadda saxla...") və e-pub faylını yerli kompüterinizdə saxlayın. Elektron nəşrlər adətən Adobe PDF və DJVU formatlarında olur.

I. Məntiq
1. Klassik məntiq
1.1. təklif məntiqi
1.1.1. deyimler
1.1.2. Məntiqin əsas qanunları
1.1.3. Rasselin məntiqi paradoksu
1.1.4. İfadələrin cəbri (məntiqi).
1.1.5. Nərdivan diaqramları
1.1.6. Ekvivalent düsturlar
1.1.7. Boole cəbri
1.1.8. Doğru və etibarlı düsturlar
1.1.9. Qərar vermə problemi
1.1.10. məntiqi nəticə
1.1.11. Sillogizmlər
1.2. Predikat məntiqi
1.2.1. Predikatlar və düsturlar
1.2.2. Şərhlər
1.2.3. Düsturların həqiqəti və qənaətbəxşliyi. Modellər, Etibarlılıq, Məntiqi Nəticə
1.2.4. Gottlob Frege
1.2.5. Skolem funksiyaları
və düsturların sklemizasiyası
1.3. Həll üsulu
1.3.1. Təklif məntiqində qərarlar metodu
1.3.2. Predikat məntiqində həll metodu

2. Formal nəzəriyyələr (hesablama)
2.1. Formal nəzəriyyənin və ya hesablamanın tərifi
2.1.1. Sübut. Nəzəriyyənin ardıcıllığı. Nəzəriyyənin tamlığı
2.2. təklif hesabı
2.2.1. Təklif hesabından nəticə çıxarmaq üçün dil və qaydalar
2.2.2. Teorem sübut nümunəsi
2.2.3. Təklif hesablamasının tamlığı və ardıcıllığı
2.3. Predikativ hesablama
2.3.1. Predikat hesablamasının dili və nəticə çıxarma qaydaları
2.3.2. Predikat hesablamasının tamlığı və ardıcıllığı
2.4. Formal arifmetika
2.4.1. Eqalitar nəzəriyyələr
2.4.2. Formal arifmetikanın alınması üçün dil və qaydalar
2.4.3. Formal hesabın ardıcıllığı. Gentzen teoremi
2.4.4. Gödelin natamamlıq teoremi
2.4.5. Kurt Gödel
2.5. Avtomatik teorem törəməsi
2.5.1. S.Yu. Maslov
2.6. Məntiq proqramlaşdırma
2.6.1. məntiq proqramı
2.6.2. Məntiq proqramlaşdırma dilləri

3. Qeyri-klassik məntiqlər
3.1. intuisiya məntiqi
3.2. qeyri-səlis məntiq
3.2.1. Qeyri-səlis alt çoxluqlar
3.2.2. Qeyri-səlis alt çoxluqlar üzərində əməliyyatlar
3.2.3. Qeyri-səlis alt çoxluqlar çoxluğunun xassələri
3.2.4. Qeyri-səlis təklif məntiqi
3.2.5. Qeyri-səlis nərdivan diaqramları
3.3. Modal məntiqlər
3.3.1. Modallıq növləri
3.3.2. Hesablama 1 və T (Feis-von Wright)
3.3.3. Hesablama S4, S5 və Wrouer Hesabı
3.3.4. Formula Qiymətləndirmə
3.3.5. Kripke semantikası
3.3.6. Modal işarələrin digər şərhləri
3.4. Georg von Wright
3.5. Müvəqqəti məntiqlər
3.5.1. Pryorun zamanlama məntiqi
3.5.2. Lemmonun müvəqqəti məntiqi
3.5.3. Von Raytın müvəqqəti məntiqi
3.5.4. Zamanlama məntiqlərinin proqramlaşdırmaya tətbiqi
3.5.5. Pnueli müvəqqəti məntiq
3.6. Alqoritmik məntiq
3.6.1. Alqoritmik məntiqin qurulması prinsipləri
3.6.2. Çarlz Hoare
3.6.3. Hoare alqoritmik məntiqi

II. Alqoritmlər
4. Alqoritmlər
4.1. Alqoritm və hesablana bilən funksiya anlayışı
4.2. Rekursiv funksiyalar
4.2.1. Primitiv Rekursiv Funksiyalar
4.2.2. Qismən rekursiv funksiyalar
4.2.3. Kilsənin tezisi
4.3. Turing-Post maşını
4.3.1. Turing-Post maşınında funksiya hesablamaları
4.3.2. Hesablama nümunələri
4.3.3. Turinq tezisi
4.3.4. Universal Turing Post Maşın
4.4. Alan Turing
4.5. Emil Post
4.6. Effektiv alqoritmlər
4.7. Alqoritmik həll olunmayan məsələlər

5. Alqoritmlərin mürəkkəbliyi
5.1. Alqoritmlərin mürəkkəbliyi anlayışı
5.2. Problem sinifləri Р və NP
5.2.1. Problem sinfi Р
5.2.2. Problemlər sinfi NP
5.2.3. Qeyri-deterministik Turinq maşını
5.3. Mürəkkəblik anlayışı haqqında
5.3.1. Üç növ çətinlik
5.3.2. Kolmogorova görə dörd kateqoriyalı rəqəmlər
5.3.3. Kolmoqorovun dissertasiyası
5.4. A.N. Kolmoqorov

6. Reallığın alqoritmləri
6.1. Virtual Reallıq Generator
6.2. Turinq prinsipi
6.3. Məntiqi Mümkün Kantqotu Mühitləri

Kitabın qısa xülasəsi

Dərslik riyazi məntiqin və alqoritmlər nəzəriyyəsinin əsaslarının təqdimatına həsr edilmişdir. Dərslik 2002-ci ildə Omsk Dövlət Universitetinin informatika fakültəsinin ikinci kurs tələbələrinə verilən mühazirə qeydləri əsasında hazırlanmışdır. “Kompüter Təhlükəsizliyi” ixtisası və “Kompüterlər, komplekslər, sistemlər və şəbəkələr” ixtisası üzrə təhsil alan tələbələr üçün.

Məntiq elmi nədir. Bu, düzgün mülahizə yürütməyi, düzgün nəticə çıxarmağı və nəticə çıxarmağı öyrədən, nəticədə düzgün (düzgün) ifadələr verən bir nəzəriyyədir. Buna görə də məntiq bir elm olaraq düzgün mülahizələrin əldə edilməsi üçün qaydaların siyahısını ehtiva etməlidir. Belə qaydalar toplusu, çıxarışlar sillogizmlərin siyahısı adlanır. Bəyanat tədqiq olunan obyektlər haqqında birmənalı və dəqiq müəyyən edilmiş məna daşıyan ifadədir. Rus dilində bir söz, bizə doğru və ya tamamilə yanlış bir şey söylədiyini söyləmək üçün dua edilən bir deklarativ cümlədir. Buna görə də ifadə ya doğru, ya da yalan ola bilər.

Kitablar, kitablar endir, kitab endir, onlayn kitablar, onlayn oxu, kitabları pulsuz endir, kitab oxu, onlayn kitab oxu, oxu, onlayn kitabxana, kitab oxu, onlayn oxu, pulsuz kitab oxu, ebook, onlayn kitab oxu, ən yaxşı kitablar riyaziyyat ve fizika, maraqli kitablar riyaziyyat ve fizika, e-kitablar, kitablar pulsuz, kitablar pulsuz yukle, pulsuz yukle kitablar riyaziyyat ve fizika, kitablar tam pulsuz yukle, online kitabxana, kitablar pulsuz yukle, kitablar online pulsuz yukle, pulsuz qeydiyyat olmadan riyaziyyat və fizika, pulsuz riyaziyyat və fizika üçün onlayn kitab oxumaq, elektron kitabxana riyaziyyat və fizika, onlayn riyaziyyat və fizika oxumaq üçün kitablar, kitablar dünyası riyaziyyat və fizika, riyaziyyat və fizikanı pulsuz oxumaq, onlayn kitabxana riyaziyyat və fizika, kitab oxumaq riyaziyyat və fizika, onlayn kitablar pulsuz riyaziyyat və fizika , populyar kitablar riyaziyyat və fizika, pulsuz kitablar kitabxanası riyaziyyat və fizika, elektron yükləyin riyaziyyat ve fizika kitabi, pulsuz online riyaziyyat ve fizika kitabxanasi, e-kitablar yukle, online riyaziyyat ve fizika derslikleri, riyaziyyat ve fizika elektron kitab kitabxanasi, e-kitablar pulsuz yukle qeydiyyat olmadan riyaziyyat ve fizika, yaxsi riyaziyyat ve fizika kitablari, tam yukle riyaziyyat və fizika kitabları, pulsuz oxunan elektron kitabxana riyaziyyat və fizika, elektron kitabxana pulsuz yükləmə riyaziyyat və fizika, riyaziyyat və fizika kitablarını yükləmək üçün saytlar, riyaziyyat və fizikadan ağıllı kitablar, riyaziyyat və fizika kitablarının axtarışı, riyaziyyat və fizikadan elektron kitablar pulsuz yükləyin fizika, elektron kitab yükləmək riyaziyyat və fizika, riyaziyyat və fizika üzrə ən yaxşı kitablar, pulsuz riyaziyyat və fizika üçün elektron kitabxana, riyaziyyat və fizikadan onlayn pulsuz kitablar oxumaq, riyaziyyat və fizika kitabları üçün sayt, elektron kitabxana, oxumaq üçün onlayn kitablar , elektron riyaziyyat və fizika kitabı, pulsuz və qeydiyyat olmadan kitab yükləmək üçün sayt , pulsuz onlayn riyaziyyat və fizika kitabxanası, burada riyaziyyat və fizika kitablarını pulsuz yükləyə, riyaziyyat və fizika kitablarını pulsuz və qeydiyyat olmadan oxuya, riyaziyyat və fizika dərsliklərini yükləyə, riyaziyyat və fizikadan elektron kitabları pulsuz yükləyə, pulsuz kitabları tam yükləyin, pulsuz onlayn kitabxana, riyaziyyat və fizikadan ən yaxşı elektron kitablar, riyaziyyat və fizika kitablarının onlayn kitabxanası, elektron kitabları pulsuz yükləyin qeydiyyat olmadan, onlayn kitabxana pulsuz yükləyin, pulsuz kitabları haradan yükləmək olar, e- kitabxanalar pulsuz, e-kitablar pulsuz, pulsuz e-kitabxanalar, pulsuz onlayn kitabxana, pulsuz kitab oxumaq, pulsuz onlayn kitablar oxumaq, pulsuz onlayn oxumaq, onlayn oxumaq üçün pulsuz kitablar, onlayn riyaziyyat və fizika oxumaq üçün maraqlı kitablar, onlayn kitab oxumaq riyaziyyat və fizika, elektron kitabxana onlayn riyaziyyat və fizika, elektron kitabların pulsuz kitabxanası riyaziyyat və fizika, onlayn kitabxana oxumaq, oxumaq pulsuz və qeydiyyat olmadan və riyaziyyat və fizika, riyaziyyat və fizika kitabını tapın, riyaziyyat və fizika kitablarının kataloqu, pulsuz riyaziyyat və fizika kitablarını onlayn yükləyin, riyaziyyat və fizika onlayn kitabxanası, riyaziyyat və fizika kitablarını pulsuz yükləyin qeydiyyat olmadan riyaziyyat və fizika, haradan yükləyə bilərsiniz pulsuz riyaziyyat və fizika kitabları, kitabları yükləyə biləcəyiniz kitablar, kitabları pulsuz yükləmək üçün saytlar, oxumaq üçün onlayn, oxumaq üçün kitabxana, onlayn oxumaq üçün kitablar pulsuz qeydiyyat olmadan, kitablar kitabxanası, pulsuz kitabxana onlayn, onlayn kitabxana pulsuz oxumaq , pulsuz və qeydiyyat olmadan oxumaq üçün kitablar, kitabları pulsuz yükləmək üçün elektron kitabxana, pulsuz oxumaq üçün onlayn.

,
2017-ci ildən biz internet saytının mobil telefonlar üçün mobil versiyasını (qısaldılmış mətn dizaynı, WAP texnologiyası) - veb səhifənin yuxarı sol küncündəki yuxarı düyməni bərpa edirik. Əgər sizin şəxsi kompüter və ya internet terminalı vasitəsilə internetə çıxışınız yoxdursa, siz mobil telefonunuzdan istifadə edərək vebsaytımıza daxil ola bilərsiniz (qısaldılmış dizayn) və lazım gəldikdə internet saytından məlumatları mobil telefonunuzun yaddaşında saxlaya bilərsiniz. Kitabları və məqalələri mobil telefonunuzda (mobil internet) saxlayın və onları telefonunuzdan kompüterinizə endirin. Kitabların mobil telefon vasitəsilə (telefon yaddaşına) və mobil interfeys vasitəsilə kompüterinizə rahat yükləmə. Lazımsız etiketlər olmadan, pulsuz (İnternet xidmətlərinin qiymətinə) və parol olmadan sürətli İnternet. Material nəzərdən keçirmək üçün təqdim olunur. Saytdakı kitab və məqalələrin fayllarına birbaşa keçidlər və onların üçüncü şəxslər tərəfindən satışı qadağandır.

Qeyd. Forumlar, bloqlar, vebsayt materiallarından sitat gətirmək üçün əlverişli mətn linki, html kodu bizim vebsayt materiallarımızdan sitat gətirərkən kopyalana və sadəcə veb səhifələrinizə yapışdırıla bilər. Material nəzərdən keçirmək üçün təqdim olunur. Həmçinin kitabları internet vasitəsilə mobil telefonunuzda saxlayın (saytın mobil versiyası var - link səhifənin yuxarı sol hissəsindədir) və onları telefonunuzdan kompüterinizə endirin. Kitab fayllarına birbaşa keçidlər qadağandır.

KAZAN TEXNIK UNİVERSİTETİ onları. A. N. Tupoleva

Ş.İ.Qəliyev

RİYASİ MƏNQİQ VƏ ALQORİTM NƏZƏRİYYƏSİ

TƏLİMAT

Kazan 2002

Qaliyev Ş.İ. Riyazi məntiq və alqoritmlər nəzəriyyəsi. - Kazan: KSTU-nun nəşriyyatı. A. N. Tupolev. 2002. - 270 s.

ISBN 5-93629-031-X

Təlimat aşağıdakı bölmələri ehtiva edir. Tətbiqlərlə təkliflərin və predikatların məntiqi, o cümlədən həll metodu və onun PROLOG dilində həyata keçirilməsi elementləri. Klassik hesablama (müddəaların və predikatların) və qeyri-klassik məntiqin elementləri: üçqiymətli və çoxqiymətli məntiqlər, modal, zaman və qeyri-səlis məntiqlər. Alqoritmlər nəzəriyyəsi: normal alqoritmlər, Tyurinq maşınları, rekursiv funksiyalar və onların əlaqələri. Hesablama mürəkkəbliyi anlayışı, problemlərin müxtəlif (mürəkkəbliyə görə) sinifləri və belə məsələlərin nümunələri.

Bütün fəsillər nəzarət sualları və tapşırıqları ilə təchiz edilmiş, tipik tapşırıqlar üçün seçimlər və materialın mənimsənilməsinə özünü idarə etmək üçün testlər verilmişdir.

Dərs vəsaiti texniki ali məktəblərin “İnformatika və hesablama texnikası” istiqamətinin 2201-ci ixtisası üzrə tələbələri üçün nəzərdə tutulmuşdur və 2202-ci ixtisas və bu sahə üzrə digər ixtisaslar üçün istifadə oluna bilər.

GİRİŞ

Məntiq adətən sübut və təkzib üsulları haqqında elm kimi başa düşülür. Riyazi məntiq riyazi metodların köməyi ilə işlənmiş məntiqdir.

Sübut və təkzib üsullarını öyrənən məntiq ilk növbədə bu və ya digər mülahizələrdə müddəaların və nəticələrin məzmunu ilə deyil, həqiqi nəticələrin əldə edilməsi forması ilə maraqlanır. Məsələn, aşağıdakı iki çıxışı nəzərdən keçirək:

1. Bütün insanlar ölümlüdür. Sokrat insandır. Deməli, Sokrat fanidir.

2. Bütün pişiklər oynamağı sevirlər. Moura pişik balasıdır. Ona görə də Moura oynamağı sevir.

Bu nəticələrin hər ikisi eyni formaya malikdir: Hamısı A B, C A; ona görə də C B-dir. Bu nəticələr məzmunundan asılı olmayaraq, öz-özlüyündə qəbul edilən müddəaların və nəticələrin doğru və ya yalan olmasından asılı olmayaraq, formasına görə doğrudur. Düzgün düşünmə yollarının sistematik şəkildə rəsmiləşdirilməsi və kataloqlaşdırılması məntiqin əsas vəzifələrindən biridir. Əgər bu halda riyazi aparatdan istifadə edilirsə və tədqiqat ilk növbədə riyazi əsaslandırmanın öyrənilməsinə həsr olunubsa, bu məntiq riyazi məntiqdir (formal məntiq). Bu tərif ciddi (dəqiq) tərif deyil. Riyazi məntiqin mövzusunu və metodunu başa düşmək üçün onu öyrənməyə başlamaq ən yaxşısıdır.

Riyazi məntiq çoxdan formalaşmağa başladı. Onun ideya və üsullarının mənşəyi təxminən eramızdan əvvəl VI əsrdən Qədim Yunanıstanda, Qədim Hindistanda və Qədim Çində baş vermişdir. e.ə e. Artıq bu dövrdə elm adamları riyazi sübutlar zəncirini elə bir zəncirdə təşkil etməyə çalışırdılar ki, bir halqadan digərinə keçid heç bir şübhə yaratmayacaq və ümumdünya tanınması qazanacaq. Artıq bizə çatan ən erkən əlyazmalarda riyazi təqdimat tərzinin "kanonu" möhkəm şəkildə qurulmuşdur. Sonradan o, böyük klassiklərin son tamamlanmasını alır: Aristotel, Evklid, Arximed. Bu müəlliflərin sübut anlayışı bizimkindən heç bir fərqi yoxdur.

Müstəqil bir elm kimi məntiq Aristotelin (e.ə. 384 - 322) tədqiqatlarında yaranır. Antik dövrün böyük filosofu Aristotel o zaman mövcud olan elmin bütün sahələrində antik biliklərin ensiklopedik sistemləşdirilməsini həyata keçirmişdir. Aristotelin məntiqi araşdırmaları, əsasən, "Organon" (Bilik Aləti) ümumi adı altında birləşən "Birinci Analitika" və "İkinci Analitika" adlı iki əsərində təqdim olunur.

Bəşəriyyət tarixinin ən parlaq nailiyyətlərindən birinin, yəni Evklidin (e.ə. 330 - 275) əsərində həndəsənin dəqiq deduktiv sistemə çevrilməsinin riyazi məntiqin formalaşması və inkişafı üçün böyük əhəmiyyəti xüsusi qeyd etmək lazımdır. "Başlanğıclar". Məqsədləri və metodları aydın dərk edən bu deduktiv yanaşma sonrakı əsrlərdə fəlsəfi və riyazi fikrin inkişafı üçün əsas olmuşdur.

Məntiqin formalaşması və inkişafı üçün cəbr (Bule cəbri) və digər riyazi fənlər, o cümlədən yenidən həndəsə (qeyri-Evklid həndəsəsinin yaradılması - Lobaçevski-Qauss-Bolyai həndəsəsi) üzrə nailiyyətlər də böyük əhəmiyyət kəsb edirdi. Riyazi məntiqin formalaşmasının qısa icmalı ilə tanış ola bilərsiniz.

İstər qədim dövrlərdə, istərsə də orta əsrlərdə və sonrakı dövrlərdə riyazi məntiqin formalaşmasında və inkişafında çoxlu və çoxlu alimlər iştirak etmişdir.

Riyazi məntiqin fundamental və tətbiqi əhəmiyyəti

Riyazi məntiqin fundamental əhəmiyyəti riyaziyyatın əsaslandırılmasıdır (riyaziyyatın əsaslarının təhlili).

Riyazi məntiqin tətbiqi dəyəri hazırda çox yüksəkdir. Riyazi məntiq aşağıdakı məqsədlər üçün istifadə olunur:

rəqəmsal kompüterlərin və digər diskret avtomatların, o cümlədən intellektual sistemlərin təhlili və sintezi (konstruksiyası);

formal və maşın dillərinin təhlili və sintezi, təbii dilin təhlili üçün;

hesablama qabiliyyətinin intuitiv konsepsiyasının təhlili və rəsmiləşdirilməsi;

müəyyən tipli məsələlərin həlli üçün mexaniki prosedurların mövcudluğunun aşkar edilməsi;

hesablama mürəkkəbliyi problemlərinin təhlili.

Həmçinin, riyazi məntiqin dilçilik, iqtisadiyyat, psixologiya və fəlsəfənin bir sıra məsələləri ilə sıx bağlı olduğu ortaya çıxdı.

Bu dərslik riyazi məntiqin əsas anlayışlarını və alqoritmlər nəzəriyyəsini əks etdirir. Təlimatda təqdim olunan material

“İnformatika və kompüter mühəndisliyi” istiqaməti üzrə dövlət təhsil standartına uyğundur və bu istiqamətdə müxtəlif ixtisaslar üzrə təhsil alan tələbələr üçün istifadə oluna bilər.

Təlimat yazarkən ədəbiyyatdan istifadə olunub və təbii ki, başqa mənbələrdən də istifadə olunub. Ədəbiyyat siyahısına maraqlanan və tələbkar tələbə üçün baxması arzu olunan kitablar daxildir.

Təlimatda hər bir fəsildə nəzəri materialın özünü sınamaq üçün suallar və problem həll etmə bacarıqlarını inkişaf etdirmək və təqdim olunan mövzu üzrə bilikləri dərinləşdirmək üçün hazırlanmış tapşırıqlar var. Bundan əlavə, təlimat materialın mənimsənilməsinə özünü idarə etmək üçün tipik tapşırıqlar və testlər üçün seçimlər təqdim edir.

Federal Təhsil Agentliyi

TOMSK DÖVLƏT İDARƏ SİSTEMLERİ VƏ RADİO ELEKTRONİKA UNİVERSİTETİ (TUSUR)

İnformasiya emalının avtomatlaşdırılması şöbəsi

Təsdiq edirəm:

Baş kafe AOI

professor

Yu.P. Exlakov

"__" _____________2007

Təlimatlar

intizam üzrə praktiki işlərin yerinə yetirilməsinə

“Riyazi məntiq və alqoritmlər nəzəriyyəsi”

230102 ixtisasının tələbələri üçün -

“İnformasiyanın emalı və idarə edilməsi üçün avtomatlaşdırılmış sistemlər”

Tərtibatçılar:

İncəsənət. kafedrasının müəllimi AOI

SONRA. Peremitina

Tomsk - 2007

Praktiki məşğələ No1 “Məktəb cəbri düsturları” 3

Praktiki məşğələ No2 “Məktəb cəbri düsturlarının ekvivalent çevrilmələri” 10

Praktiki məşğələ No3 “Düsturların normal formaları” 12

Praktiki məşğələ No4 “Məntiqi əsaslandırma” 14

Praktiki məşğələ No5 “Predikat məntiqinin düsturları” 18

Təcrübə №6 Boolean funksiyaları 23

7-ci məşq Qismən rekursiv funksiyalar 28

Təcrübə №8 Turinq Maşınları 34

Praktiki dərs №1 “Məktəb cəbri düsturları”

Təkliflər doktrinası - müddəaların cəbri və ya məntiq cəbri - ən sadə məntiqi nəzəriyyədir. Təklif cəbrinin atom anlayışı belədir bəyanat - onun həqiqəti və ya yalanı haqqında ifadənin məna kəsb etdiyi bəyannamə cümləsi.

Doğru ifadəyə misal: “Yer günəşin ətrafında fırlanır”. Yalan ifadəyə misal: "3 > 5". Hər cümlə bir ifadə deyil, ifadələrə sorğu və nida cümlələri daxil deyil. "Sıyıq ləzzətli yeməkdir" cümləsi bir ifadə deyil, çünki bunun doğru və ya yalan olduğuna dair fikir birliyi yoxdur. "Marsda həyat var" cümləsi bir ifadə hesab edilməlidir, çünki obyektiv olaraq ya doğrudur, ya da yanlışdır, baxmayaraq ki, hansının olduğunu hələ heç kim bilmir.

Məntiqin öyrənilməsi mövzusu yalnız təkliflərin həqiqət qiymətləri olduğundan, onlar üçün A, B, ... və ya X, Y ... hərf təyinatları təqdim olunur.

Hər bir ifadə ya doğru, ya da yalan hesab olunur. Qısalıq üçün həqiqi dəyər yerinə 1, yanlış qiymət yerinə 0 yazacağıq.Məsələn, X= "Yer Günəş ətrafında fırlanır" və Y= "3\u003e 5", X=1 və Y = 0. Bəyanat həm doğru, həm də yalan ola bilməz.

İfadələr sadə və ya mürəkkəb ola bilər. "Yer günəşin ətrafında fırlanır" və "3 > 5" ifadələri sadədir. Mürəkkəb müddəalar sadə sözlərdən təbii (rus) dil bağlayıcılarının köməyi ilə düzəldilir. İfadələr üçün əlifba qeydindən istifadə edərkən bu bağlayıcılar xüsusi riyazi simvollarla əvəz olunur ki, bu da məntiqi əməliyyatların simvolu sayıla bilər.

Aşağıda, cədvəl 1-də birləşdiricilərin təyin edilməsi üçün simvolların variantları və müvafiq məntiqi əməliyyatların adları verilmişdir.

İnkar (inversiya) ifadələri X yalnız və yalnız o halda doğru olan ifadədir X yalan (işaret və ya , oxuyur “yox X” və ya “bu doğru deyil X”).

bağlayıcı
iki müddəa yalnız və yalnız hər iki müddəa doğru olduqda doğru olan müddəa adlanır X və Y. Bu məntiqi əməliyyat ifadələrin "və" birliyi ilə əlaqəsinə uyğundur.

disjunksiya
iki cümlə X və Y Bir ifadənin yalan olduğu deyilir, ancaq və yalnız hər iki ifadə X və Y yalan. Danışıq nitqində bu məntiqi əməliyyat "və ya" birliyinə uyğun gəlir (eksklüziv "və ya" deyil).

mənası iki cümlə X və Y yalnız və yalnız o halda yalan olan ifadədir X doğrudur və Y- yalan (ifadə olunur
; oxuyur" X ehtiva edir Y"," əgər X, sonra Y”). Bu əməliyyatın operandlarının xüsusi adları var: X- paket, Y- nəticə.

Ekvivalentlik iki cümlə X və Y yalnız və yalnız həqiqət dəyər verdiyi halda doğru olan müddəa adlanır X və Y eynidir (simvol:
).

Cədvəl 1. Məntiqi əməliyyatlar

Məntiqi əməliyyatların operandları yalnız iki qiymət ala bilər: 1 və ya 0. Buna görə də hər bir məntiqi əməliyyat , &, , ,  qiymətlərdən asılı olaraq əməliyyatın nəticəsinin qiymətini göstərən cədvəldən istifadə etməklə asanlıqla təyin oluna bilər. operandlardan. Belə bir cədvəl adlanır həqiqət cədvəli (Cədvəl 2).

Cədvəl 2. Məntiqi əməllərin həqiqət cədvəli

Yuxarıda göstərilən məntiqi əməliyyatların köməyi ilə sadə müddəalardan qurmaq olar təklif məntiqi düsturları müxtəlif mürəkkəb ifadələri təmsil edir. Mürəkkəb ifadənin məntiqi mənası düsturla ifadə olunan ifadənin strukturundan və onu təşkil edən elementar ifadələrin məntiqi dəyərlərindən asılıdır.

İfadələri ifadə edən düsturların sistemli öyrənilməsi üçün dəyişən ifadələr təqdim olunur P, P 1 , P 2 , ..., P N, çoxluqdan dəyərlər alaraq (0, 1).

Təklif məntiqi düsturu F (P 1 , P 2 ,..., P N) tavtologiya və ya adlanır eyni dərəcədə doğrudur hər hansı bir dəyər üçün onun dəyəri P 1 , P 2 ,..., P N 1-dir (doğru). Ən azı bir dəyişən siyahısı üçün doğru olaraq qiymətləndirilən düsturlar çağırılır edilə bilən . Dəyişənlərin hər hansı bir dəyəri üçün "yanlış" dəyərini alan düsturlar adlanır ziddiyyətlər (eyni şəkildə yalan, qeyri-mümkün).

11.1. Alqoritm anlayışı və alqoritmlər nəzəriyyəsi

İntuitiv olaraq, alqoritm diskret zamanda gedən bir problemin ardıcıl həlli prosesi kimi başa düşülür ki, zamanın hər növbəti anında mövcud olan obyektlər sistemindən müəyyən qanuna uyğun olaraq alqoritmin obyektləri sistemi alınsın. əvvəlki zaman anında. İntuitivdir, çünki ciddi şəkildə desək, alqoritm anlayışı müəyyən edilə bilməyən çoxluq anlayışına bənzəyir.

GOST 19781-74 uyğun olaraq “Hesablama maşınları. Proqram təminatı. Şərtlər və anlayışlar" alqoritm dəyişən ilkin məlumatlardan istənilən nəticəyə aparan hesablama prosesini təyin edən dəqiq reseptdir. Bu, alqoritm icraçısının - bu hərəkətləri yerinə yetirmək üçün "necə" bilən bir obyektin mövcudluğunu nəzərdə tutur.

"Alqoritm" sözünün XIII əsr Orta Asiya (özbək) riyaziyyatçısı Əl Xorezminin (Əbu Abdullah Məhəmməd ibn Musa əl Xorezmi əl Medjusi) adından gəldiyi güman edilir - latın transkripsiyasında "Alqoritmi" ilk dəfə olaraq onluq say sistemində dörd arifmetik əməliyyatın yerinə yetirilməsi qaydalarını (prosedurunu) tərtib etmişdir.

Nə qədər ki, hesablamalar sadə idi, alqoritmlərə xüsusi ehtiyac yox idi. Bir neçə addım-addım prosedura ehtiyac yarandıqda, alqoritmlər nəzəriyyəsi ortaya çıxdı. Lakin tapşırıqların daha da mürəkkəbləşməsi ilə məlum oldu ki, onların bəzilərini alqoritmik şəkildə həll etmək mümkün deyil. Məsələn, bir insanın "bort kompüteri" - beyni tərəfindən həll olunan bir çox vəzifələr bunlardır. Belə məsələlərin həlli başqa prinsiplərə əsaslanır - bu prinsiplərdən yeni elm - neyroriyaziyyat və müvafiq texniki vasitələr - neyrokompyuterlər istifadə edir. Bu zaman öyrənmə, sınaq və səhv prosesləri tətbiq olunur - yəni bizim hazırda gördüyümüz işlər.

Alqoritmin keyfiyyəti onun xassələri (xüsusiyyətləri) ilə müəyyən edilir. Alqoritmin əsas xüsusiyyətləri bunlardır:

1. kütləvi xarakter. Ehtimal olunur ki, alqoritm bu tipli bütün məsələlərin həlli üçün uyğun ola bilər. Məsələn, xətti cəbri tənliklər sisteminin həlli alqoritmi ixtiyari sayda tənliklərdən ibarət sistemə şamil edilməlidir.

2. Səmərəlilik. Bu xassə o deməkdir ki, alqoritm sonlu sayda addımlarla nəticə çıxarmalıdır.

3. Əminlik. Alqoritmə daxil edilmiş təlimatlar dəqiq və başa düşülən olmalıdır. Bu xüsusiyyət verilmiş ilkin məlumatlar üçün hesablama prosesinin nəticəsinin unikallığını təmin edir.

4. diskretlik. Bu xassə o deməkdir ki, alqoritm və alqoritmin özü ilə təsvir olunan prosesi ayrıca elementar mərhələlərə bölmək olar, istifadəçinin kompüterdə yerinə yetirə bilməsi ehtimalı heç bir şübhə doğurmur.

Bu gün “rəqəmsal minillik” həyətdədir və siz hər hansı tapşırıqların alqoritmlərə tabe olduğu təəssüratı yarada bilərsiniz. Belə çıxır ki, bir çox məsələləri alqoritmlə həll etmək mümkün deyil. Bunlar alqoritmik olaraq həll olunmayan problemlərdir.

Problemlərin alqoritmik həllini və ya həll edilməməsini sübut etmək üçün riyazi cəhətdən ciddi və dəqiq vasitələr lazımdır. Ötən əsrin 30-cu illərinin ortalarında alqoritm anlayışını rəsmiləşdirməyə cəhdlər edilmiş və alqoritmlərin müxtəlif modelləri təklif edilmişdir: rekursiv funksiyalar; "maşınlar" - Turing, Post; normal Markov alqoritmləri.

Sonradan məlum oldu ki, bu və digər modellər həll etdikləri problemlərin siniflərinin üst-üstə düşməsi mənasında ekvivalentdirlər. Bu fakt Kilsənin tezisi adlanır. İndi bu, ümumiyyətlə qəbul edilir. Alqoritm anlayışının formal tərifi alqoritm nəzəriyyəsinin inkişafı üçün hələ ilk kompüterlərin yaranmasından əvvəl ilkin şərtlər yaratmışdır. Kompüter texnologiyasının inkişafı alqoritmlər nəzəriyyəsinin gələcək inkişafına təkan verdi. Alqoritmlər nəzəriyyəsi məsələlərin alqoritmik həllini qurmaqla yanaşı, addımların sayı (vaxt mürəkkəbliyi) və tələb olunan yaddaş (məkan mürəkkəbliyi) baxımından alqoritmlərin mürəkkəbliyinin qiymətləndirilməsi ilə də məşğul olur, eyni zamanda, alqoritmlərin həlli üçün səmərəli alqoritmlər hazırlayır. bu mənada.

Fizika nöqteyi-nəzərindən elementar addımların yerinə yetirilmə sürəti ilə bağlı hər hansı ağlabatan fərziyyələr əsasında bəzi alqoritmlərin həyata keçirilməsi üçün müasir baxışlara görə Kainatın mövcud olduğundan və ya atomlardan daha çox yaddaş hüceyrəsi tələb oluna bilər. Yer planetini təşkil edir.

Buna görə də alqoritmlər nəzəriyyəsinin digər vəzifəsi kombinator alqoritmlərində variantların sadalanmasının aradan qaldırılması məsələsini həll etməkdir. Alqoritmlərin mürəkkəbliyinin qiymətləndirilməsi və sözdə səmərəli alqoritmlərin yaradılması müasir alqoritm nəzəriyyəsinin ən mühüm vəzifələrindən biridir.

S. N. Pozdnyakov S. V. Rıbin

Dərslik

Rusiya Federasiyasının Təhsil və Elm Nazirliyi

Sankt-Peterburq Dövlət Elektrotexnika Universiteti "LETI"

S. N. Pozdnyakov S. V. Rıbin

RİYASİ MƏNQİQ VƏ ALQORİTM NƏZƏRİYYƏSİ

Sankt-Peterburq SPbGETU "LETİ" nəşriyyatı

UDC 510.6 BBK V12 P47

Pozdnyakov S. N., Rybin S. V. Riyazi məntiq və alqoritmlər nəzəriyyəsi: Proc. müavinət. Sankt-Peterburq: SPbGETU "LETI", 2004. 64 s.

Riyazi məntiqin əsas ideyaları, konsepsiyaları və metodları nəzərdən keçirilir, onlara maraq informasiya texnologiyalarının inkişafı ilə əlaqədar son zamanlarda meydana çıxan yeni tətbiqlər hesabına artmışdır.

Həm əyani təhsil alan tələbələr, həm də texniki universitetlərin axşam və qiyabi fakültələri üçün istifadə oluna bilər.

Rəyçilər: Sankt-Peterburq Dövlət Universitetinin Riyazi Analiz Departamenti; Dos. M. V. Dmitrieva (Sankt-Peterburq Dövlət Universiteti).

Universitetin redaksiya və nəşriyyat şurası tərəfindən təsdiq edilmişdir

tədris vəsaiti kimi

Riyazi məntiq, alqoritmlər nəzəriyyəsi kimi, kompüterlərin yaranmasından çox əvvəl meydana çıxdı. Onların yaranması riyaziyyatın daxili problemləri, onun nəzəriyyə və metodlarının tətbiqi hüdudlarının öyrənilməsi ilə bağlı olmuşdur.

AT Hal-hazırda, bu (bir-biri ilə əlaqəli) nəzəriyyələrin hər ikisi kompüter riyaziyyatı (informatika) adlanan sahədə tətbiqi inkişaf əldə etmişdir. Tətbiq olunan sahələrdə onların istifadəsinin bəzi sahələri bunlardır:

– ekspert sistemlərinin istifadəsi müxtəlif sahələr üzrə ekspertlərin fəaliyyətini simulyasiya etmək üçün formal-məntiqi nəticələr;

– mikrosxemlərin layihələndirilməsi zamanı Boolean funksiyaları nəzəriyyəsindən istifadə olunur;

– proqramların sınaqdan keçirilməsi onların strukturunun məntiqi təhlilinə əsaslanır;

– proqramların düzgünlüyünün sübutu məntiqi nəticə nəzəriyyəsinə əsaslanır;

– alqoritmik dillər iki mühüm məntiq anlayışını birləşdirir: dil anlayışı və alqoritm anlayışı;

– teorem sübutunun avtomatlaşdırılması məntiq kursunda öyrənilən həllər metoduna əsaslanır.

AT Bu dərslik həm sadalananların, həm də onun digər tətbiqlərinin əsasını təşkil edən riyazi məntiqin əsas ideyalarını, konsepsiyalarını və metodlarını əks etdirir.

1. Binar əlaqələr və qrafiklər

1.1. Giriş. Problemin formalaşdırılması

Artıq məktəb riyaziyyat kurslarında binar münasibətlərə rast gəlinir. Bu cür münasibətlərə misal olaraq bərabərsizlik, bərabərlik, oxşarlıq, paralellik, bölünmə və s. münasibətləri göstərmək olar. Binar münasibət obyektlər bu əlaqədə olduqda hər iki obyektə “hə” məntiqi qiymət verir, əks halda isə “yox”. Başqa sözlə desək, obyektlərin cüt çoxluğu iki alt çoxluğa bölünür, birinci alt çoxluğun cütləri bu münasibətdədir, ikincisi isə yox. Bu xassə binar əlaqənin tərifi üçün əsas kimi istifadə edilə bilər.

Tərif 1.1. M çoxluğu verilsin. Bu çoxluğun Kartezian hasilini və özünü M × ​​M hesab edin. M ×M çoxluğunun R alt çoxluğuna M çoxluğunda R ikili münasibət deyilir. Əgər (x; y) cütü R çoxluğuna aiddirsə, x elementinin y elementinə münasibətdə olduğu deyilir və xRy yazılır.

Misal 1.1. Müqayisəlilik əlaqəsini təqdim edək R : x cy modulu m ilə müqayisə oluna bilər o halda və yalnız x və y eyni modul m olduqda . Yəni x ≡ y (mod m) .

M = (1; 2; 3; 4; 5; 6) çoxluğunda m = 3 halı üçün daxil edilmiş R münasibətini nəzərdən keçirək, sonra

R əlaqəsi belə cütlərin çoxluğu ilə müəyyən edilir:

Misal 1.2. M = R şeylər toplusunu nəzərə alın

həqiqi ədədlər və ya başqa sözlə, həqiqi xəttdəki nöqtələr çoxluğu. Onda M × M = R 2 koordinat müstəvisində nöqtələr çoxluğudur. Bərabərsizlik əlaqəsi< определяется множеством парR = = {(x; y)|x < y} .

Məşq 1.1.

1. Həqiqi ədədlər çoxluğunda əlaqə verilir: sonra xRy

yalnız və yalnız rəqəmlərdən biri digərindən iki dəfə çox olduqda. Müstəvidə bu əlaqəni təyin edən nöqtələr toplusunu çəkin.

2. M = (1; 2; 3; 4; 5; 6) çoxluğunda bölünmə münasibəti verilir: xRy yalnız və yalnız o halda verilir ki, x y-ə bölünür. Neçə cüt edir

bu münasibətdir? Bu cütləri sadalayın.

3. M = (1; 2; 3; 4; 5; 6) çoxluğunda biz əlavə-əsas münasibətini, yəni xRy-ni yalnız və yalnız o halda təqdim edirik ki, x və y cüt-cürdür: D(x; y) = 1 . Bu əlaqə neçə cütdən ibarətdir? Bunları sadalayın

1.2. İkili Münasibətlərin xassələri

Tərif 1.2. M çoxluğunda R ikili əlaqəsi adlanır

bu çoxluğun hər bir elementi özü ilə əlaqədədirsə refleksdir: xRx x M .

Misal 1.3.

1. Müqayisə əlaqəsi refleksivdir (hər hansı təbii m və istənilən tam ədədlər toplusunda).

2. Həqiqi ədədlər çoxluğundakı ciddi bərabərsizlik əlaqəsi refleksiv deyil.

3. Bölünmə münasibəti refleksivdir (tərkibində sıfır olmayan hər hansı tam ədədlər toplusunda).

Tərif 1.3. M çoxluğunda R ikili əlaqəsi çağırılır

Əgər bu çoxluğun heç bir elementi özünə münasibətdə deyilsə, əks-refleksivdir: x M xRx olduğu doğru deyil.

Misal 1.4.

1. Həqiqi ədədlər çoxluğundakı ciddi bərabərsizlik əlaqəsi antirefleksivdir.

2. Tərkibində olmayan hər hansı tam ədədlər dəstində koprime münasibəti əks-refleksivdir 1 və −1 , (1), (−1) ,(−1; 1) dəstlərində refleksivdir və nə refleksiv, nə də antirefleksiv deyil.

əks halda.

Tərif 1.4. M çoxluğundakı R ikili münasibəti simmetrik adlanır, əgər hər bir cüt (x; y) ilə birlikdə bu əlaqə simmetrik cütü də (y; x) :x, y M xRy yRx ehtiva edir.

Misal 1.5.

1. Müqayisəlilik əlaqəsi istənilən təbii üçün simmetrikdir

2. Həqiqi ədədlər çoxluğundakı ciddi bərabərsizlik əlaqəsi simmetrik deyil.

3. Bölünmə münasibəti yalnız tərkibində bir olmayan qoşa-əmsal tam ədədlər çoxluğunda simmetrik olur. Məsələn, sadə ədədlər çoxluğunda.

4. İstənilən tam ədədlər çoxluğunda ümumi əlaqə simmetrikdir.

Tərif 1.5. M çoxluğunda R ikili əlaqəsi adlanır

əgər heç bir cüt onun simmetriki ilə birlikdə əlaqəyə girmirsə, asimmetrikdir: x, y M , əgər xRy , onda yRx olması doğru deyil.

Misal 1.6.

1. Həqiqi ədədlər çoxluğundakı ciddi bərabərsizlik əlaqəsi asimmetrikdir.

2. Tərkibində sıfır olmayan hər hansı tam ədədlər dəstində bölünmə münasibəti asimmetrik deyil.

Tərif 1.6. M çoxluğunda R ikili əlaqəsi adlanır

müxtəlif elementlərdən ibarət heç bir cüt onun simmetriki ilə birlikdə əlaqəyə girməzsə antisimmetrikdir: x, y M , əgər xRy və yRx isə x = y .

Misal 1.7.

1. Həqiqi ədədlər çoxluğunda qeyri-sərt bərabərsizliyin əlaqəsi antisimmetrikdir.

2. Bölünmə münasibəti sıfır olmayan hər hansı tam ədədlər dəstində antisimmetrikdir.

Məşq 1.2.

1. Doğrudanmı, asimmetrik əlaqə həmişə antirefleksivdir? Sübut et.

2. Simmetrik əlaqənin həmişə refleksiv olduğu doğrudurmu? Mənə deyin.

3. Asimmetrik əlaqənin həmişə antisimmetrik olduğu doğrudurmu? Sübut et.

4. Doğrudanmı, əlaqə yalnız və yalnız antirefleksiv və antisimmetrik olduqda asimmetrik olur? Sübut et.

Tərif 1.7. (x; y) cütləri ilə birlikdə (x, z) cütü də daxil olarsa, yəni x, y, x M, əgər xRy və

M çoxluğu, yRz , onda xRz münasibətində u(y; z) adlandırırıq.

Qeyd 1.1. Keçidliyin xassəsi əlçatanlıq əlaqəsi ilə yaxşı təsvir edilmişdir: əgər y nöqtəsinə x nöqtəsindən, z nöqtəsinə isə y nöqtəsindən çatmaq olarsa, z nöqtəsinə x nöqtəsindən çatmaq olar.

Misal 1.8.

1. Müqayisəlilik əlaqəsi istənilən təbii üçün keçidlidir m və istənilən tam ədədlər toplusunda.

2. Ciddi (qeyri-sərt) bərabərsizlik əlaqəsi həqiqi ədədlərin istənilən alt çoxluğunda keçidlidir.

3. Bölünmə münasibəti sıfırdan ibarət olmayan tam ədədlər çoxluğunda keçidlidir.

4. Hər hansı tam ədədlər çoxluğunda ümumi əlaqə keçidli deyil. Misal üçün, 2 c3-ə uyğundur, 3-cü c4-ə uyğundur, lakin 2 və 4-cü amil deyil.

Məşq 1.3. Doğrudur, keçid və simmetrikdir

münasibət həmişə refleksivdir? Sübut et.

1.3. Münasibətlərin müəyyənləşdirilməsi yolları

İkili əlaqəni təyin edən cütlərin açıq-aydın sadalanmasına əlavə olaraq, əlaqələrin müəyyənləşdirilməsinin aşağıdakı yolları mümkündür.

Doğrulama prosedurunun müəyyən edilməsi.

Misal 1.9.

1. Üstünlük əlaqəsi ən böyük ortaq bölənin tapılması proseduru ilə yoxlanılır: əgər D(x; y) = 1 , onda (x; y) daxil edilir

qarşılıqlı sadəlik əlaqəsi.

2. Bölünmə nisbəti qalıq ilə bölmə proseduru ilə yoxlanılır: əgər x ≡ 0 (mod y) , onda (x; y) bölünmə münasibətinə daxil edilir.

3. Eyni prosedur, bölündükdə qalıqların bərabərliyi əlaqəsini yoxlayır m : əgər(x−y)≡0 (mod m) , onda(x; y) əlaqədədir.

Sonlu çoxluqlar üzrə əlaqələr üçün (diskret riyaziyyat üçün əsas olan) əlaqələri təyin etmək və təsvir etmək üçün aşağıdakı üsullardan da istifadə olunur.

Qonşuluq matrisinin təyin edilməsi. Ölçüsü olan A matrisini təyin edək

|M| × |M |, burada |M | M çoxluğunun elementlərinin sayıdır. M çoxluğunun elementlərini nömrələyirik. Onda i nömrəli element j (iRj) nömrəli elementlə əlaqədədirsə aij = 1, əks halda aij = 0 olar.

Misal 1.10. M = (1; 2; 3; 4; 5; 6) çoxluğunda bölünmə əlaqəsi üçün bitişiklik matrisi belə görünür:

Qrafik tapşırıq. Çoxluğun elementləri müstəvi nöqtələri ilə təmsil olunur və qrafikin təpələri çoxluğunu təşkil edir. Münasibət qrafikin qövsləri (kənarları) ilə təmsil olunur: əgər (x; y) münasibətə daxil edilirsə, onda x təpəsindən y-yə doğru istiqamətlənmiş qövs çəkilir.

Misal 1.11. Müqayisəlilik modulu üçün əlaqə üçün qrafik

Qonşuluq siyahısının müəyyən edilməsi. Çoxluğun hər bir elementi üçün onunla bu əlaqədə olan elementlər sadalanır.

Misal 1.12. M = (1; 2; 3; 4; 5; 6) çoxluğundakı ümumi əlaqə üçün bitişiklik siyahısı belə görünür:

Qrafiklər və onları təsvir edən matrislər üzərində binar münasibətlərin xassələrinin şərhini verək.

Teorem 1.1. Aşağıdakı iddialar doğrudur.

1. Refleksiv əlaqənin qonşuluq matrisinin diaqonalı birlərdən ibarətdir.

2. Simmetrik əlaqənin simmetrik bitişiklik matrisi var

3. Refleksiv əlaqə qrafikinin hər təpəsində döngələr var.

4. Bir qövs birləşdirən simmetrik əlaqə qrafiki x

y ilə , y-ni x ilə birləşdirən qövs ehtiva edir.

5. Keçid əlaqənin qrafiki aşağıdakı xüsusiyyətə malikdir: əgər təpədən x , qövslər boyunca hərəkət edərək y təpəsinə çata bilərsiniz, onda qrafikdə x-i y ilə birbaşa birləşdirən qövs olmalıdır.

Qeyd 1.2. Simmetrik üçün

ilgəklər adətən çəkilmir və verilmiş təpələri birləşdirən cüt istiqamətlənmiş qövslər tək, istiqamətsiz qövslə əvəz olunur.

Məsələn, Nümunə 1.11-dəki qrafik Şəkil 1.11-də göstərilənə bənzəyir. 1.2.

və əks etdirən əlaqələr

Məşq 1.4.

1. Qonşuluq matrisinin xassələrini təsvir edin: a) antirefleksiv əlaqə; b) asimmetrik əlaqə; c) antisimmetrik əlaqə; d) keçid əlaqəsi.

2. Qrafikin xassələrini təsvir edin: a) antirefleksiv əlaqə; b) asimmetrik əlaqə; c) antisimmetrik əlaqə.

1.4. Ekvivalentlik əlaqəsi

Tərif 1.8. re xassələrinə malik olan ikili əlaqə

əyilməzlik, simmetriya və keçidliliyə ekvivalentlik münasibəti deyilir.

Misal 1.13. Müqayisəlilik əlaqəsi (hər hansı modul üzrə) belədir

ekvivalentlik əlaqəsi ilə verilir.

M çoxluğunun hər bir elementi ilə verilmiş ekvivalentlik münasibətində onunla olan bütün elementləri əlaqələndirək: Mx = (y M | xRy). Aşağıdakı teorem doğrudur.

Teorem 1.2. M x və M y çoxluqları ya kəsişmir, ya da

Sübut. Eyni sinfin bütün elementləri bir-birinə ekvivalentdir, yəni x, y Mz, onda xRy olarsa. Həqiqətən, x, y Mz, deməli, xRz və yRz olsun. R-nin simmetriyasına görə biz zRy-yə sahibik. Sonra keçid qabiliyyətinə görə xRz və zRy-dən xRy alırıq.