“O’zbekiston temir yo’llari” daтk toshkent temir yo’l muhandislari instituti

bet	3/6
Sana	03.12.2020
Hajmi	1.78 Mb.
	#157639

1 2 3 4 5 6

Bog'liq
Diskret matematika

Ta’rif: Mulohazaning inkor etulishi deb shunday mulohazani

aytiladiki u ilk mulohazayolg’on bo’lganida rost bo’ladi.

Mulohazaning inkor etulishi

bilan belgilanadi va “a emas ”deb

o’qiladi.

Ta’rif: Ikkita mulohazaning kon’yunksiyasi

deb ilk mulohazalar rost bo’lgandagina rost bo’ladigan

mulohazani aytiladi. Kon’yunksiya

yoki a

⋅b

bilan

belgilanadi va “

” deb o’qiladi.

a

а

0 1

1 0

a b a b

0 0

0

0 1

1 0

1 1

a b a b

0 0

0

0 1

Ta’rif: Ikkita mulohazaning diz’yunksiyasi deb ilk

mulohazalarlardan biri rost bo’lgandagina rost bo’ladigan mulohazani

aytiladi. Diz’yunksiy "

bilan belgilanadi va “

yoki

” deb o’qiladi.

Ta’rif: Ikkita mulohazaning implikatsiyasi deb ilk mulohazalarlardan

birinchisi rost bo’lgandagina rost va ikkinchisi yolg’on bo’ladigan

mulohazani aytiladi. Diz’yunksiy "

bilan belgilanadi va “agar

bo’lsa ,u holda

” deb o’qiladi.

Ta’rif:

Ikkita

mulohazaning

ekvivalentligi

deb

ilk

mulohazalarlardan ikkalasi rost yoki ikkalasi yolg’on

bo’lgandagina rost bo’ladigan vf qolgan hollarda yolg’on

mulohazani aytiladi. Ekvivalentlik "

bilan belgilanadi

va “

ekvivalent

” deb o’qiladi.

Barcha yuqorida aytilganlarni bir jadvalga keltiramiz va

qo’shimca yana uchta amalni qaraymiz .Bu amallar ikki moduli bo’yicha

qo’shish,Sheffer shtrixi va Pirs strelkasi deyiladi.

Mantiqi

amalnin

belgilan

ishi.

Mantiqiy

amalning

boshqabel

gilanishi.

Mantiqiy

amalning

qiymatlari.

Mantiqiy

amalning nomi.

Mantiqiy amalning

o’qilishi.

Inkor etish

a emas

a b

min(a; b)

0001

kon’yunksiya

a va b

a b

a+b

max(a; b)

0111

diz’yunksiya

а yoli b

a b

1101

implikatsiya

Agar а bo’lsa, u

holda b;

a dan b kelib

chiqadi

a b

1001

ekvivalentlik

а ekvivalent b

a b

a+ b

a b

0110

ikki

moduli

bo’yicha qo’shish

а plyus b;

yoki а, yoki b

a b

1110

antikon’yunksiya,

а Sheffer shtrixi b

1 0

1

1 1

a b a b

0 0

1

0 1

1 0

1 1

Sheffer shtrixi

a b

1000

Pirs

strelkasi,

antidiz’yunksiya

а Pirs strelkasi b

3.2. Mulohazalar algebrasining formulalari.

Ta’rif:Bo’sh bo’lmagan to’plam alfavit deyiladi.Uning elementlari

simvol deyiladi.Bu alfavitdagi simvollar ketma ketligi so’z deyiladi.

Mulohazalar algebrasining alfavitida quyidagi simvollar mavjud:

mulohazaviy o’zgaruvchilar; mantiqiy simvollar;qavslar simvollari.

Ta’rif: Mulohazalar algebrasidagi so’z quyidagi shrtlarni qanoatlantirsa u

formula deyiladi:

1)har qanday mulohazaviy o’zgaruvchi -formula;

2)agarА va В formula bo’lsa, , А В, А В, А

В, А В, А В, А

В, А В ham-formula;

3)faqat 1) va 2) shartlarni qanoatlantiruvchi so’zlar –formula.

Ta’rif: Formulaning formula bo’lgan har qanday qismi uning

formulaosti deyiladi.

Mulohazalar algebrasidagi dadi har bir formulaga rostlik jadvali tuzish

mumkin.

Ta’rif: Agar o’zgaruvchilarning qiymatlari vektorlarining birortasida

