|
§3. Normal formalar. Jetilisken dizyunktiv ha’m konyunktiv
normal formalar
Normal formalar. Toli ’q elementar dizyunkciya ha’m konyunkciyalar. Dizyunktiv normal forma.DNF.Jetilisken
dizyunktiv normalforma.JDNF
Matematikali’q logikada ten’ ku’shli tu’rlendiriwler wori’nlap, ayti’mlar algebrasi’ni’n’ formulalari’n ha’r qi’yli’ ko’riniste jazi’w
mu’mkin. Ma’selen, A ^ BC formulani’ A v BC yamasa (A v B) л (A v C) ko’rinisleri’nde jaza alami’z.
Logika algebrasi’ni’n’ kontakt ha’m rele-kontaktli sxemalar, diskret texnikada qollani’wlari’nda ha’m matematikali’q logikani’n’ basqa ma’selelerinde formulalardi’n’ normal formalari’ u’lken a’hmiyetke iye. To’mendegi belgilewdi kiritemiz:
f yeger a = 1 bolsa, A,
Aa =\ _ (1)
[yeger a = 0 bolsa, A.
ani’qlama. A1,...., An propozicional wo’zgeriwshiler
a = (a1,a2,....,an) ha’m 0 lerden du’zilgenn nabor bolsa, wonda AaiAf....Af formula elementar konyunkciya delinedi (bunda
propozicional wo’zgeriwshiler ta’kirarlang’an boli’wi’ da mu’mkin).
Biz, bul paragrafda A л B formulani’ qi’sqasha AB ko’rnisinde jazami’z.
mi ’sal.
A, ABC, AAB, AABBC
formulalar elementar konyunkciyalardan ibarat.
ani’qlama. Elementar konyukciyalardi’n’ ha’r qanday
dizyunkciyasi’ dizyunktiv normal forma (DNF) delinedi.
mi ’sal.
AvABCvAABvAABBC
formula 3.1-mi’sali’nda keltirilgen elementar konyukciyalardan du’zilgen DNF boladi’.
ani’qlama. Yeger elementar konyukciyag’a ha’r bir propozicional wo’zgeriwshi (biykarlaw belgisi qatnasqanli’g’i’n da itibarg’a alsaq) bir
44
ma’rteden arti’q kirmegen bolsa, bunday elementar konyunkciya tuwri’ elementar konyukciya delinedi.
mi ’sal.
ABC, ABC, A1 A2 A3 A4
formulalar tuwri’ elementar konyukciyalar boladi’. Joqari’dag’i’ 3.2- mi’salda keltirilgen formulani’n’ da’slepki yeki ag’zasi’ tuwri’ elementar konyukciya boladi’.
ani’qlama. A1, A2,...., An propozicional wo’zgeriwshilerden
du’zilgen tuwri’ elementar konyukciyadag’i’ ha’r bir propozicional wo’zgeriwshi bul konyukciyag’a tek bir ma’rtebe kirgen bolsa, bunday elementar konyukciya A13....,An wo’zgeriwshilerine qarata toli’q elementar konyukciya delinedi.
mi’sal. Elementar konyunkciyalar A, B, C wo’zgeriwshilerden du’zilgen bolsi’n. Bul jag’dayda ABC,ABC, formulalar toli’q elementar konyunkciyalar boladi’.
ani’qlama. Qurami’nda bir qi’yli’ elementar konyukciyalar bolmag’an ha’m de barli’q elementar konyukciyalar A1,....,An
wo’zgeriwshilerine qarata tuwri’ ha’m toli’q bolg’an DNF A1,....,An
wo’zgeriwshilerine qarata jetilisken dizyunktiv normal forma (JDNF) delinedi.
mi ’sal.
ABCvABCvABC
formula A,B,C wo’zgeriwshilerine qarata JDNF boladi’.
Teorema-1. Ayti’mlar algebrasi’ni’n’ BJ formula bolmag’an qa’legen U formulasi’ birden-bir JDNF g’a ten’ ku’shli boladi’.
Da’lilleniwi. U(A1,A2,....,An) - ayti’mlar algebrasi’ni’n’ qa’legen
B
m(p) = а2),....,а!1)Х (a
,(2)
a
(2)
a» )
...., (afr), a
,( r) 2
ar%
J formula bolmag’an formulasi’ bolsi’n. Demek, U wori’nlani’wshi’ formula boli’p, wol propozicional wo’zgeriwshilerdin’ ma’nislerinin’ hesh bolmag’anda bir g’ana nabori’nda 1 ma’nisin qabi’l yetedi. U formulani rasqa aylandi’ri’wshi’ naborlar ko’pligi m{ ) bolsi’n:
bunda 1 < r < 2n boladi’. To’mendegi DNF ni’ qarayi’q:
B( A1,...., An о Af A2“21) .... Af V ....VAf1"’ A2“2'’ .... A^’ (2) Bul DNF ni’n’ a’dette JDNF yekenligi ani’q, sebebi m( ) ni’n’
elementleri ha’r qi’yli’ naborlardan ibarat. Sonda
U(A1,...., An) . B(A1,...., An)
yekenligin ko’rsetiwimiz kerek. Meyli
a =(a( *), a2 * ),....5 a *)) e m( p)
bolsi’n. Bul jag’dayda
a =(a( *), a2 * ),....5 a *)) e m( p) boladi’ (m ) ko’pliginin’ tan’lani’wi’na tiykarlani’p). Yendi
B( A1,...., An)
formulani’n’
(a,(*), а('),....,аП*))
nabordag’i’ ma’nisin yesaplayi’q. (2) degi JDNF qurami’nda
Aa Aa2 Aan
toli’q elementar konyukciya qatnasqan boli’p B(A1, A2,....,An) ni’n’
(a1(*), a^,....,^^) nabordag’i’ B(a1(*), a^s),....,a^s)) ma’nisin yesaplawda
(a^a (a2*))a2*)....(an*^
ag’za payda boladi’. (1) ge tiykarlani’p 11 =1 ha’m de 00 = 0 = 1
boladi’, sebebi A1 = A, A0 = A . Demek, ai qanday boli’wi’na qaramastan (qatti’y na’zer)
(a1*1 T =1, (i=^...^n)
ha’m de
(a1(*))“1 (a2s))a2 ....(a^s))an> = 1, (1 < * < r) ibarat.
A v 1 = 1 ge tiykarlani’p
B(a(*), a^,....,^) = 1
boladi’. Solay yetip, p) g’a tiyisli naborlarda berilgen U formulasi’
da, 1 ma’nisin qabi’l qi’ladi’ yeken.
p = (p^ e2,...., pn) e m(p)
bolg’an qa’legen nabor bolsi’n. Bul jag’dayda wol nabor m(p) g’a
kiriwshi qa’legen (a^s), ),....,a^s)) nabordan hesh bolmag’anda bir
elementi menen pari’q qi’ladi’ (bul naborlar ta’rtiplengen naborlar yekenligin yesletip wo’temiz). B ni’n’ p nabori’ndag’i’ ma’nisin yesaplawda payda bolatug’i’n an’latpada qatnasqan qa’legen
_
(1 < s < r) (3)
aw „aw .~ам
ea ea .... pa,
ag’za da hesh bolmag’anda bir g’ana i ushi’n P Ф a(s) boladi’. (1) ge
tiykarlani’p 10 = 1 = 0 ha’m 01 = 0 bolg’ani’ ushi’n (3) an’latpani’n’ ma’nisi 0 ge ten’ boladi’. Bunnan
B(P, P2,...., Pn) = 0
yekenligi kelip shi’g’adi’. в e m{ ) bolg’ani’ ushi’n
U (p P2 ’....’ Pn) = 0;
demek, m( ) g’a kirmegen naborlarda U ha’m B formulalar 0
ma’nisine iye yeken. Solay yetip, U = B yag’ni’y U formula (2) JDNF g’a ten’ ku’shli yekenligi kelip shi’g’adi’. U formula birden-bir usi’lda JDNF g’a jayi’latug’i’nli’g’i’ ani’q, sebebi B formula U formulani’n’ ma’nisin 1 ge aylandi’ri’wshi’ barli’q naborlar ja’rdeminde jalg’i’z usi’lda g’ana payda yetiledi.
Natiyje. Ten’ ku’shli formulalar birqi’yli’ JDNF g’a iye.
Ayti’mlar algebrasi’ni’n’ ha’r bir U formulasi’ yaki wo’zi keltirilgen formula, yaki woni’ wog’an ten’ ku’shli keltirilgen formula menen almasti’ri’w mu’mkin degen teoremag’a tiykarlani’p, ayti’mlar algebrasi’ni’n’ qa’legen U formulasi’ni’n’ wo’zi keltirilgen formula boladi’ yamasa woni’ ten’ ku’shli tu’rlendiriwler ja’rdeminde keltirilgen formula ko’rnisine ali’p keliw mu’mkin.
Biz, to’mende ha’r qanday keltirilgen formulani’ JDNF g’a jayi’li’w algoritmin keltiremiz.
Do'stlaringiz bilan baham: | 
