Контрольная работа по курсу «Дискретная математика»Вариант 99. Используя правила де Моргана, получить ДНФ и упростить ееРешение:19. Даны две функции f₁(x, y), f₂(x, y, z). Требуется: а) для функции f₁(x, y) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. Упростить, если возможно, СДНФ. б) для функции f₂(x, y, z) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную РКС. в) составить таблицу Поста для системы функций f₁(x, y), f₂(x, y, z), проверить полноту системы и выбрать базисы, если она полная.Решение:а) составим таблицу истинности для функции

x	y			СДНФ	СКНФ
0	0	1	1
0	1	0	1
1	0	0	0
1	1	1	0

---

СДНФ – строится на наборах, на которых функция принимает значение 1СКНФ – строится на наборах, на которых функция принимает значение 0Минимизированная ДНФ Полином ЖегалкинаДля n=2 Р(х,у)=а₀+а₁х+а₂у+а₃хуf(0,0)=P(0,0)=1= а₀+а₁*0+а₂*0+а₃*0= а₀, получим а₀=1f(0,1)=P(0,1)=1= а₀+а₁*0+а₂*1+а₃*0= 1+а₂= 1, получим а₂=0f(1,0)=P(1,0)=0= а₀+а₁*1+а₂*0+а₃*0= 1+а₁= 0, получим а₁=1f(1,1)=P(1,1)=0= а₀+а₁*1+а₂*1+а₃*1= 1+1+а₃= 0, получим а₃=0Р(х,у)=1+х – полином Жегалкинаб) составим таблицу истинности для функции

x	у	z				СДНФ	СКНФ
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	0	1	1

---

СДНФ – строится на наборах, на которых функция принимает значение 1СКНФ – строится на наборах, на которых функция принимает значение 0Минимизированная ДНФ =Полином ЖегалкинаДля n=3 Р(х,у,z)=а₀+а₁х+а₂у+а₃z+а₄хy+а₅уz+а₆xz+ а₇xyzf(0,0,0)=P(0,0,0)= а₀=1, получим а₀=1f(0,0,1)=P(0,0,1)= а₀ +а₃z= 1 +а₃= 1 , получим а₃=0f(0,1,0)=P(0,1,0)= а₀ +а₂y= 1 +а₂= 0 , получим а₂=1f(0,1,1)=P(0,1,1)= а₀+а₂у+а₃z+а₅уz=1+1+ а₅ = 1 , получим а₅=1f(1,0,0)=P(1,0,0)= а₀ +а₁x= 1 +а₁= 1 , получим а₁=0f(1,0,1)=P(1,0,1)= а₀+а₁х+а₃z+а₆xz = 1+ а₆= 1 , получим а₆=0f(1,1,0)=P(1,1,0)= а₀+а₁х+а₂у+а₄хy=1+1+ а₄ = 1 , получим а₄=0f(1,1,1)=P(1,1,1)= а₀+а₁+а₂+а₃+а₄+а₅+а₆+а₇ = 1+1+1+1+1+а₇ = 1 , получим а₇=0Р(х,у,z)=1+y+xy+yz+xyz– полином ЖегалкинаНайдем минимизированную ДНФ с помощью карт КарноОбласть 1:

yz x	00	01	11	10
0	1	1	1	0
1	1	1	1	1

К1: хОбласть 2:

yz x	00	01	11	10
0	1	1	1	0
1	1	1	1	1

К2:

---

Область 3:

yz x	00	01	11	10
0	1	1	1	0
1	1	1	1	1

К3: Минимизированная ДНФ: Построим РКСв) таблицы Постадля функции Класс T₀Функция принадлежит классу T₀, если на нулевом наборе она сохраняет 0.На нулевом наборе значение функции f(0,0)=1, поэтому функция не принадлежит классу T₀.Класс T₁Функция принадлежит классу T₁, если на единичном наборе она сохраняет 1. На единичном наборе значение функции f(1,1)=0 поэтому функция не принадлежит классу T₁.Класс LФункция принадлежит классу линейных функций (L), если её полином Жегалкина не содержит произведений. Полином Жегалкина функции: не содержит произведений, поэтому функция принадлежит классу L.Класс MФункция принадлежит классу монотонных функций (M), если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β). Сравним соседние наборы по первой переменнойСравним значения {1} и {1}: условие монотонности выполнено.Сравним значения {0} и {0}: условие монотонности выполненоСравним соседние наборы по второй переменнойСравним значения {1,1} и {0,0}: условие монотонности нарушеноТаким образом функция не принадлежит классу M.

---

Класс SФункция принадлежит классу самодвойственных функций (S), если на противоположных наборах она принимает противоположные значения. Проверим значения на наборах {0, 0} и {1, 1}: 1 и 0 противоположны. Проверим значения на наборах {0, 1} и {1, 0}: 1 и 0 противоположны Поэтому функция принадлежит классу SПостроим таблицу

	T0	T1	L	M	S
	-	-	+	-	+

для функции Класс T₀Функция принадлежит классу T₀, если на нулевом наборе она сохраняет 0.На нулевом наборе значение функции f(0,0,0)=1, поэтому функция не принадлежит классу T₀.Класс T₁Функция принадлежит классу T₁, если на единичном наборе она сохраняет 1. На единичном наборе значение функции f(1,1,1)=1 поэтому функция принадлежит классу T₁.Класс LФункция принадлежит классу линейных функций (L), если её полином Жегалкина не содержит произведений. Полином Жегалкина функции: Р(х,у,z)=1+y+xy+yz+xyz содержит произведения, поэтому функция не принадлежит классу L.Класс MФункция принадлежит классу монотонных функций (M), если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β). Сравним соседние наборы по первой переменнойСравним значения {1} и {1}: условие монотонности выполнено.Сравним значения {0} и {1}: условие монотонности выполненоСравним значения {1} и {1}: условие монотонности выполнено Сравним значения {1} и {1}: условие монотонности выполненоСравним соседние наборы по второй переменнойСравним значения {1,1} и {0,1}: условие монотонности нарушеноТаким образом функция не принадлежит классу M.Класс SФункция принадлежит классу самодвойственных функций (S), если на противоположных наборах она принимает противоположные значения. Проверим значения на наборах {0, 0, 0} и {1, 1, 1}: 1 и 1 совпадают. Поэтому функция не принадлежит классу SПостроим таблицу

	T0	T1	L	M	S
	-	+	-	-	-

---

Смотрите также файлы

• 1 Понятие уголовного права и его источники. Ук рф его задачи и структура.docx

• Великая отечественная война.docx

• Что такое функция. Пример. Способы задания функции. Область определения функции. Сложная функция. Пример.docx

• Oлимпийские игры, или же Олимпиада, являются международными спортивными соревнованиями. Существуют зимние и летние игры, и каждые проводятся раз в 4 года.docx

• Министерство науки и образования рф фгбоу во государственный аграрный университет северного зауралья.docx