Алгебра Жегалкина, её свойства и применение

Особенности алгебры над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции. Характеристика полиномома Жегалкина. Основные аспекты его поиска. Анализ основ использования метода неопределенных коэффициентов.

Рубрика Математика
Вид реферат
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.