Дискреттік математика негіздері



бет4/4
Дата08.02.2022
өлшемі345 Kb.
#118558
түріСабақ
1   2   3   4

Қатынас

  • Қатынас деп әр түрлі нысандар қасиетін және олардың арасындағы байланысты анықтайтын математикалық құрылымды айтады.
  • (Х,R) жиындар жұбын қатынас деп атайды, мұндағы RХn.
  • Жиында берілетін n-орынды (n-арнды) қатынас деп, жиындардың тура көбейтіндісінің ішкі жиындары аталады

Қатынастар түрлері

  • Бір орынды немесе унарлы қатынас деп бір айнымалымен орындалатын қатынасты айтады (терістеу амалы, санның дәрежесін табу).
  • Екі орынды қатынастарды бинарлы деп атайды және оларды инфиксті жазбамен жазады: хRу. (конъюнкция, дизъюнкция)
  • Үш орынды қатынастарды тренарлы деп атайды.
  • Би” сөзі “екі”, “уно” сөзі “бір” деген мағынаны береді.

Қатынастар қасиеттері

  • Рефлексивтік
  • х R х - ақиқат ;
  • Антирефлексивтік
  • х R х - жалған;
  • Симметриялық
  • х R у  у R х ;
  • Антисимметриялық
  • (х R у)&(у R х)  x=y ;
  • Сызықтық
  • Егер (х R у) – ақиқат, онда (у R х) – жалған;
  • Транзитивтік
  • (х R у)&(у R z)  x R z .

Графтар

  • Граф деп өзара байланысқан нысандар жиынтығын айтады. Нысандар-шыңдар деп аталады және нүктелер арқылы белгіленеді. Ал шыңдар арасындағы байланыс-доғалар немесе қабырғалар деп аталады
  • Граф G = (V, Е) V және Е соңғы жиындар жұбымен беріледі. Бірінші жиын элементтері v1, v2,..., v M графтың шыңы деп аталады (графикалық көріністе оларға нүктелер сәйкес). Екінші жиын элементтері el, e2, ..., e N қабырғалар деп аталады. Әр қабырға шыңдар жұбымен анықталады (графикалық көріністе қабырғалар графтың екі шыңын қосады).

Сурет 1.

  • Суретте бес шыңы және жеті қабырғасы бар бағытталған граф кескінделген.

Графтың түрлері

  • Егер графтың барлық қабырғалары бағытталмаған болса, онда ол бағытталмаған граф деп, ал егер графтың барлық қабырғалары бағытталған болса, онда ол бағытталған граф деп аталады.
  • Егер графта бағытталған және бағытталмаған да қабырғалар болса, ол аралас граф деп аталады.
  • Егер граф қабырғалары шыңдардың реттелген жұбымен анықталса, онда оны бағытталған қабырға немесе доға деп атайды (сызбада бағытталған қабырғаға оның бағытын анықтайтын стрелкалар қойылады).
  • Егер екі шың екі немесе одан да көп қабырғалармен қосылса, онда мұндай қабырғалар параллельді деп аталады (мысалы, қабырғалар е4 және е5).
  • Егер қабырғаның басы мен соңы бір жерден шықса, онда мұндай қабырға ілмек (петля) деп аталады(мысалы, қабырға e7). Ілмексіз және параллельді қабырғаларсыз графтар қарапайым деп аталады.
  • Графтың қасиеттері

Ағаштар

  • Ағаш деп циклсыз бағытталмаған байланысшы графты айтады.
  • Орман – бұл циклсыз кез-келген граф.
  • Суретте бес шыңды мүмкін ағаштар көрсетілген.

Бақылау сұрақтары:

  • Жиын анықтамасын беріңіз?
  • Жиынның қандай түрлерін білесіз?
  • Логиканы негізін салушы кім?
  • Ақиқаттық кестесі деген не?
  • Логиканың негізгі заңдарын атаңыз?
  • Граф деген не?
  • Ағаш деген не ?


Достарыңызбен бөлісу:
1   2   3   4




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет