Лабораторный Практикум по Дискрмат2

в)

Вариант 15. а) б)

в)

Вариант 16. а) б)

в)

Вариант 17. а) б)

в)

Вариант 18. а) б)

в)

Вариант 19. а) б)

в)

an 1

2an

bn

b

2a

n

7b .

n 1

n

an 3

3an 2

4an 1

12an

0 ;

an 4

2an 3

2an 1

an

0 ;

an

1

an

bn

b

1

a

n

3b .

n

n

an 3

an 2

3an 1

3an

0 ;

an 4

an 3

an 1

an

0 ;

an 1

an

bn

b

a

n

3b .

n 1

n

an 3

2an 2

3an 1

6an

0;

an 4

8an 3

18an 2

16an

0 ;

an 1

2an

bn

b

a

n

3b .

n 1

n

an 3

an 2

2an 1

2an

0 ;

an 4

4an 3

3an 2

4an 1

4an

0 ;

an 1

2an

bn

b

1

2a

n

3b .

n

n

an 3

2an 2

2an 1

4an

0;

an 4

8an 3

22an 2

24an 1

9an

0 ;

an 1

2an

bn

b

3a

n

2b .

n 1

n

Вариант 20.

а) an 3 3an 2 2an 1 6an 0 ;

81

б) an 4 4an 3 2an 2 12an 1 9an 0;

в)

an 1

an

bn

.

b

a

n

3b

n 1

n

Вариант 21.

а) an 3

2an 2

3an 1

6an

0 ;

б) an 4

10an 3

37an 2

60an 1

36an

0 ;

an 1

3an

bn

в)

b

2a

n

b .

n 1

n

Вариант 22.

а) an 3

an 2

an 1 3an

0 ;

б) an 4

6an 3

8an 2

6an 1

9an

0 ;

an 1

3an

bn

в)

b

3a

n

2b .

n 1

n

Вариант 23.

а) an 3

2an 2

3an 1

6an

0 ;

б) an 4

10an 3

36an 2

54an 1

27an

0 ;

an 1

3an

bn

в)

b

4a

n

b .

n 1

n

Вариант 24.

а) an 3

4an 2

3an 1

12an

0;

б) an 4

4an 3

an 2

8an 1

4an

0;

an 1

2an

bn

в)

b

2a

n

3b .

n 1

n

Вариант 25.

а) an 3

2an 2

3an 1

6an

0;

б) an 4

4an 3

5an 2

36an 1 36an

0 ;

an 1

3an

bn

в)

b

5a

n

2b .

n 1

n

82

Практическое занятие № 1

ЛОГИЧЕСКИЕ ФУНКЦИИ. ОСНОВНЫЕ СВОЙСТВА ЛОГИЧЕСКИХ ФУНКЦИЙ. ПОЛНЫЕ СИСТЕМЫ ЛОГИЧЕСКИХ ФУНКЦИЙ

Цель работы

Построить совершенные формы для данных логических функций. Построить суперпозицию данных функций. Для данной логической функции построить полином Жегалкина.

Краткая теория

Логической (булевой) функцией называется любая функция, заданная

на множестве {0, 1}n с областью значений {0, 1}. Согласно определению понятия логической функции, существуют только четыре функции от одного аргумента: две функции, являющиеся логическими константами f (x) 0 , f (x) 1, тождественная функция f (x) x и ее отрицание f (x) x . Других функций от одного аргумента не существует.

Все существующие логические функции от двух аргументов можно перечислить при заполнении таблицы 1. Таких функций ровно 16. В таблице 3 приведены 14 функций. Существуют еще две – это функции

g0(x, y) = 0 и g15(x, y) = 1. Других логических функций от двух аргументов не существует. Число логических функций от п переменных определяется

аналогичным их перечислением и равно 22n . Сравнивая логические значения функций, приведенных в таблице 3, с таблицами истинности основных логических операций алгебры высказываний легко заметить, что

g1(x, y) = x y, g7(x, y) = x y, g13(x, y) = x y, g9(x, y) = x y. Для многих других логических функций от двух аргументов существуют специальные

