2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 СДНФ и формула Лагранжа (Колмогоров мат. логика)
Сообщение17.04.2011, 19:18 
Аватара пользователя
Книга Колмогорова, Драгалина "Введение в математическую логику", глава 1, пункт 9:

Цитата:
9. Рассмотрим булево кольцо $F_n$ функций от $n$ переменных $x_1, ..., x_n \in D$ со значениями из $D$ (булево кольцо $D$ состоит из двух элементов $0$ и $1$), так называемых булевых функций.
Пользуясь операциями сложения и умножения в кольце $D$, можно представить такую функцию по формуле Лагранжа в виде

$f(x_1, ..., x_n) = \displaystyle\sum_{a_1, a_2, ..., a_n}f(a_1, ..., a_n)\displaystyle\prod_{k=1}^{n}(x_k + a_k + 1),$ (1)

где суммирование ведется по всем наборам $a_1, ..., a_n$ из нулей и единиц, т.е. по всем элементам кольца $D^n$ (например, $D^2$ состоит из $\{\langle 0,0 \rangle, \langle 0,1 \rangle, ..., \langle 1,1 \rangle\}$ ).


Дальше на основе этого представления вводится совершенная дизъюнктивная нормальная форма и в принципе понятно каким образом.

Вопрос в другом, а именно:

* что за формула Лагранжа о которой говорится в этой книге? (я посмотрел в гугле, но ничего похожего я не нашел)
* где в другой литературе она имеет такой вид и используется для представления СДНФ (СКНФ)?

 
 
 
 Re: СДНФ и формула Лагранжа (Колмогоров мат. логика)
Сообщение17.04.2011, 19:43 
Аватара пользователя
creative в сообщении #435969 писал(а):
* что за формула Лагранжа о которой говорится в этой книге? (я посмотрел в гугле, но ничего похожего я не нашел)
Ссылка идет на интерполяционный полином Лагранжа - мы собираем функцию из значений в каждой точке. с помощью многочленов, которые в этой точке равны 1, а в остальных 0.

Других источников, где ДНФ вводится так, не вспомню, но в каких-то статьях точно встречалось (sum of minterms)

 
 
 
 Re: СДНФ и формула Лагранжа (Колмогоров мат. логика)
Сообщение17.04.2011, 20:42 
Аватара пользователя
Xaositect

Спасибо.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group