Күрделі конъюнкциялар үшін жалпыланған жұтылу критериі

Логикалық алгебраның әдістері көптеген ғылыми облыстарда: биология, медицина, әскери қызметтерде, автоматтарды басқаруда, тәжірибелерді жоспарлау және т.б. бірнеше актуал мәселелерді зерттеу үшін, маңызды шамалар арасындағы санды қатыстыруға ғана емес, қарастырылып отырған процестерді сипаттауға және олардың логикалық тәуелділігін байланыстыруда да, жалпы барлық жерде қолдануын тапқан сала болып есептеледі.

Логикалық алгебраның жаңа ғылыми облыстарындағы қосымша бағыты болып келетін және соңғы кездері өте оптимал жолдармен логикалық теңдеулер жуйесінің шешіміне алып келетін объекттер жиынымен құбылыстарды танып-білу проблемелары, медициналық немесе техникалық диагностикаларды, қазіргі кездегі автоматтардың құрылуы, тесттік мәселелерді тексеру, дискреттік құрылымдағы қателіктерді табу және жөндеуі [1,2] т.б. салалар болып табылады.

Төменде үсынылып отырған жумыста

W(x,Y(x)) = U₁ (x,Y(x)) v…v U_m (x, Y (x)) типтегі арнайы дизъюнктивті нормалды формаларды қысқартудің негізгі критериін қарастырамыз, бұл жерде

U­_і(x, Y (x)) = x_i1^σ1 … x_ik^σk Y_v1…vp^σk+1 …Y_w1…wr^σk+l (i=1,2,…,m)көрінісіндегі күрделі конъюнкциялар [3].

Айталық

• U (x, Y(x)) ≡ 0 – нөлге теңдік ;
• U₁ (x, Y(x)) v U₂ (x, Y (x)) = U₂ (x,Y(x)) – қарапайым жұтылу ;

_m

• [U(x,Y(x)) → V U_i(x,Y(x)] ≡ 1 – жалпыланған жұтылу заңдары

^{i =1}

болсын.

Теорема (Жұтылу критериі). Егер ортогональ болмаған

U(x, Y (x)), U ₁ (x, Y (x)),…, U_m(x,Y(x))

кұрделі конъюнкциялардан құралған

U(x,Y(x))= 1 ,

U₁(x,Y(x)) = 0,

——————(1)

U_m(x, Y(x)) = 0

жүйе үйлесімсіз болса, сонда тек сондағана

W(x,Y(x)) = U₁(x, Y(x)) v…v U_m (x,Y (x))

арнайы д.н.ф. U(x, Y(x)) күрделі конъюнкцияны жұтады.

Дәлелдеу. Қажеттілік шарты.

Айталық W(x, Y (x)) дизъюнктивті нормалды форма U(x,Y(x)) күрделі конъюнкцияны жұтатын болсын:[U (x,Y(x))→ W(x,Y(x))] ≡ 1 немесе

_m

[ U(x, Y (x)) → V U_i(x, Y(x)) ] ≡ 1(2)

^{i = 1}

Онда_mm

[¬U(x,Y(x)) v ( V U_i(x,Y(x)) ) ] ≡ 1 немесе[ U(x,Y(x)) & ¬( V U_i(x,Y(x)) ) ] ≡ 0

болады .ⁱ⁼¹ⁱ⁼¹

Енді_m

[ U(x,Y(x)) & ¬ ( V U_i (x,Y(x)) ) ] ≠ 0

деп есептейік.ⁱ⁼¹

Онда U(ά) = 1 және¬( VU_i(ά)) = 1 немесе U(ά) = 1 және V U_i (ά) = 0 болған ά € E_n²

жиналым табылады. Сондықтан, егер

U (x, Y (x)) = 1

U₁ (x, Y (x)) = 0

——————-(3)

U_m (x, Y (x)) = 0

_mm

жүйе үйлесімді болса, онда U (ά) =1 , V U_i (ά) = 0 және[ U(ά) & ¬(V U_i (ά))] ≡ 1

ⁱ⁼¹ⁱ⁼¹

болған ά жиналым табылады. Егер (3) жүйе үйлесімсіз болса, онда

_mmm

[ U(ά) & ¬(V U_i(ά))] ≠ 1 яғни [ U(ά) & ¬(V U_i (ά))] = 0 немесе [U(ά) → V U_i (ά)] = 1

^i=1i=1i=1

болған ά € E_n² жиналым табылмайды.

Сондықтан (2) теңдік орындалғанда (1) жүйе үйлесімсіз болады. Сонымен қажеттілік шарты дәлелденді.

Жеткілікті шарт. Айталық теорема шарты орындалған болсын. Сонда

[U(x,Y(x)) → W(x, Y(x))] ≡ 1

болуыны дәлелдейміз.

Кез келген ά € E _n² жиналым үшін U(ά) ≡ 0 болғанда [U(ά) → W(ά)] = 1 теңдік барлық уақыт орындалатындығын көру қиын емес. Енді U(ά) = 1 болған жағдайды қарастырамыз. Егер (1) жүйе үйлесімсіз болса, онда бұл жүйеде U_k(ά) = 1, 1 ≤ k ≤ m болған кемінде бір теңдеу табылады. Сондықтан _i=1V^m U_і(ά) = 1 теңдік орынды және кез келген ά € E_n² үшін [U (ά) → W (ά)] ≡ 1 болады. Сонымен теорема толық дәлелденді.

Әдебиеттер

1. Журавлев Ю.И, Платоненко И.М, Об экономном умножений

булевых уравнении – ЖВМ и МФ, том-24,1984г

2. Яблонский С. В. , Введение в дискретную математику. Москва «Наука», Главная редакция физико-математической литературы, «1979 г.
3. Байжуманов А.А., Об одном эффективном представлений высказываний системы булевых уравнений второй степени – Материалы научной конференций «Проблемы прикладной математики» ( 19-20 мая 2006 г.), Шымкент, 2006 г.