обозначения: g6(x, y) = x							y, g8(x, y) = x				y, g14(x, y) = x| y.
																Таблица 1
					Логические функции от двух аргументов
	х	у	g1	g2	g3	g4	g5	g6	g7		g8	g9	g10	g11	g12		g13	g14
	0	0	0	0	0	0	0	0	0		1	1	1	1	1		1	1
	0	1	0	0	0	1	1	1	1		0	0	0	0	1		1	1
	1	0	0	1	1	0	0	1	1		0	0	1	1	0		0	1
	1	1	1	0	1	0	1	0	1		0	1	0	1	0		1	0

83

Логические функции настолько тесно связаны с формулами алгебры высказываний, что иногда их отождествляют. Однако отождествлять логические функции и формулы алгебры высказываний не следует. Все формулы алгебры высказываний, имеющие одинаковые таблицы истинности, то есть, равносильные формулы, представляются всего одной логической функцией. В этом выражается их отличие, а связь между ними характеризуется тем, что многие свойства основных логических операций алгебры высказываний по существу повторяются как свойства логических функций. Перечислим эти свойства, а также свойства некоторых новых функций от двух аргументов.

Основные свойства логических функций

1.

x

y = y x;

18. x

y = y

x;

2.

(x

y)

z = x

(y

z);

19. (x

y)

z = x

(y

z);

3.

x

(y

z) = (x y)

(x

z);

20. x

(y

z) = (x

y)

(x z);

4.

x

(x y) =x;

21. x

(x y) =x;

5.

x ( x

y) =x y;

22. x

( x

y) =x y;

y ;

y ;

6.

x

y = x

23.

x

y

x

7.

x

x

=0;

24.

x

x =1

8.

x

1 = x;

25. x

1 =1

9.

x

x = x;

26. x

x =x

y = x

10. x = x

;

27. x

y;

11. x

y = (x

y)

(y

x);

28. x

y = y

x ;

12. x

y=y

x;

29. x

(y

z) = (x

y)

z;

13. x

(y

z) = (x y) (x z);

30. x

y =x

y

x

y ;

14. x

x =0;

31. x

0 = x;

15. x

y = x

y ;

32. x|y = x

y ;

16. x

y = (x|y)|(x|y);

33. x

y = (x|x)|(y|y);

17.

x =x|x;

34.

x = x

1.

Формулами

над

множеством

логических

функций

,',

,

,

,

, |,

называются выражения следующего вида:

1)

любая переменная x1 , x2 ,..., xn ;

2)

если

F1 , F2 -

формулы

над

,

то

F / , (F F ), (F F ), (F F ), (F F ),

1

1

2

1

2

1

2

1

2

(F1

F2 ), (F1 | F2 ), (F1

F2 )

- также формулы.

Суперпозицией (композицией) логических функций { f1, f2, … , fn}

называется новая логическая функция,

полученная в результате замены

84

аргументов одной из данных функций на данные функции. Например,

возьмем функцию f2(x1, x2, … , xn) и построим новую функцию f2(f1, f5, … , f9). Система логических функции { f1, f2, … , fn} называется полной, если

любая логическая функция, из множества всех логических функций является суперпозицией функции этой системы. Примерами полных систем логических функций являются следующие системы:

1) , , / ; 2) , / ; 3)

, / ; 4) , , / ; 5)

; 6) | .

Логическая функция f(x1, x2, … , xn) называется несущественно зависящей от своего аргумента хi , если для любых логических констант i из множества {0, 1} выполняются следующие равенства:

f( 1 , 2 , …, 0 , … , n ) = f( 1 , 2 , …, 1 , … , n ) ,

где 0 и 1 в левой и правой части равенства расположены на позиции xi . В противном случае, переменная хi называется существенной.

Полиномом Жегалкина называется формула, представленная в виде линейной комбинации конъюнкций переменных с логическими константами, то есть, выражение вида:

F	i i	...i	xi	xi	... xi
	1 2	n	1	2	n

где i1i2 ...in - логические константы 0 и 1 .

Порядок выполнения работы

1.Построить совершенные формы для данных логических функций.

2.Выяснить существенность переменных для данных функций и, в случае несущественности, исключить из ее совершенной конъюнктивной нормальной формы.

3.Построить суперпозицию данных функций.

4.При помощи метода неопределенных коэффициентов построить для данной логической функции полином Жегалкина.

