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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

13
f
i
(F
1
,…,F
n(i)
), где f
i
∈
S
n(i)
- число аргументов f
i
, а F
1
,…,F
n(i)
-
формулы, максимальная из глубин которых равна
k. F
1
,…,F
n(i)
называются подформулами
F; все подформулы формул F
1
,…,F
n(i)
также называются подформулами
F. Например, f
2
(x
1
,x
2
) - это
формула глубины
1, а f
3
(f
1
(x
3
,x
1
), f
2
(x
1
,f
3
(x
1
,x
2
))) - формула глубины
3, содержащая одну подформулу глубины 2 и две подформулы
глубины
1. Если f
1
обозначает дизъюнкцию, f
2
- конъюнкцию, а f
3
-
сложение по
mod2, то приведенная формула примет более
привычный вид:
((x
3
∨
x
1
)
⊕
(x
1
&(x
1
⊕
x
2
))) (3.1)
Все формулы, построенные описанным способом, т.е.
содержащие только символы переменных, скобки и знаки функций
из множества
S называются формулами над S.
Всякая формула, выражающая функцию
f, как суперпозицию
других функций, задает правило ее вычисления: для вычисления
формулы необходимо вычислить значения всех ее подформул.
Вычислим, например, формулу (3.1) на наборе
x
1
=1, x
2
=1, x
3
=0.
Используя таблицу 2.3 получим
x
3
∨
x
1
=1; x
1
⊕
x
2
=0,
x
1
&(x
1
⊕
x
2
)=x
1
&0=0; ((x
3
∨
x
1
)
⊕
(x
1
&(x
1
⊕
x
2
)))=1
⊕
0=1.
Таким образом, формула каждому набору значений аргументов
ставит в соответствие значение функции и, поэтому, может
служить наряду с таблицей способом задания и вычисления
функции. По формуле, вычисляя ее на всех
2
n
наборах, можно
восстановить таблицу функции. О формуле, задающей функцию,
говорят, что она реализует
или представляет эту функцию.
В отличие от табличного задания представление данной
функции формулой не единственно. Например, функцию
f
14
«штрих Шеффера» из таблицы 2.3 можно выразить формулами
f
14
(x
1
,x
2
)=
21
xx ∨
f
14
(x
1
,x
2
)=
21
xx (3.2)
а функцию
f
8
«стрелка Пирса» - формулами
f
8
(x
1
,x
2
)=
12
x
x
⋅
f
8
(x
1
,x
2
)=
21
xx ∨ (3.3)
Формулы, представляющие одну и ту же функцию, называются
эквивалентными
или равносильными. Эквивалентность формул
обозначается знаком равенства:

Страницы