Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 10 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

10
системе исчисления (т.е. в системе, имеющей только две цифры 0
и 1). Если b можно представить в виде
b=b
n
2
n
+ b
n-1
2
n-1
+…+ b
1
2
1
+ b
o
2
o
,
где b
i
∈
B, i=0,…,n, т.е. либо 0 либо 1, то двоичная запись числа b
будет выглядеть следующим образом b
n
b
n-1
…b
1
b
o
.
Примеры: 0
10
=0
⋅
2
o
=0
2
1
10
=1
⋅
2
o
=1
2
2
10
=1
⋅
2
1
+0
⋅
2
o
=10
2
6
10
=1
⋅
2
2
+1
⋅
2
1
+0
⋅
2
o
=110
2
Вернемся к приведенной выше таблице. При любом наборе
значений аргументов логическая функция может принимать
значение либо 0, либо 1. Поскольку число различных наборов
значений n аргументов равно 2
n
, то число ⏐P
2
(n)⏐ различных
функций n переменных равно
n
2
2
.
Введенное понятие функции несовершенно, поскольку оно не
позволяет рассматривать функции от меньшего числа аргументов
как функции от большего числа аргументов. Для устранения этого
недостатка введем следующее определение.
Определение.
Функция f(x
1
,…,x
i-1
,x
i
,x
i+1
,…x
n
) из P
2
зависит
существенным образом от аргумента x
i
, если существуют такие
значения
β
1
,…,
β
i-1
,
β
i
,
β
i+1
,…,
β
n
переменных x
1
,…,x
i-1
,x
i
,x
i+1
,…,x
n
, что
f(
β
1
,…,
β
i-1
,0,
β
i+1
,…,
β
n
)
≠
f (
β
1
,…,
β
i-1
,1,
β
i+1
,…,
β
n
).
В этом случае переменная x
i
называется существенной. Если x
i
не является существенной переменной, то она называется
несущественной
или фиктивной.
Если переменная x
i
является фиктивной, то функция
f(x
1
,…,x
i-1
,x
i
,x
i+1
,…,x
n
) по существу зависит лишь от (n-1)-й
переменной, т.е. представляет собой функцию g(x
1
,…,x
i-1
,x
i+1
,…x
n
)
от (n-1) переменной. Будем говорить, что функция g получена из
функции f удалением фиктивной переменной, а функция f
получена из функции g введением фиктивной переменной.
Определение.
Функции f и g называются равными, если
функцию g можно получить из функции f путем добавления или
изъятия фиктивных переменных.
В дальнейшем все функции мы будем рассматривать с
точностью до фиктивных переменных.
Смысл удаления или введения фиктивных переменных в том,

Страницы