Контрольная работа по "Спецглавы математики"

Федеральное Агентство  по образованию

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

 

 

 

 

 

 

 

 

 

 

Спецглавы математики 3

Контрольная работа № 6

Вариант № 8

 

 

 

 

 

 

 

Преподаватель    Студент

___________ /____________. / __________ /

 

___________ г.   __________  г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Для формулы (x→y) →z записать двойственную ей и отрицание.

 Сформулировать принцип  двойственности.

 

Решение:

Избавимся от знака →:

¦=(x→y) →z =⌐(x→y)Úz=⌐(⌐xÚy)Úz=(x&⌐y)Úz

Заменим в исходной формуле все знаки (&)*=Ú, (Ú)*=&, (⌐А)*=⌐А    функций на двойственные:

¦*=(xÚ⌐y) &z

Для получения отрицания функции  инвертируем все значения входных  переменных:

¦=(⌐xÚ⌐⌐y) &⌐z=(⌐xÚy) &⌐z

 

Принцип двойственности. Если БФ ¦ можно представить суперпозицией, содержащей знаки функций ¦₁, ¦₂,…, ¦_r, то двойственную БФ ¦ можно представить такой же суперпозицией, но с заменой знаков  ¦₁, ¦₂,…, ¦_r на  

¦*₁, ¦*₂,…, ¦*_r соответственно.

 

2. Записать формулу A→B&C«(A→B) &(A→C) в СДНФ И СКНФ, используя таблицу истинности.

 

Решение:

Построим таблицу истинности.

 

A	B	C	A→B	A→C	1&2	B&C	A→3	5«3
			1	2	3	4	5	6
0	0	0	1	1	1	0	1	1	⌐A⌐B⌐C (СДНФ)
0	0	1	1	1	1	0	1	1	⌐A⌐BC (СДНФ)
0	1	0	1	1	1	0	1	1	⌐AB⌐C (СДНФ)
0	1	1	1	1	1	1	1	1	⌐ABC (СДНФ)
1	0	0	0	0	0	0	0	1	A⌐B⌐C (СДНФ)
1	0	1	0	0	0	0	0	1	⌐AB⌐C (СДНФ)
1	1	0	1	0	0	0	0	1	AB⌐C (СДНФ)
1	1	1	1	1	1	1	1	1	ABC (СДНФ)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СДНФ: ¦= ⌐A⌐B⌐CÚ⌐A⌐BCÚ⌐AB⌐CÚ⌐ABCÚA⌐B⌐CÚ⌐AB⌐CÚAB⌐CÚABC

СКНФ: по теореме 4 функцию, тождественно равную 1, нельзя представить в  СКНФ. Поскольку данная функция ¦≡1, то её нельзя представить в  СКНФ.

 

 

3. Записать полином Жигалкина   для отрицания формулы (x→y) →z.

 

Решение:

Для формулы ¦ =(x→y) →z в задании №1 было получено её отрицание:

¦ =(⌐xÚy) &⌐z

Зададим БФ  ¦ с помощью таблицы. По определению отрицания булевы функции ¦ и ¦  на одинаковых наборах списка переменных будут принимать противоположные значения. Поэтому для получения таблицы БФ  ¦   заменим значения таблицы ¦ на противоположные. В строках таблицы, где БФ ¦ принимает значение единица, запишем ПЭК:

 

 

x	y	z	¦	¦	СДНФ
0	0	0	0	1	⌐x⌐y⌐z
0	0	1	1	0
0	1	0	0	1	⌐xy⌐z
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	0	1	xy⌐z
1	1	1	1	0

 

 

 

 

 

 

 

 

 

 

 

СДНФ для БФ ¦ построена:  ⌐x⌐y⌐z Ú  ⌐xy⌐z Ú xy⌐z.

Заменим знак Ú на ⊕ и заменим отрицание.

(x⊕1)(y⊕1)(z⊕1)⊕(x⊕1)y(z⊕1)⊕xy(z⊕1)=

=(xy⊕x⊕y⊕1)(z⊕1)⊕(xy⊕y)(z⊕1)⊕(xyz⊕xy)=

= xyz⊕xz⊕xy⊕z⊕xy⊕x⊕y⊕1⊕xyz⊕yz⊕xy⊕y⊕xyz⊕xy=

