Дәріс 3. Дискретті математиканың негізі

Функция, қатынас және жиын. Логика негізі, логикалық ойларды айту, логикалық байланыстар, ақиқаттылық кестелері. Графтар және ағаштар: ағаштар, бағытталмаған графтар, бағытталған графтар

Логика алгебрасы дегеніміз логикалық тұжырымдарды жазуға, есептеуге, өңдеуге, арналған математикалық аппарат.

Логика алгебрасының негізін ХIХ ғасырда ағылшын математигі Джордж Буль қалаған. Оның құрметіне бұл алгебра тұжырымдардың бульдік алгебрасы деп аталған.

Логика алгебрасының негізгі ұғымдары:

1) Логикалық тұжырым- бір нәрсені растайтын немесе терістейтін хабарлы сөйлем.

Түрлері: 1)жалпы;

2) жекелей;

Жалпы тұжырым- барлығы, әрбіреуі, ешбіреуі деген сөздереден басталады.

Жеке тұжырым- кейбір, көпшілік деген сөздерден басталады.

Мысалы: Барлық балықтар –жалпы тұжырым;

Кейбір студенттер-жеке тұжырым.

2) Логикалық шамалар- ақиқат, жалған сөздерімен анықталатын сөздер.

Мысалы: Бүгін күн жылы- жалған

3) Логикалық операциялар –

а) Конъюнкция (логикалық көбейту немесе «және » деген сөз сәйкес келеді, орысша «и», ағылшынша «and», , -белгілері).

Мысалы: Бүгін күн жылы & студенттер сабақта отыр.

б)Дизъюнкция - (логикалық қосу, немесе, или, or, V белгісі).

Мысалы:Бүгін күн жылы V студенттер сабақта отыр.

с) Терістеу- (емес, not, ¬ ) - сөйлемдерді теріске шығару.

Мысалы: Бүгін күн жылы емес

4) Логикалық формула.

A= Бүгін күн жылы .

В = Студенттер сабақта. → А & В → А V В

5) Логикалық тұрақты немесе логикалық мән: ақиқат (true), жалған (false).

6) Логикалық айнымалы- мәні өзгеріп отыратын шама.

Компьютердің логикалық элементі – қарапайым логикалық функцияны жүзеге асыратын электрондық логикалық схеманың бір бөлігі.

Компьютердің логикалық элементтеріне ЖӘНЕ, НЕМЕСЕ, ЕМЕС, ЖӘНЕ–ЕМЕС, НЕМЕСЕ– ЕМЕС электрондық схемалары, вентильдер, триггер жатады. Вентильдердің кіріс саны сегізге дейін, ал шығыс саны 1 немесе екі болады.

Вентильде сигнал бар болса «1», жок болса «0» деп белгіленеді. Жоғары деңгей «ақиқат» (1), төменгі деңгей «жалған» (0) қалыптарын көрсетеді. Мысалы, кернеу деңгейі +5 вольт және 0 вольт

Әрбір логикалық элементтің шартты белгілені бар.

Ақиқаттық кестелерді құру және мәнін анықтау

Ақиқаттық кесте дегеніміз логикалық схеманың (формуланы) кірістегі сигналдарының барлық мүмкін мәндері мен оларға сәйкес шығыс сигналдарының мәндерін кесте түрінде бейнелеу. Шығыс сигналдарының мәндерін төмендегі кесте бойынша анықталады.

Логикалық мәндер		А және В	А немесе В	А емес	A XOR B
А	В
Ақиқат (1)	Ақиқат (1)	1	1	0	0
Ақиқат 1)	Жалған 0)	0	1	0	1
Жалған 0)	Ақиқат 1)	0	1	1	1
Жалған 0)	Жалған 0)	0	0	1	0

1- Мысал.

Берілген тұжырымдар: А=”Бүгін күн жылы”; В=”Екі мен бес тең”; С=”10 жұп сан”; D=”100 3-ке бүтіндей бөлінбейді” бойынша логикалық формулалардың ақиқаттық кестесін толтыру.

1) A&BVC&D; 2) B+C) &D+A; 3) ;4) CBVAD; 5)

A	B	C	D	A&B	C&D	A&BVC&D
1	0	1	1	0	1	1

1)

2)

A	B	C	D	B+C	B+C) &D	B+C) &D+A
1	0	1	1	1	1	1

2-Мысал: Берік, Саят, Маржан қытай, жапон, араб тілдерін оқиды. Кім қай тілді оқиды деген сұраққа мынадай жауап берілді: «Берік қытай тілін оқиды, Саят қытай тілін оқымайды, ал Маржан араб тілін оқымайды». Жауаптың біреуі ғана ақиқат, ал қалған екеуі жалған. Кім қай тілді оқиды?

