Математическая логика и теория алгоритмов. Анкудинов Г.И - 13 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

1.6. Логические функции
Логической функцией от n аргументов называют функции вида
f: {0,1}
n
→ {0,1},
т.е. областью определения логической функции являются
всевозможные n–местные векторы, компоненты которых принимают
значения из множества {0,1}={И,Л}, а областью значений – то же
множество {0,1}. Логические функции называют также булевыми
функциями, по имени англичанина Дж.Буля, разработавшего в XIX
веке основы логики высказываний. Другое название логических
функций – переключательные функции, поскольку они широко
применяются для анализа и синтеза логических устройств из
релейных (переключательных) элементов. Общее обозначение
логической функции: f(x
1
,x
2
,…,x
n
), где x
1
,x
2
,…,x
n
– логические
(булевы) переменные.
Дизъюнктивной нормальной формой (д.н.ф.) называется
формула, представляющая логическую функцию f(x
1
,x
2
,…,x
n
) в виде
дизъюнкции некоторого числа элементарных конъюнкций и
логических переменных с отрицанием или без отрицания, причем
под элементарной конъюнкцией понимается логическое
произведение любого числа неодинаковых логических переменных x
i
(i=1,…,n) с отрицанием или без отрицания.
Пример д.н.ф.: f(x
1
,x
2
,x
3
)=
32132121
xxxxxxxx ∨∨
.
Каждую элементарную конъюнкцию можно представить в общем
виде
n
n
xxxС
σ
σσ
...
21
21
=
, где
⎩
⎨
⎧
=
=
=
.0 если ,
;1 если ,
ii
ii
i
x
x
x
i
σ
σ
σ
Элементарная конъюнкция называется
конституентой единицы функции f(x
n
n
xxxС
σ
σσ
...
21
21
=
1
, x
2
,…, x
n
), если она содержит
все n переменных функции и C⇒f(x
1
, x
2
,…, x
n
), т.е. f(
σ
1
,
σ
2
,…,
σ
n
)=1.
97

Страницы