Образец выполнения заданий

Для логических функций f1, f2, f3 построить совершенные формы. Выяснить существенность переменных для логических функций f1, f2. В случае несущественности, исключить эти переменные из ее совершенной конъюнктивной нормальной формы. Построить суперпозицию g(x, y, z) = f2(f1, f3, f2). При помощи метода неопределенных коэффициентов построить для логической функции f3 полином Жегалкина.

f1 = (1,0,0,0,0,1,0,1), f2 = (1,0,1,0,0,0,0,1), f3 = (1,0,0,1,0,1,0,1).

85

Решение. Построим СДНФ и СКНФ для данных функций. Для этого можно применить правила построения совершенных форм для формул алгебры высказываний. Таблицы истинности функций представлены в векторной форме. Запишем соответствующие им аргументы в следующей таблице 4:

Таблица 4.

Таблицы значений логических функций f1, f2, f3.
x	y	z	f1	f2	f3
0	0	0	1	1	1
0	0	1	0	1	0
0	1	0	0	0	0
0	1	1	0	0	1
1	0	0	0	1	0
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	1	0	1

Согласно правилу построения СДНФ, выберем единичные значения

функции f1	и построим соответствующие им элементарные конъюнкции:
x y z , x y z ,		x y	z . Тогда, соединяя эти элементарные конъюнкции
операцией дизъюнкция, получим СДНФ для функции f1:
			f1 = x y z x y z x y z .
Выбирая	нулевые		значения функции f1 ,	аналогичным	образом
построим	сначала		элементарные дизъюнкции:	x y z ,	x y z ,
x y z , x y		z ,	x y z . Соединяя эти элементарные дизъюнкции
операцией конъюнкция, получим СКНФ для функции f1:

f1 = ( x y z ) ( x y z ) ( x y z ) ( x y z ) ( x y z ).

Аналогично совершенным формам для f1, построим совершенные формы для функций f2 и f3:

f2 = x

y

z

x

y

z

x

y

z

x y z - СДНФ;

f2

= ( x

y z )

( x

y

z )

( x

y

z ) ( x

y z ) – СКНФ;

f3 = x

y

z

x

y

z

x

y

z

x y z - СДНФ;

f3

= ( x

y z )

( x

y

z )

( x

y

z ) ( x

y z ) – СКНФ.

Выясним существенность аргументов для логических функций f1, f2. Проверим существенность переменной x. Для этого, согласно определению, необходимо сравнить те пары строк в таблице, где

86

переменная x принимает противоположные значения, а соответствующие им значения других аргументов – одинаковые значения. Сравнивая такие строки, заметим, что f1(0, 0, 0) = 1 f1(1, 0, 0) = 0. Следовательно, переменная x является существенной для функции f1. Аналогично, ввиду того, что

f1(0, 0, 0) = 1 f1(0, 1, 0) = 0, f1(0, 0, 0) = 1 f1(1, 0, 0) = 0

переменные y, z также являются существенными. Проверим существенность аргументов логической функции f2. Сравнивая пары строк, в соответствии с определением, заметим, что аргументы x, z функции f2 не являются существенными. Следовательно, эти переменные можно исключить из выражения этой функции в виде формулы. Аргумент y является существенной переменной, так как f2(0, 0, 0) = 0 f2(0, 1, 0) = 1. Для исключения переменных x и z из СКНФ функции f2 можно применить основные свойства логических функций. Применяя эти свойства к СКНФ функции f2, получим

f2 = ( x y z ) ( x y z ) ( x y z ) ( x y z ) = = [( x y ) ( z z )] [( x y ) ( z z )] =

= ( x y ) ( x y ) = ( x x ) y = y.

Построим суперпозицию g(x, y, z) = f2(f1, f3, f2). Для этого воспользуемся данными в таблице соответствиями аргументов функций f1, f2, f3 их значениям и, последовательно вычисляя, получим

