Дискретная математика
.pdfiZ OPREDELENIQ 2 SLEDUET, ^TO L@BAQ FUNKCIONALXNAQ SHEMA REALIZUET NA WYHODE ZNA^ENIE NEKOTOROJ BULEWOJ FUNKCII OT ZNA^E- NIJ EE WHODOW, \TA FUNKCIQ POLU^AETSQ SUPERPOZICIQMI IZ BULEWYH FUNKCIJ, REALIZUEMYH FUNKCIONALXNYMI \LEMENTAMI \TOJ SHEMY I FUNKCIJ PROECIROWANIQ.
pRIMER 1. nA^ERTITX FUNKCIONALXNU@ SHEMU, REALIZU@]U@ BU-
LEWU FUNKCI@ f(a; b; c; d) = ab _ bc _ d NA OSNOWE \LEMENTOW i-ne, \LEMENTY i-ne (SM. RIS. 9), REALIZU@T FUNKCI@ y = x1x2 : : : xn .
rE[ENIE. pREOBRAZUEM DANNU@ FORMULU SLEDU@]IM OBRAZOM:
f(a; b; c; d) = ab bc d . iSKOMAQ SHEMA IZOBRAVENA NA RIS. 10.
|
|
|
& |
|
- |
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
&c |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
. |
|
|
|
e |
|
|
|
|
& |
|
|
|
|
|
|
- |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
|
c |
|
|
|
c |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rIS. 9 |
|
|
|
|
|
|
|
rIS. 10 |
|
|
|
|
|
|
|||||||
|
x12. pOLNOTA SISTEM BULEWYH FUNKCIJ |
|
||||||||||||||||||||||
oPREDELENIE 1 |
. |
sISTEMA LOGI^ESKIH SWQZOK |
S = f 1; : : : ; mg |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
NAZYWAETSQ POLNOJ, ESLI L@BU@ BULEWU FUNKCI@ f(x1 |
; x2; : : : ; xn) |
MOVNO REALIZOWATX pf, SOSTAWLENNOJ IZ PEREMENNYH S ISPOLXZOWANIEM \TIH LOGI^ESKIH SWQZOK.
pOLNAQ SISTEMA NAZYWAETSQ BAZISOM, ESLI NIKAKAQ EE PODSISTEMA NE QWLQETSQ POLNOJ.
pRIMER 1. sISTEMA f_; ^; q g QWLQETSQ POLNOJ, T.K. L@BU@ FUNKCI@ f =6 0 MOVNO PREDSTAWITX W dnf, A KONSTANTU 0 MOVNO REALIZOWATX TAK: 0 = xx . |TA SISTEMA NE QWLQETSQ BAZISOM, T.K. EE PODSISTEMY f_; q g I f^; q g TOVE POLNY, POSKOLXKU a _ b = a ^ b
I a ^ b = a _ b . sISTEMA f_; ^g NE QWLQETSQ POLNOJ. oPREDELENIE 2. fUNKCI@ F , WY^ISLQEMU@ PO FORMULE
F (t1; : : : ; tm) = f(g1(t1; : : : ; tm); g2(t1; : : : ; tm); : : : ; gn(t1; : : : ; tm)) ,
NAZYWA@T SUPERPOZICIEJ FUNKCIJ f; g1; g2; : : : ; gn .
21
oPREDELENIE 3. sISTEMA bf S = f'1 ; '2; : : : ; 'mg NAZYWA- |
|||||||||||||
ETSQ POLNOJ, ESLI L@BU@ BULEWU FUNKCI@ |
F MOVNO POLU^ITX IZ |
||||||||||||
FUNKCIJ ' |
; ' |
2 |
; : : : ; ' |
|
I FUNKCIJ |
Ik S POMO]X@ KONE^NOGO ^ISLA |
|||||||
1 |
|
|
m |
|
|
|
|
|
|
|
n |
|
|
SUPERPOZICIJ, |
GDE Ik(x |
; x |
; : : : ; x |
n |
) = x |
{ FUNKCII PROECIROWA- |
|||||||
|
|
|
|
n |
1 |
2 |
|
|
k |
|
|||
NIQ. |
|
|
|
|
|
|
|
|
|
|
|
|
|
pRIMER 2. sISTEMY |
f |
|
|
||||||||||
x; x1 _ x2; x1 ^ x2g , fx1 x2; x1 ^ x2; 1g | |
|||||||||||||
POLNY. |
|
|
|
|
|
|
|
|
|
|
|
|
|
sWOJSTWO. eSLI SISTEMA |
S = |
|
f'1; '2; : : : ; 'mg POLNA I KAV- |
||||||||||
DAQ IZ FUNKCIJ |
'1; '2 ; : : : ; 'm QWLQETSQ SUPERPOZICIEJ FUNKCIJ |
||||||||||||
1; 2 ; : : : ; l I FUNKCIJ Ink , TO I S0 = f |
1; 2 ; : : : ; lg TOVE POL- |
||||||||||||
NAQ SISTEMA. |
|
|
|
|
|
|
|
|
|
|
|
|
|
pRIMER 3. fUNKCI@ '(x; y) = (1110)T NAZYWA@T [TRIHOM {EF- |
FERA I OBOZNA^A@T ^EREZ xjy . sISTEMA fxjyg | POLNA, T.K. x = xjx I xy = (xjy)j(xjy) , A SISTEMA f^; q g QWLQETSQ POLNOJ.
x13. kLASSY FUNKCIJ, SOHRANQ@]IH 0 ILI 1
oPREDELENIE 1. bULEWA FUNKCIQ f SOHRANQET KONSTANTU 0, ESLI f(0;0; : : : ; 0) = 0 . kLASS WSEH bf, SOHRANQ@]IH 0, OBOZNA^AETSQ ^EREZ K0 . bULEWA FUNKCIQ f SOHRANQET 1, ESLI f(1; 1; : : : ; 1) = 1 ,
KLASS TAKIH FUNKCIJ OBOZNA^AETSQ ^EREZ K1 . |
|
|||
|
pRIMER 1. fUNKCII y = x , y = x1^x2 , y = x1_x2 |
PRINADLEVAT |
||
KAVDOMU IZ KLASSOW K0 I K1 ; FUNKCIQ y = x1 x2 |
PRINADLEVIT |
|||
K0 |
, NO NE PRINADLEVIT K1 ; FUNKCIQ y = x1 ! x2 |
PRINADLEVIT |
||
K1 |
, NO NE PRINADLEVIT K0 ; FUNKCIQ y = |
x |
NE PRINADLEVIT NI |
ODNOMU IZ \TIH KLASSOW.
K0 I K1 . kAVDYJ IZ KLASSOW K0 I K1 ZAMKNUT OTNOSITELXNO SUPERPOZICII, T.E. SUPERPOZICIQ FUNKCIJ, PRINADLEVA]IH ODNOMU IZ \TIH KLASSOW, SNOWA PRINADLEVIT TOMU VE KLASSU.
dOKAZATELXSTWO. pUSTX FUNKCII f(t1; t2; : : : ; tn) I gi(x1 ; : : : ; xm); GDE i = 1; 2; : : : ; n PRINADLEVAT KLASSU K0 . tOGDA IH SUPERPOZICIQ
h(x1 ; : : : ; xm) = f(g1(x1 ; : : : ; xm); : : : ; gn(x1; : : : ; xm)) TAKVE PRINADLEVIT K0 , T.K. h(0; : : : ; 0) = f(g1(0; : : : ; 0); : : : ; gn(0; : : : ;0)) =
= f(0; : : : ; 0) = 0 . zAMKNUTOSTX K1 DOKAZYWAETSQ ANALOGI^NO.
22
x14. kLASS SAMODWOJSTWENNYH FUNKCIJ
oPREDELENIE 1. bULEWA FUNKCIQ f NAZYWAETSQ SAMODWOJST-
WENNOJ, ESLI f(x1; x2; : : : ; xn) f(x1; x2; : : : ; xn) . kLASS SAMODWOJSTWENNYH FUNKCIJ OBOZNA^AETSQ ^EREZ S .
iZ OPREDELENIQ 1 SLEDUET, ^TO SAMODWOJSTWENNAQ FUNKCIQ NA PROTIWOPOLOVNYH NABORAH ARGUMENTOW PRINIMAET PROTIWOPOLOVNYE ZNA^ENIQ. eSLI FUNKCIQ ZADANA S POMO]X@ STANDARTNOJ ISTINNOSTNOJ TABLICY, TO STRO^KI \TOJ TABLICY, RAWNOOTSTOQ]IE OT KONCOW, PROTIWOPOLOVNY, PO\TOMU ESLI STOLBEC ZNA^ENIJ SAMODWOJSTWENNOJ FUNKCII SOGNUTX POPOLAM, TO ZNA^ENIQ 0 DOLVNY NALOVITXSQ NA ZNA^ENIQ 1 WO WSEH RAZRQDAH. nAPRIMER, FUNKCII
y |
= (0111 0001)T |
I y = (1010)T QWLQ@TSQ SAMODWOJSTWENNYMI, A |
y = (0111 1001)T |
I y = (0010)T NESAMODWOJSTWENNY. |
tEOREMA O ZAMKNUTOSTI KLASSA S . kLASS SAMODWOJSTWENNYH FUNKCIJ ZAMKNUT OTNOSITELXNO SUPERPOZICII.
dOKAZATELXSTWO PROWEDEM NA QZYKE FUNKCIONALXNYH SHEM. pUSTX FUNKCIONALXNAQ SHEMA SOSTAWLENA IZ SAMODWOJSTWENNYH \LEMENTOW. eSLI ZNA^ENIQ SIGNALOW NA WHODAH \TOJ SHEMY POMENQTX NA PROTIWOPOLOVNYE, TO SIGNALY NA WYHODAH WSEH EE \LEMENTOW TOVE POMENQ@TSQ NA PROTIWOPOLOVNYE, POSKOLXKU ONI SAMODWOJSTWENNY. zNA^IT I SIGNAL NA WYHODE SHEMY TOVE POMENQETSQ, T.K. ON QWLQETSQ WYHODOM ODNOGO IZ \LEMENTOW SHEMY. tEOREMA DOKAZANA.
lEMMA O NESAMODWOJSTWENNOJ FUNKCII. sUPERPOZICIEJ NE-
SAMODWOJSTWENNOJ FUNKCII f(x1; x2; : : : ; xn) I OTRICANIQ x MOVNO POLU^ITX KONSTANTU.
dOKAZATELXSTWO. pOSKOLXKU f 2= S , TO MOVNO UKAZATX TAKIE PROTIWOPOLOVNYE STRO^KI W TABLICE ISTINNOSTI, NA KOTORYH \TA FUNKCIQ PRINIMAET ODINAKOWYE ZNA^ENIQ. pUSTX f(a1; a2; : : : ; an) =
= f(a1; a2; : : : ; an) . rASSMOTRIM FUNKCI@ g(x) = f(xa1 ; : : : ; xan ) ,
KOTORAQ POLU^ENA SUPERPOZICIEJ f I x , POSKOLXKU x0 = x . iMEEM:
g(0) = f(0a1 ; 0a2 ; : : : ;0an ) = f(a1; a2; : : : ; an) = f(a1; a2 ; : : : ; an) =
= f(1a1 ; 1a2 ; : : : ; 1an ) = g(1) I, ZNA^IT, g(x) { KONSTANTA; PRI \TOM MY WOSPOLXZOWALISX TEM, ^TO 0a = a I 1a = a . lEMMA DOKAZANA.
23
x15. kLASS MONOTONNYH FUNKCIJ
oPREDELENIE 1. bULEWA FUNKCIQ f | MONOTONNA, f 2 M , ESLI
DLQ L@BYH NABOROW ;! = ( 1; 2 ; : : : ; n) I ;! = ( 1 ; 2; : : : ; n)
WYPOLNENO ;! 6 ;! =) f(;!) 6 f(;!) .
mONOTONNOSTX FUNKCII LEGKO WYQSNQETSQ IZ EE ISTINNOSTNOJ TABLICY NEPOSREDSTWENNO PO OPREDELENI@ 1. nA QZYKE FUNKCIONALXNYH SHEM MONOTONNOSTX OZNA^AET, ^TO USILENIE SIGNALOW NA NEKOTORYH WHODAH SHEMY NE PRIWODIT K UMENX[ENI@ SIGNALA NA WYHODE \TOJ SHEMY.
pRIMER 1. fUNKCII y = x , y = x1^x2 , y = x1_x2 PRINADLEVAT KLASSU M , A FUNKCII y = x , y = x1 x2 , y = x1 ! x2 , y = x1 x2
tEOREMA O ZAMKNUTOSTI KLASSA M . kLASS MONOTONNYH FUNK-
CIJ ZAMKNUT OTNOSITELXNO SUPERPOZICII.
dOKAZATELXSTWO PROWEDEM NA QZYKE FUNKCIONALXNYH SHEM. pUSTX FUNKCIONALXNAQ SHEMA SOSTAWLENA IZ MONOTONNYH \LEMENTOW. eSLI USILITX ZNA^ENIQ SIGNALOW NA NEKOTORYH WHODAH \TOJ SHEMY, TO SIGNALY NA WYHODAH WSEH EE \LEMENTOW NE UMENX[ATSQ, POSKOLXKU ONI MONOTONNY. zNA^IT I SIGNAL NA WYHODE SHEMY TOVE NE UMENX[ITSQ, T.K. ON QWLQETSQ WYHODOM ODNOGO IZ \LEMENTOW SHEMY. tEOREMA DOKAZANA.
lEMMA O NEMONOTONNOJ FUNKCII. sUPERPOZICIEJ NEMONO-
TONNOJ FUNKCII f(x1; x2; : : : ; xn) I KONSTANT 0, 1 MOVNO POLU^ITX OTRICANIE x .
dOKAZATELXSTWO. pOSKOLXKU f 2= M , TO MOVNO UKAZATX NABORY
;! = ( 1; 2; : : : ; n) I ;! = ( 1; 2 ; : : : ; n) TAKIE, ^TO ;! 6 ;! ,
NO f(;!) > f(;!) , T.E. f(;!) = 1 , A f(;!) = 0 . pOSTROIM NABOR
;! = ( 1; 2; : : : ; n) PO PRAWILU: i = i , ESLI i = i I i = x ,
ESLI i < i , i = 1; 2; : : : ; n . lEGKO WIDETX, ^TO ;!jx=0 = ;! , A ;!jx=1 = ;! . rASSMOTRIM FUNKCI@ g(x) = f( 1; 2; : : : ; n) , KOTORAQ QWLQETSQ SUPERPOZICIEJ FUNKCII f I KONSTANT 0, 1. pOSKOLXKU
g(0) = f( 1; 2; : : : ; n) = 1 , A g(1) = f( 1; 2; : : : ; n) = 0 , TO
g(x) = x . lEMMA DOKAZANA.
24
x16. kLASS LINEJNYH BULEWYH FUNKCIJ
oPREDELENIE 1. fUNKCIQ f NAZYWAETSQ LINEJNOJ, f 2 L , ESLI EE MNOGO^LEN vEGALKINA NE SODERVIT KON_@NKCIJ PEREMENNYH, T.E.
f(x1; x2 ; : : : ; xn) = C0 |
C1x1 C2x2 : : : Cnxn , GDE KO\FFICIENTY |
||||||||||||
Ci 2 f0; 1g . |
|
|
|
|
|
|
|
|
|
|
|
|
|
pRIMER |
1. |
fUNKCII |
y |
= x , y = x , y = x1 x2 , y = x1 x2 |
|||||||||
|
|
|
|
|
|||||||||
PRINADLEVAT KLASSU |
L , |
A |
y = x1 ^ x2 , y = x1 _ x2 , y = x1 ! x2 |
||||||||||
|
|
|
|
|
|
||||||||
QWLQ@TSQ NELINEJNYMI FUNKCIQMI. |
|
|
|||||||||||
tEOREMA O ZAMKNUTOSTI KLASSA L . kLASS LINEJNYH FUNKCIJ |
|||||||||||||
ZAMKNUT OTNOSITELXNO SUPERPOZICII. |
|
|
|||||||||||
dOKAZATELXSTWO |
. |
pUSTX |
y = a0 a1t1 a2t2 a3t3 : : : amtm |
||||||||||
|
|
|
|
|
|
||||||||
I ti = bi0 |
bi1x1 bi2x2 |
|
: : : |
binxn |
{ LINEJNYE FUNKCII. iH |
||||||||
SUPERPOZICIEJ BUDET LINEJNAQ FUNKCIQ |
y = c0 c1 x1 : : : cnxn , |
U |
|||||||||||
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
KOTOROJ KO\FFICIENTY ck |
= |
|
aibik PRI k = 0; 1; : : : ; n . tEOREMA |
||||||||||
|
|
|
|
|
|
|
|
i=0 |
|
|
|
|
|
DOKAZANA. |
|
|
|
|
|
|
|
P |
|
|
|
|
|
lEMMA O NELINEJNOJ FUNKCII. |
sUPERPOZICIEJ NELINEJNOJ |
FUNKCII f(x1; x2; : : : ; xn) , KONSTANT 0, 1 I OTRICANIQ x MOVNO POLU^ITX KON_@NKCI@ x1 ^ x2 .
dOKAZATELXSTWO. pOSKOLXKU FUNKCIQ f 2= L , TO W EE MNOGO- ^LENE vEGALKINA IMEETSQ HOTQ BY ODNA KON_@NKCIQ, MOVNO S^I-
TATX, ^TO \TO x1x2 . pEREPI[EM \TOT MNOGO^LEN vEGALKINA TAKIM |
||||||||||||||||
OBRAZOM |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
: f(x1; x2; : : : ; xn) = x1x2g1(x3 ; : : : ; xn) x1g2(x3; : : : ; xn) |
||||||||||||||
x2g3(x3; : : : ; xn) g4(x3; : : : ; xn) . mNOGO^LEN g1(x3; : : : ; xn) PO USLO- |
||||||||||||||||
WI@ NE MOVET TOVDESTWENNO RAWNQTXSQ NUL@, SLEDOWATELXNO, SU- |
||||||||||||||||
]ESTWU@T ZNA^ENIQ x ; : : : ; x TAKIE, ^TO g1(x ; : : : ; x ) = 1 . |
|
|
||||||||||||||
|
|
|
|
|
|
3 |
n |
|
|
3 |
|
n |
|
|
|
|
|
|
rASSMOTRIM FUNKCI@ g(x1; x2) = f(x1; x2 ; x ; : : : ; x ) , KOTORAQ |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
n |
|
|
|
QWLQETSQ SUPERPOZICIEJ FUNKCII f |
I KONSTANT 0, 1. |
mNOGO^LEN |
||||||||||||||
vEGALKINA DLQ NEE IMEET WID |
|
; x2) = x1 x2 |
x1 |
x2 |
, |
|||||||||||
|
|
|
|
|
|
|
: g(x1 |
|||||||||
GDE = g2(x ; : : : ; x ) , = g3(x ; : : : ; x ) I |
= g4 |
(x ; : : : ; x ) . |
|
|||||||||||||
|
|
|
3 |
|
n |
|
3 |
n |
|
3 |
|
n |
|
|
||
|
|
rASSMOTRIM FUNKCI@ |
h(x1; x2) = g(x1 ; x2 ) ; |
ONA QWLQETSQ |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
SUPERPOZICIEJ FUNKCII g |
I OTRICANIQ. pOSLE UPRO]ENIJ POLU^A- |
|||||||||||||||
EM |
, |
^TO |
h(x1 ; x2) = x1 x2 |
|
. |
eSLI |
|
= 0 , |
TO ISKO |
- |
||||||
|
|
|
|
|
||||||||||||
MAQ KON_ |
@NKCIQ |
x1 |
^ x2 |
RAWNA |
h(x1; x2) , A, ESLI = 1 , TO |
|||||||||||
|
|
|
|
|
|
|
||||||||||
x1 ^ x2 = h(x1; x2) . lEMMA DOKAZANA. |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|
x17. tEOREMA pOSTA O POLNOTE SISTEM BULEWYH FUNKCIJ
tEOREMA pOSTA O POLNOTE. dLQ POLNOTY SISTEMY BULEWYH FUNKCIJ NEOBHODIMO I DOSTATO^NO, ^TOBY SREDI NIH BYLI FUNKCII
2 |
|
2 |
, s |
2 |
2 |
I |
2 |
0 = K0 |
, |
1 = K1 |
= S , |
m = M |
l = L . |
||
dOKAZATELXSTWO. 1. |
pUSTX DANA POLNAQ SISTEMA BULEWYH FUNK- |
CIJ. eSLI W \TOJ SISTEME WSE FUNKCII SOHRANQ@T NOLX, TO IZ TEOREMY O ZAMKNUTOSTI KLASSA K0 SLEDUET, ^TO I L@BAQ SUPERPOZICIQ FUNKCIJ \TOJ SISTEMY TAKVE SOHRANQET NOLX, A \TO PROTIWORE^IT POLNOTE DANNOJ SISTEMY. sLEDOWATELXNO W SISTEME IMEETSQ FUNK-
CIQ |
0 = K0 . aNALOGI^NO DOKAZYWAETSQ, ^TO W \TOJ SISTEME IME@T- |
||||||||||||||
|
|
2 |
1 = K1 , |
|
|
= S , |
m = M |
I |
l = L . nEOBHODIMOSTX |
||||||
SQ FUNKCII |
|
s |
|||||||||||||
DOKAZANA. |
2 |
|
|
|
2 |
2 |
|
2 |
|
|
|
|
|||
|
2. dOKAVEM DOSTATO^NOSTX. pUSTX W SISTEME BULEWYH FUNKCIJ |
||||||||||||||
IME@TSQ FUNKCII |
0 |
|
= K0 , 1 |
= K1 , |
s = S , |
m = M I |
l |
= L . |
|||||||
|
|
|
|
|
2 |
|
2 |
2 |
2 |
|
2 |
|
|||
|
|
|
|
|
|
|
|
|
|
||||||
uBEDIMSQ, ^TO SUPERPOZICIEJ \TIH FUNKCIJ MOVNO POLU^ITX |
|
x I |
|||||||||||||
x1 |
|
x2 . rASSMOTRIM FUNKCI@ |
0(x1; : : : ; xn) |
= K0 , TOGDA FUNK- |
|||||||||||
|
^ |
0(x; x; : : : ; x) |
|
|
|
|
2 |
|
|
|
|
||||
CIQ |
'(x) = |
UDOWLETWORQET USLOWI@ '(0) = 1 . dALEE |
|||||||||||||
RASSMOTRIM DWA SLU^AQ: '(1) = 1 I '(1) = 0 . |
|
|
|
|
|
||||||||||
|
2.1. pUSTX '(1) |
= |
1 , |
TOGDA FUNKCIQ |
'(x) |
QWLQETSQ KONSTAN- |
TOJ 1. wTORU@ KONSTANTU 0 MOVNO POLU^ITX, ISPOLXZUQ FUNKCI@
1 = K1 , PO FORMULE 1(1;1; : : : ; 1) = 0 . dALEE, |
SUPERPOZICIEJ |
|||||||||||||||||
2 |
m = M I KONSTANT 0, 1 MOVNO POLU^ITX |
|
|
|
|
|
|
|||||||||||
|
x PO LEMME O |
|||||||||||||||||
FUNKCII |
|
|||||||||||||||||
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
l = L , |
|||
NEMONOTONNOJ FUNKCII. nAKONEC, SUPERPOZICIEJ FUNKCII |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
KONSTANT |
0, 1 I OTRICANIQ x MOVNO POLU^ITX KON_@NKCI@ |
|||||||||||||||||
x1 ^ x2 |
||||||||||||||||||
PO LEMME O NELINEJNOJ FUNKCII. |
|
|
|
|
|
|
||||||||||||
2.2. pUSTX '(1) = 0 , TOGDA FUNKCIQ '(x) = |
|
. sUPERPOZICIEJ |
||||||||||||||||
x |
||||||||||||||||||
FUNKCII |
s 2= S I OTRICANIQ |
|
|
|
MOVNO POLU^ITX KONSTANTU PO |
|||||||||||||
x |
||||||||||||||||||
LEMME O NESAMODWOJSTWENNOJ FUNKCII. wTORU@ KONSTANTU MOVNO |
||||||||||||||||||
POLU^ITX, ISPOLXZUQ |
|
. nAKONEC, SUPERPOZICIEJ FUNKCII |
l = L , |
|||||||||||||||
x |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
KONSTANT |
0, 1 I OTRICANIQ x MOVNO POLU^ITX KON_@NKCI@ |
|||||||||||||||||
x1 ^ x2 |
||||||||||||||||||
PO LEMME O NELINEJNOJ FUNKCII. |
|
|
|
|
|
|
||||||||||||
iTAK, |
SUPERPOZICIEJ FUNKCIJ DANNOJ SISTEMY MY POLU^ILI |
|
|
|||||||||||||||
x |
||||||||||||||||||
I x1 ^ x2 . pOSKOLXKU SISTEMA f |
|
|
TO I ISHODNAQ |
|||||||||||||||
x; x1 ^ x2g POLNA, |
||||||||||||||||||
|
26 |
|
|
|
|
|
|
|
|
SISTEMA BULEWYH FUNKCIJ QWLQETSQ POLNOJ. |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
tEOREMA pOSTA O POLNOTE DOKAZANA. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
w TABL. 14 PRIWEDENY SWEDENIQ O PRINADLEVNOSTI (+) |
ILI NE- |
|||||||||||||||||||||||||||||||
PRINADLEVNOSTI (;) KLASSAM K0 , K1 , S , |
M I L OSNOWNYH BU- |
|||||||||||||||||||||||||||||||||
LEWYH FUNKCIJ. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
tABLICA 14 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
K0 |
|
|
K1 |
|
|
S |
|
|
M |
|
|
L |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
; |
|
|
; |
|
|
+ |
|
|
; |
|
|
+ |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
x |
_ y |
|
|
+ |
|
|
+ |
|
|
; |
|
|
+ |
|
|
; |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
+ |
|
|
+ |
|
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
x |
^ y |
|
|
|
|
|
|
; |
|
|
|
|
; |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
x ! y |
|
|
; |
|
|
|
|
; |
|
|
; |
|
|
; |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
x |
y |
|
|
+ |
|
|
; |
|
|
; |
|
|
; |
|
|
+ |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
x |
y |
|
|
; |
|
|
+ |
|
|
; |
|
|
; |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
xjy |
|
|
; |
|
|
; |
|
|
; |
|
|
; |
|
|
; |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
pRIMER 1. pROWERITX POLNOTU SISTEMY fx |
y; x y; xyg . |
|||||||||||||||||||||||||||||||
|
|
rE[ENIE |
. |
iZ TABLICY |
14 |
WIDNO |
, |
^TO |
x |
|
y = K0 |
, x |
|
y = K1 , |
||||||||||||||||||||
x |
|
y = L , x |
|
|
y = M I |
x |
|
|
|
|
|
|
|
|
|
|
|
x |
2 |
y , |
x |
|
|
2 |
|
|||||||||
^ |
|
|
y = M , NAKONEC, |
|
|
y , |
xy = S . |
|||||||||||||||||||||||||||
|
2 |
|
2 |
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
||||||||||
pO TEOREME pOSTA \TA SISTEMA QWLQETSQ POLNOJ. |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
x18. pONQTIE PREDIKATA. sWOBODNYE I SWQZANNYE |
||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
PEREMENNYE |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
oPREDELENIE 1. n -MESTNYM PREDIKATOM NAZYWAETSQ FUNKCIQ |
||||||||||||||||||||||||||||||||
y = P (x1; x2; : : : ; xn) , |
GDE |
x1 2 |
M1 , |
x2 |
2 |
M2; : : : ; xn |
2 Mn , A |
|||||||||||||||||||||||||||
y 2 f0; 1g . wYSKAZYWANIE S^ITAETSQ 0-MESTNYM PREDIKATOM. |
|
|||||||||||||||||||||||||||||||||
|
|
pRIMER 1. o^ENX ^ASTO WSTRE^A@TSQ SLEDU@]IE PREDIKATY: |
||||||||||||||||||||||||||||||||
EQ(x; y) = (x = y) , NE(x; y) = (x = y) , LT(x; y) = (x < y) , |
||||||||||||||||||||||||||||||||||
LE(x; y) = (x 6 y) , GDE |
x; y |
2 R . |
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
oPREDELENIE 2. oBLASTX@ ISTINNOSTI PREDIKATA P(x1; : : : ; xn) |
||||||||||||||||||||||||||||||||
NAZYWAETSQ |
|
I = f(x1; x2 |
; : : : ; xn) j |
P(x1; x2; : : : ; xn) = 1g . |
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
eSLI I = ? , TO P | TOVDESTWENNO LOVNYJ, ESLI |
I = ? , TO P |
|||||||||||||||||||||||||||||||
NAZYWAETSQ WYPOLNIMYM. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
pUSTX DANY PREDIKATY P (x1; x2; : : : ; xn) I Q(x1; x2; : : : ; xn) . |
||||||||||||||||||||||||||||||||
kON_@NKCIEJ PREDIKATOW P |
|
|
I Q NAZYWAETSQ PREDIKAT |
P ^ Q , |
||||||||||||||||||||||||||||||
ZNA^ENIE KOTOROGO NA L@BOM NABORE (x1; x2; : : : ; xn) |
OPREDELQETSQ |
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
27 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
KAK KON_@NKCIQ WYSKAZYWANIJ P (x1; x2; : : : ; xn)^Q(x1 ; x2; : : : ; xn) . aNALOGI^NO OPREDELQ@TSQ OSTALXNYE LOGI^ESKIE OPERACII S PREDI-
KATAMI.
pRIMER 2. oBLASTX@ ISTINNOSTI PREDIKATA (x > 2) ^ (x 6 4) QWLQETSQ (2; 4] , A OBLASTX@ ISTINNOSTI PREDIKATA (x < 2) _(x > 4)
BUDET (;1; 2) [ [4; 1) .
eSLI P (x1; x2; : : : ; xn) = Q(x1; x2; : : : ; xn) DLQ L@BYH ZNA^ENIJ x1 2 M1 , x2 2 M2; : : : ; xn 2 Mn , TO PREDIKATY P I Q NAZYWA@TSQ RAWNOSILXNYMI.
w x1 I x2 BYLI PRIWEDENY SWOJSTWA LOGI^ESKIH OPERACIJ S WYSKAZYWANIQMI. o^EWIDNO, ^TO \TI SWOJSTWA OSTA@TSQ SPRAWEDLIWYMI I DLQ PREDIKATOW, PRI^EM S L@BOJ OBLASTX@ OPREDELENIQ.
pEREMENNYE, IME@]IESQ W DANNOM WYRAVENII, RAZDELQ@TSQ NA SWOBODNYE I SWQZANNYE. k SWOBODNYM OTNOSQTSQ TE PEREMENNYE, WMESTO KOTORYH MOVNO PODSTAWLQTX IH KONKRETNYE ZNA^ENIQ, A SWQZANNYMI QWLQ@TSQ PEREMENNYE NE DOPUSKA@]IE \TOGO.
|
n |
|
|
pRIMER 3. w WYRAVENII |
|
ai PEREMENNYE n; a QWLQ@TSQ SWO- |
|
|
i=1 |
|
|
BODNYMI, A i | SWQZANNOJ. w WYRAVENII |
min f(x) PEREMENNYE |
||
|
P |
|
|
x2[a;b]
a; b; f | SWOBODNYE, A x | SWQZANNAQ PEREMENNAQ.
sWQZANNYE PEREMENNYE POLU^A@TSQ IZ SWOBODNYH POSLE TOGO, KAK S WYRAVENIEM PROIZWODITSQ OPERACIQ, PRI KOTOROJ \TA PEREMENNAQ PROBEGAET NEKOTOROE MNOVESTWO SWOIH ZNA^ENIJ I PO\TOMU REZULXTAT ZAWISIT UVE NE OT KONKRETNOGO ZNA^ENIQ PEREMENNOJ, A OT WSEGO MNOVESTWA EE ZNA^ENIJ.
wYRAVENIE NE IZMENITSQ, ESLI ZAMENITX IMQ SWQZANNOJ PEREMENNOJ NA NOWOE, NE MENQQ, PRI \TOM, MNOVESTWA EE ZNA^ENIJ, NAPRIMER,
nn
ai = |
aj ; |
min f(x) = min f(t) . |
|||
i=1 |
j=1 |
x2[a;b] |
t2[a;b] |
|
|
P oPASNOP, ODNAKO, DAWATX SWQZANNOJ PEREMENNOJ IMQ DRUGOJ PERE- |
|||||
MENNOJ, IME@]EJSQ W \TOM WYRAVENII | MOVET POLU^ITXSQ, KAK |
|||||
GOWORQT, KOLLIZIQ PEREMENNYH I WYRAVENIE MOVET IZMENITX SWOE |
|||||
|
|
|
|
x |
|
ZNA^ENIE. nAPRIMER, W WYRAVENII |
R |
f(t; y)dt MOVNO ZAMENITX IMQ |
|||
|
|
|
|
0 |
|
SWQZANNOJ PEREMENNOJ |
t NA x , NO NELXZQ ZAMENITX NA y . |
||||
|
|
|
28 |
|
|
x19. kWANTORY I IH SWOJSTWA
|
|
oPREDELENIE 1. pUSTX P (x) | PREDIKAT, OPREDELENNYJ NA |
|||||||||||||||||||||
MNOVESTWE M . pREDLOVENIE "SU]ESTWUET x 2 M TAKOJ, ^TO P(x) " |
|||||||||||||||||||||||
OBOZNA^AETSQ |
|
|
x P(x) , EGO ZNA^ENIE OPREDELQETSQ TAK: |
|
|||||||||||||||||||
|
|
|
|
x M |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
2 M TAKOJ, ^TO P(x0) = 1; |
||||||||||||
|
x P (x) = |
1; ESLI NAJDETSQ x0 |
|||||||||||||||||||||
x M |
0; |
ESLI |
P (x) |
|
0 |
PRI |
x |
|
M: |
|
|
|
|
|
|
|
|||||||
9 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 M . pREDLOVE- |
|||||||||
|
|
oPREDELENIE 2. pUSTX |
P (x) |
| PREDIKAT, x |
|||||||||||||||||||
NIE "DLQ L@BOGO x M WYPOLNQETSQ P (x) " OBOZNA^AETSQ x P(x) , |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x M |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
EGO ZNA^ENIE OPREDELQETSQ TAK: |
|
|
|
|
|
|
|
|
|
|
|
2 |
|||||||||||
|
x P (x) = |
|
|
1; ESLI P (x) |
|
1 PRI x 2 M; |
|
^TO |
|
|
|
|
|||||||||||
x M |
|
|
0; |
ESLI NAJDETSQ |
x0 |
|
M |
TAKOJ |
, |
P(x0) = 0: |
|||||||||||||
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
2 |
|
x P(x) |
|
|
|
|
2INOGDA PI[UT |
|
|
|
|
|
|||||||||||
|
|
wMESTO |
I x P (x) |
|
9 |
x |
2 |
M P (x) I |
|||||||||||||||
|
|
|
x M |
|
|
|
x M |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
9 |
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
2 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8x 2 M P(x) . eSLI MNOVESTWO M FIKSIROWANO, TO MOVNO NE UKAZYWATX, ^TO x 2 M I PISATX TAK: 9x P (x) I 8x P(x) .
sIMWOL 9 NAZYWAETSQ KWANTOROM SU]ESTWOWANIQ, A 8 | KWANTOROM WSEOB]NOSTI. gOWORQT, ^TO 9x P(x) POLU^AETSQ NAWE[IWA-
NIEM KWANTORA SU]ESTWOWANIQ NA x2M ANALOGI^NO OBSTOIT DELO I
P (x) ,
S NAWE[IWANIEM KWANTORA WSEOB]NOSTI.
pRIMER 1. 9x 2 R (x > 5) = 1 , A 8x |
2 R (x > 5) = 0 . |
|
|
|
|
|
||||||||||
sWOJSTWO 1. A) |
9 |
x P(x) = |
|
9 |
t P(t) , |
B) |
8 |
x P (x) = |
|
8 |
t P (t) . |
|||||
|
|
|
|
|
|
|
|
|
||||||||
|
x |
2 |
M |
t |
2 |
M |
|
x |
2 |
M |
t |
2 |
M |
|
||
|TO SWOJSTWO OB_QSNQETSQ TEM, ^TO PRI NAWE[IWANII KWANTORA |
||||||||||||||||
PO PEREMENNOJ x , ONA PROBEGAET WSE ZNA^ENIQ IZ MNOVESTWA |
M I, |
|||||||||||||||
PO\TOMU, REZULXTAT ZAWISIT NE OT KONKRETNOGO ZNA^ENIQ |
x , |
A OT |
WSEGO MNOVESTWA M ; TAKAQ PEREMENNAQ x QWLQETSQ SWQZANNOJ.
eSLI DAN PREDIKAT P (x1; x2 ; : : : ; xn) , TO POSLE NAWE[IWANIQ NA NEGO KWANTORA SU]ESTWOWANIQ ILI WSEOB]NOSTI PO PEREMENNOJ xi POLU^AETSQ (n ; 1) -MESTNYJ PREDIKAT, ZAWISQ]IJ OT x1; : : : ; xi;1 , I NE ZAWISQ]IJ OT PEREMENNOJ xi , KOTORAQ POSLE NA-
WE[IWANIQ KWANTORA STANOWITSQ SWQZANNOJ.
eSLI NA n -MESTNYJ PREDIKAT POSLEDOWATELXNO NAWESITX PO RAZLI^NYM PEREMENNYM m KWANTOROW, TO POLU^ITSQ (n;m) -MESTNYJ PREDIKAT PRI m 6 n .
29
sWOJSTWO 2. |
9 |
x |
9 |
t P (x; t) = |
9 |
t |
9 |
x P (x; t) . |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
x |
2 |
A t |
2 |
B |
t |
2 |
B x |
2 |
A |
|
|
|
|
||||
dOKAZATELXSTWO. lEGKO WIDETX, ^TO OBE ^ASTI \TOGO RAWENSTWA |
|||||||||||||||||||
ISTINNY, ESLI MOVNO UKAZATX TAKIE ZNA^ENIQ x0 |
2 A , t0 2 B , ^TO |
||||||||||||||||||
P (x0; t0) = 1 ; |
OBE ^ASTI RAWENSTWA LOVNY |
, |
ESLI |
P(x; t) 0 |
PRI |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x 2 A , t 2 B . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
sWOJSTWO 3. |
8 |
x |
8 |
t P (x; t) = |
8 |
t |
8 |
x P (x; t) . |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
x |
2 |
A t |
2 |
B |
|
2 |
|
|
2 |
A |
|
|
|
|
|||
|
|
|
|
|
t B x |
|
|
|
|
|
|
dOKAZATELXSTWO. oBE ^ASTI RAWENSTWA ISTINNY, ESLI P(x; t) 1 PRI x 2 A , t 2 B ; OBE ^ASTI RAWENSTWA LOVNY, ESLI MOVNO UKAZATX
TAKIE ZNA^ENIQ x0 2 A , t0 2 B , ^TO P (x0; t0) = 0 .
zAME^ANIE. kWANTORY WSEOB]NOSTI I SU]ESTWOWANIQ PERESTAWLQTX MEVDU SOBOJ, KAK PRAWILO, NELXZQ. nAPRIMER, O^EWIDNO, ^TO
8 |
x |
9 |
t (t > x) = 1 , A |
9 |
t |
8 |
x (t > x) = 0 . |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
x |
2 |
R t |
2 |
R |
|
t |
2 |
R x |
2 |
R |
|
|
|
|
|
|
|
|
||||
|
|
|
|
sWOJSTWO 4. 9x P(x) = 8x P (x) , |
|
8x P(x) = 9x P (x) | ZAKONY |
||||||||||||||||
DE mORGANA. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
dOKAZATELXSTWO. rASSMOTRIM PERWYJ IZ \TIH ZAKONOW DE mORGA- |
||||||||||||||||||
NA. |
9x P(x) = 1 () 9x P (x) = 0 () P(x) 0 () P (x) 1 () |
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||
8x P |
(x) = 1 . wTOROJ ZAKON DE mORGANA DOKAZYWAETSQ ANALOGI^NO. |
|||||||||||||||||||||
|
|
|
|
pRIMER 2. pUSTX |
P(x; y) OPREDELEN DLQ x 2 [a; b] , y 2 [c; d] I |
|||||||||||||||||
QWLQETSQ ISTINNYM W OBLASTI I(P ) |
(SM. RIS. 11). tOGDA PREDIKAT |
|||||||||||||||||||||
A(y) = 8x P (x; y) |
QWLQETSQ ISTINNYM PRI y 2 [c; p] , A PREDIKAT |
|||||||||||||||||||||
B(y) = 9x P(x; y) |
| ISTINNYJ DLQ y 2 [c; q] . |
|||||||||||||||||||||
|
|
|
|
pRIMER 3. dLQ x 2 [;1; 2] , y2 |
2 [;1; 2] NAJTI OBLASTX ISTINNOS- |
|||||||||||||||||
TI PREDIKATA P (y) = |
9x((y > x |
) ^ (x > 0)) . |
||||||||||||||||||||
|
|
|
|
rE[ENIE. pREDIKAT |
A(x; y) = (y > x2)^(x > 0) QWLQETSQ ISTIN- |
|||||||||||||||||
NYM W OBLASTI, I(A) |
|
(SM. RIS. 12), TOGDA P(y) | ISTINNYJ DLQ |
y 2 [0; 2] . |
y |
|
y |
|
|
|
6 |
|
6 |
|
|
d |
|
|
I(A) |
|
|
q |
|
1 |
|
||
p |
I(P ) |
|
|
- |
|
|
0 |
1 |
x |
||
c |
- |
||||
|
|
|
|||
|
|
|
|
ab x
rIS. 11 |
rIS. 12 |
30