3. Берілген сигнатураның ешбір структурасына орындалмайтын формуланы әрқашан жалған(қайшылық) деп атайды
Егер сигнатурасының кез келген алгебралық жүйесінде формуласы ақиқат болса, онда формуласын әрқашан ақиқат (жалпымәнді) формула деп айтамыз. Белгілеуі: .
Анықтама. Г берілген сигнатурадағы формулалар жиыны және осы сигнатураның белгілі бір формуласы болсын. Егер Г жиынының кез келген формуласы орындалатын осы сигнатураның әрбір структурасының кез келген тізбегінде формуласы да орындалса (қысқаша , Mn, Г, [ ] [ ]), онда формуласы Г жиынының семантикалық салдары деп аталады.
Белгілеуі: Г . Егер және формулалары үшін ( Оқылуы: формуласы формуласының салдары) және ( формуласы формуласының салдары) болған жағдайда және формулаларын логикалық эквивалентті(Белгілеуі: ) формулалар деп атайды.
1
№13 дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
1. Граф және оның түрлері.
2. Графтардың берілу тәсілдері.
Дәрістің қысқаша мазмұны:
Граф ұғымы. Көптеген қолданбалы есептерде айналамызды қоршаған ортаның әртүрлі объектілер арасындағы байланыстар жүйесі зерттеледі. Объектілер төбелер деп аталып, нүктелер арқылы белгіленеді, ал төбелер арасындағы байланыстар доғалар деп аталып, сәйкес нүктелерді қосатын бағытталған түзулермен белгіленеді. Қала көшелерін граф арқылы кескіндеуге болады: көше қиылысуларын графтардың төбесі деп, ал көшелерді доғалар деп алуға болады;
Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф төбелері, ал операцияның орындалу кезегін көрсететін стрелкалар доғалар.
Анықтама: G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R M2 элементтері доғалар деп аталады. Сонымен граф төбелері дегеніміз –айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз оларды натурал сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. Граф қабырғаларын әдетте латын әріптерімен белгілейді. G= ‹M,R› графының геометриялық кескіні жазықтықта графтың әр төбесін нүкте арқылы белгілеп , егер (a,b) R болса а төбесінен b төбесіне доға жүргізу арқылы алынады.
Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы туралы ақпараттар маңызды емес.Төбелердің арасында байланыс бар екендігі және ол байланыс туралы ақпарат R доғалар жиынында екендігі болса болды.Төбелерді қосатын сызықтардың бағыты көрсетілген болуы мүмкін (мысалдағы сияқты). Мұндай граф бағытталған граф деп аталады (оргграф). Оған математикалық түрде мынандай анықтама беруге болады.
G= графына а төбесін қосқаннан <М {a}, R> графы құралады.
Графқа доға қосу операциясының нәтижесінде <М {(a,b)}, R {(a,b)}> графы құрылады.
Графтан доға алу–R доғалар жиынынан (a,b) жұбы алынады. Графтан төбе алу операциясының нәтижесінде. G графынан а төбесі оған инцидентті доғалармен бірге алынады деп айтады. Графтың a,b төбелерін теңестіру деп графтан a,b төбелерін алып тастап мына тәртіппен төбе мен қабырға қосу: жаңа а1 төбесі мен (а1, с), егер (а, с) R немесе (b, с) R және (с, а1) доғасын егер (с, а) R немесе (с, b) R болса:<(M\{a,b}) {a1}, (R\{(с, d)│c=a немесе d=a, немесе c=b, немесе d=b}) {(a1,c)│(a, c) R, немесе (b, c) R} {(c, a1)│(c, a)R, немесе (c, b) R}).
Алынған граф G графынан a,b төбелерін теңестіргеннен алынды делінеді.
1
№14 дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
1. Цикл. Эйлер және Гамильтон циклдары.
2. Цикломатикалық және хроматикалық сан.
3. Маршрут. Графтың байланыс компоненттері.
Дәрістің қысқаша мазмұны:
