Дискретная математика

a b c d

iZ 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

tEOREMA O ZAMKNUTOSTI KLASSOW

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

QWLQ@TSQ NEMONOTONNYMI.

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

xi+1; : : : ; xn

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