Полиномы Жегалкина для логических операций

Введение

На сегодняшний день практически каждый человек в мире ежедневно пользуется такими благами цивилизации, как компьютеры, мобильные телефоны, калькуляторы и пр. Люди стали остро зависеть от сетевого общения и от Интернет-ресурсов, позволяющих найти нужную нам информацию гораздо быстрее, чем при поиске ее традиционными способами в книгах, газетах, журналах. Однако мало кто задумывается о том, каким образом работают наши электронные «помощники».

Математической основой цифровой техники является алгебра логики, разработанная в середине XIX века английским математиком Джорджем Булем. В честь своего «отца» алгебру логики также называют булевой алгеброй. Возможность её применения в технике заметил впервые в 1910 году известный физик П. Эренфест. Доказательство такой возможности привёл и обосновал в своих работах советский физик В. И. Шестаков.

Булева алгебра оперирует с переменными, которые принимают только лишь два значения — 0 и 1, то есть с двоичными переменными. Функция двоичных переменных, принимающая те же два значения, называется логической функцией или булевой функцией.

Теория булевых функций, начиная с прошлого века и продолжая сегодняшним днем, является теоретической базой современных ЭВМ. Возникло понятие алгоритма, и это очень помогает решать многие доселе неразрешимые проблемы. Именно через математическую логику и теорию алгоритмов сейчас математические методы проникают в экономику, биологию, лингвистику и многие другие науки.

Целью моей курсовой работы является рассмотрение и изучение одного из способов приведения логических функций к более короткому виду, точнее — приведение логических функций к многочлену (полиному) Жегалкина.

Разработанный в начале ХХ века русским математиком Иваном Ивановичем Жегалкиным вид логического многочлена сейчас широко применяется в самых различных сферах человеческой деятельности — начиная от криптографии (шифрования данных для их сбережения от посторонних глаз) и заканчивая применением в сумматорах — аналого-цифровых устройствах, которые реализуют логическую операцию «исключающее ИЛИ», которую также называют суммой по модулю 2. К слову, сумматоры являются обязательной частью любого аналого-цифрового устройства, любого без исключений процессора.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ Высказывание — повествовательное предложение. О нём можно сказать либо, что оно истинно, либо, что оно ложно, но ни в коем случае не истинно и ложно одновременно. В логике главенствующее значение в высказывании имеет не его значение, а истинность его или ложность. Истинное значение высказывания принимают за «1», а ложное — за «0». То есть существует множество {1;0}, которое называется множеством истинных значений.

Алгебру высказываний также называют булевой алгеброй, а переменные, принимающие значения 1 и 0 называют булевыми переменными.

Логическая операция (оператор, связка) — операция над высказываниями, которая позволяет составлять новые высказывания, соединяя высказывания более простые.

Простейшие связки

1. Дизъюнкция — операция «ИЛИ», называемая также логической суммой. Дизъюнкцией высказываний Х и Y называют высказывание, обозначаемое как Х? Y (или Х+Y) и представляющее собой ложное высказывание в том случае, когда Х и Y ложны, и истинное высказывание во всех остальных случаях.

Таблица истинности для дизъюнкции

2. Конъюнкция — операция «И», которую также называют логическим произведением. Конъюнкцией высказываний Х и Y называют высказывание, обозначаемое как Х? Y (или Х•Y) и представляющее собой истинное высказывание в том случае, когда Х и Y истинны, и ложное высказывание во всех остальных случаях.

Таблица истинности для конъюнкции

3. Отрицание, называемое также инверсией, высказывания Х называют высказывание, обозначаемое как, которое является ложным при истинном Х и истинным при ложном Х.

Таблица истинности для отрицания

4. Импликацией (логическое следование) высказываний Х и Y называется высказывание, обозначаемое Х>Y, которое является ложным только в том случае, когда Х истинно, а Y — ложно. В остальных случаях импликация является истинной.

Логическое следование представляет собой оборот речи «если Х, то Y». Например, «если я сдам курсовую по дискретной математике вовремя, то у меня ее примут».

Таблица истинности для импликации:

Импликация — не симметричная логическая операция, то есть высказывания и не являются эквивалентными (равными).

Высказывание называется конверсией высказывания .

5. Эквивалентностью высказываний и называется высказывание вида, которое принимает истинные значения лишь в тех случаях, когда оба высказывания (и) либо одновременно истинны, либо одновременно ложны.

Таблица истинности для эквивалентности:

Выше мной были перечислены основные логические операции, которые, в случае отсутствия скобок, выполняются в следующем порядке:

1. Конъюнкция (?)

2. Дизъюнкция (?)

3. Импликация (>)

4. Эквивалентность (-)

5. Отрицание ()

Помимо элементарных или, как их иначе называют, простейших связок существует еще несколько логических операций.

1. Штрих Шеффера (антиконъюнкция) обозначается как (или)

Таблица истинности