Шешуі: Егер 1 тұжырым ақиқат болса, онда: 2 және 3 –жалған, яғни Берік пен Саят қытай тілін оқиды. Бұл дұрыс емес.

Егер 2 тұжырым ақиқат болса, онда: 2 және 3 –жалған, онда қытай тілін ешкім оқымайды. Бұл дұрыс емес.

Егер 3 тұжырым ақиқат болса, онда: 1 және 2 –жалған, яғни, Берік-ағылшын, Саят-қытай, Маржан-жапон тілдерін оқиды.

3-мысал: Формуланың ақиқаттық кестесін құру.

	A	B	C	D
1	0	0	0	0	1	0	0
2	0	0	0	1	1	0	0
3	0	0	1	0	1	1	0
4	0	0	1	1	1	1	1
5	0	1	0	0	0	0	0
6	0	1	0	1	0	0	0
7	0	1	1	0	0	0	0
8	0	1	1	1	0	0	0
9	1	0	0	0	0	0	0
10	1	0	0	1	0	0	0
11	1	0	1	0	0	0	0
12	1	0	1	1	0	0	0
13	1	1	0	0	0	0	0
14	1	1	0	1	0	0	0
15	1	1	1	0	0	0	0
16	1	1	1	1	0	0	0

Компьютердің логикалық элементтерінің белгіленуі

ЖӘНЕ	НЕМЕСЕ		ЕМЕС
ЖӘНЕ–ЕМЕС		НЕМЕСЕ– ЕМЕС

3 мысал: Логикалық формулаға сәйкес логикалық схема салу

Логикалық операция дизъюнкции «НЕМЕСЕ» сұлбасы арқылы таратылады, сигнал 1 шығыста болады егер кем дегенде сигнал 1 кірісте болса.

Инвентор терістеу функциясын орындайды, оның шығыс белгісі әр қашан кіріс белгісіне қарама-қарсы болады.

Негізгі сақтау элементі триггер. Триггер ұзақ мерзімде тұрақты жағдайлардың бірінде тұра алады, ол тұрақты жағдайларды бірлік және нөлдік деп атайды. Триггер –қиын логикалық сұлбалардың негізгі элементі, мысалы регистірлер, счетчиктер және т.б.

Қиын логикалық элементтер – регистірлер, счетчиктер, дешифраторлар- негізгі логикалық элементтердің базында құрылады.

Регистр белгілі қызметтерді атқаратын және келісіп жұмыс істейтін триггерлер тобын көрсетеді. Регистрлер есте сақталатын және қозғалмалы болады. Есте сақталатын регистр бір сөзді сақтауға арналған. Сөздегі разрядтар саны регистрлердің триггерлер санын анықтайды. Қозғалмалы регистр параллельды сан реттегі кодының жаңартуы үшін және де берілген разрядтар санына регистірдегі сан кодын қозғалту үшін қолданылады. Мысалы, арифметика-логикалық құрылғыларды регистірлер операнттарды алу және сақтау үшін қолданылады, ал орталықтандырылған басқару құрылғысында командалар регистрі ретінде қолданылады.

Дешифратор шығыс шиналардың бірінде кіріс және шығыс белгілерінің кодының жаңартылуын жүзеге асырады. Әр кіріс белгісінің комбинациясына бір шығыс сигналы сәйкес келеді. Дешифратор команда да операция кодын табу үшін және сәйкес басқару белгісін шығаруға арналған.

4-Мысал: Берік, Саят, Маржан қытай, жапон, араб тілдерін оқиды. Кім қай тілді оқиды деген сұраққа мынадай жауап берілді: «Берік қытай тілін оқиды, Саят қытай тілін оқымайды, ал Маржан араб тілін оқымайды». Жауаптың біреуі ғана ақиқат, ал қалған екеуі жалған. Кім қай тілді оқиды?

Шешуі: Егер 1 тұжырым ақиқат болса, онда: 2 және 3 –жалған, яғни Берік пен Саят қытай тілін оқиды. Бұл дұрыс емес.

Егер 2 тұжырым ақиқат болса, онда: 2 және 3 –жалған, онда қытай тілін ешкім оқымайды. Бұл дұрыс емес.

Егер 3 тұжырым ақиқат болса, онда: 1 және 2 –жалған, яғни, Берік-ағылшын, Саят-қытай, Маржан-жапон тілдерін оқиды. Жауабы осы болады.

Тапсырма: Ақиқаттық кесте және схема құру. CBVAD;