Булевы функции

Функция  f(x,y,z)=(01100011)

I.Представить всеми способами.

II.Представить в виде СДНФ и СКНФ.

III.Представить в виде полинома Жегалкина двумя способами.

IV.Найти существенные и фиктивные переменные двумя способами.

V. Разложить по переменным x и z.

VI. Выяснить, является ли данная функция шефферовой. Если нет, то какую одну функцию надо добавить к ней, чтоб получить полную систему. Единственным ли образом это можно сделать?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнение  теоретической части

I. Представить всеми способами.

    1) Аналитический способ.

          f(x,y,z)= x̄ȳzvy(xvz̄)

 

2)Табличныйспособ.

xyz	f(x,y,z)
000 001 010 011 100 101 110 111	0 1 1 0 0 0 1 1

 

    3)Векторный  способ.

       f(x,y,z)=(01100011)

 

    4) Через  область единичных или нулевых  значений.

       f(x,y,z)=Σ₁(1,2,6,7)= Σ₀(0,3,4,5)

 

     5)Графический  способ.

 

 111

011                    101          110

                        010

001                                      100

000

 

 

6) Через коды  Грея.

  Г₃ :  000,010,011,001,101,111,110,100

 

7) Через карты  Карно.

     {x,y,z}={x}ᴗ{y,z}={y}ᴗ{x,z}={z}ᴗ{x,y}

a) {x}ᴗ{y,z}

б) {y}ᴗ{x,z}

в) {z}ᴗ{x,y}

 

а)

y,z x	00	01	11	10
0	0	1	0	1
1	0	0	1	1

 

 

 

 

б)

x,z y	00	01	11	10
0	0	1	0	0
1	1	0	1	1

 

в)

x,y z	00	01	11	10
0	0	1	1	0
1	1	0	1	0

 

 

II. Представить в виде СДНФ и СКНФ.

  СДНФ = V ⁼ x̄ȳzvx̄yz̄vxyz̄vxyz

^{(δ₁,δ₂,δ₃)}

^{f(δ₁,δ₂,δ₃)=1}

 

   СКНФ = &^{= (х}vyvz)(xvȳvz̄)(x̄vyvz)(x̄vyvz̄)

^{(δ₁,δ₂,δ₃)}

^{f(δ₁, δ₂, δ₃)=0}

 

 

 

 

 

 

 

III. Представить в виде полинома Жегалкина двумя способами.

   1) Метод  таблиц.

f(x,y,z)= (01100011) = ^x̄ȳz+x̄yz̄+xyz̄+xyz=

^{(δ₁,δ₂,δ₃)}

^{f(δ₁, δ₂, δ₃)=1}

= x̄ȳz+yz̄(x̄+x)+xyz = x̄ȳz+yz̄+xyz = z(x̄ȳ+xy)+yz̄ = z((x+1)(y+1)+xy)+y(z+1) =

= z(xy+x+y+1+xy)+xy+y = xz+yz+z+yz+y = xz+z+y

 

2) Метод неопределенных коэффициентов.

f(x,y,z)= ⁼

1) f(0,0,0)=0:=0;

2) f(0,0,1)=1:=1ó=1

3) f(0,1 ,0)=1:=1ó=1;

4) f(0,1,1)=0:=0ó+1+1ó=0;

5) f(1,0,0)=0:=0ó=0;

6) f(1,0,1)=0:=0ó+1=0ó=1;

7) f(1,1,0)=1:=1ó+1=1ó=0;

8) f(1,1,1)=1:=1ó+1+1+1=1ó=0.

Вывод: f(x,y,z)=xz+y+z

IV. Найти существенные и фиктивные переменные двумя способами.

   1) Метод  таблиц.

X: α=(α₂,α₃), что f(0,α₂,α₃) ≠ f(1,α₂,α₃)

α=(0,1) , что f(0,0,1) ≠ f(1,0,1) →  x – существенная

Y: α=(α₁, α₃), что f(α₁,0,α₃) ≠ f(α₁,1,α₃)

α=(0,0), что f(0,0,0) ≠ f(0,1,0) →  y – существенная

Z:α=(α₁,α₂), что f(α₁,α₂,0) ≠ f(α₁,α₂,1)

α=(0,0),что f(0,0,0) ≠ f(0,0,1) →  z – существенная

 

2)Методэквивалентныхпреобразований.

f(x,y,z)=x̄ȳzvx̄yz̄ vxyz̄ vxyz = x̄ȳzvyz̄(x̄ vx) vxyz = x̄ȳzvyz̄ vxyz =

= x̄ȳzvyz̄ vxyzvxy = x̄ȳzvyz̄ vxy = x̄ȳzvy(z̄ vx)

 

 

 

 

V. Разложить по переменным  x и z.

 

1)f(x,y,z)=

^{(δ₁,δ₂)}

 

 

 

 

 

^{(δ₁,δ₂)}

 

 

 

 

^{(δ₁,δ₂)}

 

 

гдеf(0,y,0)= y

f(0,y,1)=y̅

f(1,y,0)=y

f(1,y,1)=y

 

=

 

 

 

 

 

 

 

 

 

 

 
VI. Выяснить, является ли данная функция шефферовой. Если нет, то какую одну функцию надо добавить к ней, чтоб получить полную систему. Единственным ли образом это можно сделать?

 

xyz	f(x,y,z)
000 001 010 011 100 101 110 111	0 1 1 0 0 0 1 1

 

 

 

 

	T0	T1	S	M	L
f(x,y,z)	+	+	-	-	-
	-	-	-	-	-
x̅	-	-
h(x,y,z)	-	-

 

 

 

 

 

1) fÎT₀, т. к. f(0,0,0)=0;

2) fÎТ₁, т.к. f(1,1,1)=1;

3) fÎS, т.к. f(0,0,1)≠f(1,1,0);

4) fÎM, т. к. (0,0,1)≤(0,1,1), но f(0,0,1)>f(0,1,1);

5) fÎL, т.к. f(x,y,z)= xz+ y + z; 
6) Данная функция не является шефферовой, т.к. она содержится в классах

fÎT₀, Т₁.

Добавим функцию gÎT₀,Т₁, где g(x,y,z)=

[{f,g}]=P₂.

7) Это можно сделать не единственным образом. Можно добавить ͞х ÎТ₀, Т₁или h(x,y,z)=(10001110) Î Т₀, Т₁

[{f,͞х }]=P₂

[{f,h }]=P₂.