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

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

Введение

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

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

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

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

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

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

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Высказывание - повествовательное предложение. О нём можно сказать либо, что оно истинно, либо, что оно ложно, но ни в коем случае не истинно и ложно одновременно. В логике главенствующее значение в высказывании имеет не его значение, а истинность его или ложность. Истинное значение высказывания принимают за «1», а ложное - за «0». То есть существует множество {1;0}, которое называется множеством истинных значений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

)

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

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

14.    Противоположность

Действия с логическими константами (нулём и единицей)

БУЛЕВЫ ФУНКЦИИ

Булевой функцией называется функция f (x1,x2,…,xn), которая принимает значение либо 1, либо 0. Число булевых функций переменной определяется по формуле .

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

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

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

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

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

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