Лабораторная работа булевы функции. Многочлены жегалкина

ЛАБОРАТОРНАЯ РАБОТА 7. БУЛЕВЫ ФУНКЦИИ. МНОГОЧЛЕНЫ ЖЕГАЛКИНА. Цель работы: Изучить свойства булевых функций, методы построения ДНФ, КНФ, СДНФ, СКНФ, алгоритмы построения многочлена Жегалкина булевой функции. Порядок выполнения работы. Изучить теоретические сведения. Получить задание у преподавателя. Исследовать методы построения ДНФ, КНФ, СДНФ, СКНФ, алгоритмы построения многочлена Жегалкина булевой функции. Сделать выводы по результатам исследований. Оформить отчет. Требования к отчету. Цель работы. Постановка задачи. Результаты исследования методов построения ДНФ, КНФ, СДНФ, СКНФ, алгоритмов построения многочлена Жегалкина булевой функции. Выводы. Теоретические сведения. Свойства элементарных булевых функций 1. Для булевых функций справедливы равенства, аналогичные формулам, сформулированным для высказываний. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности. 2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности. Для доказательства справедливости любых из приведенных тождеств нужно составить таблицы истинности для булевых функций. Булеву функцию любого числа переменных можно задать формулой, содержащей функции одной и двух переменных посредством подстановки одних булевых функций вместо переменных в другие булевы функции, т. е. посредством суперпозиции булевых функций. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний Конъюнктивным одночленом от переменных х1, х2, ..., хп называется конъюнкция этих переменных или их отрицаний. Дизъюнктивным одночленом от переменных х1, х2, ..., хп называется дизъюнкция этих переменных или их отрицаний. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных конъюнктивных одночленов, называется дизъюнктивной нормальной формой (ДНФ) данной формулы. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных дизъюнктивных одночленов, называется конъюнктивной нормальной формой (КНФ) данной формулы. Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм Алгоритм построения (1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы: Избавиться от знаков двойного отрицания. Применить, если нужно, к операциям конъюнкция и дизъюнкции свойства дистрибутивности и формулы поглощения. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ). Совершенная дизъюнктивная нормальная форма (СДНФ) – это ДНФ, в которой в каждый конъюнктивный одночлен каждая переменная хi из набора f(х1, х2, ..., хп) входит ровно один раз, причем входит либо сама хi либо ее отрицание . Конструктивно СДНФ для каждой формулы алгебры высказываний, приведенной к ДНФ, можно определить так: Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами: ДНФ не содержит двух одинаковых конъюнкций. Ни одна конъюнкция не содержит одновременно двух одинаковых переменных. Ни одна конъюнкция не содержит одновременно некоторую переменную и ее отрицание. Каждая конъюнкция содержит либо переменную хi либо ее отрицание для всех переменных, входящих в формулу. Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить так: Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам: КНФ не содержит двух одинаковых дизъюнкций. Ни одна из дизъюнкций не содержит одновременно двух одинаковых переменных. Ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание. Каждая дизъюнкция СКНФ содержит либо переменную хi либо ее отрицание для всех переменных, входящих в формулу. Сформулируем следующие теоремы: Приведенные формулы позволяют сформулировать следующие утверждения: Каждая булева функция от n переменных, отличная от константы 0, имеет единственную СДНФ. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ. Эти утверждения называются теоремой о функциональной полноте. Многочлены Жегалкина Согласно сформулированным утверждениям, можно говорить, что система булевых функций полна. Тогда любую булеву функцию можно представить в виде многочлена от своих переменных и такой многочлен называется многочленом Жегалкина. Многочленом Жегалкина называется многочлен, являющийся суммой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени. Сформулируем алгоритм построения многочлена Жегалкина. Выше было указано, что любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности Индивидуальные задания Лексикографическое упорядочение наборов в таблице истинности булевой функции позволяет задать функцию двоичным набором длины 2n, который будем обозначать буквой F. Двоичный набор данной функции F = 11111111. Отметим, что двоичный набор определяет булеву функцию в том и только в том случае, когда его длина есть степень двойки, а соответствующий показатель степени определяет число переменных данной функции. Задача 16 Постройте таблицу истинности функции. С помощью эквивалентных преобразований приведите функцию к ДНФ, КНФ, СДНФ, СКНФ. Составьте двумя способами полином Жегалкина и проверьте линейность функции. Индивидуальные задания Вариант задание1 1 16(3) 2 16(6) 3 16(10) 4 16(5) 5 16(14) 6 16(12) 7 16(1) 8 16(9) 9 16(13) 10 16(15) 11 16(2) 12 16(7) 13 16(4) 14 16(8) 15 16(11) Контрольные вопросы Что называется высказыванием? Приведите пример высказываний. Какое высказывание называется истинным, а какое ложным? Что называется составным высказыванием? Перечислите виды логических операций над высказываниями и сформулируйте их определение. Какие основные символы используются в теории высказываний? Какие связки простейшие? Назовите другие связки. Что такое таблица истинности высказывания и как она строится? Как еще называется эта таблица? Какие существуют логические отношения между высказываниями? Перечислите варианты импликации. Сформулируйте основные законы алгебры высказываний. Как их доказать? Что такое булева функция? Как строится таблица истинности для булевых функций? Что такое ДНФ и КНФ? Дайте определение совершенного одночлена. Приведите правило преобразования формул в СДНФ и СКНФ. Как булевы функции связаны с формулами алгебры высказываний? Дайте определение многочлена Жегалкина и сформулируйте теорему Жегалкина. Сформулируйте первый алгоритм построения многочлена Жегалкина булевой функции. В чем состоит метод неопределенных коэффициентов для построения многочлена Жегалкина? Какой многочлен Жегалкина называется нелинейным? Каков алгоритм определения линейности (нелинейности) булевой функции? Список использованных источников 1 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-пресс, 2007. – 176 с. 2 Таран, Т. А. Сборник задач по дискретной математике / Т.А. Таран, Н.А. Мыценко, Е.Л. Темникова. – 2-е изд., перераб. и доп. – Киев: Инрес, 2005. – 64 с. 3 Таран, Т. А. Основы дискретной математики / Т. А. Таран. – Киев: Просвiта, 2003. – 288 с.

