Formulalarning normal shakllari

FORMULALARNING NORMAL SHAKLLARI.
REJA.
1.Elementar kon`yunksiya.
2.Elementar diz`yunksiya.
3.Formulaning normal shakli.
4.Mukammal normal shakllar.

Teng kuchli almashtirishlar bajarib, mulohazalar algebrasining formulalarini har xil ko`rinishlarda yozish mumkin. Masalan, formulani ABC yoki (AB)(AC) ko`rinishlarda yozish mumkin.Mantiq algebrasining kontakt va rele-kontaktli sxemalar, diskret matematikaning texnikadagi tadbiqlarida va matematik mantiqning boshqa masalalarida formulalarning normal shakllari katta ahamiyatga ega.Quyidagicha belgilash kiritamiz:

x^ = x , agarda  = ch bo`lsa, ga teng agarda  = y obo`lsa.

1. 
   ta`rif.Ushbu
   

(1)
Ko`rinishdagi formula elementar kon`yuksiya deb ataladi, bu erda  = {₁, ₂,…., _n} ixtiyoriy qiymatlar satri va x_i o`zgaruvchilar orasida bir xillari bo`lishi mumkin.

2. 
   2- ta`rif. Ushbu
   

(1)
ko`rinishdagi formula elementar kon`yuksiya deb ataladi, bu erda  = {₁, ₂,…., _n} ixtiyoriy qiymatlar satri va x_i o`zgaruvchilar orasida bir xillari bo`lishi mumkin.

3. 
   Ushbu
   

(2)
ko`rinishdagi formula elementar diz`yuksiya deb ataladi, bu erda  = {₁, ₂,…., _n} ixtiyoriy qiymatlar satri va x_i o`zgaruvchilar orasida bir xillari bo`lishi mumkin.
3-ta`rif. Elementar diz`yunksiyalarning kon`yunksiyasi formulaning kon`yunktiv normal shakli (KNSH) va elementar kon`yunksiyalarning diz`yunksiyasi formulaning diz`yunktiv normal shakli (DNSH) deb ataladi.
KNSH ga formula va DNSH ga formula misol bo`la oladi.
1-teorema.Elementar mulohazalarning har bir P formulasiga teng kuchli kon`yunktiv normal shaldagi Q formula mavjud.
Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz:
(3)
Izoh. P formulani kon`yunktiv normal shaklga keltirish jarayonida quyidagi teng kuckliliklardan foydalanib, uni soddalashtirish mumkin:

2-teorema. P formula doimo chin bo`lishi uchin uning KNSH dagi har bir elementar diz`yunktiv hadida kamida bitta elementar mulohaza bilan birga bu mulohazaning inkori ham mavjud bo`lishi zarur va etarli.

Foydalanilgan adabiyotlar ro‘yhati
Asosiy adabiyotlar
1. G. P.Gavrilov, A. A.Sapojnikov. Zadachi i uprajneniya po diskretnoy matematike: Uchebnoye posobiye. M: FIZMATLIT, 2005, 416 s.
2. Kayzer G.Dj. Kombinatornaya matematika. M.. Mir, 1966
3. 3. Yemelichev V.A. i dr. Leksii po teorii grafov. M.. Nauka, 1990.
4. Mendelson E. Vvedeniye v matematicheskuyu logiku. M., Nauka, 1976.
5. Yoqubov T. Matematik logika elementlari. Toshkent, “O‘qituvchi”, 1983.


Qо‘shimcha adabiyotlar
6. To‘rayev H. Matematik mantiq va diskret matematika. Samarqand, 2003.
7. Gavrilov G.P. i dr. Sbornik zadach po diskretnoy matematiki. M.: Nauka, 1977.
8. Ore O. Teoriya grafov. Moskva, Nauka, 1968.
9. Igoshin V.I. Zadachnik-praktikum po matematicheskoy logike. M., Pros-iye, 1986.
10. Yevstigneyev V.A. Primeneniye teorii grafov v programmirovanii. M., Nauka, 1985.
11. Zikov A.A. Osnovi teorii grafov. M., Nauka, 1987.
12. Yershov Y.L. i dr. Matematicheskaya logika. M., Nauka, 1987.
13. Karri X. Osnovaniya matematicheskoy logiki. M., Mir, 1969.
14. Pospelov D.A. Logiko-lingvisticheskiye modeli v sistemax upravleniya. M., Energoizdat, 1981.