Дискретная математика. Кулабухов С.Ю. - 64 стр.

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

gLAWA   III.   aLGEBRA WYSKAZYWANIJ

   fORMULY (1) I (2) RAWNOSILXNY, TAK KAK IME@T ODNU I TU VE TABLICU ISTINNOSTI. oTMETIM,
^TO W DANNOM SLU^AE UDOBNEE STROITX FORMULU (1).
   lEGKO PONQTX, ^TO PROWEDENNYE RASSUVDENIQ GODQTSQ I DLQ OB]EJ SITUACII, TO ESTX NAHOV-
DENIQ FORMULY PO ZADANNOJ PROIZWOLXNOJ TABLICE ISTINNOSTI.
   2.2. nORMALXNYE FORMY. dLQ KAVDOJ FORMULY ALGEBRY WYSKAZYWANIJ MOVNO UKAZATX
RAWNOSILXNU@ EJ FORMULU, SODERVA]U@ IZ LOGI^ESKIH SWQZOK LIX OTRICANIE, KON_@NKCI@ I
DIZ_@NKCI@. dLQ \TOGO DOSTATO^NO WOSPOLXZOWATXSQ PRAWILAMI UDALENIQ IMPLIKACII I \KWIWA-
LENCII (SM. III.1.7.). rASSMOTRENIE OSOBOGO WIDA TAKIH FORMUL I SOSTAWLQET CELX POSLEDU@]IH
TREH PUNKTOW.
oPREDELENIE 1. kON_@NKTIWNYM ODNO^LENOM OT WYSKAZYWATELXNYH PEREMENNYH A1 : : : An
NAZYWAETSQ KON_@NKCIQ \TIH PEREMENNYH ILI IH OTRICANIJ.
   nAPRIMER, FORMULY
                                    A1 & :A2 & A3 
                                    A2 & A3 & :A2 & A5 
                                    A1 & A2 & :A1 & A3 & A1
QWLQ@TSQ KON_@NKTIWNYMI ODNO^LENAMI.
oPREDELENIE 2. dIZ_@NKTIWNYM ODNO^LENOM OT WYSKAZYWATELXNYH PEREMENNYH A1 : : : An
NAZYWAETSQ DIZ_@NKCIQ \TIH PEREMENNYH ILI IH OTRICANIJ.
   nAPRIMER, FORMULY
                                       :A1 _ A2 _ A4
                                       A3 _ A3 _ A3 
                                       :A1 _ A5 _ A4 _ :A4
QWLQ@TSQ DIZ_@NKTIWNYMI ODNO^LENAMI.
oPREDELENIE 3. dIZ_@NKTIWNOJ NORMALXNOJ FORMOJ NAZYWAETSQ DIZ_@NKCIQ KON_@NKTIW-
NYH ODNO^LENOW, TO ESTX WYRAVENIE WIDA a1 _ a2 _ : : : _ ak , GDE WSE ai , i = 1 2 : : : k QWLQ@TSQ
KON_@NKTIWNYMI ODNO^LENAMI (NE OBQZATELXNO RAZLI^NYMI).
oPREDELENIE 4. kON_@NKTIWNOJ NORMALXNOJ FORMOJ NAZYWAETSQ KON_@NKCIQ DIZ_@NKTIW-
NYH ODNO^LENOW b1 & b2 & : : : & bl , GDE WSE bi , i = 1 2 : : : l QWLQ@TSQ DIZ_@NKTIWNYMI ODNO-
^LENAMI (NE OBQZATELXNO RAZLI^NYMI).
   tAKVE BUDEM NAZYWATX DIZ_@NKTIWNOJ (KON_@NKTIWNOJ) NORMALXNOJ FORMOJ UKAZANNYE WY-
RAVENIQ PRI k = 1 ILI l = 1.
   nORMALXNU@ FORMU, PREDSTAWLQ@]U@ FORMULU a (TO ESTX RAWNOSILXNU@ a) BUDEM NAZYWATX
PROSTO NORMALXNOJ FORMOJ \TOJ FORMULY.
   nETRUDNO PONQTX ^TO WSQKAQ FORMULA OBLADAET KAK DIZ_@NKTIWNOJ, TAK I KON_@NKTIWNOJ
NORMALXNYMI FORMAMI. bOLEE TOGO, U DANNOJ FORMULY a SU]ESTWUET NEOGRANI^ENO MNOGO KAK
DIZ_@NKTIWNYH, TAK I KON_@NKTIWNYH NORMALXNYH FORM.
    2.3. sOWERENNYE NORMALXNYE FORMY. sREDI MNOVESTWA DIZ_@NKTIWNYH (RAWNO KAK
I KON_@NKTIWNYH) NORMALXNYH FORM, KOTORYMI OBLADAET DANNAQ FORMULA ALGEBRY WYSKAZYWA-
NIJ, SU]ESTWUET UNIKALXNAQ FORMA: ONA EDINSTWENNA DLQ DANNOJ FORMULY. |TO TAK NAZYWAEMAQ
SOWERENNAQ DIZ_@NKTIWNAQ NORMALXNAQ FORMA (SREDI KON_@NKTIWNYH FORM | SOWERENNAQ
KON_@NKTIWNAQ NORMALXNAQ FORMA).
oPREDELENIE 1. oDNO^LEN (KON_@NKTIWNYJ ILI DIZ_@NKTIWNYJ) OT WYSKAZYWATELXNYH PE-
REMENNYH A1  : : : An NAZYWAETSQ SOWERENNYM, ESLI W NEGO OT KAVDOJ PARY FORMUL Ai  :Ai
(i = 1 2 : : : n) WHODIT ROWNO ODNA FORMULA.
    nORMALXNAQ FORMA (DIZ_@NKTIWNAQ ILI KON_@NKTIWNAQ) OT PEREMENNYH A1  : : : An NAZYWA-
ETSQ SOWERENNOJ OT \TIH PEREMENNYH, ESLI W NEE WHODQT LIX NEPOWTORQ@]IESQ SOWERENNYE
ODNO^LENY (KON_@NKTIWNYE ILI DIZ_@NKTIWNYE SOOTWETSTWENNO) OT A1 : : : An

                                                 64

Страницы