= xyz⊕xz⊕xy⊕z⊕x⊕y⊕1⊕yz = 1⊕x⊕y⊕z⊕xy⊕xz⊕yz⊕xyz.

При этом a₀=1, a₁ =1, a₂ =1a₃ =1, a₁₂ =1, a₁₃ =1, a₂₃ =1, a₁₂₃ =1.

 

4. Определить принадлежность функций системы пяти замкнутым классам. Проверить выполнение условий теоремы Поста для системы БФ:

f₁=x⊕y⊕z, f₁=xy, f₃=1, f₄=0. 

 

Решение:

а) Определим, принадлежат ли функции системы  классу Т₀:

f₁(0,0,0)=0⊕0⊕0=0, Þ f₁ÎТ₀

f₂(0,0)=0*0=0, Þ f₂ÎТ₀

f₃=1, Þ f₃ÏТ₀

f₄=0, Þ f₄ÎТ₀

 

б) Определим принадлежат ли функции  системы классу Т₁:

f₁(1,1,1)=1⊕1⊕1=0, Þ f₁ÏТ₁

f₂(1,1)=1*1=1, Þ f₂ÎТ₁ 

f₃=1, Þ f₃ÎТ₁ 

f₄=0, Þ f₄ÏТ₁ 

 

в) Определим, принадлежат ли функции  системы классу S

Очевидно, что  f₁ÏS, и f₂ÏS, и f₃ÏS, и f₄ÏS   т. к.

      f*(x₁,…, x_n)¹f(x₁,…, x_n).

 

г) Определим, принадлежат ли функции  системы классу L. Для этого построим полиномы Жигалкина для каждой функции системы.

f₁(x,y,z)= x⊕y⊕zÎL, т.к. ее полином Жигалкина первой степени

f₂(x,y)=xyÏL, т. к. ее полином Жигалкина второй степени

f₃=1, степень полинома равна 0, следовательно f₃ÎL

f₄=0, степень полинома равна 0, следовательно f₄ÎL .

 

д) Определим, принадлежат ли функции  системы классу М.

Функция f₁ зависит от 3-х переменных (n=3) и между двоичными словами установлен следующий частичный порядок:

        111

 

110                                                      011

     101

 

  100   010   001

000

При (011)³(001)

Условие f₁ (0,1,1)> f₁(0,0,1) не выполняется, т.к.

f₁(0,1,1)= 0⊕1⊕1=0

f₁(0,0,1)= 0⊕0⊕1=1, следовательно f₁ Ï М.

 

Функция f₂ зависит от 2-х переменных (n=2) и между двоичными словами уставлен следующий частичный порядок:

  11

01                                                               10 

00

 

Для f₂ (x,y)=xy запишем порядок значений

 

   1

0 0

 

 

   0

 

Имеем, что f₂ (1,1)> f₂ (0,1), f₂(1,1)> f₂(1,0), f₂(1,0)= f₂(0,0), f₂(0,1)= f₂(0,0).

Следовательно функция f₂ Î М.

Очевидно, что f₃Î М, f₄Î М.

Занесем данные в таблицу

	T0	T1	S	L	M
f1	+	-	-	+	-
f2	+	+	-	-	+
f3	-	+	-	+	+
f4	+	-	-	+	+

 

Система БФ будет полной, если в  каждом столбце таблицы встретится хотя бы один знак «-», таким образом, система БФ – полная система.

Применим док-во теоремы Поста: построим с помощью функций  f₁, f₂, f₃, f₄ конъюнкцию и отрицание.

Т.к. f₃ÏТ₀, f₄ÎT₁, то согласно 1-у шагу док-ва теоремы 7, j(x)= f₃ º1 и

y(x)= f₄º0, т.е. имеет наличие случай г). Для построения отрицания найдем немонотонную функцию – это функция f₁.

Выбираем два соседних набора (0,0,1) и (0,1,1).

При этом f₁ (0,0,1)=1, а f₁ (0,1,1)=0.

Тогда x = f₁ (0,x,1).

Выполним подстановку x = f₁ (f₄,x, f₃).

Тогда x=0ÅxÅ1.

