5
Funk
je
boolo
wskie
i
inne
Przykªad
5.1.
Przedsta
w
implik
a j
x
)
y
za
p
omo
¡
op
eratora
NAND.
R
ozwi¡zanie
5.1.
Przyp
omnijm
y
,
»e:
NAND
(x;
y
)
=
:(x
^
y
);
NOR
(x;
y
)
=
:(x
_
y
);
:x
=
NAND
(x;
x)
=
NOR
(x;
x):
Z
de ni ji,
x
)
y
jest
ró
wno
w
a»ne
:x
_
y
.
Nastpnie:
:x
_
y
:(:(:x)
^
:y
)
:(:(:x)
^
:y
)
NAND
(x;
:y
)
NAND
(x;
:y
)
NAND
(x;
NAND
(y
;
y
)):
Zad
anie
5.2.
Przedsta
w:
a)
zaprze zenie
implik
a ji
y
)
x
za
p
omo
¡
op
eratora
NOR,
b)
f
(x;
y
)
=
x
_
y
za
p
omo
¡
op
eratora
NOR,
)
f
(x;
y
)
=
x
^
y
za
p
omo
¡
op
eratora
NOR,
d)
f
(x;
y
)
=
:x
_
y
za
p
omo
¡
op
eratora
NOR,
e)
f
(x;
y
)
=
x
_
y
za
p
omo
¡
op
eratora
NAND,
f
)
f
(x;
y
)
=
x
^
y
za
p
omo
¡
op
eratora
NAND.
Defini ja
5.3.
W
pro
w
ad¹m
y
ozna zenie
x
1
=
x
oraz
x
0
=
x.
Dla
do
w
olnego
w
ektora
a
2
f0;
1g
n
,
nie
h
a(i)
ozna za
i-t¡
wsp
óªrzdn¡
w
ektora
a.
Rozw
a»m
y
wyra»enie
m
a
(x)
=
x
a(1)
1
^
x
a(2)
2
^
:
:
:
^
x
a(n)
n
.
Zau
w
a»m
y
,
»e
m
a
(x)
=
1
wtedy
i
t
ylk
o
wtedy
,
gdy
dla
k
a»dego
i,
x
i
=
a(i),
zyli
dla
x
=
a.
Wó
w
zas
dysjunk yjna
p
osta¢
normalna
(ozn.
DNF)
funk
ji
f
dana
jest
wzorem:
f
(x)
=
_
a2f
1
(1)
m
a
(x):
Rozw
a»m
y
teraz
wyra»enie
s
a
(x)
=
x
:a(1)
1
_
x
:a(2)
2
_
:
:
:
_
x
:a(n)
n
.
Zau
w
a»m
y
,
»e
s
a
(x)
=
0
wtedy
i
t
ylk
o
wtedy
,
gdy
dla
k
a»dego
i,
x
i
=
a(i),
zyli
dla
x
=
a.
Wó
w
zas
koniunk yjna
p
osta¢
normalna
(ozn.
CNF)
funk
ji
f
dana
jest
wzorem:
f
(x)
=
^
a2f
1
(0)
s
a
(x):
Przykªad
5.4.
F
unk
ja
f
:
B
3
!
B
przyjm
uje
w
arto± i
ró
wne
1
t
ylk
o
dla
w
ektoró
w
(1;
0;
0),
(0;
1;
0)
i
(0;
0;
1).
Przedsta
w
t¡
funk
j
w
p
osta ia
h
normaln
y
h
(dysjunk
yjna
DNF
i
k
oniunk
yjna
CNF).
R
ozwi¡zanie
5.4.
W
prakt
y e
ozna za
to,
»e
ab
y
przedsta
wi¢
funk
j
f
w
p
osta i
DNF
istotne
s¡
te
argumen
t
y
,
dla
który
h
przyjm
uje
ona
w
arto±¢
1:
x
y
z
f
(x;
y
;
z
)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
x
y
z
m
a
()
0
0
0
1
0
0
1
:x
^
:y
^
z
0
1
0
:x
^
y
^
:z
0
1
1
1
1
0
0
x
^
:y
^
:z
1
0
1
1
1
1
0
1
1
1
1
1
40
Ostate znie
p
osta¢
dysjunk
yjna
wygl¡da
nastpuj¡ o:
f
(x;
y
;
z
)
=
(:x
^
:y
^
z
)
_
(:x
^
y
^
:z
)
_
(x
^
:y
^
:z
):
Natomiast,
ab
y
przedsta
wi¢
funk
j
f
w
p
osta i
CNF
istotne
s¡
te
argumen
t
y
,
dla
który
h
przyjm
uje
ona
w
arto±¢
0:
x
y
z
f
(x;
y
;
z
)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
x
y
z
s
a
()
0
0
0
x
_
y
_
z
0
0
1
1
0
1
0
1
0
1
1
x
_
:y
_
:z
1
0
0
1
1
0
1
:x
_
y
_
:z
1
1
0
:x
_
:y
_
z
1
1
1
:x
_
:y
_
:z
Ostate znie
p
osta¢
k
oniunk
yjna
wygl¡da
nastpuj¡ o:
f
(x;
y
;
z
)
=
(x
_
y
_
z
)
^
(x
_
:y
_
:z
)
^
(:x
_
y
_
:z
)
^
(:x
_
:y
_
z
)
^
(:x
_
:y
_
:z
):
Zad
anie
5.5.
Przedsta
w
p
oni»sze
funk
je
w
p
osta ia
h
normaln
y
h
DNF
i
CNF:
a)
f
(x;
y
;
z
)
=
(x
^
y
)
(x
^
y
),
b)
f
(x;
y
;
z
)
=
x
_
(:(y
)
z
)),
)
f
(x;
y
;
z
)
=
(:x
)
y
)
^
z
,
d)
f
(x;
y
;
z
)
=
[(x
_
y
)
^
(x
_
z
)℄
(x
^
z
).
Przykªad
5.6.
Narysuj
sie¢
b
o
olo
wsk
¡
dla
funk
ji
f
(x;
y
;
z
)
=
:x
^
y
_
z
_
1.
Jaki
jest
k
oszt
i
gªb
ok
o±¢
otrzymanej
sie i?
R
ozwi¡zanie
5.6.
Przykªado
w
¡
sie¢
b
o
olo
wsk
¡
przedsta
wia
p
oni»szy
rysunek
(nale»y
wsp
omnie¢,
»e
p
osta¢
sie i
nie
jest
okre±lona
jednozna znie).
Koszt
p
oni»szej
sie i
(li zba
tzw.br
amek
)
wynosi
8,
a
jej
gªb
oko±¢
(dªugo±¢
na
jdªu»szej
± ie»ki)
wynosi
4.
x
y
z
1
:
^
_
_
f
Zad
anie
5.7.
Narysuj
sie¢
b
o
olo
wsk
¡
dla
funk
ji
z
zadania
5.5
przed
i
p
o
zamianie
na
p
osta ie
normalne.
Jaki
jest
k
oszt
i
gªb
ok
o±¢
otrzyman
y
h
sie i?
Zad
anie
5.8.
Narysuj
sie¢
b
o
olo
wsk
¡
dla
funk
ji
z
zadania
5.4.
Jaki
jest
k
oszt
i
gªb
ok
o±¢
otrzymanej
sie i?
Zad
anie
5.9.
Dla
sie i
z
rysunku
na
nastpnej
stronie
spra
wd¹
wynik
przy
x
1
=
0;
x
2
=
1;
y
1
=
1;
y
2
=
1.
41
x
2
y
2
x
1
y
1
^
_
^
^
s
3
s
2
s
1
Przykªad
5.10.
Dla
w
ektoró
w
x
=
(1;
0;
0;
1;
1);
r
1
=
(0;
1;
1;
0;
0);
r
2
=
(1;
0;
1;
0;
0),
p
oli zy¢
P
ar
(x)
i
P
ar
r
i
(x);
i
=
1;
2.
R
ozwi¡zanie
5.10.
Zgo
dnie
z
de n j¡:
P
ar
(x)
=
5
M
i=1
x
i
=
x
1
x
2
x
3
x
4
x
5
;
gdzie
x
=
x
1
x
2
x
3
x
4
x
5
:
Zatem
P
ar
(x)
=
1.
Nastpnie
k
orzysta
j¡
z
defni ji
P
ar
r
(x)
=
5
M
i=1
(x
i
^
r
i
)
=
(x
1
^
r
1
)
(x
2
^
r
2
)
(x
3
^
r
3
)
(x
4
^
r
4
)
(x
5
^
r
5
);
gdzie
x
=
x
1
x
2
x
3
x
4
x
5
:
otrzym
ujem
y
,
»e
P
ar
(0;1;1;0;0)
((1;
0;
0;
1;
1))
=
0
oraz
P
ar
(1;0;1;0;0)
((1;
0;
0;
1;
1))
=
1.
Zad
anie
5.11.
Dla
w
ektoró
w
x
=
(0;
1;
1);
r
1
=
(0;
0;
1);
r
2
=
(0;
1;
0);
r
3
=
(1;
0;
1);
r
4
=
(1;
1;
0),
p
oli zy¢
P
ar
(x)
i
P
ar
r
i
(x);
i
=
1;
2.
Przykªad
5.12.
Dan
y
jest
w
ektor
x
=
(0;
1;
1).
Dla
jaki
h
w
ektoró
w
r
2
B
3
,
P
ar
r
(x)
=
1?
R
ozwi¡zanie
5.12.
Zgo
dnie
z
de ni j¡
otrzym
ujem
y
,
»e
P
ar
(r
1
;r
2
;r
3
)
((0;
1;
1))
=
3
M
i=1
(x
i
^
r
i
)
=
(0
^
r
1
)
(1
^
r
2
)
(1
^
r
3
)
=
0
r
2
r
3
=
r
2
r
3
=
1:
Ró
wno±¢
ta
p
o
i¡
ga
za
sob¡,
»e
alb
o
r
2
=
1
i
r
3
=
0
lub
r
2
=
0
i
r
3
=
1;
zau
w
a»m
y
,
»e
r
1
jest
do
w
olne.
Zatem
szuk
ane
r
2
f(0;
0;
1);
(1;
0;
1);
(0;
1;
0);
(1;
1;
0)g.
Zad
anie
5.13.
Dane
s¡
2
w
ektory:
a)
x
=
(1;
0;
1)
i
y
=
(0;
1;
0).
Dla
jaki
h
w
ektoró
w
r
2
B
3
mam
y
P
ar
r
(x)
=
P
ar
r
(y
)?
b)
x
=
(1;
1;
0)
i
y
=
(0;
0;
1).
Dla
jaki
h
w
ektoró
w
r
2
B
3
mam
y
P
ar
r
(x)
=
P
ar
r
(y
)?
)
x
=
(0;
1;
0)
i
y
=
(0;
0;
1).
Dla
jaki
h
w
ektoró
w
r
2
B
3
,
P
ar
r
(x)
6=
P
ar
r
(y
)?
42
Wyszukiwarka
Podobne podstrony:
13 Funkcje boolowskie, informatyka
Matematyka dyskretna 2002 05 Funkcje boolowskie
BANK CENTRALNY I JEGO FUNKCJE
Zaburzenia funkcji zwieraczy
Genetyka regulacja funkcji genow
BYT 2005 Pomiar funkcjonalnosci oprogramowania
Diagnoza Funkcjonalna
Insulinoterapia funkcjonalna
Postać kanoniczna funkcji kwadratowej
Wpływ choroby na funkcjonowanie rodziny
LAB PROCEDURY I FUNKCJE
STRUKTURA I FUNKCJONOWANIE GN
układ pokarmowy budowa i funkcja
15 Fizjologiczne funkcje nerek
funkcja produkcji
więcej podobnych podstron