Buxoro davlat universiteti fizika-matematika fakulteti "matematika" kafedrasi

2- teorema: Mulohazalar algebrasining aynan rost bo’lmagan har

qanday

F( A₁ , A₂,..,A_n )

formulasi yagona MKNSH ga teng kuchlidir.

1. 
   natija: Teng kuchli formulalar bir xil MKNSH ga ega bo’ladi.
   

2. 
   natija: Tarkibida n ta har xil o’zgaruvchilar qatnashgan formula aynan yolg’on bo’lishi uchun uning MKNSH si 2ⁿ ta har xil to’liq elementar dizyunksiyalarning konyunksiyasidan iborat bo’lishi zarur va yetarlidir.
   

3. 
   natija: Mulohazalar algebrasining har qanday formulasining inkori shu formula MKNSH siga kirmagan to’liq elementar dizyunksiyalarning va faqat shularning konyunksiyasidan iborat bo’ladi.
   

Yuqorida keltirilgan teoremalar va ularning natijalari yordamida mulohazalar algebrasining har qanday formulasini aynan rost, aynan yolg’on yoki bajariluvchi formula bo’lishini rostlik jadvalidan foydalanmay aniqlash mumkin. Shuningdek, berilgan qiymatlar to’plamiga ko’ra mulohazalar algebrasining formulasini tuzish mumkin.

Umuman, mulohazalar algebrasining ko’pgina masalalarini mukammal normal formalar yordamida oson hal qilish mumkin.

Misol 1.	A&B\/⌐A&B\/A&⌐B						– MDNSh;
	(⌐A1\/A2\/A3 )&(A1\/⌐A2\/⌐A3) – MKNSh bo‘ladi.
Misol 2.	 A&B		CB&			formulani DNSh ga keltiramiz.
		C		A

0. 
    A&BC C  A&B A BC C  A&B A BC&C  A&B
   

1. 
   A BC&C  A&B A&C B&C C&C  A&A&BB&A&B
   
   1. 
      C&A&B A&B&C&C&AB AC BC C AB0A
      

23. 
    ABC ABC&A B AC  BC  AB ABCC ABC 
    

2. 
   CAB  AB1 AB ABC СBA AACC  ABBC 
   



 B 

BB

– MDNSH.

Mustaqil yechish uchun masalalar:

Quyidagi formulalarni MDNSh va MKNShga keltiring:

0. 
   α(x,y,z)=(xyz)→xz
   

0. 
   α(x,y,z)=(xy)→(zyx)
   

0. 
   α(x,y,z)=(x→y)(zx)
   

0. 
   α(x,y,z)=(xy)(zy)
   

0. 
   α(x,y,z)=((xy)z)→x((yz)(xz)
   

0. 
   α(x,y,z)=(x&yy)&(x→z)
   

0. 
   α(x,y,z)=(xz yxyz)xy
   

0. 
   α(x,y,z)=(x→z)&(y→x)
   

0. 
   α(x,y,z)=((xy)z)x)y
   

0. 
   α(x,y,z)=(((xy)z)y)&(y→z)
   

0. 
   α(x,y,z)=((xy)(yz))(x(y→z))
   

0. 
   α(x,y,z)=(xy→z)((xy)z)
   

0. 
   α(x,y,z)=(xy)(xxyyz(xyz))
   

Quyidagi rostlik jadvali berilgan mantiq funksiyalarining formulasini tiklang:

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

XULOSA

Ushbu kurs ishida mukammal dizyuntiv va mukammal konyunktiv formalar haqida bir qancha ta’riflar, teoremalar va bir nechta natijalar keltirilgan.

Agar dizyunktiv normal shakl ifodasida har bir elementar konyunktiv had to’g’ri va to’liq bo’lsa, u mukammal dizyunktiv normal shakl(MDNSH) deyiladi.

Agar konyunktiv normal shakl ifodasida har bir elementar dizyunktiv had to’g’ri va to’liq bo’lsa, u mukammal konyunktiv normal (MKNSH) shakl deyiladi.

n ta elementar mulohazalarning aynan yolg’on formulasidan farqli har bir A formulani MDNSH ga keltirish mumkin.

n ta elementar mulohazalarning aynan chin formulasidan farqli har bir A formulani MKNSH ga keltirish mumkin.

Foydalanilgan adabiyotlar :

1. Mirziyoyev Sh . M. Erkin va farovon demokratik O’zbekiston davlatini birgalikda barpo etamiz . O’zbekiston Respublikasi Prezidenti lavozimiga kirishish tantanali marosimiga bag’ishlangan Oliy Majlis palatalarining qo’shma majlisidagi nutq , Toshkent , 2016 .

2. Mirziyoyev Sh . M . Buyuk kelajagimizni mard va olijanob xalqimiz bilan birga quramiz . Mazkur kitobdan O’zbekiston Respublikasi Prezidenti Shavkat Mirziyoyevning 2016 yil 1- noyabrdan 24 noyabrga qadar Qoraqalpog;iston Respublikasi , viloyatlar va Toshkent shahri saylovchilari vakillari bilan o’tkazilgan saylovoldi uchrashuvlarida so’zlagan nutqlari o’rin olgan . Toshkent , O’zbekiston , 2017 . 488- bet .

3 . Mirziyoyev Sh . M . Qonun ustuvorligi va inson manfaatlarini taminlash yurt taraqqiyoti va xalq farovonligining garovi . O’zbekiston Respublikasi Konstitutsiyasi qabul qilinganining 24 yilligiga bag’ishlangan tantanali marosimdagi ma’ruza . 2016 yil , 7- dekabr – Toshkent , O’zbekiston 2017, 48- bet.

4. 
   Ю.Л.Ершов, Е.А.Палютин. Математическая логика.Москва
   

«Наука»,1979.

4. 
   И.Я.Депман. Первое знакомство с математической логикой. Ленинград.
   

1963.

4. 
   В.Зегет. Элементарная логика. Москва. «Вўсшая школа». 1985.
   

4. 
   Э.Мендельсон. Введение в математическую логику. Москва Наука,1976.
   

8. Hotam To’rayev “ Matematik mantiq va diskret matematika “

Toshkent “ O’qituvchi “ -2003 .

9 . Kenneth H. Rosen Discrete mathematics and is applications , 7- edition , The Mc Graw – Hill Companies 2012 .Введение в математичискую Логину : М . Наука 1984

10. Мендельсон Е.Введение в математичискую Логину : М . Наука 1984.

11. Яблонский С .В . Введение в дискретнию математику - М . Наука 1986.

12. Y unusov A . S . - Matematik mantiq va algoritimlar nazariyasi elementlari . Toshkent 2008 .

13. Hotam To’rayev 2 jildli kitob “ Diskret matematika va matematik mantiq “ 2013 – yil .

14 . Зиков А. А . Основы теории графов . М . « Наука « , 1987.

15 . Новиков П . С . Элементы математической логики . М . Наука , 1973 .

Internet saytlari

16. www.lib.homelinex.org /math

17 . www.eknigu.com./lib/ Mathematics/

18 . www.ziyonet.uz
19. http://dimacs,Rutgers,edu/

20. http://www.math.uu.se/logic-server/

21 . http://book.uhost.ru./036413/