Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля

Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля

Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathema...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2020
Hauptverfasser: Spectorsky, I. Ya., Galganov, O. A.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020
Schlagworte:
поліном Жегалкіна
метод трикутника
трикутник Паскаля
Online Zugang:http://journal.iasa.kpi.ua/article/view/189119
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:System research and information technologies

Institution

System research and information technologies
id journaliasakpiua-article-189119
record_format ojs
spelling journaliasakpiua-article-1891192020-08-11T08:50:57Z Triangle method for constructing Zhegalkin polynomial: connection with Pascal's triangle Метод треугольника для построения полинома Жегалкина: связь с треугольником Паскаля Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля Spectorsky, I. Ya. Galganov, O. A. поліном Жегалкіна метод трикутника трикутник Паскаля полином Жегалкина метод треугольника треугольник Паскаля boolean function Zhegalkin polynomial triangle method Pascal’s triangle Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathematician V.P. Suprun. Applying of the triangle method mainly coincides with step-by-step constructing Pascal triangle rows using the equality Cn+1k+1 = Cnk + Cnk+1. Therefore, it would be natural to expect for the relation between the calculation of Zhegalkin polynomial by the triangle method and an arrangement of binomial coefficients in Pascal triangle. In this paper, the connection between the triangle method and constructing of Pascal triangle is studied. Besides that, a rather simple proof of the triangle method correctness is proposed. This proof is based on juxtaposition of the triangle method steps and a step-by-step construction of Pascal triangle. Полином Жегалкина — удобный способ представления булевой функции в виде суммы по операции ⨁ (xor, или сумма по модулю 2) конечного числа конъюнкций переменных — предложен в 1927 г. советским ученым И.И. Жегалкиным. Одним з алгоритмов построения полинома Жегалкина для заданной булевой функции есть метод треугольника, предложенный в 1985–1987 гг. советским математиком В.П. Супруном. Применение метода треугольника совпадает с пошаговым построением треугольника Паскаля "строка за строкой" по известному соотношению Cn+1k+1 = Cnk + Cnk+1. Естественно ожидать связь между вычислением полинома Жегалкина методом треугольника с расположением биномиальных коэффициентов в треугольнике Паскаля. Проанализирована связь метода треугольника с построением строк треугольника Паскаля; предложено относительно простое доказательство корректности метода треугольника путем сопоставления шагов алгоритма с пошаговым построением строк биномиальных коэффициентов в треугольнике Паскаля. Поліном Жегалкіна — зручний спосіб зображення булевої функції у вигляді суми за операцією ⨁ (xor, або сума за модулем 2) скінченної кількості кон’юнкцій змінних — запропонований у 1927 р. радянським ученим І.І. Жегалкіним. Одним з алгоритмів побудови полінома Жегалкіна для заданої булевої функції є метод трикутника, запропонований у 1985–1987 рр. радянським математиком В.П. Супруном. Застосування методу трикутника збігається з почерговою побудовою рядків трикутника Паскаля з використанням відомого співвідношення Cn+1k+1 = Cnk + Cnk+1. Природно очікувати на зв’язок обчислення полінома Жегалкіна методом трикутника з розташуванням біноміальних коефіцієнтів у трикутнику Паскаля. Проаналізовано зв’язок методу трикутника з побудовою рядків трикутника Паскаля; запропоновано відносно просте доведення коректності методу трикутника шляхом зіставлення кожного кроку алгоритма з покроковою побудовою рядків біноміальних коефіцієнтів у трикутнику Паскаля. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-06-23 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/189119 10.20535/SRIT.2308-8893.2020.1.12 System research and information technologies; No. 1 (2020); 129-145 Системные исследования и информационные технологии; № 1 (2020); 129-145 Системні дослідження та інформаційні технології; № 1 (2020); 129-145 2308-8893 1681-6048 uk http://journal.iasa.kpi.ua/article/view/189119/209253 Copyright (c) 2021 System research and information technologies
institution System research and information technologies
baseUrl_str
datestamp_date 2020-08-11T08:50:57Z
collection OJS
language Ukrainian
topic поліном Жегалкіна
метод трикутника
трикутник Паскаля
spellingShingle поліном Жегалкіна
метод трикутника
трикутник Паскаля
Spectorsky, I. Ya.
Galganov, O. A.
Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
topic_facet поліном Жегалкіна
метод трикутника
трикутник Паскаля
полином Жегалкина
метод треугольника
треугольник Паскаля
boolean function
Zhegalkin polynomial
triangle method
Pascal’s triangle
format Article
author Spectorsky, I. Ya.
Galganov, O. A.
author_facet Spectorsky, I. Ya.
Galganov, O. A.
author_sort Spectorsky, I. Ya.
title Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
title_short Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
title_full Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
title_fullStr Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
title_full_unstemmed Метод трикутника для побудови полінома Жегалкіна: зв’язок з трикутником Паскаля
title_sort метод трикутника для побудови полінома жегалкіна: зв’язок з трикутником паскаля
title_alt Triangle method for constructing Zhegalkin polynomial: connection with Pascal's triangle
Метод треугольника для построения полинома Жегалкина: связь с треугольником Паскаля
description Introduced by Soviet scientist I. Zhegalkin in 1927, Zhegalkin polynomial is a way to represent a Boolean function as an exclusive or of conjunctions of variables. One of the known algorithms for constructing Zhegalkin polynomial is so called ‘triangle method’ proposed in 1985–1987 by Soviet mathematician V.P. Suprun. Applying of the triangle method mainly coincides with step-by-step constructing Pascal triangle rows using the equality Cn+1k+1 = Cnk + Cnk+1. Therefore, it would be natural to expect for the relation between the calculation of Zhegalkin polynomial by the triangle method and an arrangement of binomial coefficients in Pascal triangle. In this paper, the connection between the triangle method and constructing of Pascal triangle is studied. Besides that, a rather simple proof of the triangle method correctness is proposed. This proof is based on juxtaposition of the triangle method steps and a step-by-step construction of Pascal triangle.
publisher The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
publishDate 2020
url http://journal.iasa.kpi.ua/article/view/189119
work_keys_str_mv AT spectorskyiya trianglemethodforconstructingzhegalkinpolynomialconnectionwithpascalstriangle
AT galganovoa trianglemethodforconstructingzhegalkinpolynomialconnectionwithpascalstriangle
AT spectorskyiya metodtreugolʹnikadlâpostroeniâpolinomažegalkinasvâzʹstreugolʹnikompaskalâ
AT galganovoa metodtreugolʹnikadlâpostroeniâpolinomažegalkinasvâzʹstreugolʹnikompaskalâ
AT spectorskyiya metodtrikutnikadlâpobudovipolínomažegalkínazvâzokztrikutnikompaskalâ
AT galganovoa metodtrikutnikadlâpobudovipolínomažegalkínazvâzokztrikutnikompaskalâ
first_indexed 2025-07-17T10:26:38Z
last_indexed 2025-07-17T10:26:38Z
_version_ 1837889486402355200

Ähnliche Einträge