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

                                           x 1. bULEWY FUNKCII. rEALIZACIQ BULEWYH FUNKCIJ FORMULAMI

  9.   f  1  f , f _ 0  f , f _ 1  1, f  0  0, 10  0, 00  1.
 10.   zAKON KONTRAPOZICII:
       f ! g  g0 ! f 0 :
 11.   pRAWILO ISKL@^ENIQ IMPLIKACII:
       f ! g  f 0 _ g

 12.   pRAWILO ISKL@^ENIQ \KWIWALENCII:
       f  g  (f ! g)  (g ! f):
 13.   f 0  f j f  f # f  f + 1.
 14.   f j g  (f  g)0 , f # g  (f _ g)0 .
 15.   f _ g  (f j f) j(g j g), f  g  (f # f) #(g # g), f ! g  f j(g j g).
 16.   f + g  (f  g)0 .
   dOKAZATELXSTWO \TIH RAWNOSILXNOSTEJ PROWODITSQ POSTROENIEM TABLIC ISTINNOSTI.
   1.5. pODSTANOWKA I ZAMENA. eSLI W FORMULU F WHODIT PEREMENNAQ x, TO \TOT FAKT BU-
DEM OBOZNA^ATX F(: : :
 x
 : : :). zAPISX F (: : :
 G
 : : :) OBOZNA^AET, ^TO FORMULA F SODERVIT W SWOEJ
ZAPISI PODFORMULU G. wMESTO PODFORMULY (W ^ASTNOSTI, WMESTO PEREMENNOJ) W FORMULU MOVNO
PODSTAWITX DRUGU@ FORMULU (W ^ASTNOSTI, PEREMENNU@), W REZULXTATE POLU^ITSQ NOWAQ PRAWILX-
NO POSTROENNAQ FORMULA. eSLI POSTANOWKA PROIZWODITSQ WMESTO NEKOTORYH WHOVDENIJ (W TOM
^ISLE WMESTO ODNOGO), TO REZULXTAT PODSTANOWKI OBOZNA^IM F(: : :
 G1
 : : :)fG2=G1g. eSLI VE POD-
STANOWKA PROIZWODITSQ WMESTO WSEH WHOVDENIJ ZAMENQEMOJ PODFORMULY (ILI PEREMENNOJ), TO
REZULXTAT PODSTANOWKI OBOZNA^IM F (: : :
 G1
 : : :)fG2 ==G1g.
pRIMER 1.0
   1. x _ x fy  z==xg = (y  z) _ (y  z)0 .
   2. x ! (y _ z)fx0==y _ z g = x ! x0 .
   3. zAMENA PERWOGO WHOVDENIQ PEREMENNOJ: x  x0fy=xg = y  x0 .
   4. zAMENA WTOROGO WHOVDENIQ PODFORMULY: x _ (y  z)0 _ (y  z)fx=y  z g = x _ (y  z)0 _ x.
pRAWILO ZAMENY. eSLI W FORMULE ZAMENITX NEKOTORU@ PODFORMULU NA RAWNOSILXNU@ EJ, TO
POLU^ITSQ RAWNOSILXNAQ FORMULA
                       G1  G2 =) F (: : :
 G1
 : : :)  F(: : :
 G1
 : : :)fG2 =G1g:

pRAWILO PODSTANOWKI. eSLI W RAWNOSILXNYH FORMULAH WMESTO WSEH WHOVDENIJ NEKOTOROJ
PEREMENNOJ x POSTAWITX ODNU I TU VE FORMULU, TO POLU^ATSQ RAWNOSILXNYE FORMULY
         F1(: : :
 x
 : : :)  F2 (: : :
 x
 : : :) =) F1 (: : :
 x
 : : :)fG==xg  F2(: : : 
 x
 : : :)fG==xg:


pRIMER 2. tAK KAK x ! y  x0 _ y, TO, PO PRAWILU ZAMENY
    (z  (x ! y)) _ (x ! y)  (z  (x ! y)) _ (x0 _ y) = (z  (x ! y)) _ (x ! y)fx0 _ y=x ! yg:
tAK KAK x0  (y ! x)  (x + 1)  (y ! x), TO, PO PRAWILU ZAMENY, IMEEM
                       x0  (y ! x)fx _ z==xg  (x + 1)  (y ! x)fx _ z==xg
ILI
                           (x _ z)0  (y ! (x _ z))  ((x _ z) + 1)  (y ! (x _ z)):
   oTMETIM, ^TO W PRAWILE PODSTANOWKI USLOWIE ZAMENY WSEH WHOVDENIJ SU]ESTWENNO. nAPRIMER,
x _ x0  1 I x _ x0fy==xg = y _ y0  1, NO x _ x0 fy=xg = y _ x0 6 1.

                                                        77