praktikum-4

							11
	Задача 8.	В данной			формуле	y z y x перейти к
формулам в базисах:							4) x, x y ;
1) x, xy ; 2)		x, x		y ;	3) x, x y ;
5)	x, x y ;	6) x y, x y, 1 ;				7) x y , xy, 0 ;
8)	x y , x y, 0 2.

Решение.

Так как заданные системы функций являются базисами, то через базисные функции можно выразить любую функцию ал-

гебры логики, в том числе и заданную f y z y x .

1) Так как в базисе x, xy отсутствует дизъюнкция, то из законов де Моргана выразим ее через базисные функции, а именно x y x y . Тогда можно выразить заданную функцию

в данном базисе:

f y z y x yz yx .

2) Выразим конъюнкцию и дизъюнкцию через функции базиса x, x y , а именно x y x | y , x y x y x | y . Поэтому заданная функция в новом базисе примет вид:

fy z y x y | z y | x y | z | y | x .

3)Из законов де Моргана выразим конъюнкцию через

функции базиса x, x y , получим x y x y . Тогда исход-

ная функция в новом базисе примет вид:

f y z y x y z y z .

4) Выразим конъюнкцию и дизъюнкцию через функции базиса x, x y , то есть x y x y , x y x y x y . То-

гда исходная функция в новом базисе примет вид:

f y z y x y z y x y z y x .

2 Напомним, что x y x y , x1 x , x0 x .

Практикум-4

Елкина Н. В.

примет вид:

12

5) Известно, что x y x y (можете убедиться самостоятельно, составив таблицы этих функций). Тогда можем вы-

разить конъюнкцию		и дизъюнкцию через		функции базиса
x, x y ,	при	этом	получим:	x y x y ,

x y x y x y . Тогда исходная функция в новом базисе примет вид:

fy z y x z y y x z y y x .

6)Выразим отрицание и конъюнкцию через функции базиса

x y, x y, 1 , а именно x x 1, x y x yx 1 y 1 1. Тогда исходная функция в новом базисе

f y z y x y z 1 y 1 xy z 1 1 y 1 x 1 1.

7) Выразим отрицание и дизъюнкцию через функции базисаx y , xy, 0 , получим: x x0 , x y x y x0 y0 0 . Тогда исходная функция в новом базисе примет вид:

		0	z		0 0	0			y	0	0		0	0		y	0	0	yx	0	.
f y z y x y											x							z
8) Выразим отрицание и конъюнкцию через функции базиса
x y , x y, 0 , получим:	x x0 ,					x y									x0		y0 0 . Тогда
											x y
исходная функция в новом базисе примет вид:
f y z y x y z 0 y x 0 0
				0 0				0			0	0
y z					y				x			.

Практикум-4

Елкина Н. В.

13

Задачи для самостоятельного решения

1. Какую нужно сделать подстановку на места переменных

в немонотонных функциях: а) f			x y z , б)	f xy z ,
чтобы получить отрицание x ?
2.	Определить,	какие	из переменных	функций:
~	11011000 , б)	~
а) f x		f x 1000 1101 0010 1100 следует

заменить на x , а какие на x	с тем, чтобы получить константу.
3. Подставляя на места переменных нелинейных функций:
~	~
а) f x 11010101 , б) f x 11001110 какие-либо функ-

ции из множества 0,1, x, y , получить хотя бы одну из функций xy , xy , x | y .

	4. Полна ли данная система функций?
а)	N1 1,	x, x y z x y z , x y ;
б) N2 x,		x y z yz, x y z .
	5. Доопределить функции до шефферовских.
а)		б)

x, y, z	f
010	0
100	0
101	1

x, y, z	f
100	1
001	0
011	0

6. Являются ли заданные системы базисами в P2 ?

а) N1 x y, x y, x y ; б) N2 x y, x yz .

7. Из полных в P2 систем:
а) N1 1,	x, xy x y , x y xy yz xz ,
б) N2 0,	x y, x y,	xy xz .
выделить всевозможные базисы.			б) y z y x ;
8. В данных формулах:		а) yz y x ;

в) yz yx перейти к формулам в базисах:

Практикум-4

Елкина Н. В.

14

1) x, xy ; 2) x, x				y ; 3) x, x y ; 4) x, x y ;
5)	x, x y ; 6)			x y, x y, 1 ; 7) x y , xy, 0 ;
8)	x y , x y, 0 .
	Ответы
	2. а) f x, x, x 1.
	3.	а) f x, y,0 x y , б)			f x,1, y xy .
	4.	а) Нет, б) Да.

6.а) Нет

7.а) B1 1, x, f , B2 x, xy x y , f , где f x y xy yz xz ,

б) B1 0, x y , B2 x y, x y , B3 0, xy xz , B4 x y, xy xz .

Библиографический список

1.Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учебное пособие.– 3-е изд.– М.: Физ-

матлит, 2005.– 416 с.

2.Тишин В. В. Дискретная математика в примерах и задачах.– СПб.: БХВ-Петербург, 2008.– 352 с.

3.Тарасов В. В., Елкина Н. В. Дискретная математика. Часть 1: Учебное пособие. РГРТУ.– Рязань, 2009.– 92 с.

Практикум-4

Елкина Н. В.