g(0, 0, 0) = f2(f1(0, 0, 0), f3(0, 0, 0), f2(0, 0, 0)) = f2(1, 1, 1) = 0, g(0, 0, 1) = f2(f1(0, 0, 1), f3(0, 0, 1), f2(0, 0, 1)) = f2(0, 0, 1) = 1, g(0, 1, 0) = f2(f1(0, 1, 0), f3(0, 1, 0), f2(0, 1, 0)) = f2(0, 0, 0) = 1, g(0, 1, 1) = f2(f1(0, 1, 1), f3(0, 1, 1), f2(0, 1, 1)) = f2(0, 1, 0) = 0.

Аналогично найдем остальные четыре значения искомой функции:

g(1, 0, 0) = 1, g(1, 0, 1) = 0, g(1, 1, 0) = 1, g(1, 1, 1) = 0.

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

g(x, y, z) = f2(f1, f3, f2) = (0, 1, 1, 0, 1, 0, 1, 0).

Построим для логической функции f3 полином Жегалкина. Это можно сделать преобразованием совершенных форм к виду полинома и используя свойства логических функций. Можно также при помощи метода неопределенных коэффициентов. Рассмотрим второй способ. Согласно определению полинома Жегалкина, для функций от трех аргументов полином будет иметь следующий вид:

87

f3(x, y, z) = a b x c y d z e x y f x z g y z h x y z.

Подставляя в это выражение аргументы, и приравнивая соответствующим значениям, согласно определению функции f3, получим систему из восьми линейных уравнений:

f3(0, 0, 0) = а = 1,	f3(0, 0, 1) = a				d = 0,	f3(0, 1, 0) = a				c = 0,
f3(1, 0, 0)	= a	b= 1,		f3(1, 0, 1) = a			b	d	f = 0,
f3(1, 1, 0) = a	b	c	e = 1,		f3(0, 1, 1) = a			c	d	g = 0,
f3(1, 1,	1) = a		b	c	d e f	g	h = 1.

В ходе решения этой системы, найденные уже коэффициенты необходимо подставить в остальные уравнения. Все уравнения необходимо решить в двоичной системе счисления. В результате вычислений получим сначала a

= 1, затем из уравнения 1				d = 0 получим, d = 1. Из уравнений 1	c = 0,
1	b= 1	получим с = 1, b = 0. Аналогично, из уравнений 1 0 1			f = 0,
1	0 1	e = 1, 1 1	1	g = 0 получим f = 0, e =1, g =1. Тогда из
последнего равенства 1			0	1 1 1 0 1 h = 1 получим коэффициент h

= 0. Подставляя найденные коэффициенты в общее выражение полинома Жегалкина, получим искомый полином:

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

Вопросы для самопроверки

1.Определите понятие логической функции.

2.Сколько логических функций, имеющих шесть аргументов?

3.Сформулируйте правило построения формулы для логической функции.

4.Какие системы логических функций называются полными.

5.Что собой представляет полином Жегалкина.

Литература: [3], гл.2, с. 13 – 37; [2], Часть 1, с. 21 – 38; [7], гл. 3, стр. 50 – 70. [12], § 4, стр. 65 –73.

Задания для самостоятельной работы

Вариант 1. f1 = (1,1,0,0,0,0,0,1), f2 = (1,0,1,0,0,0,1,1), f3 = (1,0,1,1,0,0,0,1).

88

Вариант 2. f1 = (1,0,0,1,0,1,0,1), f2 = (1,0,0,0,1,0,0,1), f3 = (1,0,0,1,0,1,1,1).

Вариант 3. f1 = (1,0,0,0,1,1,0,1), f2 = (1,0,1,1,0,0,0,1), f3 = (1,0,0,1,1,1,0,1).

Вариант 4. f1 = (1,0,0,0,0,1,0,1), f2 = (0,1,1,0,0,0,0,1), f3 = (1,0,0,1,1,1,0,1).

Вариант 5. f1 = (1,1,0,0,0,1,0,1), f2 = (1,0,1,0,0,1,0,1), f3 = (1,0,0,0,0,1,1,1).

Вариант 6. f1 = (1,1,1,0,0,1,0,1), f2 = (1,0,0,1,0,0,1,1), f3 = (1,1,0,0,0,1,0,1).

Вариант 7. f1 = (1,0,0,1,0,1,0,0), f2 = (0,1,1,0,0,0,0,1), f3 = (1,0,0,1,0,1,0,1).

