Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/TDF/ZadachiDM2008.doc Дата изменения: Tue Jun 10 11:03:18 2008 Дата индексирования: Mon Oct 1 22:08:06 2012 Кодировка: koi8-r Поисковые слова: m 5

P2


1 Задачи на «3»


Выделить базис в [A]:

_
A = { 0, 1, x, x }

A = { 1, x+y+z+1 }


Самодвойственна ли функция f?

_ _ _ _
f = (x V y V z)t V xyz

f = (0001 0010 0110 0111)


Линейна ли функция f?

f = x1x2(x1+x2)

f = (x1x2 V x1x2)+x3

f = (x1(x2)(x2(x1)~x3

f = (1010 1010 0110 1000)

f = (1001 0110 1001 0110)

Является ли A базисом в L?

A = { 1, x+y }

A = { x~y, x+y+z }


Подсчитать число функций от n переменных в множестве:

L\(T0(T1)

T0\S

S(T1


Содержит ли замыкание множества A ( P2 функцию f:

_ _ _

A={ x y V x y, x }

f=x(y


_

A={ xy, z V xyz }

f=x(y



2 Задачи на «4»


Выделить базис в [A]:

A = { x V y, xyz, x V yz (x V y)z }

A = { (x(y)((y(z), x V y V (y+z) }

A = { xy, x V y, x(y, x+y+z+u }


Является ли A базисом в L?

A = { 0, x+y+z+1 }

A = { x+y+z+1, x+y+z }

Подсчитать число функций от n переменных в множестве:

L(S(T1

S\(T0 U T1)


Из функции f подстановкой x и x получить константу:

f = (00111001)
_ _
f = (x V y V z)t V xyz

f = xy V xz V yt V zt


Исследовать систему на полноту в P2:

{ xy V yz V xz, x+y+z, x(y, 0}


{ xy + yz + xz, x V y V z, x(y, 0}


{ xy+z, (x~y)+z }

_____

{ x(y, x+y+z }

{ x(y, (1100 0011 0011 1100)}

{ (1011), (1111 1100 1100 0000) }


3 Задачи на «5»


Исследовать систему на полноту в P2:

(S\M) U (L\(T0 U T1))

(L\S) U (M\(T0 ( T1))

Выделить из системы всевозможные базисы:

_ _
{ (x V y)(x V y), xy+z, (x+y)~z, m(x,y,z) }
_
{ 1, x, xy(y~z), x+y+m(x,y,z) }
_ _
{ m(x,y,z), x V (x+y) V z, (x~y)~z, xy+zu }


Pk


1 Задачи на «3»


Представить функцию в 1-й и 2-й формах

1) ~x, k=5


2) min(x,y,), k=3


3) x2 • y2, k=4



Представить функцию в виде многочлена

1) Jk-2(x), k=5


2) j1(x2-x), k=5

Проверить эквивалентность формул в Pk

1) (x+2)(x+y+1) и j0(x)J0(y)+J0(x)J1(y)+J1(y)J2(x)+J2(x)j2(y), k=3


2) x2+2xy+2y+2 и 2J0(x)J0(y)+J1(x)J1(y)+J0(x)J1(y)+2J1(x)J2(y), k=3


3) (x2+3)(y2+3y+2) и 2J0(x)J0(y)+2J0(x)J1(y)+2J0(y)J2(x)+2J1(y)J2(x),
k=4


4) xy(xy+x+2y+2) и 2J1(x)J1(y)+2J1(x)J2(y)+2J1(y)J3(x)+2J2(y)J3(x),
k=4


5) y2+xy+x+2 и 2J0(x)J0(y)+J2(x)J0(y)+2J1(x)J1(y)+J2(x)J1(y), k=4



Исследовать систему на полноту в Pk

1) {max(x+5, xy+y+5), x+2y+j2(x)+6, min(x+1,y)}, k=7


2) {j1(x)+2j2(y)+3j3(z), max(xyz, x+y+z)} , k=8


3) {j2(x)j2(y)+x, max(J4(x)J4(y), J4(4x+4y)), J5(x)+J5(y)+xy}, k=6


4) {J0(x+y+3)+J2(x+y+4)+J4(x+y+5)+J6(x+y+6), x+y+xy,
max(J1(x)+J2(y)+J3(z), xyz)} , k=8


5) {j3(x+y+2xy)+5x, min(J1(5x),5+3y), J4(x)+J6(y)+y}, k=9



Подсчитать число классов сохранения разбиений в Pk

1) k=4


2) k=5



Доказать, что при составном k функция не представима в виде многочлена

1) ji(x), i=0,1,.,k-1


2) max(x,y)



2 Задачи на «4»


