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

   x   4.   pREDWARENNAQ NORMALXNAQ FORMA
     pRIWEDENNAQ FORMA DLQ FORMUL ALGEBRY PREDIKATOW pREDWARENNAQ NORMALXNAQ FORMA
                                                       .                            .


   cELX DANNOGO PARAGRAFA | DOKAZATX, ^TO WSQKU@ FORMULU ALGEBRY PREDIKATOW MOVNO PRI-
WESTI K TAKOMU WIDU, W KOTOROM ONA WOSPRINIMAETSQ (S TO^KI ZRENIQ EE SODERVATELXNOGO SMYSLA)
GORAZDO LEG^E.
  4.1. pRIWEDENNAQ FORMA DLQ FORMUL ALGEBRY PREDIKATOW.
oPREDELENIE 1. fORMULA a NAZYWAETSQ PRIWEDENNOJ FORMOJ ESLI a NE SODERVIT OPERACIJ
                                                                  ,
IMPLIKACII I \KWIWALENCII I ZNAKI OTRICANIQ OTNOSQTSQ LIX K \LEMENTARNYM FORMULAM.
pRIMER 1. fORMULY (8x P(x
 y) _:Q(z)) ! A, :(B & :P(x)), :8x Q(y) NE QWLQ@TSQ PRIWEDEN-
NYMI FORMAMI, A FORMULY (9x :P (x
 y) & Q(z)) _ A, :S _ P(x), 9x :Q(x) QWLQ@TSQ PRIWEDENNYMI
FORMAMI.
tEOREMA 1. wSQKAQ FORMULA ALGEBRY PREDIKATOW RAWNOSILXNA NEKOTOROJ PRIWEDENNOJ FORME.
dOKAZATELXSTWO. pUSTX a | PROIZWOLXNAQ FORMULA ALGEBRY PREDIKATOW. w SILU UPR. 2 PRE-
DYDU]EGO PARAGRAFA WSQKAQ FORMULA RAWNOSILXNA TAKOJ FORMULE, W KOTOROJ NET OPERACIJ !
I .
   pROWEDEM DOKAZATELXSTWO INDUKCIEJ PO KOLI^ESTWU n OPERACIJ (SWQZOK) W FORMULE a.
   eSLI n = 0, TO ESTX a NE SODERVIT SWQZOK, TO a ESTX \LEMENTARNAQ FORMULA I, SLEDOWATELXNO,
a QWLQETSQ PRIWEDENNOJ FORMOJ.
   pUSTX n > 0 I DLQ WSQKOGO k, 0  k < n, FORMULY, SODERVA]IE k LOGI^ESKIH OPERACIJ,
RAWNOSILXNY PRIWEDENNOJ FORME. pO OPREDELENI@ FORMULA a IMEET ODIN IZ SLEDU@]IH WIDOW:
                                        1) a = :b
                                        2) a = b & d
                                        3) a = b _ d
                                        4) a = 8x b
                                        5) a = 9x b.
pRI^EM, FORMULY b I d PO INDUKTIWNOMU PREDPOLOVENI@ RAWNOSILXNY PRIWEDENNYM FORMAM:
                                            b  b
                                            d  d
tOGDA: 
2) a  b & d | PRIWEDENNAQ FORMA
3) a  b _ d | PRIWEDENNAQ FORMA
4) a  8x b | PRIWEDENNAQ FORMA
5) a  9x b | PRIWEDENNAQ FORMA.
    tAKIM OBRAZOM OSTALOSX RASSMOTRETX SLU^AJ 1).
    1) a  :b , GDE b | PRIWEDENNAQ FORMA. sTROGO GOWORQ, \TOT SLU^AJ SLEDUET DOKAZYWATX
INDUKCIEJ PO KOLI^ESTWU LOGI^ESKIH SWQZOK W b . oDNAKO MY OGRANI^IMSQ LIX APELLQCIEJ K
PONIMANI@    TOGO, PO^EMU \TO TAK.
    b | PRIWEDENNAQ FORMA. pOLXZUQSX ZAKONAMI DE mORGANA I TEOREMOJ 3.4.1 OTRICANIE W FOR-
MULE :b POSLEDOWATELXNO MOVNO OTNESTI K \LEMENTARNYM FORMULAM, SOSTAWLQ@]IM FORMULU b .
tAKIM OBRAZOM, TEOREMU MOVNO S^ITATX DOKAZANNOJ.
  4.2. pREDWARENNAQ NORMALXNAQ FORMA.
oPREDELENIE 1. fORMULA a NAZYWAETSQ PREDWARENNOJ NORMALXNOJ FORMOJ ESLI a IMEET WID
                                                                          ,                  :


                                  a = Q1 x1 Q2 x2 : : :Qn xn b

GDE Q1 
 : : :
 Qn 2 f8
 9g, A FORMULA b QWLQETSQ PRIWEDENNOJ FORMOJ, NE SODERVA]EJ KWANTOROW.

                                              115