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

0

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

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

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

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

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

            Айталық

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

                               m

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

                              i =1

болсын.

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

      U(x, Y (x)),  U 1 (x, Y (x)),…, Um(x,Y(x))

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

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

                  U1(x,Y(x))  = 0,

                  ——————                                                                                                        (1)

                  Um(x, Y(x)) = 0

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

      W(x,Y(x)) = U1(x, Y(x)) v…v Um (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 Ui(x, Y(x)) ]  ≡ 1                                                         (2)

                                                  i = 1

Онда                     m                                                                                                                     m

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

 болады  .             i=1                                                                                                                  i=1

Енді                                                                 m

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

деп есептейік.                                                 i=1

     Онда U(ά) = 1 және    ¬( VUi(ά)) = 1 немесе U(ά) = 1 және V Ui (ά) = 0 болған ά € En2                                                                  

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

                  U (x, Y (x))  =  1

                  U1 (x, Y (x)) = 0

                  ——————-             (3)

                  Um (x, Y (x)) = 0

                                                                 m                                                                           m

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

                                                                 i=1                                                                        i=1

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

                   m                                                                          m                                                                           m

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

                   i=1                                                                       i=1                                                                         i=1

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

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

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

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

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

Кез келген ά € E n2 жиналым үшін U(ά) ≡ 0 болғанда [U(ά) → W(ά)] = 1 теңдік барлық уақыт орындалатындығын көру қиын емес. Енді U(ά) = 1 болған жағдайды қарастырамыз. Егер (1) жүйе үйлесімсіз болса, онда бұл жүйеде Uk(ά) = 1, 1 ≤ k ≤ m болған кемінде бір теңдеу табылады. Сондықтан  i=1Vm Uі(ά) = 1 теңдік орынды және кез келген  ά € En2 үшін [U (ά) → W (ά)] ≡ 1 болады. Сонымен теорема толық дәлелденді.

Әдебиеттер

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

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

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

ОСТАВЬТЕ ОТВЕТ