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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

12
опускают). Конъюнкция
x
1
и x
2
равна 1, если только x
1
и x
2
равны
1, поэтому ее часто называют функцией И. Еще ее называют
логическим умножением,
т.к. ее таблица совпадает с таблицей
умножения для
0 и 1.
Функция
f
7
(x
1
,x
2
) называется дизъюнкцией x
1
и x
2
и
обозначается как
x
1
∨
x
2
. Она равна 1, если x
1
или x
2
равны 1,
поэтому ее называют еще функцией
ИЛИ (“или” здесь понимается
в неразделительном смысле - хотя бы один из двух).
Функция
f
6
(x
1
,x
2
) - это сложение по модулю 2. Ее обозначение
x
1
⊕
x
2
. Она равна 1, когда значения ее аргументов различны.
Поэтому ее еще называют неравнозначностью.
Функция
f
9
(x
1
,x
2
) называется эквивалентностью и обозначается
как
x
1
~ x
2
или x
1
≡
x
2
. Она равна 1, когда значения ее аргументов
равны, и равна
0 в противном случае.
f
13
(x
1
,x
2
) - импликация. Обозначение x
1
→
x
2
или x
1
⊃
x
2
.(читается
“если
x
1
, то x
2
”).
f
8
(x
1
,x
2
) - стрелка Пирса. Обозначение x
1
↓
x
2
.
f
14
(x
1
,x
2
) - штрих Шеффера. Обозначение x
1
⎜
x
2
.
Остальные функции специальных названий не имеют.
В заключении отметим, что
x
1
& x
2
=min(x
1
,x
2
), x
1
∨
x
2
=max(x
1
,x
2
).
3. Суперпозиции и формулы. Булева Алгебра.
Суперпозиции и формулы.
Пусть даны функции f:A
→
B и g:B
→
C. Функция h:A
→
C
называется композицией
функций f и g, если имеет место
равенство
h(x)=g(f(x)), где x
∈
A. Говорят, что функция h получена
подстановкой
f в g.
Суперпозицией
функций f
1
,…,f
m
называется функция f,
полученная с помощью подстановок этих функций друг в друга, а
формулой
называется выражение, описывающее эту
суперпозицию.
Пусть дано множество исходных функций
S=
{
f
1
,…,f
m
,…
}
.
Символы переменных
x
1
,…,x
n
,… будем считать формулами
глубины 0. Формула F имеет глубину k+1 , если F имеет вид

Страницы