Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 44 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

y
0
и y
15
— кон стан ты 0 и 1;
y
3
= x
1
;
y
5
= x
2
;
y
12 1
= x
;
y
10
2
= x
;
y
1 1
2
= x x&
— конъ юнк ция;
y
7
1
2
= Úx x
— дизъ юнк ция;
y
13 1
2
= Éx x
— им пли ка ция;
y9 = x
1
: x
2
— эк ви ва лен ция;
y
8
1
2
= ¯x x
— стрел ка Пир са;
|
y
14 1
2
= x x
— штрих Шеф фе ра;
y
11 1
2
= x xo
— функ ция Веб ба;
y
4 2
1
= Éx x
— им пли ка ция;
y
6
1
2
= Åx x
— сло же ние по мо ду лю 2 (функ ция Же гал ки на);
y y
2
13
=
.
Су пер по зи ци ей функ ций f
1
… f
n
на зы ва ет ся функ ция f, по лу чен ная
с по мо щью под ста но вок этих функ ций друг в дру га и пе ре име но ва ния
пе ре мен ных. Фор му лой на зы ва ет ся вы ра же ние, опи сы ваю щее эту су пер -
по зи цию.
Сим во лы пе ре мен ных (x
1
… x
n
) на зы ва ют ся фор му ла ми глу би -
ны 0. Фор му ла глу би ны 1 по лу ча ет ся пу тем пе ре име но ва ния од ной из
пе ре мен ных. Фор му ла глу би ны 2 по лу ча ет ся под ста нов кой не ко то рой
функ ции f
l
вме сто ка кой-ли бо пе ре мен ной x
j
и т.д. На при мер, фор му ла
глу би ны 3, со дер жа щая од ну под фор му лу глу би ны 2 и две — глу би ны 1,
вы гля дит так:
f f x x f x f x x
3
1
3
1
2
1 1 1
2
( ( , ); ( , ( , ))
.
Вся кая фор му ла, вы ра жаю щая функ цию f как су пер по зи цию дру -
гих функ ций, за да ет спо соб ее вычисления.
При мер:
F x x x x x= Ú Å Å( ) ( &( ))
3
1 1 1
2
Вы чис лим F при зна че нии x
1
= 1; x
2
= 1; x
3
= 0;
x x x x x x x x
1
2 3
1 1 1
2
1
0 1 0 0Å = Ú = Å = =; ; &( ) & ;
F x x x x x= Ú Å Å = Å =( ) ( &( )) ,
3
1 1 1
2
1 0 1
то есть мы вы чис ли ли од ну строч ку из таб ли цы ис тин но сти 1.7.8. Вы -
чис лив все ос таль ные строч ки, мож но вос ста но вить таб ли цу функ ции.
ДНФ все гда име ет глу би ну 2.
44
     y0 и y15 — константы 0 и 1;
     y3 = x1;
     y5 = x2;
     y 12 = x 1 ;
     y 10 = x 2 ;
     y 1 = x 1 & x 2 — конъюнкция;
     y 7 = x 1 Ú x 2 — дизъюнкция;
     y 13 = x 1 É x 2 — импликация;
     y9 = x1 : x2 — эквиваленция;
     y 8 = x 1 ¯ x 2 — стрелка Пирса;
     y 14 = x 1 | x 2 — штрих Шеффера;
     y 11 = x 1 o x 2 — функция Вебба;
     y 4 = x 2 É x 1 — импликация;
     y 6 = x 1 Å x 2 — сложение по модулю 2 (функция Жегалкина);
     y 2 = y 13 .
      Суперпозицией функций f1 … fn называется функция f, полученная
с помощью подстановок этих функций друг в друга и переименования
переменных. Формулой называется выражение, описывающее эту супер-
позицию.
      Символы переменных (x1 … xn) называются формулами глуби-
ны 0. Формула глубины 1 получается путем переименования одной из
переменных. Формула глубины 2 получается подстановкой некоторой
функции fl вместо какой-либо переменной xj и т.д. Например, формула
глубины 3, содержащая одну подформулу глубины 2 и две — глубины 1,
выглядит так: f 3 ( f1 ( x 3 , x 1 ); f 2 ( x 1 , f1 ( x 1 , x 2 )).
      Всякая формула, выражающая функцию f как суперпозицию дру-
гих функций, задает способ ее вычисления.
     Пример:
                      F = ( x 3 Ú x 1 ) Å ( x 1 &( x 1 Å x 2 ))
     Вычислим F при значении x1 = 1; x2 = 1; x3 = 0;
          x 1 Å x 2 = 0; x 3 Ú x 1 = 1; x 1 &( x 1 Å x 2 ) = x 1 & 0 = 0;
                F = ( x 3 Ú x 1 ) Å ( x 1 &( x 1 Å x 2 )) = 1 Å 0 = 1,
то есть мы вычислили одну строчку из таблицы истинности 1.7.8. Вы-
числив все остальные строчки, можно восстановить таблицу функции.
      ДНФ всегда имеет глубину 2.
44

Страницы