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

Содержание

1. Введение ……………………………………………………………………4
2. Логические операции ……………………………………………………...6
3. Булевы функции…………………………………………………………  12
4. Свойства элементарных булевых функций, задаваемых логическими операциями ……………………………………………………………….14
5. Полиномы Жегалкина для логических операций ……………………...16
6. Свойства алгебры Жегалкина ………………………………………… ..17
7. Способы построения полиномов Жегалкина …………………………..19
1. С помощью таблиц истинности (метод неопределенных коэффициентов) …………………………………………………...19
2. С помощью эквивалентных преобразований ДНФ и КНФ, СДНФ

 и СКНФ ……………………………………………………………24

3. Методом треугольника ……………………………………………26
8. Заключение ……………………………………………………………….27
9. Список использованной литературы ……………………………………28

 

 

Введение

 

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

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

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

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

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

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

 

 

 

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

 

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

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

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

 

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

 

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

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

 

Х	Y	Х⋁Y
0	0	0
0	1	1
1	0	1
1	1	1

 

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

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

 

0	0	0
0	1	0
1	0	0
1	1	1

 

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

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

 

0	1
1	0

 

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

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

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

0	0	1
0	1	1
1	0	0
1	1	1

 

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

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

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

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

 

0	0	1
0	1	0
1	0	0
1	1	1

 

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

1. Конъюнкция (⋀)
2. Дизъюнкция (⋁)
3. Импликация (→)
4. Эквивалентность (↔)
5. Отрицание (¬)

 

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

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

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

 

0	0	1
0	1	1
1	0	1
1	1	0

 

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

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

 

0	0	1
0	1	0
1	0	0
1	1	0

 

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

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

 

0	0	0
0	1	1
1	0	1
1	1	0

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

 

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)	f2(x)	f3(x)	f4(x)
0	0	0	1	1
1	0	1	0	1