Теперь построим конъюнкцию. Нелинейной является функция f₂. Ее полином Жегалкина  имеет вид – f₂ =xyÅ0ÅxÅ0ÅyÅ0 (т.е. a=0, b=0, d=0). Поэтому преобразование

x₁x₂=m(x₁Åb, x₂Åa)ÅabÅd означает в нашем случае m(x₁Å0, x₂Å0)Å0Å0,

т.е. f₂ (x,y)= f₁ (f₄, f₂(x,y), f₃)

        = f₁ (f₄, f₂(x,y), f₃)= 0ÅxyÅ1= xy = x&y.

Конъюнкция и отрицание представлены в виде суперпозиций функций f₁ = xÅyÅz, f₂ = xy, f₃ =1, f₄ =0, следовательно любую БФ можно представить в виде суперпозиции этих функций, т.е. {Å, &1, 0} – полная система.

  

5. Минимизировать БФ: f(x,y,z,t)=å(0,1,3,8,9,12,13,11).

 

Решение:

Карта Карно для f(x,y,z,t) имеет вид

       x₁

1
1
1	1	1	1
1			1

               x₂                             

                                                       x₄

 

 

                         x₃

 
Можно склеить три «четверки» единиц.

При этом получим следующие ЭК:

при склеивании вертикальной четверки:

 x₁x₂⌐x₃⌐x₄ Ú x₁⌐x₂⌐x₃⌐x₄ Ú  x₁x₂⌐x₃x₄ Ú x₁⌐x₂⌐x₃x₄  = x₁⌐x₃⌐x₄Ú x₁⌐x₃ x₄= x₁⌐x₃

при склеивании горизонтальной  четверки: 

x₁⌐x₂⌐x₃x₄ Ú ⌐x₁⌐x₂⌐x₃x₄ Ú  x₁⌐x₂x₃x₄ Ú ⌐x₁⌐x₂x₃x₄  = ⌐x₂⌐x₃x₄Ú ⌐x₂x₃ x₄= ⌐x₂x₄

при склеивании  четверки (9,8,1,0): 

x₁⌐x₂⌐x₃x₄  Ú⌐x₁⌐x₂⌐x₃x₄ Ú  x₁⌐x₂⌐x₃⌐x₄ Ú  ⌐x₁⌐x₂⌐x₃⌐x₄=

=⌐x₂⌐x₃x₄ Ú⌐x₂⌐x₃⌐x₄=⌐x₂⌐x₃

Таким образом

f(x₁,x₂ ,x₃ ,x₄) = x₁⌐x₃ Ú ⌐x₂x₄ Ú ⌐x₂⌐x₃

 

6. Провести синтез  схемы, реализующей БФ f(x,y,z)=(x®y) ®(x®z). Оптимизировать по числу ФЭ, если это возможно.

 

Решение:

Решим в начале вопрос о существовании  такой СФЭ. Система БФ {Ú,&,Ø} является полной, поэтому задача имеет решение.

Представим f(x,y,z) таблицей, а затем запишем ее в СДНФ.

 

x	y	z	f(x,y,z)	ПЭК
0	0	0	1	ØxØyØz
0	0	1	1	ØxØyz
0	1	0	1	ØxyØz
0	1	1	1	Øxyz
1	0	0	1	xØyØz
1	0	1	1	xØyz
1	1	0	0
1	1	1	1	xyz

 

 

f(x,y,z)=  ØxØyØz Ú ØxØyz Ú ØxyØz Ú Øxyz Ú xØyØz Ú xØyz Ú xyz

СФЭ, соответствующая этому представлению f(x,y,z) содержит 31ФЭ. Количество ФЭ можно уменьшить. Составим карту Карно данной БФ.

 

	1	1	1
1	1	1	1

 
При склеивании четверок:

(3,2,1,0): Øxyz ÚØxØyz ÚØxyØz ÚØxØyØz = Øxz Ú ØxØz = Øx

(4,5,1,0): xØyØz ÚØxØyØz ÚxØyz ÚØxØyz = Øyz Ú ØyØz = Øy

(7,3,5,1): xyz Ú xØyz Ú Øxyz Ú ØxØyz = xz Ú Øxz = z

 

f(x,y,z) = Øx Ú Øy Ú z.

 

СФЭ, соответствующая форме записи БФ f(x,y,z) = Øx Ú Øy Ú z содержит только 4 ФЭ