2. Стрелка Пирса (антидизъюнкция) обозначается как (или)

Таблица истинности

3. Сумма по модулю 2 (антиэквивалентность) обозначается как (или)

Таблица истинности:

СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ

1. Коммутативность дизъюнкции и конъюнкции

2. Ассоциативность дизъюнкции и конъюнкции

3. Дистрибутивность дизъюнкции и конъюнкции относительно друг друга

4. Идемпотентность дизъюнкции и конъюнкции

5. Двойное отрицание

6. Закон Моргана

7. Склеивание

8. Поглощение

9. Закон исключения третьего

10. Отрицание противоречия

11. Контрапозиция

)

12. Ценное заключение

13. Модус поненс

14. Противоположность Действия с логическими константами (нулём и единицей) БУЛЕВЫ ФУНКЦИИ Булевой функцией называется функция f (x1,x2,…, xn), которая принимает значение либо 1, либо 0. Число булевых функций переменной определяется по формуле .

Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, которые отличаются только лишь значением переменной xi, значения функции совпадают.

Фиктивные переменные функции можно добавлять к функции и исключать из нее.

Две булевы функции называют рaвными или рaвносильными, если одну можно получить из другой путем добавления и/или изъятия фиктивных переменных.

Все функции от двух аргументов в булевой алгебре называют элементарными булевыми функциями. Основные элементарные булевы функции — это конъюнкция, дизъюнкция и отрицание. Они удовлетворяют всем аксиомам булевой алгебры.

Рассмотрим функции одной переменной:

Функции f1(x) и f4(x) называются константами нуля и единицы соответственно. Функция f2(x) совпадает по своим значениям с переменной х и называется тождественной переменной х. Функция f3(x) совпадает с инвертированной переменной х. Исходя из этого, можно построить таблицу истинности, которая будет более краткой в написании (это совершенно необязательно, однако подобное представление таблиц истинности часто используется в литературе):

Рассмотрим функции двух переменных (считать f (x)) :

Функции f1 и f16 называют константами 0 и 1 соответственно. Функции f4 = х1, f6= х2, f11= f13, то есть f4, f6, f11, f13 зависят лишь от одной переменной, в отличие от остальных функций Функции f3 и f5 называются функциями запрета.

алгебра булевый логический таблица СВОЙСТВА ЭЛЕМЕНТАРНЫХ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАВАЕМЫХ ЛОГИЧЕСКИМИ ОПЕРАЦИЯМИ

1. Дизъюнкция, конъюнкция, эквивалентность, сумма по модулю 2, штрих Шеффера, стрелка Пирса обладают свойством коммутативности, то есть замена переменных местами в выражении не играет роли.

2. Дизъюнкция, конъюнкция, сумма по модулю 2 имеют свойства ассоциативности (когда результат вычисления не зависит от порядка выполнения операций между несколькими переменными (расстановки скобок), потому позволительно опускать скобки в записи), которую также называют сочетательным законом, и дистрибутивности, называемую также распределительным законом.

3. Закон ДеМоргана

=?

=

4. Закон двойного отрицания

=х

5. Выражение дизъюнкции через конъюнкцию и сумму по модулю 2

? ?

6. Выражение конъюнкции через импликацию

7. Выражение отрицания через штрих Шеффера, стрелку Пирса, сумму по модулю 2 и эквивалентность

8. Выражение конъюнкции через штрих Шеффера

9. Выражение дизъюнкции через стрелку Пирса

10. Закон поглощения

11. Закон склеивания Для конъюнкции, дизъюнкции и суммы по модулю 2 существует несколько справедливых тождеств ПОЛИНОМЫ ЖЕГАЛКИНА ДЛЯ ЛОГИЧЕСКИХ ОПЕРАЦИЙ Полином (многочлен) Жегалкина от n переменных — это функция вида

(1)

где — коэффициенты, принимающие значение либо нуля, либо единицы, или в более общем виде

(2)

где — элементарная конъюнкция, то есть полином Жегалкина есть многочлен, представляющий собой сумму по модулю 2 n элементарных конъюнкций.

Любую булеву функцию возможно представить в виде многочлена Жегалкина, и при том только единственным образом. Это утверждение также называют теоремой Жегалкина.

По сути, операция приведения логической функции представляет собой выражение логических операций через конъюнкцию и сумму по модулю 2.

СВОЙСТВА АЛГЕБРЫ ЖЕГАЛКИНА Множество булевых функций, в которых могут быть задействованы только операции конъюнкции и суммы по модулю 2 и единица (также говорят, что эти булевы функции заданы в базисе Жегалкина S ={?, ?, 1}), называется алгеброй Жегалкина.

Основные свойства алгебры Жегалкина

1. Коммутативность

2. Ассоциативность

3. Дистрибутивность

4. Свойства констант Утверждение: через операции алгебры Жегалкина можно выразить все другие булевы функции