Вариант 8. f1 = (0,0,1,0,0,0,1,1), f2 = (0,0,1,0,0,1,0,1), f3 = (0,1,0,0,0,1,0,1).

Вариант 9. f1 = (0,0,0,1,0,1,0,1), f2 = (1,0,1,0,1,0,0,1), f3 = (1,0,0,1,0,1,0,0).

Вариант 10. f1 = (1,0,0,0,0,1,0,1), f2 = (1,0,1,0,0,0,0,1), f3 = (1,0,0,1,0,1,0,0).

Вариант 11. f1 = (1,0,0,0,0,1,1,0), f2 = (1,0,1,0,0,1,0,0), f3 = (1,0,1,0,0,1,0,0).

Вариант 12. f1 = (0,0,1,0,0,1,1,1), f2 = (1,0,1,0,0,0,0,1), f3 = (1,0,0,1,0,1,0,0).

Вариант 13. f1 = (0,1,0,1,0,1,0,0), f2 = (1,0,0,1,1,0,0,1), f3 = (0,0,1,1,0,1,0,1).

Вариант 14. f1 = (0,0,0,1,1,1,0,1), f2 = (1,0,1,0,0,1,0,0), f3 = (0,1,0,1,0,1,0,1).

Вариант 15. f1 = (0,0,0,1,0,1,0,1), f2 = (0,0,1,0,1,0,0,1), f3 = (1,1,0,1,0,1,0,0).

Вариант 16. f1 = (1,1,0,0,0,1,1,1), f2 = (1,1,1,0,0,0,0,1), f3 = (1,0,0,0,1,1,0,1).

Вариант 17. f1 = (0,1,0,1,0,1,0,1), f2 = (0,1,1,0,1,0,0,1), f3 = (1,1,0,1,0,0,1,0).

Вариант 18. f1 = (0,0,1,1,0,1,0,1), f2 = (0,0,0,1,1,1,0,1), f3 = (0,1,1,1,0,1,1,0)

Вариант 19. f1 = (0,0,1,1,1,1,0,0), f2 = (0,1,1,0,1,0,1,0), f3 = (1,0,0,1,1,1,0,0).

Вариант 20. f1 = (0,1,0,1,0,1,0,1), f2 = (0,1,1,1,1,0,0,1), f3 = (0,1,1,1,0,1,0,0).

Вариант 21. f1 = (1,0,0,1,0,0,0,1), f2 = (0,0,1,0,0,1,0,1), f3 = (0,1,1,0,1,0,1,0).

Вариант 22. f1 = (0,1,0,0,1,1,0,0), f2 = (0,1,0,0,1,0,1,0), f3 = (1,0,0,1,0,1,0,0).

Вариант 23. f1 = (0,0,1,1,0,1,0,1), f2 = (0,1,1,0,1,0,0,0), f3 = (1,1,1,1,0,0,0,0).

89

Вариант 24. f1 = (0,1,0,1,0,1,1,1), f2 = (1,0,1,1,0,0,0,1), f3 = (1,0,0,1,1,1,0,0).

Вариант 25. f1 = (1,0,1,0,0,1,0,1), f2 = (0,1,1,0,1,0,0,1), f3 = (0,1,0,1,0,1,0,0).

Практическое занятие № 2

ОСНОВНЫЕ КЛАССЫ ЛОГИЧЕСКИХ ФУНКЦИЙ. ПОЛНОТА СИСТЕМ ЛОГИЧЕСКИХ ФУНКЦИЙ. ТЕОРЕМА ПОСТА

Цель работы

Выяснить принадлежность данных функций к основным замкнутым классам L, S, M, T0, T1. Проверить полноту данной системы логических функций.

Краткая теория

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

Логическая функция называется линейной, если она является линейной комбинацией своих аргументов с логическими константами, то

есть,	если	ее	можно	представить	в	следующем
виде: f (x1 ,..., xn ) a0		a1 x1	... an xn . Для того, чтобы выяснить линейность

логической функции можно построить ее полином Жегалкина. Если полином не будет содержать произведений переменных, то логическая функция будет линейной.

Функция f (x1, x2 , ... , xn ) называется двойственной к данной функции f (x1 , x2 , ... , xn ) . Если двойственная функция совпадает с самой

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

90