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

                                                   x 3. rAWNOSILXNYE FORMULY ALGEBRY PREDIKATOW

  3.6. pERESTANOWKA KWANTOROW.
tEOREMA 1. dLQ L@BOJ FORMULY a SPRAWEDLIWY UTWERVDENIQ         :


                                    (a) 8x 8y a  8y 8x a

                                    (b) 9x 9y a  9y 9x a:
   dOKAZATELXSTWO NEPOSREDSTWENNO SLEDUET IZ OPREDELENIQ KWANTORNYH OPERACIJ.
   tAKIM OBRAZOM IZ TEOREMY SLEDUET, ^TO ODNOTIPNYE KWANTORY PERESTANOWO^NY. sLEDU@]IJ
NIVE PRIMER POKAZYWAET, ^TO RAZNOTIPNYE KWANTORY NEPERESTANOWO^NY.
pRIMER 1. rASSMOTRIM DWE FORMULY 8x 9y P (x
 y) I 9y 8x P (x
 y) NA N. pROINTERPRETIRUEM
PEREMENNYJ PREDIKAT P(x
 y) NA N TAK: P(x
 y) = \x  y". tOGDA ISHODNYE FORMULY W TAKOJ IN-
TERPRETACII OBRATQTSQ W WYSKAZYWANIQ 8x 9y (x  y) I 9y 8x (x  y), IZ KOTORYH PERWOE ISTINNO,
A WTOROE | LOVNO. |TO OZNA^AET, ^TO NA N FORMULY 8x 9y P (x
 y) I 9x 8y P(x
 y) NERAWNOSILXNY,
SLEDOWATELXNO \TI FORMULY NERAWNOSILXNY.
   3.7. nOWYE TERMINY. sOWMESTNAQ INTERPRETACIQ DWUH FORMUL. fORMULY, RAWNOSILXNYE
NA MNOVESTWE. rAWNOSILXNYE FORMULY.
   3.8. kONTROLXNYE WOPROSY.
  1. pRIWEDITE PRIMERY FORMUL, RAWNOSILXNYH NA ODNOM MNOVESTWE I NERAWNOSILXNYH NA DRU-
     GOM.
  2. sPRAWEDLIWY LI ZAKONY DE mORGANA DLQ FORMUL ALGEBRY PREDIKATOW? pO^EMU?
     uKAZANIE. iSPOLXZUJTE TEOREMU 3.2.1.
  3. rAWNOSILXNY LI FORMULY:
      (a) 8x 9y a(x
 y) I 8z 9y a(z
 y)
      (b) 8x 9y a(x
 y) I 8z 9y a(y
 z)
      (c) 8x 9y a(x
 y) I 8y 9x a(x
 y)
      (d) 8x 9y a(x
 y) I 8y 9x a(y
 x)
   3.9. uPRAVNENIQ.
  1. dOKAVITE, ^TO ESLI W TEOREME 3.1.1 OTBROSITX USLOWIE DOPUSTIMOSTI L@BOGO MNOVESTWA DLQ
     FORMUL a I b, TO:
     (a) IZ OB]EZNA^IMOSTI FORMULY a  b SLEDUET RAWNOSILXNOSTX a  b.
     (b) IZ RAWNOSILXNOSTI a  b NE SLEDUET OB]EZNA^IMOSTX FORMULY a  b.
  2. pOLXZUQSX TEOREMOJ 3.2.1, DOKAVITE W ALGEBRE PREDIKATOW ISTINNOSTX SLEDU@]IH RAWNO-
     SILXNOSTEJ:
      (a) a  b  (a ! b) & (b ! a) | PRAWILO ISKL@^ENIQ \KWIWALENCII
      (b) a ! b  :a _ b | PRAWILO ISKL@^ENIQ IMPLIKACII
      (c) a _ b  :(:a & :b) | PRAWILO ISKL@^ENIQ DIZ_@NKCII.
  3. pOLXZUQSX IZWESTNYMI SWOJSTWAMI RAWNOSILXNYH FORMUL, DOKAZATX ISTINNOSTX SLEDU@]IH
     RAWNOSILXNOSTEJ DLQ FORMUL a, b I d, GDE d NE SODERVIT SWOBODNYH WHOVDENIJ BUKWY x:
      (a) 8x (a(x) ! d)  9x a(x) ! d,
      (b) 9x (a(x) ! d)  8x a(x) ! d,
      (c) 8x (d ! a(x))  d ! 8x a(x),
      (d) 9x (d ! a(x))  d ! 9x a(x).

                                             113