Diskret tuzilmalar” fani

A
¬
0		1
1	0

Ta`rif 2. A va B mulohazalarning kon’yunktsiyasi deb, A va B mulohazalar bir vaqtda rost bo`lgandagina rost bo`lib, qolgan barcha hollarda yolg`on qiymat qabul qiluvchi mulohazaga aytiladi.
A va B mulohazalarning kon‟yunktsiyasi A&B yoki A/\B kabi belgilanadi hamda “va” deb o`qiladi. A mulohaza kon‟yunktsiyaning birinchi hadi, B mulohaza esa ikkinchi hadi deyiladi. Kon‟yunktsiya amali xuddi 0 va 1 sonlarini ko`paytirishga o`xshagani uchun ham uni ko`pincha mantiqiy ko`paytirish deb
ham atashadi.
Kon‟yunktsiya amalining rostlik jadvali quyidagicha:

A	B	A&B
0	0	0
0	1	0
1	0	0
1	1	1

Ta`rif 3. A va B mulohazalarning diz’yunktsiyasi deb, A va B mulohazalardan kamida bittasi rost bo`lganda rost bo`lib, qolgan hollarda yolg`on qiymat qabul qiluvchi mulohazaga aytiladi.
A va B mulohazalarning kon‟yunktsiyasi A\/B kabi belgilanadi hamda
“yoki” deb o`qiladi. A mulohaza diz‟yunktsiyaning birinchi hadi, B esa ikkinchi hadi deyiladi. Diz‟yunktsiya amalining rostlik jadvali quyidagicha:

A	B	A/\B
0	0	0
0	1	1
1	0	1
1	1	1

Ta`rif 5. A va B mulohazalarning implikatsiyasi deb, A mulohaza rost bo`lib, B yolg`on bo`lgandagina yolg`on, qolgan barcha hollarda rost qiymat qabul
qiluvchi mulohazaga aytiladi.
A va B mulohazalarning implikatsiyasi A→B kabi belgilanadi va “A dan B kelib chiqadi” yoki “Agar A o`rinli bo`lsa, B o`rinli bo`ladi” deb o`qiladi. A mulohaza implikatsiyaning birinchi hadi, B esa ikkinchi hadi hisoblanadi.
Implikatsiya amali uchun rostlik jadvali quyidagicha:

A		B	A→B
0	0		1
0	1		1
1	0		0
1	1		1

Misol. A : “Bugun yomg`ir yog`di” va B: “Men soyabon oldim” mulohazalar bo`lsin. Agar yomg`irda ho`l bo`lganimizni 0, quruq bo`lganimizni 1 qiymatlar bilan belgilasak, implikatsiyani shunday tushuntirish mumkin.

A	B	A→B
Bugun yomg`ir yog`madi	Menda soyabon yo`q	1 (quruq
Bugun yomg`ir yog`madi	Men soyabon oldim	1 (quruq)
Bugun yomg`ir yog`di	Menda soyabon yo`q	0 (ho`l)
Bugun yomg`ir yog`di	Men soyabon oldim	1 (quruq)

Ta`rif 6. A va B mulohazalarning ekvivalentligi deb, A va B mulohazalarning bir xil qiymatlarida rost bo`lib, har xil qiymatlarida esa yolg`on bo`luvchi mulohazaga aytiladi.

1. 
   va B mulohazalarning ekvivalentligi A~B, A↔B kabi belgilanadi va “A va B teng kuchli”, “A bo`ladi, qachonki B bo`lsa” yoki “A mulohaza
   