formulaning qiymati 1(0)bo’lsa u bajariladigan(inkor etiladigan)formula

deyiladi.

Ta’rif: Agar o’zgaruvchilarning qiymatlari vektorlarining barchasida

formulaning qiymati 1(0)bo’lsa u tavtologiya(aynan yolg’on)formula

deyiladi.

3.3. Mulohazalar algebrasining formulalarini teng kuchliligi.

Ta’rif: Agar A va B formulalar bir xil o’zgaruvchilarga bog’liq bo’lsa va

ularning qiymatlarining barcha vektorlarida bir xil qiymat qabul qilsa bu

formulalar teng kuchli deyiladi va A=B bilan ifodalanadi.

Teorema. Aytaylik А, В, С-mantiqiy amallarning quyidagi xossalari

o’rinli:

1. Idempotentlik

А А = А

2. Kommutativlik

А В = В А

3. Assosiativlik

А (В С) = (А В) С

4. Yutilish qoidalari

А (А В) = А

5. Distributivlik

А (В С) = (А В) (А С)

6. De Morgan qoidalari

В

А

В

А

А

В

А

7. O’zgarmaslarning xossalari

А 1 = А

А 0 = 0

А 0 = А

А 1 = 1

8. Uchinchisini inkor etish qonuni

0

А

А

А

9. Ikkilangan inkor etish qonuni

А

А

10. Parchalanish f0rmulalari

А

В

А

В

А

В

А

В

А

11. Implikatsiyadan qutilish

А

В

В

А

В

А

В

А

12. Ekvivalentlikdan qutilish

В

А

В

А

А

В

В

А

В

А

Bu teng kuchliliklarning barchasi rostlik jadvali yordamida isbotlanishi

mumrin.Shuni aytish kerakki ba’zan rostlik jadvalini tuzishdan ko’ra teng

kuchlilikni yuqodagi formulalardan foydalanib isbotlash ma’qul.

3.4. Normal shakllar

Ta’rif: O’zgaruvchilar va ularning rad etilishining kon’yunksiyalari

elementar kon’yunksiya deyiladi.

Bunda elementlar takrorlanishiga yo’l qo’yiladi.

Ta’rif: O’zaro juft jifti bilan farq qiluvchi elementar kon’yunksiyalarning

diz’yunksiyasi diz’yunktiv normal shakl(DNSh) deyiladi.

DNShda elementlar takrorlanishi mumkin.

Ta’rif: O’zgaruvchilar va ularning rad etilishining diz’yunksiyalari

elementar diz’yunksiya deyiladi.

Bunda elementlar takrorlanishiga yo’l qo’yiladi.

Ta’rif: O’zaro juft jifti bilan farq qiluvchi elementar diz’yunksiyaning

kon’yunksiyasi kon’yunktiv normal shakl(KNSh) deyiladi.

KNShda elementlar takrorlanishi mumkin.

3.5.Mukammal normal shakllar

Ta’rif: Mukammal diz’yunktiv normal shakl (MDNSh) deb quyidagi

shartlarni qanoatlantiradigan diz’yunktiv normal shaklni aytiladi:

1. diz’yunksiyning barcha hadlari har xil;

2. har bir kon’yunksiyning barcha hadlari har xil;

3.birorta ham kon’yunksiyda o’zgaruvchi va uning rad etilishi

qatnashmaydi;

har

bir

kon’yunksiy

formulada

ishtirok etgan barcha

o’zgaruvchilardan tuzilgan, yani formula ushbu ko’rinishda

n

n

c

n

c

c

c

F

n

x

x

x

x

x

F

...

...,

bunda diz’yunksiy F(c)=1 bo’lgan 0 va1dan iborat barcha с=(с

, с

, …, с

)

vektorlar bo’yicha tuzilgan.

Teorema. (MDNSh haqida). Mulohazalar algebrasining aynan nol

bo’lmagan barcha F(x

, x

, …, x

) formulalari uchun xuddi shu

ro’yxatdagi o’zgaruvchilardan tuzilgan va bu ro’yxatga nisbatan

MDNShda bo’lgan F formulaga teng kuchli F

formula mavjud. F

formula

diz’yunktiv hadlari o’rni almashishi aniqligida yagonadir.

Ta’rif: Mukammal kon’yunktiv normal shakl (MKNSh) deb quyidagi

