ЗАДАЧИ И УПРАЖНЕНИЯ IIГО – ТИПА 1 страница

Содержание

Содержание. 2

ЗАДАЧИ И УПРАЖНЕНИЯ I^ГО – ТИПА. 3

Задание 1: 3

ЗАДАЧИ И УПРАЖНЕНИЯ II^ГО – ТИПА. 6

Задание 1: 6

Задание 2: 17

Задание 3: 18

Задание 4: 19

Задание 5: 21

ЗАДАЧИ И УПРАЖНЕНИЯ III^ГО – ТИПА. 22

Задание 1: 22

Задание 2: 24

Задание 3: 25

Задание 4: 29

Задание 5: 30

ЗАДАЧИ И УПРАЖНЕНИЯ IГО – ТИПА

Задание 1: Найти минимальную ДНФ функции , принимающей значение 1 на наборах с номерами от 0 до 7, от 11 до 21 и от 26 до 31.

Решение:

запишем исходную ФАЛ:

Далее необходимо произвести минимизацию данной ФАЛ любым из ранее изученных методов. Я решил использовать метод Квайна-Мак-Класки:

запишу исходные импликанты данной функции в виде их двоичных кодов (каждому члену ставится в соответствие по известному правилу его собственная вершина). Все множество так записанных импликант разобью по числу единиц в их кодах на группы. При этом в -ю группу войдут коды, имеющие в своей записи единиц. Попарное сравнение импликант достаточно производить только между соседними группами, т.к. только эти группы отличаются одним знаком в кодах входящих в них членов. Сравнивая коды членов соседних групп, образую члены низшего ранга. На месте исключенного знака запишу в них “тире”. Затем всю совокупность членов низшего ранга вновь разобью на группы по местоположению знака “тире”. Снова произведу сравнение членов соседних групп, но уже внутри групп, образуя члены низшего ранга по тому же правилу и т.д.

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания	Результаты 3-го склеивания
Коды	группы	Коды	Коды	Коды	Коды
	0-я	00000*	0000-	1-я	-0000*	000--*	00---
	1-я	00001*	000-0		-0001*	00-0-*	-00--
		00010*	00-00		-0010*	-000-*	-0-0-
		00100*	-0000		-0100*	00—0*	0-1--
		10000*	000-1		-0011*	-00-0*	--10-
	2-я	00011*	00-01		-0101*	-0-00*	-11--
		00110*	-0001		-1100*	00—1*
		01100*	0001-		-1011*	-00-1*
		10001*	00-10		-1101*	-0-01*
		10010*	-0010		-1110*	00-1-*
		10100*	0010-		-1111*	-001-*
	3-я	00111*	001-0	2-я	0-100*	001--*
		01011*	0-100		0-011*	0-10-*
		01101*	-0100		0-101*	-010-*
		01110*	1000-		0-110*	0-1-0*
		10011*	100-0		1-010*	--100*
		10101*	10-00		1-100*	100--*
		11010*	00-11		0-111*	10-0-*
		11100*	0-011		1-011*	0—11
	4-я	01111*	-0011		1-101*	--011
		11011*	001-1	3-я	00-00*	0-1-1*
		11101*	0-101		00-01*	--101*
		11110*	-0101		00-10*	0-11-*
	5-я	11111*	0011-		10-00*	011--*
			0-110		00-11*	-110-*
			0110-		10-01*	-11-0*
			011-0		01-11*	1-01-
			-1100		11-10*	1-10-*
			100-1		11-11*	-1-11
			10-01	4-я	000-0*	-11-1*
			1001-		000-1*	-111-*
			1-010		001-0*	11-1-
			1010-		100-0*	111--*
			1-100		001-1*
			0-111		011-0*
			01-11		100-1*
			-1011		011-1*
			011-1		111-0*
			-1101		111-1*
			0111-	5-я	0000-*
			-1110		0001-*
			1-011		0010-*
			1-101		1000-*
			1101-		0011-*
			11-10		0110-*
			1110-		1001-*
			111-0		1010-*
			-1111		0111-*
			11-11		1101-*
			111-1		1110-*
			1111-		1111-*

Далее строится таблица меток, в нее вписываются исходные и первичные импликанты в виде двоичных кодов. Обработка таблицы меток производится по методу Квайна.

ЗАДАЧИ И УПРАЖНЕНИЯ IIГО – ТИПА

Задание1: Проверить полноту заданной системы функций. Для функционально полной системы выделить базис.

1) F={ , }, где =x y, =x yz,

Таблица истинности:

x	y	z	x y			x yz

Проверка на принадлежность к классам Поста:

P₀- класс функций, сохраняющих нуль (т.е. если f(0,0,...,0)=0, то f принадлежит этому классу).

(0,0,0)=1 ;

(0,0,0)=1 ;

P₁ - класс функций, сохраняющих единицу (т.е. если f(1,1,...,1)=1, то f принадлежит этому классу).

(1,1,1)=1 ;

(1,1,1)=0 ;

S - класс самодвойственных функций, то есть для которых выполняется:
f(x₁,x₂,...,x_n)=f(x₁,x₂,...,x_n).

(0,0,1)=1, (1,1,0)=1 ;

(0,0,1)=1 (1,1,0)= 0 ;

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

(0,1,0) (0,1,1), а набор (0,1,0)<(0,11). Для любых двух наборов и , таких, что , выполняется равенство: .

Данная функция не принадлежит классу монотонных функций, так как значение функции (0,1,0) (0,1,1), а набор (0,1,0)<(0,11). Для любых двух наборов и , таких, что , выполняется равенство: .

L-класс функций, представимых линейным многочленом Жегалкина.

Функция называется линейной, если она представима в следующем виде:

, где коэффициенты , {0,1}, = .

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

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

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

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

( x, y, z ) = x y z=1 0x 1y 0z=1 y.

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

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

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

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

( x, y, z ) = x y z=1 0x 1y 0z=1 y.В результате получаем таблицу вида:

x	y	z	x y	1 y	x yz

Функции , не принадлежат классу линейных функций.

	P0	P1	S	M	L
	-	+	+	+	-
	-	-	-	-	-

Система функций F={ , }, где =x y, =x yz является функционально полной.

Получим базис { }.

2) F={ , , , }, где =xy, =x~yz, =0, =1,

Таблица истинности:

x	y	z		=x y	yz	=x~yz	=0	=1

Проверка на принадлежность к классам Поста:

P₀:

(0,0,0)=0 ;

(0,0,0)=1 ;

(0,0,0)=0 ;

(0,0,0)=1 ;

P₁:

(1,1,1)=0 ;

(1,1,1)=1 ;

(1,1,1)=0 ;