2. 
   uchun yetarli va zarur” deb o`qiladi. A mulohaza ekvivalentlikning birinchi hadi, B esa ikkinchi hadi hisoblanadi.
   

Ekvivalentlik amali uchun rostlik jadvali quyidagicha:

A	B	A~B
0	0	1
0	1	0
1	0	0
1	1	1

Halqali yig‘indi amali AB.
Bu amal ekvivalentlik amalining inkoriga teng bo‟ladi, ya‟ni
AB = (AB)
Halqali yig„indi amali uchun rostlik jadvali quyidagicha:

A	B	B
0	0
0	1
1	0
1	1

A
0
1
1
0
Sheffer shtrixi AB.
Ushbu amalni kon`yunktsiya va diz`yunktsiya amallari yordamida hosil qilish mumkin, ya‟ni
AB= (AB)= AB
Sheffer shtrixi amali uchun rostlik jadvali quyidagicha:

A	B	AB
0	0	1
0	1	1
1	0	1
1	1	0

Sheffer shtrixi amali uchun quyidagi xossalar o‟rinli:
10 . AB = AB = (AA)(BB)
20 . A&B = (AB) = (AB)(AB)
30 . A = AA
Pirs strelkasi AB.
Ushbu amalni ham kon`yunktsiya va diz`yunktsiya amallari yordamida hosil qilish mumkin, ya‟ni AB= (AB)= A&B
Pirs strelkasi amali uchun rostlik jadvali quyidagicha:

A	B	AB
0	0	1
0	1	0
1	0	0
1	1	0

Pirs strelkasi amali uchun quyidagi xossalar o‟rinli:
10 . AB = (AB) = (AB)  (AB)
20 . A&B = AB = (AA)  (BB)
30 . A = AA
{0; 1; ¬; &; \/} - to‟plamga mulohazalar algebrasi yoki Bul
algebrasi deyiladi. Argumenti va funksiya qiymati 0 yoki 1 qiymatini qabul
qiluvchi n ta o‟zgaruvchi x₁,x₂,...,x_n ga bog‟liq bo‟lgan har qanday y = f (x₁,x₂,...,x_n ) funksiyaga Bul funksiya deyiladi.
1.misol: A V B  C Rostlik jadvalini tuzing.
Yechish. Ushbu misolda birinchi bo‟lib qaysi mantiqiy amal bajarilishi kerakligini topib olamiz so‟ngra rostlik jdvalini tuzamiz. 1 - B  C ,
2 - A V B  C amallarni bajaramiz.

A	B	C	C	B 	A V B  C
0	0	0		0	1
0	0	1		1	1
0	1	0		1	1
0	1	1		0	0
1	0	0		0	1
1	0	1		1	1
1	1	0		1	1
1	1	1		0	1

2. misol: A  B  C Rostlik jadvalini tuzing.
Yechish. Ushbu misolda birinchi bo‟lib qaysi mantiqiy amal bajarilishi kerakligini topib olamiz so‟ngra rostlik jdvalini tuzamiz. 1 - B  C,

2. 
   - A  B  C
   

A	B	C	B  C	A  B  C
0	0	0	1	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	0	0

2. 
   – misol: A&B \/ A  C misolning rangini toping.
   

Yechish. Rangini toppish uchun nechta mantiqiy amal borligini sanab olamiz.
Javob: misolning rangi 3 ga teng.

2. 
   – misol: AB V CB→D formula osti formulalarini toping.
   

Yechish: Misolni yechish uchun ( AB ), (AB V C),( AB V C V B),  ( AB V C V B),
( AB V C V B) →D kabi yozish kerak. Bu misolning 5 ta formula osti formulalari bor ekan.

2-Vazifa: Bul algebrasi
Quyidagi mantiq algebrasi funksiyalari uchun rostlik jadvallarini tuzing:

Variant raqami	Topshiriqlar
1-variant	F(A,B,C)= AB(AC)

A	B	C	A	AB	AC	(AC)	AB(AC)
1	1	0	0	0	1	0	0
1	1	1	0	0	1	0	0
1	0	0	0	0	1	0	0
1	0	1	0	0	1	0	0
0	1	0	1	1	0	1	1
0	1	1	1	1	1	0	1
0	0	0	1	0	0	1	1
0	0	1	1	0	1	0	0