Гаврилов Г.П. Сборник задач по дискретной математике / Г.П. Гаврилов, А.А. Сапоженко.-М.: Наука, 1977, 1991 (2-е изд.,перераб. и доп.), 2004 (3-е изд.,перераб.)

Лабораторные работы по дискретной математике.

Ф.И.О.: Смирнов В.В.

Группа:ИТСС-12

Теоретическая часть.

F(x,y,z)=(01101111)

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

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

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

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

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

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

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

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

xz+xy+x+y+z

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

x,y,z	f(x,y,z)

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

h(x,y,z)=(01101111)

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

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

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

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

f(x,y,z):Г₃:000,010,011,001,101,111,110,100.

f(x):Г₁:01.

f(x,y):Г₂:00,01, 11,10.

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

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

А)

y,z x

Б)

x,y z

В)

x,z y

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

x,y,z	f(x,y,z)

СКНФ:f(x,y,z)=&(x^δ1˅y^δ2˅z^δ3)= (x˅y˅z)(x˅ ˅ )

(δ₁,δ₂,δ₃₎

f(δ₁,δ₂,δ₃)=0

СДНФ:f(x,y,z)=˅_x^δ1&y^δ2&z^δ3= x͞yz˅ y ˅x ˅x z˅xy ˅xyz

(δ₁,δ₂,δ₃₎

f(δ₁,δ₂,δ₃)=1

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

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

f(x,y,z)=(01101111)=a₁xyz+a₂xy+a₃xz+a₄yz+a₅x+a₆y+a₇z+a₈

1. f(000)=0: a₈=0

2. f(001)=1: a₇+a₈=1óa₇=1

3. f(010)=1: a₆+a₈=1óa₆=1

4. f(011)=0: a₄+a₆+a₇+a₈=0ó a₄+1+1=0óa₄=0

5. f(100)=1: a₅+a₈=1óa₅=1

6. f(101)=1: a₃+a₅+a₇+a₈=1óa₃+1+1=1óa₃=1

7. f(110)=1: a₂+a₅+a₆+a₈=1óa₂+1+1=1óa₂=1

8. f(111)=1: a₁+ a₂+ a₃+ a₄+a₅+a₆+ a₇+a₈=1ó a₁+1+1+1+1+1=0óa₁=0

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

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

∑x^δ1y^δ2z^δ3= z+ y +x +x z+xy +xyz= z+ y +x ( +z)+xy( +z)= z+ y +x +xy=

(δ₁,δ₂,δ₃) z+ y +x( +y)= z+ y +x=(x+1)((y+1)z+y(z+1))+x=(x+1)(yz+z+yz+y)

f(δ₁,δ₂,δ₃)=1 +x=(x+1)(z+y)+x=xz+xy+z+y+x

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

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

x: f(0,λ₂,λ₃)≠f(0,λ₂,λ₃)

f(000)≠f(100)=>x существенный

y: Ǝ =(λ₁,λ₃),что f(λ₁,0,λ₃)≠f(λ₁,0,λ₃)

Ǝ =(0,0),что f(000)≠f(010)=>y существенный

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

Ǝ =(0,0),что f(000)≠f(001)=>z существенный

Метод эквивалентных преобразований.Записать функцию в аналитической форме СДНФ.

f(x,y,z)= z˅ y ˅x ˅x z˅xy ˅xyz= z˅ y ˅x ( ˅z)˅xy( ˅z)= z˅ y ˅x ˅xy=)= z˅y )˅x( ˅y)= z˅y )˅x

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

f(x,y,z)=˅x^δ1&z^δ2f(δ₁,y,δ₂)=x⁰z⁰f(0,y,0)˅x⁰z¹f(0,y,1)˅x¹z⁰f(1,y,0)˅x¹z¹f(1,y,1)= f(o,y,o)˅ zf(

( ,δ₂)

0,y,1)˅x f(1,y,0)˅xzf(1,y,1)=

x^δ1z^δ2f(δ₁,y,δ₂)= f(0,y,0)+ zf(0,y,1)+x f(1,y,0)+xz(1,y,1)=

(δ₁,δ₂)

=&( ˅ ˅f(δ₁,y,δ₂))=( ˅ ˅f(0,y,0))&( ˅ ˅f(0,y,1))&( ˅ ˅f(1,y,0))&( ˅ ˅f(1,y,1))=(x˅z˅f(o,y,o))(x˅ ˅f(0,y,1))( ˅z˅f(1,y,0))( ˅ ˅f(1,y,1))

f(x,y,z)= (x˅z˅y)(x˅ ˅y) ( ˅z˅1)( ˅ ˅1)

f(0,y,0)=y

f(0,y,1)=

f(1,y,0)=

f(1,y,1)=

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

6.1)

x,y,z	h(x,y,z)

	T0	T­1	S	M	L
h(x,y,z)	+	+	-	-	-
	-	-
	-	-
	-	-

h ϵ T₀ т.к. h(0,0,0)= 0.

h ϵ T₁ т.к. h(1,1,1)=1.

h ϵ S т.к. h(0,0,0)≠h(1,1,1).

h ϵ M т.к. (0,1,1)≥(0,1,0).

Для того, что бы понять h не ϵ L, надо полиному Жигалкина.

h(x,y,z)= xz+xy+z+y+x

h ϵ L т.к. h(x,y,z)=xz+xy+x+y+z

h(x,y,z) не является шефферевой, т.к. h ϵ T₀,T₁.

6.2)

Добавляем f которая ϵ Т₀,T₁, где f(x,y,z)= .

[{h,f}]=P₂ по теореме о полноте.

6.3)

Получить полную систему можно не единственным образом т.к. можно добавить не одну функцию, а несколько, например: , .

Литература

Яблонский, С.В. Введение в дискретную математику/ С.В.Яблонский. –М.: Наука, 1979, 1986 (2-у изд., перераб. И доп.),2001(3-е изд.,стер.).

Гаврилов Г.П. Сборник задач по дискретной математике / Г.П. Гаврилов, А.А. Сапоженко.-М.: Наука, 1977, 1991 (2-е изд.,перераб. и доп.), 2004 (3-е изд.,перераб.).

3) Михеева, Е.А. Индивидуальные задания для математического практикума на ЭВМ по <<Дискретной математике>>: методические указания / Е.А.Михеева.- Ульяновск: фМГУ, 1995.- 49 с.