Похожие:

	2 Приближение функций многочленами [10 часов] Аппроксимация мнк в различных базисах: базис «алгебраических» многочленов, ортогональные базисы (многочлены Лежандра, «факториальные»...		Лабораторная работа №3. Тема Тема. Программирование функций. Рекурсивные функции. Функции с переменным количеством параметров. Стандартные функции сортировки...
	Контрольная работа №1 по документоведению Лабораторная работа на тему «Документ его функции. Способы документирования»		Лабораторная работа №8 Программирование с использованием функций Вычислить значение выражения при различных исходных данных. Вычисление функции а оформить в виде подпрограммы-функции с параметрами...
	Лабораторная работа №6 "Функции и массивы"		Лабораторная работа №1 Вариант задачи выбирается по последней цифре зачетной книжки. Текст функции сохраняйте в файле. Функция может вызывать вспомогательные...
	Лабораторная работа №1. Интерполяция. Известно, что функция удовлетворяет условию при любом Рассчитать шаг таблицы значений функции f(X), по которой с помощью линейной интерполяции можно было бы найти промежуточные значения...		Лабораторная работа № Встроенные функции excel Простейший способ получения полной информации о любой из них заключается в переходе на вкладку Поиск из меню ?, после чего необходимо...
	Лабораторная работа Имитационное моделирование случайных событий, случайных величин ...		Лабораторная работа №1 Исследование линейных систем Ознакомление с базовыми свойствами линейных разомкнутых систем. Определение характеристик линейной разомкнутой системы: нулей и полюсов,...