? X

СПОСОБЫ ПОСТРОЕНИЯ ПОЛИНОМОВ ЖЕГАЛКИНА Существует несколько способов построения полиномов Жегалкина, каждый из которых удобен по-своему в определенных случаях.

ПОСТРОЕНИЕ ПОЛИНОМОВ ЖЕГАЛКИНА С ПОМОЩЬЮ ТАБЛИЦ ИСТИННОСТИ (МЕТОД НЕОПРЕДЕЛЕННЫХ КОЭФФИЦИЕНТОВ) Построение полиномов Жегалкина с помощью таблиц истинности или, как еще говорят, методом неопределенных коэффициентов — процесс кропотливый, требующий внимания и определенной сноровки, а также полного осознания того, что надо делать.

Этот способ можно применять и тогда, когда функция задана таблицей истинности, и тогда, когда функция представлена логической формулой.

Пример 1: построить полином Жегалкина для функции Составим таблицу истинности для функции

1. Теперь, используя формулу (1), построим полином Жегалкина для нашей функции в общем виде (для трёх переменных):

. (3)

2. Найдем значения коэффициентов

Так как-то .

3. Составим полином Жегалкина, подставив полученные значения коэффициентов в формулу (3)

Ответ: полином Жегалкина, построенный для функции, будет равен Пример 2: построить многочлен Жегалкина, используя данную таблицу истинности

Решение:

1. Запишем общий вид полинома Жегалкина (с неопределенными коэффициентами), то есть формулу (1) для 3 переменных

2. Найдём коэффициенты Так как-то .

3. Подставим найденные коэффициенты в формулу (3) и найдем таким образом многочлен Жегалкина Ответ: полином Жегалкина для данной таблицы истинности имеет следующее значение: .

ПОСТРОЕНИЕ ПОЛИНОМОВ ЖЕГАЛКИНА С ПОМОЩЬЮ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ДНФ И КНФ, СДНФ И СКНФ В тех случаях, когда функция задана логической формулой, иногда удобнее использовать не громоздкий метод неопределенных коэффициентов, а компактный метод эквивалентных преобразований. Для этого необходимо уметь привести функцию в ДНФ или СДНФ, не прибегая к использованию таблиц истинности. Чаще всего используются следующие тождества, а также закон ДеМоргана. Далее следует раскрыть скобки по самым обычным правилам.

Пример 1: построить полином Жегалкина для функции, заданной в виде СДНФ ;

Решение:

1. Избавимся от дизъюнкции с помощью закона ДеМоргана

=

2. Избавимся от отрицаний

= = =

Ответ: полином Жегалкина имеет вид) = .

Пример 2: построить полином Жегалкина для функции, представленной в ДНФ ;

Решение:

1. Заменим дизъюнкцию конъюнкцией и суммой по модулю два

(?) (?) = (? ?) (? ?)

2. Избавимся от отрицаний

(?) (?) = (? ?) (? ?) =? ?? ?? ?? = 0? ? 0? 0? ? 0?? ? =? ?? ? =? ?

Ответ: полином Жегалкина имеет вид

) =? ?

МЕТОД ТРЕУГОЛЬНИКА Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина с помощью построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.

2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.

3. Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.

4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.

5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т. д.

6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Заключение

Математика — наука очень точная, однако в ней можно проявить фантазию, решая задачи различными способами. Дискретная математика не является в этом исключением.

В своей курсовой работе я рассмотрела несколько самых распространенных способов решения поставленной мне задачи: приведения логических функций к полиномам Жегалкина. Каждый из рассмотренных мной способов имеет свои особенности применения, но все они требуют безусловной внимательности и сосредоточенности.

В заключение хочется сказать, что Иван Иванович Жегалкин оказал большую услугу человечеству, когда вывел полином, названный впоследствии его именем. Полином, члены которого связываются только двумя операциями и единицей, оказался невероятно полезен и очень широко применяется человеком в процессе его жизни и деятельности.

1. Яблонский С. В.

Введение

в дискретную математику: Учеб. пособие для вуов. — 2-е изд., перераб. и доп. — М.: Наука. Гл. ред. физ.-мат. лит. — 1986. 384 с.

2. Марченков С. С. Замкнутые классы булевых функций. — М.: Физ.-мат. лит. — 2000. — 126 с.

3. Дунаев С. Д., Золотарев С. Н. Цифровая схемотехника: Учебное пособие для техникумов и колледжей ж.-д. транспорта. — М.: ГОУ «Учебно-методический центр по образованию на железнодорожном транспорте», 2007. — 238 с.

4. Супрун В. П. Табличный метод полиномиального разложения булевых функций — М.: Кибернетика. — 1987. — № 1

5. Логачёв О. А, Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии — МЦНМО, 2004. — 470с.

6. Е. Л Рабкин, Ю. Б. Фарфоровская, дискретная математика — электронное издание.

.ur