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

UptoLike

ВУЗ: 

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

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

Рубрика: 

gLAWA   VI.   aLGEBRA PRELIKATOW

pRIMER 1. fORMULY: 8x P (x), 9x 8y 9z (:P (x y) _ Q(z)), 8x 8y ((P(x y) & Q(z)) _ :P(x y)) |
PREDWARENNYE NORMALXNYE FORMY, A FORMULY: :8x P (x), 9x 8y 9z :(P (x y) _ A), 8x 9y (8z P(z) _
_:Q(x y)) NE QWLQ@TSQ PREDWARENNYMI NORMALXNYMI FORMAMI. pOQSNITE, PO^EMU.
tEOREMA 1. wSQKAQ FORMULA a ALGEBRY PREDIKATOW RAWNOSILXNA NEKOTOROJ PREDWARENNOJ NOR-
MALXNOJ FORME.
dOKAZATELXSTWO. kAK I W PREDYDU]EJ TEOREME MOVNO S^ITATX, ^TO a NE SODERVIT OPERACIJ !
I .
   tAK KAK WSQKAQ FORMULA RAWNOSILXNA PRIWEDENNOJ FORME, SM. TEOREMA 4.1.1, TO DOSTATO^NO
POKAZATX, ^TO FORMULA a RAWNOSILXNA FORMULE
                                            Q1x1 Q2 x2 : : :Qnxn b                                        (1)
GDE b | BESKWANTORNAQ FORMULA.
   iNDUKCIQ PO KOLI^ESTWU n LOGI^ESKIH OPERACIJ W FORMULE a.
   eSLI n = 0, TO a QWLQETSQ \LEMENTARNOJ FORMULOJ I, SLEDOWATELXNO, a ESTX PREDWARENNAQ
NORMALXNAQ FORMA.
   pUSTX TEPERX n > 0 I DLQ WSQKOGO k, 0  k < N FORMULY S KOLI^ESTWOM LOGI^ESKIH OPERACIJ k
RAWNOSILXNY FORMULE WIDA (1).
   pO OPREDELENI@ FORMULY, a IMEET WID:
                                                  1) a = :b
                                                  2) a = b & d
                                                  3) a = b _ d
                                                  4) a = 8x b
                                                  5) a = 9x b.
pRI^EM MOVNO S^ITATX, ^TO FORMULY b I d IME@T WID (1). pUSTX:
                                        b = Q1x1 Q2x2 : : :Qnxn b1
                                        d = R1 y1 R2 y2 : : :Rm ym d1 
GDE b1 I d1 | BEZKWANTORNYE FORMULY, Q1 : : : Qn R1 : : : Rm 2 f8 9g.
   nA OSNOWANII TEOREMY 3.3.1 MOVNO S^ITATX, ^TO BUKWY x1  : : : xn NE WHODQT W ZAPISX FORMU-
LY d, A BUKWY y1  : : : ym NE WHODQT W ZAPISX FORMULY b.
   1) a = :b. pOLXZUEMSQ TEOREMOJ 3.4.1.
        a = :b = :Q1x1 Q2 x2 : : :Qn xn b1  Q01 x1 (:Q2x2 : : :Qnxn b1 )  : : :  Q01x1 : : :Q0nxn :b1
| IMEET WID (1). zDESX
                                          Q0i =
                                                  
                                                      8
                                               ESLI Qi = 9,
                                                      9
                                               ESLI Qi = 8.
   2) a = b & d. wOSPOLXZUEMSQ TEOREMOJ 3.5.1 P. (1), (2).
                     a = b & d = Q1 x1 Q2x2 : : :Qn xn b1 & R1y1 R2y2 : : :Rm ym d1 
                      Q1x1 (Q2x2 : : :Qnxn b1 & R1y1 R2y2 : : :Rmym d1)  : : :
                     : : :  Q1 x1 : : :Qn xn (b1 & R1 y1 R2 y2 : : :Rm ym d1 ) 
                      Q1x1 : : :Qnxn R1y1 (b1 & R2y2 : : :Rmym d1)  : : :
                     : : :  Q1 x1 : : :Qn xn R1y1 : : :Rm ym (b1 & d1 )
| IMEET WID (1).
   3) a = b _ d. wOSPOLXZOWAWISX TEOREMOJ 3.5.1 P. (3), (4) I PROWODQ RAWNOSILXNYE PREOBRAZO-
WANIQ, PODOBNYE PREOBRAZOWANIQM PREDYDU]EGO PUNKTA, POLU^IM NUVNOE.
   4) a = 8x b = 8x Q1x1 : : :Qnxn b1 | IMEET WID (1).
   5) tO^NO TAKVE, KAK I W 4).

                                                           116

Страницы