Представить функцию в виде многочлена

1) min(x,y), k=3


2) max(x, j2(y)), k=7



Является ли функция шефферовой

1) (x+1)(y+1)+j1(x)+J1(x)j3(y)+j3(x)j1(y)+j1(y)+j2(x)+1, k=4


2) (x+2)(y+4)+j2(y)+j3(x)+2J1(x)j1(y) , k=5


3) (2x+3)(y+1)+J1(x)+J2(x)+J6(x)j6(y)+3j6(x) , k=7


4) (x+1)(y+2)+j1(x)+j1(y)+j2(x)j2(y)+4j1(x)j2(y)+4j2(x)j1(y)+4j5(x)j5(y)
, k=6


5) (x+1)j0(y)+y•j0(x) [ указание: применить критерий Слупецкого ]



Исследовать систему на полноту в Pk

1) {(x+4)(y+2)+j0(y)(x+6)+j3(y)(x+5), min(xy, x+2)} , k=8


2) {3, j3(x), x+yz}, k>3


3) {x+2y+4z+1, j2(x)} , k=5


4) {J4(x), xy+z+y, j0(x)} , k>4


5) {1,x+y+xz}, [ ответ: полна, если k - простое ]



Представима ли функция в виде многочлена

1) 3j0(x), k=6


2) (max(x,y)-min(x,y))2, k=4


3) min(x,y), k=100

3 Задачи на «5»


Полна ли система A\{f}, где A={0, 1,., k-1, J0(x), J1(x),., Jk-1(x),
min(x,y), max(x,y)}

1) f= J0(x) [ ответ: f=J1(max(1,J1(x),.,Jk-2(x),x)) ]


2) f= Jk-1(x) [ ответ: f=J0(max(J0(x),.,Jk-2(x))) ]



Автоматы


1 Задачи на «3»


Является ли отображение f :E2*( E2* О.Д.Ф., если да, найти ее вес:

y(t+1)=x(t+1) V y(x(t))

y(0)=0

y(1)=1

..................................................
y(t+1)=x(t+1) & y(x(t))

y(0)=0

y(1)=1

..................................................
y(1)=y(2)=1

y(t)=x(t-2)



2 Задачи на «4»


Является ли отображение f :E2*( E2* О.Д.Ф., если да, найти ее вес:

y(2t)=x(t+1)
y(2t-1)=x(t)+1
..................................................
y(1)=1
y(2t-1)=x(2t-1)+y(2t-3)
y(2t)=x(2t-1)


Доопределить частичный оператор до О.Д.Ф. с минимально возможным весом:

((0()=0101[100]( , ((1()=11[10](

((0()=00[101]( , ((1()=110[110](


Построить диаграмму Мура и систему канонических уравнений для ОДФ:

y(t+1)=x(t+1)y(t) V x(t+1)x(t) V x(t)y(t)

y(0)=0

..................................................
y(t+1)=x(t+1)y(t) + x(t+1)x(t) + x(t)y(t)

y(0)=0



ОДФ (1 и (2 имеют веса r1 и r2 соответственно. Может ли вес суперпозиции
(1((2) быть больше r1r2? меньше r1? меньше r2?


3 Задачи на «5»


Доопределить частичный оператор до О.Д.Ф. с минимально возможным весом,
построить диаграмму Мура и систему канонических уравнений:

((0()=1(, ((1[0]()=[10](

(([011010]()=[0111](, ((0[1]()=0[1](

((1[10]()=[01](, (([001]()=1[10](

y(3t-1)=x(3t-1), y(3t)=x(3t-1)+1


Реализовать ОДФ схемой над множеством из единичной задержки и штриха
Шеффера:

y(t)=(x(t) V q1(t-1))(q2(t-1)
q1(t)=x(t)(q2(t-1)
q2(t)=(q1(t-1)+1) V (q2(t-1)+1)
q1(0)=q2(0)=1
..................................................
y1(t)=x(t)((q1(t-1)+1)
y2(t)=q1(t-1)&q2(t-1)
q1(t)=x(t)+1
q2(t)=(q1(t-1) V q2(t-1))&(x(t)+1)
q1(0)=q2(0)=0


Найти вес ОДФ, получающейся из заданной введением обратной связи по x3 и
y2:

y1(t)=x1(t)((x3(t)(q(t-1))
y2(t)=x2(t) ( x1(t)
q(t)=x2(t) ( ( x1(t)(x3(t)+1) ( (x1(t) ( q(t-1)) )
q(0)=0
..................................................
y1(t)=x1(t)x3(t)(q(t-1)
y2(t)=x2(t)q(t-1)
q(t)=(x2(t)+1) V x3(t) V q(t-1)
q(0)=0