Алгебра Жегалкина, её свойства и применение
Особенности алгебры над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции. Характеристика полиномома Жегалкина. Основные аспекты его поиска. Анализ основ использования метода неопределенных коэффициентов.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 06.04.2015 |
| Размер файла | 37,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Институт космических и информационных технологий Сибирского федерального университета
Реферат
По дисциплине «Математическая логика и теория алгоритмов»
на тему «Алгебра Жегалкина, её свойства и применение»
2013
1. Алгебра Жегалкина, её свойства и применение
Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции & и , и две нульарные операции - константы 0 и 1.
В алгебре Жегалкина выполняются следующие соотношения:
1. x y = y x;
2. x ( y z ) = x y x z;
3. x x = 0; (1)
4. x = 1;
5. x 0 = x.
Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант
Найдем выражения для основных элементарных функций алгебры логики в алгебре Жегалкина.
1. = x 1.
Это соотношение проверяется непосредственной подстановкой 0 и 1 в обе части равенства.
2. x y = x y x y.
Доказательство:
x y = = 1 = ( x 1 )( y 1 ) 1 =
= x y x y 1 1 = x y x y.
3. x > y = x y x 1.
Доказательство: Используем выражение для импликсации в
x1 v x2 ~ & ~ .
Тогда:
x > y = y = y y = ( x 1 ) y ( x 1 ) y =
= x y y x 1 y = x y x 1.
4. x / y = x y 1.
Доказательство: Используем выражение для x / y в
х1 / x2 ~ ~ .
Тогда:
x / y = = xy 1.
5. x v y = x y x y 1.
Доказательство: Используем выражение для x v y в
x1 v x2 ~ & ~ .
Тогда:
x v y = = ( x 1 )( y 1) = x y x y 1.
6. x ~ y = 1 x y.
Доказательство: Легко проверить, что x ~ y = x y .Тогда:
x ~ y = x y ( x 1 )( y 1 ) = x y x y x y 1 = 1 x y.
Определение. Полиномом Жегалкина для n логических переменных называется полином, являющийся суммой константы и различных одночленов, в которые все переменные входят не выше, чем в первой степени:
алгебра бинарный жегалкин
a ? x x … x , ( 1 ? k ? n )
причем в каждом наборе ( i, , i ) все i различны, а суммирование по mod 2 ведется по некоторому множеству таких не совпадающих наборов.
Например, 1 x x x , x x x x xx - некоторые полиномы Жегалкина для двух и трех переменных соответственно.
От формулы алгебры логики всегда можно перейти к формуле алгебры Жегалкина. Для этого нужно заменить основные элементарные функции алгебры логики на соответствующие эквивалентные выражения алгебры Жегалкина (1) - (5), представленные выше.
В полученной формуле нужно раскрыть скобки и произвести упрощения, используя соотношения (1), а также следующие соотношения: x & x = x и x·1 = x. Полученное выражение и будет полиномом Жегалкина для данной формулы.
Пример. Найти полином Жегалкина для функции:
f( x, y ) = ( xy )( x z ).
Полученное выражение и есть полином Жегалкина.
При нахождении полинома Жегалкина для некоторой формулы алгебры логики можно использовать следующее соотношение, вытекающее из представления дизъюнкции в алгебре Жегалкина:
f1 f2 = f1 f2, (2)
справедливое при f1f2 = 0. Используем соотношение (2) для нахождения полинома Жегалкина в следующих примерах.
Пример. Найти полином Жегалкина для функции: f( x, y ) = x y .
Сделаем следующие преобразования:
f( x,y ) = x y = x y = x y ( x 1 )( y 1 ) =
= x y x y x y 1 = 1 x y - полиномом Жегалкина.
Пример. Найти полином Жегалкина для функции:
f( x, y ) = x z.
Сделаем следующие преобразования:
f( x,y ) = x z = x z = x ( y 1 )( x 1 ) z =
= x y x x z z = x z x y x z. - полиномом Жегалкина.
Теорема. Для любой логической функции существует полином Жегалкина и притом единственный.
Доказательство: Существование полинома доказано вышеприведенным алгоритмом получения полинома из логической формулы. Для доказательства единственности надо показать, что между множеством всех логических функций от n переменных и множеством всех полиномов Жегалкина от n переменных существует взаимно однозначное соответствие.
Полином Жегалкина можно найти методом неопределенных коэффициентов. Рассмотрим этот метод на следующим примере.
Пример. Найти полином Жегалкина для функции заданной векторно:
f( x,y ) = ( 0, 1, 1, 0 ).
Составим таблицу 1 задания данной функции.
Таблица 1
|
x |
y |
f |
|
|
0 |
0 |
0 |
|
|
0 |
1 |
1 |
|
|
1 |
0 |
1 |
|
|
1 |
1 |
0 |
Полином Жегалкина для функции двух переменных ищем в следующем виде:
f( x, y ) = a0 a1·x a2·y a3·xy (3)
Для определения коэффициентов полинома нужно подставить значения неизвестных и соответствующее значение функции в (3), согласно таблице 1.
Подставляя набор переменных(0,0) в (3) получим:
. a = 0.
Аналогично для набора (0,1) получим:
. a = 1.
Для набора (1,0) получим:
a = 1.
Для набора (1,1) получим:
a = 0.
Подставляя в (3) найденные значения коэффициентов получим искомый полином для данной функции:
f( x, y ) = x y.
Замечание.
Можно показать, что переменная x будет фиктивной для некоторой функции тогда и только тогда, когда полином Жегалкина для нее не содержит переменной x.
Список использованных источников
1. Акимов В.А. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003, 376 с.
2. Ершов Ю.А., Полюнин Е.А. Математическая логика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. - мат. лит., 1987, 336 с.
3. Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003, 320 с.
4. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. - М.: ФОРУМ: ИНФРА-М, 2004, 128 с.
5. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. - М.: ИНФРА - М; Новосибирск: НГТУ, 2003, 280 с. - (Серия «Высшее образование»).
Размещено на Allbest.ru
...Подобные документы
Свойства алгебры Жегалкина. Действия с логическими константами (нулём и единицей). Свойства элементарных булевых функций, задаваемых логическими операциями. Способы построения полиномов с помощью таблиц истинности (метод неопределенных коэффициентов).
курсовая работа [467,2 K], добавлен 28.11.2014Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
реферат [63,3 K], добавлен 06.12.2010Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
контрольная работа [227,5 K], добавлен 20.04.2015Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
курсовая работа [644,4 K], добавлен 16.05.2010Алгебра логики, булева алгебра. Алгебра Жегалкина, педикаты и логические операции над ними. Термины и понятия формальных теорий, теорема о дедукции, автоматическое доказательство теорем. Элементы теории алгоритмов, алгоритмически неразрешимые задачи.
курс лекций [652,4 K], добавлен 29.11.2009Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
контрольная работа [43,2 K], добавлен 27.04.2011Понятие и свойства n-арных операций, универсальной алгебры и сигнатуры. Характеристика централизаторов конгруэнции универсальных алгебр и доказательство их основных свойств. Нильпотентные и абелевы алгебры, формулировка и метод доказательства их лемм.
курсовая работа [399,1 K], добавлен 22.09.2009Вычисление интеграла, выполнение интегрирования по частям. Применение метода неопределенных коэффициентов, приведение уравнения к системе. Введение вспомогательных функций в процессе поиска решения уравнения и вычисления интеграла, разделение переменных.
контрольная работа [617,2 K], добавлен 08.07.2011Характеристика булевой алгебры и способы представления булевых функций. Понятие и сущность бинарных диаграммах решений. Упорядоченные бинарные диаграммы решений, их построение и особенности применения для обработки запросов в реляционных базах данных.
дипломная работа [391,7 K], добавлен 21.01.2010Элементы алгебры, логические операции над высказываниями. Получение логических следствий из данных формул и посылок для данных логических следствий. Необходимые и достаточные условия. Анализ и синтез релейно-контактных схем. Логические следствия и формы.
дипломная работа [295,2 K], добавлен 11.12.2010Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.
курс лекций [651,0 K], добавлен 08.08.2011Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
реферат [40,5 K], добавлен 17.11.2008Понятие, основные свойства элементарных булевых функций и соотношения между ними. Формулировка принципа двойственности. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Многочлен (полином) Жегалкина. Суперпозиция и замыкание класса функций.
презентация [24,4 K], добавлен 05.02.2016Основные этапы развития булевой алгебры и применение минимальных форм булевых многочленов к решению задач, в частности, с помощью метода Куайна - Мак-Класки. Применение минимизирования логических форм при проектировании устройств цифровой электроники.
курсовая работа [58,6 K], добавлен 24.05.2009Элементы линейной алгебры. Элементы аналитической геометрии и векторной алгебры. Введение в математический анализ. Дифференциальное исчисление функций одной переменной. Дифференциальное исчисление функций нескольких независимых переменных. Интеграл.
методичка [90,5 K], добавлен 02.11.2008Системы цифровой обработки информации. Понятие алгебры Буля. Обозначения логических операций: дизъюнкция, конъюнкция, инверсия, импликация, эквивалентность. Законы и тождества алгебры Буля. Логические основы ЭВМ. Преобразование структурных формул.
презентация [554,8 K], добавлен 11.10.2014Определение МДНФ логической функции устройства различными методами (Квайна, Петрика, неопределенных коэффициентов и др.). Составление алгоритма метода минимизации функции и разработка его рабочих программ. Выполнение синтеза схемы логического устройства.
курсовая работа [60,2 K], добавлен 21.11.2010Законы алгебры Буля и их применение для преобразования логических выражений. Расчет информационной емкости документов предметной области. Построение инфологической, реляционной и даталогической моделей. Применение методов поиска и сортировки данных.
курсовая работа [261,7 K], добавлен 05.01.2013
