Контрольная работа по "Дискретной математике"

11. Составим таблицы истинности формул:

x	y
0	0	0	1	1
0	1	1	0	1
1	0	1	0	1
1	1	0	0	0

 

 

 

 

x	y	z
0	0	0	1	0	1	1
0	0	1	1	1	1	0
0	1	0	1	0	1	1
0	1	1	1	1	1	0
1	0	0	1	0	1	1
1	0	1	1	1	1	0
1	1	0	0	1	0	1
1	1	1	0	1	0	1

 
12. Проверим двумя способами эквивалентность следующих формул:

а) С помощью  составления таблицы истинности:

x	y	z
0	0	0	1	1
0	0	1	1	1
0	1	0	0	1
0	1	1	1	1
1	0	0	1	0
1	0	1	1	0
1	1	0	0	1
1	1	1	1	0

 

 

 

x	y	z	(x|y)	(x|z)
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	0	0
1	1	0	0	1	1
1	1	1	0	0	1

 

	1
1	1
1	1
1	1
1	1
0	0
0	1
1	1
0	1

 

Формулы не эквивалентны, т.к. соответствующие им функции не равны.

б) с помощью приведения формул к СКНФ с помощью эквивалентных преобразований:

 

 

 

СКНФ этих формул и орпорпорапоаророрропорпорорпр                                                                                                    не эквивалентны, а значит и тоже не эквивалентны.

13. С помощью  эквивалентных преобразований приведем  формулы к ДНФ:

 КНФ:

СДНФ:

Добавим к первой конъюнкции , ко второй и третьей :

Используем дистрибутивные законы, получаем:

Удаляем одну из пары одинаковых конъюнкций:

СКНФ:

Добавляем к первой дизъюнкции , ко второй и третьей :

Используем дистрибутивные законы:

Удаляем одну из пары одинаковых дизъюнкций:

 

Построим полином  Жегалкина:

Выписываем СДНФ функции:

Заменяем знак дизъюнкции на суммы Жегалкина :

Вынесем из первой и второй конъюнкций  :

Проделаем замены получим:

Раскрываем скобки:

Вычеркиваем пары одинаковых слагаемых:

Получаем полином  Жегалкина:

14. Найдем сокращенную ДНФ формулы двумя способами:

а) Методам Квайна:

Наборам 0,1,1; 1,0,0; 1,1,0 соответствуют  конъюнкции

Составим дизъюнкции полученных конъюнкций, т.е. составим СДНФ функции:

Теперь с помощью операций склеивания   поглощения приводим ее в такой вид:

 

 

б) С помощью  карт Карно:

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

 

1. (00-); (-01); (1-1).

Соответствующие конъюнкции:

 

Выясним, к какому классу Поста относится данная функция:

Т0	Т1	L	S	M
-	+	-	-	-

 

x	y	z
0	0	0	1		1		1		0			0			1			0		1
0	0	1		0		0		1		0			1			1			1
0	1	0			0		1		1			1			0			0
0	1	1				1		0			0			1			0
1	0	0					1		0			1			1
1	0	1						1		1				0
1	1	0							0			1
1	1	1							1

 

Функция не принадлежит классу Т₀ , т.к. а(0,0,0) не равно нулю, принадлежит к классу T₁, т.к. f(1,1,1)=1, она не линейна, т.к. в полиноме Жегалкина есть такие члены как yz, xz, xyz, не самодвойственна и не монотонна.

16. Выясним, является ли полной система функций, образует ли она базис.

Построим векторы функций:

f₁={1101}; f₂ ={1000}.

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

 

x	y
0	0	1		1		0		1
0	1		0		1		1
1	0			1		0
1	1			1

x	y
0	0	1		0		0		0
0	1		1		0		0
1	0			1		0
1	1			1

 

 

Построим базис: