1. Булевы функции и способы их задания
 Скачать 0.81 Mb.
|
|
1. Булевы функции и способы их задания. Определение. Набор ̃ ( ), где { } ̅̅̅̅̅̅̅̅̅ называется булевым или двоичным набором (вектором). Элементы набора называются компонентами или координатами. Число - длиной набора ̃. Определение. Множество всех двоичных наборов длины образует мерный булев куб ( ) Пример 1. Изобразить графически для {( ) ( )} –состоит из двух наборов, каждый из которых можно изобразить точкой на прямой ОХ. рис.1 {( ) ( ) ( ) ( )} –состоит из четырех наборов, каждый из которых можно изобразить точкой на плоскости ХОY, являющейся вершиной единичного квадрата с соответствующими координатами. рис.2 {( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )} – состоит из восьми наборов, каждый из которых можно изобразить точкой пространстве ХYZ, являющейся вершиной единичного куба с соответствующими координатами рис.3 Замечание 1. Число различных двоичных наборов длины равно ( ) Доказательство: Рассмотрим двоичный набор ̃ ( ) длины n. Поскольку каждая компонента может принимать одно из двух возможных значений либо 0 либо 1, то для заполнения каждой из nпозиций двоичного набора имеется 2 варианта. Таким образом, число всех возможных вариантов ( ) ⏟ Определение. Каждому двоичному набору ̃ ( ) можно взаимно однозначно сопоставить целое неотрицательное число ( ̃) такое что: ( ̃) ∑ называемое номером набора. ( ̃) . Например, для наборов из трех переменных номера будут такими: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Расположение двоичных наборов одной длины по порядку возрастания их номеров называется стандартным или лексикографическим расположением наборов. Определение. Функция ( ) областью определения которой является -мерный булев куб ( ), а областью значениймножество { } называется булевой функцией или функцией алгебры логики. Множество всех булевых функций зависящих от n переменных принято обозначать ( ) Способы задания булевых функций. 1. Табличный способ задания (таблица истинности) Любую булеву функцию ( ) можно представить в виде таблицы состоящей из двух столбцов: в первом в лексикографическом порядке расположены все двоичные наборы длины (всего строк), во втором в каждой строке записано значение, которое функция принимает на этом наборе ( ) ( ) ( ) ( ) ( ) ( ) ( ) Пример 2. Табличный способ задания функции двух переменных ( ) Наборы в первом столбце расположены в порядке возрастания номеров: ( ) ( ) ( ) ( ) Во втором столбце расположены значения, которые функция принимает на соответствующих наборах. ( ) ( ) ( ) ( ) 2. Векторный способ задания булевой функции. Вектор значений функции. Поскольку в таблице истинности различных функций - переменных первый столбец всегда одинаковый, то функцию можно однозначно определить вектором соответствующим второму столбцу таблицы истинности: ̃ ( ) Где координата равна значению функции на наборе с номером Пример 3. Вектор значений функции из примера 2 будет равен ̃ ( ) Замечание 2. | ( )| Доказательство: так как вектор значений ̃ ( ) функции n-переменных имеет координат, каждая из которых может принимать лишь два возможных значения: либо 0 либо 1, тогда число различных наборов длины будет равно . Значит и различных булевых функций от n-переменных будет , поскольку между булевой функций и ее вектором значений имеется взаимно однозначное соответствие. Пример 4. Функция задана вектором значений ̃ ( ) Найдите таблицу истинности функции . Поскольку в векторе значений функции восемь координат и , то значит это функция от 3-х переменных ( ). Запишем таблицу истинности функции: первый столбик – все двоичные наборы трех переменных расположенные в лексикографическом порядке, во второй столбик сверху вниз запишем вектор значений функции. Таблица истинности данной функции: ̃ 3. Задание булевой функции с помощью носителя. Определение. Множество всех наборов ̃ ( ) на которых функция ( ) принимает значение 1 называется носителем функции { ̃ | ( ̃) } Определение. Множество всех наборов ̃ ( ) на которых функция ( ) принимает значение 0 называется дополнением носителя функции ̅ ̅ { ̃ | ( ̃) } Поскольку ̅ , то если мы перечислим все наборы на которых функция принимает значение 1 (т.е. зададим носитель) – это будет достаточно для однозначного задания булевой функции. Пример 5. Найти носитель функции из примера 2. {( ) ( )}, ̅ {( ) ( )} Пример 6. Найти носитель функции из примера 4. {( ) ( ) ( ) ( )}, ̅ {( ) ( ) ( ) ( )} 4. Геометрический способ задания булевой функции. Этот способ удобно применять для функций зависящих не более чем от 4-х переменных. Для функций 1, 2,3 -х переменных на булевом кубе отмечают (например "жирными" точками) вершины соответствующие наборам принадлежащим носителю функции. Для функций 4-х переменных используют карту Карно (см.) Пример 7. Изобразить геометрически функции из примера 2 и из примера 4. ̃ ( ) ̃ ( ) рис.4 5. Задание функции с помощью формулы. Двоичные функции одной переменной Существует всего 4 двоичные функции зависящие от одной переменной | ( )| Приведем таблицы истинности этих функций ( ) ( ) ( ) ( ) ( ) – тождественный нуль ( ) – тождественная единица ( ) –тождественная функция ( ) ̅ – функция отрицание, или инверсия Двоичные функции двух переменных Двоичных функций двух переменных всего 16 | ( )| Приведем таблицы истинности некоторых из них | 1. или – функция конъюнкция, логическое умножение, логическое «и» ( ). 2. – функция дизъюнкция, логическое сложение, логическое «или» ( ) 3. – функция сложение по модулю 2, «исключающее или». Значение функции равно остатку от деления алгебраической суммы чисел и на 2. 4. – функция эквивалентность, логическое тождество. Функция принимает значение 1, на наборах где . Заметим, что значение функции «эквивалентность» на каждом наборе противоположно значению функции «сложение по модулю 2». Значит функцию «эквивалентность» можно выразить формулой: ̅̅̅̅̅̅ 5. – функция импликация, «логическое следование». Для запоминания значений, которые принимает функция можно использовать правило: «из лжи может следовать все что угодно из истины следует только истина» (0-ложь, 1-истина) 6. | – штрих Шеффера, «не и» | ̅̅̅̅̅̅ 7. – стрелка Пирса, «не или» ̅̅̅̅̅̅̅ Перечисленные функции одной и двух переменных называются элементарными булевыми функциями. Другие двоичные функции двух и более переменных можно выразить через элементарные булевы функции с помощью формул. Если функция задана формулой, то говорят что, формула реализует или представляет данную функцию. Формулы, реализующие одну и туже функцию называются эквивалентными или равносильными. Порядок выполнения действий в формулах: 1. Сначала выполняются действия в скобках 2. Функция «отрицание переменной» выполняется прежде других булевых функций. При этом учитывается, что если отрицание относится к некоторой функции, то скобки вокруг нее могут быть опущены, например: ( ) ̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅. 3. выполняется раньше чем и (логическое умножение выполняется раньше сложения) Пример 8. Для функции заданной формулой ( ) ( ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ найти вектор значений ̃. Искомая функция является функцией трех переменных ( ). Определим порядок действий: 5 ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ( ) ( ) Сначала выполняем действия в скобках и , потом логическое умножение , затем логическое сложение , функция инверсия выполняется последней так как относится к формуле, а не к переменной. Каждое получившихся из пяти действий соответствует элементарной булевой функций: ̅ Запишем результаты этих действий в общую таблицу: ̅ Последний столбец таблицы истинности является вектором значений искомой функции ̃( ) ( ) Основные законы алгебры логики. 1. Коммутативность (переместительный закон) Функция означает любую из функций | Отметим, из всех элементарных булевых функций, только функция импликация не является перестановочной: , все остальные функции не зависят от порядка переменных, например: и 2. Ассоциативность (сочетательный закон) ( ) ( ), где { } 3. Дистрибутивность (распределительный закон) ( ) ( ) ( )( ) 4. Законы де Моргана ̅̅̅̅̅̅ ̅ ̅ ̅̅̅̅̅̅̅ ̅ ̅ 5. Закон двойного отрицания ̿ 6. Закон идемпотентности и 7. Закон противоречия ̅ 8. Закон исключения третьего ̅ 9. Свойства констант ̅ 10. Закон поглощения ( ) 11. Закон склеивания ̅ 12. Законы сложения по модулю два ̅ ̅ В справедливости этих законов, можно убедиться путем сопоставления таблиц истинности для левой и правой частей равенств. 2. Специальные представления булевых функций. Дизъюнктивная и конъюнктивная нормальные формы Введем обозначение { ̅ то есть ̅ и Определение. Логическое произведение переменных или их отрицаний называется элементарной конъюнкций Например, , ̅ , ̅ ̅ – элементарные конъюнкции. Определение. Логическая сумма переменных и их отрицаний называется элементарной дизъюнкцией например: , ̅ , ̅ ̅ – элементарные дизъюнкции. Замечание 1. В элементарную конъюнкцию или дизъюнкцию не может одновременно входить переменная и ее отрицание. ( ̅ ̅ не является элементарной конъюнкцией). Определение. Количество переменных и отрицаний переменных входящих в элементарную конъюнкцию (дизъюнкцию) называется ее рангом (обозначение ) Например, для ранг равен 1 ( ), для ̅ ̅ ранг равен 3 ( ) Определение. Дизъюнктивная нормальная форма ( )– это формула, в которой функция представлена в виде дизъюнкции элементарных конъюнкций. Определение. Конъюнктивная нормальная форма ( )– это формула, в которой функция представлена в виде конъюнкции элементарных дизъюнкций. Определение. Сумма всех рангов элементарных конъюнкций (дизъюнкций) входящих в форму называется рангом формы (или сложностью формы) Совершенная дизъюнктивная нормальная форма (СДНФ) Определение. Представление функции в виде дизъюнкции элементарных конъюнкций построенных по всем наборам принадлежащим носителю функции называется совершенной дизъюнктивной нормальной формой (СДНФ) ( ) ̃ Алгоритм построения СДНФ. 1. Находим наборы ̃ ( ) входящие в носитель функции , такие что ( ) 2. Для каждого набора составляем соответствующую ему элементарную конъюнкцию ̃ 3. Соединяем все полученные конъюнкции знаком , получившаяся форма является СДНФ ̃ ̃ Пример 1. Найти СДНФ функции заданной вектором значений ̃ ( ) Выпишем таблицу истинности данной функции ( ). Подчеркнем наборы принадлежащие носителю функции, по каждому из этих наборов составляем элементарную конъюнкцию ̃ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ Составляем СДНФ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ Теорема 1. Любая булева функция, не являющаяся константой, может быть представленная СДНФ. Замечание 1. | | , где | |- число наборов в носителе. Доказательство. Каждая из элементарных конъюнкций, входящих в СДНФ имеет ранг n, число таких конъюнкций равно числу наборов в носителе функции, следовательно | | . Совершенная конъюнктивная нормальная форма (СКНФ) Определение. Представление функции в виде конъюнкции элементарных дизъюнкций построенных по всем наборам принадлежащим дополнению носителя функции называется совершенной конъюнктивной нормальной формой (СКНФ) ( ) ̃ ̅ ( ̅ ̅ ̅ ) Алгоритм построения СКНФ: 1. Находим наборы ̃ ( ) входящие в дополнение носителяфункции ̅ , т.е. такие что ( ) . 2. Для каждого набора составляем соответствующую ему элементарную дизъюнкцию ̃ ̅ ̅ ̅ 3. Соединяем все полученные дизъюнкции знаком , получившаяся форма является СКНФ ̃ ̅ ̃ Пример 2. Найти СКНФ функции заданной вектором значений ̃ ( ) из примера 1. Подчеркнем наборы принадлежащие дополнению носителю функции, по каждому из этих наборов составляем элементарную дизъюнкцию ̃ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ Составляем СДНФ ( ̅ )( ̅ ̅)( ̅ ̅) Теорема 2. Любая булева функция, не являющаяся константой, может быть представленная как СКНФ. Замечание 2. | ̅ | , где | ̅ |- число наборов принадлежащих дополнению носителя. Замечание 3. Если функция является тождественной константой ( ̃) или ( ̃) , ее тоже можно представить в виде суперпозиции переменной, отрицания переменной, , . Например, возможны следующие представления: ̅ и ̅ Многочлен Жегалкина Определение. Формула вида ( ̃) называется многочленом Жегалкина. Другими словами это сумма по модулю два всех возможных элементарных конъюнкций, не содержащих отрицаний. - либо 0 либо 1 Теорема 3 (Жегалкин И.И.). Любая булева функция представима в виде многочлена Жегалкина причем единственным образом (с точностью до перестановки слагаемых). Рассмотрим два алгоритма для нахождения многочлена Жегалкина. Алгоритм 1 построения многочлена Жегалкина (посредством СДНФ) 1. В СДНФ функции заменить все символы на символы . 2. Выносим за скобки одинаковые сомножители и упрощаем формулу, применяя закон: ̅ ( ̅) (так как ̅ ). 3. Все отрицания переменных ̅ заменяем на выражения 4. Раскрываем скобки, применяя сочетательный и распределительный законы алгебры логики, приводим подобные члены, вычеркивая одинаковые пары слагаемых, поскольку . 5. Полученный в результате преобразований многочлен будет многочленом Жегалкина для данной функции. Пример 3. Найти многочлен Жегалкина для функции из примера 1, используя СДНФ. В примере 1 мы нашли СДНФ для ̃ ( ) ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ 1. Заменяем знак на знак ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ 2. Вынесем за скобки общие множители и упростим формулу, учитывая что ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅( ̅ ) ̅ ̅ ( ̅ ) ̅ ̅ ̅ ̅ 3. Заменим все отрицания переменных ̅ и раскроем скобки ̅ ̅ ̅ ̅ ( )( ) ( )( ) ( ) ( ) Вычеркиваем одинаковые пары слагаемых, так как Алгоритм 2 построения многочлена Жегалкина (метод треугольника) 1. Выписываем левый столбец таблицы истинности (он одинаков для всех функций переменных) 2. Вектор значений функции выписываем горизонтально в первую строку, т.е. около набора из всех нулей. 3. Заполняем строку стоящую ниже: находим сумму по модулю 2 всех пар соседних элементов вышестоящей строки. В каждой следующей строке элементов будет на 1 меньше чем впредыдущей, в последней строке будет 1 элемент 4. Крайние левые значения полученных строк будут коэффициентами многочлена Жегалкина (конъюнкция будет состоять из тех переменных, которые в наборе стоящим в данной строке в первом столбце принимают значение 1) Пример 4. Найти многочлен Жегалкина для функции ̃ ( ) из примера 1 используяметод треугольника. 1. Заполним первый столбец таблицы истинности и расположим вектор значений функции в первой строке 1 1 0 0 1 0 1 1 2. Заполним вторую строку: берем два соседних элемента это 1 и 1, находим их сумму по модулю 2, так как , то получившийся 0 записываем во вторую строку, между элементами которые складывали 1 1 0 0 1 0 1 1 0 берем следующие два соседних элемента первой строки это 1 и 0, находим их сумму по модулю 2, так как , то получившийся 1 записываем во вторую строку, между элементами которые складывали 1 1 0 0 1 0 1 1 0 1 3. Аналогично поступаем с каждой парой соседних элементов первой строки, записываем получившиеся суммы во вторую строку 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 4. Потому же принципу заполняем оставшиеся строки 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 5. Первый (наклонный столбик) получившегося треугольника – это коэффициенты многочлена Жегалкина. Подчеркиваем 1 стоящие в наклонном столбике и наборы переменных в соответствующей строке. 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 Для подчеркнутых наборов построим конъюнкции по правилу: в конъюнкцию входят переменные равные 1 на рассматриваемом наборе. Выпишем конъюнкции для нашего примера. 1 1 0 0 1 0 1 1 1- свободный член 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 Составляем многочлен Жегалкина. Коэффициент, находящийся в строке надо поставить перед конъюнкцией, выписанной в этой строке и соединить между собой получившиеся произведения знаком . Если некоторый коэффициент равен нулю, то такая конъюнкция не будет входить в многочлен Жегалкина ( ), поэтому на 0 в наклоном столбике можно не обращать внимания. Если коэффициент равен 1, то соответствующую конъюнкцию мы записываем в многочлен Жегалкина, однако сам коэффициент перед конъюнкцией не пишут ( ). Многочлен Жегалкина в нашем примере: Пример 5. (задание типового расчета) Для функции заданной формулой (( ) ( ̅ )) (( ̅| ) ( ̅ ̅)) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ найдите таблицу истинности, вектор значений, носитель функции и его дополнение, СДНФ, СКНФ и многочлен Жегалкина. 1. Построим таблицу истинности. Разобьем функцию на элементарные, согласно правилам порядка выполнения действий в формулах. – значение функции записано в первом столбике таблицы истинности ̅ – второй столбик – третий столбик – четвертый столбик | – пятый столбик ̅ – шестой столбик ̅ – седьмой столбик – восьмой столбик – девятый столбик ̅ – десятый столбик – одиннадцатый столбик x y z 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 2. Вектор значений ̃ ( ) (последний столбик таблицы истинности). 3.Носитель функции {( ) ( ) ( ) ( ) ( ) ( ) ( )} ̅̅̅ = {(011)} - дополнение носителя. 4. ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ , . 5. ̅ ̅ , 6. Найдем многочлен Жегалкина 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0 |