shartlarni qanoatlantiradigan kon’yunktiv normal shaklni aytiladi :

1. kon’yunksiyning barcha hadlari har xil;

2. har bir diz’yunksiyning barcha hadlari har xil;

3.birorta ham diz’yunksiyda o’zgaruvchi va uning rad etilishi

qatnashmaydi;

4. har bir diz’yunksiy formulada ishtirok etgan barcha o’zgaruvchilardan

tuzilgan, yani formula ushbu ko’rinishda

1

1

, ...,

(

...

)

n

n

c

с

n

n

F c

c

F x x

x

x

x

bunda kon’yunksiya F(c)=0 bo’lgan 0 va1dan iborat barcha с=(с

, с

, …,

) vektorlar bo’yicha tuzilgan.

Teorema. (MKNSh haqida). Mulohazalar algebrasining aynan bir

bo’lmagan barcha F(x

, x

, …, x

) formulalari uchun xuddi shu

ro’yxatdagi o’zgaruvchilardan tuzilgan va bu ro’yxatga nisbatan

MKNShda bo’lgan F formulaga teng kuchli F

formula mavjud. F

formula

kon’yunktiv hadlari o’rni almashishi aniqligida yagonadir.

Quyida mukammal normal shakllarga keltirishning ikki usulini keltiramiz.

1- analitik usul.

MDNShga keltirish algoritmi.

1.Formulani teng kuchli almashtirishlar yordamida DNShga keltirish.

2. Diz’yunksiyaning bir xil o’zgaruvchi va uning rad etilishi qatnashgan

hadlarini tashlab yuborish.

3. Diz’yunksiyaning bir xil hadlaridan bittasini qoldirish.

4. Kon’yunksiyaning bir xil hadlaridan bittasini qoldirish.

5. Agar birorta kon’yunksiyada o’zgaruvchilar ro’yxatidagi birorta x

qatnashmagan bo’lsa bu kon’yunksiyaga

i

i

x

x

formulani qo’sib

kon’yunksiyaning distributivlik qonunini qo’llash.

6.Agar hosil bo’lgan diz’yunksiyada bir xil hadlar bo’lsa 3- bosqichni

qo’llash.

Hosil bo’lgan formula berilgan formulaning mukammal diz’yunktiv

shakli bo’ladi.

Misol. Quyidagi formulalarni teng kuchli almashtirish bilan

MDNShga keltiring:1.

y

x

y

x

;2.

z

y

x

;3.

xy

y

x

Yechish.

1.

y

x

xy

y

y

x

x

y

x

y

x

|

xyz

z

y

x

z

y

x

y

xz

xzy

z

y

x

z

y

x

y

y

xz

z

z

y

x

xz

y

x

z

y

x

.

xy

yxy

xy

x

xy

y

x

xy

y

x

MKNShga keltirish algoritmi.

1.Formulani teng kuchli almashtirishlar yordamida KNShga keltirish.

2. Kon’yunksiyaning bir xil o’zgaruvchi va uning rad etilishi qatnashgan

hadlarini tashlab yuborish.

3. Kon’yunksiyaning bir xil hadlaridan bittasini qoldirish.

4. Diz’yunksiyaning bir xil hadlaridan bittasini qoldirish.

5. Agar birorta diz’yunksiyada o’zgaruvchilar ro’yxatidagi birorta x

qatnashmagan bo’lsa bu kon’yunksiyaga

i

i

x

x

formulani qo’sib

diz’yunksiyaning distributivlik qonunini qo’llash.

6.Agar hosil bo’lgan kon’yunksiyada bir xil hadlar bo’lsa 3- bosqichni

qo’llash.

Hosil bo’lgan formula berilgan formulaning mukammal kon’yunktiv

shakli bo’ladi.

Misol. Quyidagi formulalarni teng kuchli almashtirish bilan MDNShga

keltiring:1.

z

y

x

;2.

xy

y

x

Yechish.

.

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

x

x

z

y

z

z

y

y

x

z

y

x

.

y

x

y

x

y

x

x

y

x

y

y

x

y

x

y

x

x

x

y

y

y

x

y

x

xy

y

x

xy

y

x

2-jadval usuli. MDNShga keltirish.

Formulaning rostlik jadvalini tuzaviz. Uning faqat qiymatlari 1 bo’lgan

satrlarni qaraymiz. Har bir bunday satrga o’zgaruvchilarning

kon’yunksiyasi mos keladi. Bu kon’yunksiyada qiymati 0 bo’lgan

o’zgaruvch rad etilgan holda, qiymati 1 bo’lgani esa o’zi qatnashadi. Oxiri

hosil bo’lgankon/yunksiyalarning diz’yunksiyasini tuzamiz.

Misol.Berilgan formulalarning MDNShni yozing:

1.

z

y

x

F

.2.

.

xy

y

x

F

Yechish.

1.

z

y

x

F

F formulaning rostlik jadvalini tuzamiz:

№ x y z

y

y

x

F

0 0 0 0 1

1 0 0 1 1

2 0 1 0 0

3 0 1 1 0

4 1 0 0 1

5 1 0 1 1

6 1 1 0 0

7 1 1 1 0

Faqat 4, 5 va 7 satrlarda o’zgaruvchilarning qiymatlarini qaraymiz. Bu

qiymatlarda formulaning qiymati 1. Shu sababli uning uchun MDNSh:

.

xyz

z

y

x

z

y

x

F

.

xy

y

x

F

F formulaning rostlik jadvalini tuzamiz:

№ x y x y F=(x y) x y

0 0 0

1 0 1

2 1 0

3 1 1

MDNSh (1): F = x

⋀y.

MKNShga keltirish algoritmi.

Formulaning rostlik jadvalini tuzaviz. Uning faqat qiymatlari 0 bo’lgan

satrlarni qaraymiz. Har bir bunday satrga o’zgaruvchilarning

diz’yunksiyasi mos keladi. Bu diz’yunksiyada qiymati 1 bo’lgan

o’zgaruvch rad etilgan holda, qiymati 0 bo’lgani esa o’zi qatnashadi. Oxiri

hosil bo’lgan dizyunksiyalarning kon’yunksiyasini tuzamiz.

Misol.Berilgan formulalarning MKNShni yozing:1.

z

y

x

F

.

xy

y

x

F

Yechish.

F formulaning rostlik jadvalini tuzamiz:

№ x y z

z

y

x

F

0 0 0 0

1 0 0 1

2 0 1 0

3 0 1 1

4 1 0 0

5 1 0 1

6 1 1 0

7 1 1 1

Faqat 0,1,2,3 va 6 satrlarda o’zgaruvchilarning qiymatlarini qaraymiz. Bu

qiymatlarda formulaning qiymati 0. Shu sababli uning uchun MKNSh

.

z

y

x

z

y

x

z

y

x

z

y

x

z

y

x

F

F formulaning rostlik jadvalini tuzamiz:

№ x y F=(x y) x y

0 0 0

1 0 1

2 1 0

3 1 1

MKNSh (1):0, 1, 2:

.

y

x

y

x

y

x

F

3.6. Bull funksiyalari.

Ta’rif:Agar n- o’zgaruvchili f(x

, x

, …, x

) funksiyaning barcha

argumtntlari {0, 1} to’plamdan qiymat qabul qilsa va funksiya ham shu

qiymatlarni qabul qilsa u Bull funksiyasi deyiladi.

Har qanday Bull funksiyasini 2

satrdan iborat jadval bilan berish

mumkin.Bunda har bir satrda o’zgaruvchilar qiymatlarining vektori

tuziladi va unga 0 yoki 1 qiymat mos keltiriladi.

Misol.Aytaylik uch o’zgaruvchili Bull funksiyasi berilgan bo’lsin. U

holda

o’zgaruvchilarning

qiymatlaridan

tuzilgan vektorlar soni

2

3

bo'ladi.

№ набора х

0 0

1 0

0 1

1 0

0 1

1 1

0 0

1 1

Bunda vektorlarning nomeri noldan boshlanadi va har bir vektor o’z

nomerining ikki asosga ko’ra kodini bildiradi. Jadvalning birinchi to’rtta

ustuni har qanday uch o’zgaruvchilh Bull funksiyasi uchun bir xil bo’ladi.

Funksiyaning qiymatlari ustuni esa beriladi yoki hisoblanadi. Xuddi shu

funksiyani ushbu ko’rinishda yozish mumkin: f(х

, х

)=00101101.

Barcha n-o’zgaruvchili Bull funksiyalari

n

xildir.O’zgarmaslar 0 va 1

nol o’rinli Bull funksiyasi deb hisoblanadi.

Download 1.78 Mb.

Do'stlaringiz bilan baham:

1 2 3 4 5 6