выш мат. Алексеев-В.В.-Алгебра-логики. Инистерство образования и науки российской федерации
 Скачать 6.59 Mb.
|
|
1.3.3 Свойства функций сложения по модулю два, импликации, Шеффера, Пирса 1. Функция сложения по модулю два Эта функция может быть выражена через другие функции следующим образом: . (1.17) Функция сложения по модулю два обладает следующими свойствами: коммутативности (переместительный закон) ; ассоциативности (сочетательный закон) ; дистрибутивности (распределительный закон) . Для этой функции справедливы законы: ; ; ; . На основании аксиом и свойств можно вывести правила перевода функций И, ИЛИ, НЕ через функцию сложения по модулю два и наоборот. ; ; . 2. Функция импликации Чаще всего функция импликации выражается через дизъюнкцию и отрицание следующим образом: . (1.18) Для данной функции справедливы следующие законы: ; ; ; ; ; . Из этих законов следует, что функция импликации обладает только свойством коммутативности (переместительный закон) в измененном виде: . Свойство ассоциативности (сочетательный закон) для этой функции не справедливо, т.е. . Действительно: ; . Функции НЕ, ИЛИ, И выражаются через импликацию следующим образом: ; ; . 3 Функция Шеффера . (1.19) Для функции Шеффера справедливы следующие законы: ; ; ; ; ; . Для функции Шеффера справедливо только свойство коммутативности . Однако для трех и более переменных . Свойство ассоциативности для функции Шеффера несправедливо. Действительно, рассмотрим функции трех переменных: и . Имеем: , а =, т.е. получены совершенно разные функции. Следовательно, свойство ассоциативности несправедливо для трех переменных и будет несправедливо и для n переменных. Свойство дистрибутивности также несправедливо для функции Шеффера, т.е. . Это можно показать следующим образом: = , что не соответствует распределительному закону (свойству дистрибутивности). Формулы преобразования, полученные из основных свойств алгебры логики, для функции Шеффера имеют вид: ; ; . 4 Функция Пирса (Вебба) (1.20) Для функции Пирса справедливы законы: ; ; ; . Для функции Пирса справедливо только свойство коммутативности: . Функции И, ИЛИ, НЕ выражаются через функцию Пирса следующим образом (формулы преобразования): ; ; . Функции Шеффера и Пирса связаны между собой соотношениями, аналогичными формулам Де-Мограна для конъюнкции и дизъюнкции: (1.21) Действительно, например, для первого равенства имеем: . Аналогично доказывается справедливость и второго равенства: . 1.4 Аналитическое представление ФАЛ. Существует несколько способов заданий логических функций. Табличный метод не является компактным. Проще выглядит аналитическая запись в виде формул. Пусть мы имеем двоичный набор <>, на котором задана ФАЛ. Сопоставим ему число i, определяемое следующим образом : i= Число i будем называть номером набора < >. Рассмотрим функцию , определяемую следующим соотношением: (1.22) Такую функцию называют характеристической функцией единицы, или конъюнктивным термом, или минтермом. Теорема 1.3 Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме : (1.23) где - множество номеров наборов, на которых функция обращается в единицу. Действительно, если на каком-либо наборе функция =()=1, то вследствие того, что в правой части 1.23 всегда найдется элемент, равный единице (), у которого соответствует номеру рассматриваемого набора. Если же на наборе i функция =()=0, то в правой части не найдется ни одного элемента, равного единице, т.к. 0v0v ... v 0=0. Т.о. каждому набору i, для которого =1 соответствует элемент =1, а наборам i, на которых =0 не соответствует ни одного элемента =1. Поэтому таблица истинности однозначно отображается аналитической записью вида 1.23 (дизъюнкция минтермов). В теории мы воспользовались дизъюнкцией минтермов. Посмотрим, нельзя ли вместо дизъюнкции использовать какую-либо другую функцию. Для того чтобы выполнялось соотношение 1.23, необходимо чтобы при обращении любого в 1 все выражение обращалось в 1, а при обращении всех в 0 все выражения также становились равными 0. Сформулированные условия можно записать в виде таблицы:
где значком условно обозначена некоторая неизвестная операция. Знак "?" в последней строке таблицы соответствует такой комбинации значений , которая никогда не может встретиться (ij). Поэтому искомая функция (операция) может быть определена двумя различными способами. Если в определяющую таблицу вместо “?” поставить ‘1’, то будет дизъюнкцией (=V). Этот случай рассматривался в теореме 1.3. Если же знак “?” заменить нулем (имеется в виду логическая переменная равная нулю), то будет функцией сложения по модулю два (=). Следствие Любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме : (1.24) Представление функции в виде 1.23 называется дизъюнктивным представлением, а в виде 1.24- полиноминальным представлением. Для получения представления другого типа рассмотрим функцию и определяется как : (1.25) Такие функции называют характеристическими функциями нуля, или макстермы. Из соотношения 1.22 и 1.25 видно, что = Теорема 1.4 Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме : (1.26) где - количество номеров наборов, на которых функция обращается в 0. Доказательство этой теоремы аналогично доказательству теоремы теореме 1.3 Вместо конъюнкции в соотношении 1.26 можно взять любую функцию, которая удовлетворяет следующим условиям:
При записи в первой строке вместо "?" нуля , получаем конъюнкцию, рассмотренную в теореме 1.4 (=), а при замене "?" единицей - функцию эквивалентности ( = ) Следствие Любая таблично заданная ФАЛ может быть представлена в аналитической форме : (1.27) Представление ФАЛ в виде 1.26 называется конъюнктивным представлением. Определение. Логические переменные, объединенные знаком V или & называются термом. Определение. Ранг терма r определяется количеством переменных, входящих в данный терм. Введем в рассмотрение степень аргумента х, которую будем обозначать (1.28) при этом 1.5 Совершенные нормальные формы. 1.5.1 СНДФ. Рассмотрим конъюнкцию (1.29) Набор < > двоичный и существует таких различных наборов. Т.о., число различных конъюнкций вида 1.29 также равно . Сопоставим каждой конъюнкции (1.29) номер, определяемый номером набора < >. Тогда запись : () означает дизъюнкцию всех конъюнкций с номерами из множества . Аналогично, запись () означает конъюнкцию всех дизъюнкций с номерами из множества . Покажем, что =1 тогда и только тогда, когда выполняется равенство. Это вытекает из рассмотрения следующих четырех возможных случаев. 1. 3. 2. 4. Таким образом, конъюнкция не обращается в нуль только в том случае, если одновременно выполняются следующие i равенств. (1.30) Из 1.30 вытекает, что ()= при условии, что Тогда на основании теоремы 1.3 можно утверждать, что любая ФАЛ, кроме нуля, может быть представлена в виде: ()= () (1.31) При этом дизъюнкция берется только по тем номерам наборов аргументов, на которых функция, заданная таблицей, обращается в единицу. Представление функции в виде 1.31 называется дизъюнктивной совершенной нормальной формой, (ДСНФ) или совершенной нормальной дизъюнктивной формой (СНДФ). 1.5.2 Алгоритм перехода из таблично заданной ФАЛ к СНДФ . Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как 1, он выписывается без изменения в конъюнкцию, соответствующую данному набору. Если же =0, то в соответствующую конъюнкцию вписывается его отрицание. Все полученные конъюнкции соединяются между собой знаками дизъюнкции. Пример. Пусть имеем таблично заданную ФАЛ: Табл. 1.5.1.
и тогда имеем: (,,,)= v v v v v v v Если вместо соотношения 1.23 воспользоваться соотношением 1.24, то получим совершенно нормальную полиноминальную форму СНПФ. СНПФ получается из СНДФ заменой знака V на . Так, в рассмотренном примере функция в СНПФ будет иметь вид: (,,,)= 1.5.3. Совершенная нормальная конъюктивная форма(СНКФ) Теорема 1.5. Любая ФАЛ, кроме единицы, может быть представлена в виде: (1.32.) Символ означает, что & берется только по тем наборам , для которых выполняется равенство: =0. Доказательство: Имеем: или . Равенство не нарушается, если от обеих частей взять отрицание: . Применяя закон де - Моргана получаем: На тех наборах, для которых , соответствующая дизъюнкция . И такие наборы на значение конъюнкции не влияют и ими можно пренебречь, и тогда: Теорема доказана для всех . Представление функции в виде 1.32 называется СНКФ – совершенной нормальной конъюктивной формой. Из сравнения (1.26) и (1.32) вытекает, что, при условии, что . 1.5.4 Алгоритм построения СНКФ 1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль. 2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как 0, он выписывается без изменения в дизъюнкцию, соответствующему данному набору. Если же входит в данный набор как 1, то в соответствующую дизъюнкцию выписывается его отрицание. 3. Все полученные дизъюнкции соединяются между собой знаками конъюнкций. Пример (см. табл. 1.5.1.): =& && & Если в выражении 1.32 использовать вместо конъюнкции эквивалентность, то мы получим представление в форме 1.27. 1.5.5 Представление ФАЛ в импликативной форме Теорема 1.6. Любая ФАЛ, кроме тождественной единицы, может быть представлена в следующей форме: ѓ=. (1.33) Доказательство. Для любого набора значений аргументов , для которого f=0, найдется в конъюнкции импликация =, обращающаяся в нуль на этом наборе и принимающая значения 1 на всех остальных наборах. Для этого достаточно вхождения всех аргументов , кроме в с отрицанием, если =1 и без отрицания в противном случае. Для условия вхождения противоположны. Конъюнкцию в 1.33 можно заменить при желании импликацией и отрицанием т.к. = * Пример. Записать ФАЛ табл. 1.5.1 в импликативной форме. и тогда ѓ=& && && &. Применив * получим: f= Импликативная форма записи является аналогом СНКФ. Теорема 1.7. Любая ФАЛ, кроме тождественного нуля, может быть представлена в форме: f= (1.34) Для доказательства 1.34 достаточно заметить, что функции устроены так, что каждая такая функция обращается в единицу на наборе, соответствующем набору <> и равна 0 на остальных. Дизъюнкция 1.34 может быть заменена через импликацию и отрицание Пример. Записать ФАЛ табл. 1.5.1. в импликативной форме ( ИДФ) . . и тогда f=VV VVVV VV и применив ** получим: f= . 1.5.6 Представление ФАЛ в виде полинома Жегалкина Согласно свойствам функции сложения по модулю два, которая имеет еще множество различных названий (неравнозначности, исключающее ИЛИ, нетождественности, разноименности и т.п.) для двух переменных мы имеем следующие равносильности: (свойство коммутативности); (свойство ассоциативности); (свойство дистрибутивности). На основе свойства ассоциативности рассматривается многоместная операция сложения по модулю два , которая принимает значения логической единицы тогда и только тогда, когда в ней содержится четное количество единиц. Именно на этой операции основан контроль передачи двоичных слов по линиям связи в цифровых устройствах. Теорема Жегалкина. Любая ФАЛ может быть представлена в виде: где . Доказательство. Запишем ФАЛ в совершенной полиноминальной форме: . (1.35) Поскольку то Подставив в (1.35) вместо выражение , получаем: . Раскрыв скобки (свойство дистрибутивности) и на основании правила , приводим функцию к виду , где коэффициенты равны 0 или 1. Коэффициент, соответствующий пустому множеству индексов представляет собой свободный член полинома. Указанное представление носит название полинома Жегалкина. 1.5.7 Разложение ФАЛ по переменным Итак мы установили, что для логической переменнойи Вполне очевидно, что тогда и только тогда, когда . Следовательно, конъюнкция равна 1 на единственном наборе значений аргументов, когда , т.е. . Теорема о разложении ФАЛ. Любая ФАЛ для любого ( может быть представлена в виде: , где дизъюнкция берется по всевозможным наборам значений аргументов . Доказательство. Для доказательства необходимо и достаточно показать, что для любого набора аргументов () левая и правая часть формулы принимают одинаковые значения. Рассмотрим правую часть. Поскольку 0 когда и 1, то , т.е совпадает со значением левой части. Теорема доказана. Например, если функцию представить в виде разложения, например, по переменной , то она будет выглядеть следующим образом: . Пример. Функцию разложить по переменным а и b. Т.к. функцию требуется разложить по двум переменным, следовательно, она будет представлена четырьмя слагаемыми: . Нетрудно увидеть, что метод разложения ФАЛ по переменным является простым и эффективным средством упрощения ФАЛ для представления их, например, в ДНФ. 1.6. Основные классы ФАЛ Для решения ряда принципиальных вопросов, связанных с теорией функций алгебры логики и с практическим применением результатов этой теории для анализа и синтеза схем, полезно рассмотреть основные классы функций алгебры логики. Пусть имеются логические функции и . Будем считать, что функции зависят от одних и тех же аргументов (этого можно достигнуть, добавив, при необходимости, к аргументам некоторых из функций фиктивные аргументы). Функцию называют суперпозицией функций q и . Рассмотрим некоторый класс A логических функций. Определение: Класс А называется замкнутым, если для всяких функций и из А их суперпозиция содержится в А. Приведем некоторые важные примеры замкнутых классов. Класс функций, сохраняющих константу нуль, т.е. таких функций, для которых имеет место f(0,0,0,...,0)=0. Обозначим этот класс . Очевидно, что при фиксированном n число функций этого класса составляет половину всех ФАЛ, т.е. . Аналогично, класс функций, сохраняющих константу единица определен как класс функций, для которых f(1,1,...,1)=1. Этот класс, состоящий также из функций, обозначен символом . Определение: Функция называется двойственной к функции , если имеет место равенство: = Принципы и законы двойственности. Принципы двойственности можно записать следующим образом: Если имеет место тождество , где , то справедливо также тождество , т.е. если в каком-либо тождестве произвести взаимную замену символов 0 и 1 (если они имеются) и операций V и &, то будет получено также тождество. Два тождества, связанные между собой таким образом, являются двойственными. Истинность самого принципа двойственности не доказывается, т.к. данный принцип является внутренним свойством алгебры логики (заключен в ее аксиомах). Законы двойственности (теоремы де-Моргана) устанавливают способ отыскания инверсных функций, представляющих собой V и & 2-х переменных. Клод Шеннон предложил обобщение этих теорем, позволяющее отыскивать инверсию любой функции fx, где x=. Закон двойственности, установленный Шенноном имеет вид: , где x=, =. Т.е. инверсию любой функции f(x) можно получить взаимной заменой переменных и их инверсий (i=1,2, .....n) и операций V и &. Пример: , тогда . На основании закона двойственности легко показать, что . Определение Функция называется самодвойственной, если она совпадает с двойственной себе функцией, т.е. имеет место равенство =. Класс самодвойственных функций обозначим символом S. Число членов этого класса равно , т.к. самодвойственная функция от n аргументов полностью определяется на половине наборов значений аргументов. Определение. Функция называется линейной, если она представима в следующем виде: , где может принимать значения 0 или 1. Класс линейных функций обозначим буквой L. Число членов этого класса равно . Набор значений аргументов не меньше набора значений аргументов , если между всеми компонентами наборов и установлено соотношение . Например, набор 1,1,0, 1,0 не меньше набора 1,0,0,1,0, а наборы 1,1,0,1,0 и 1,0,1,1,0 несравнимы. Определение. Функция называется монотонной, если для двух наборов и таких, что имеет место равенство . Класс монотонных функций обозначим буквой M. Число функций класса M оценивается асимптотически формулой , где - число монотонных функций алгебры логики, A- константа. Нижняя оценка получена Э.Н. Гильбертом, верхняя- В.К. Коробовым. Определение. Функция называется симметричной, если она не изменяется при произвольной перенумерации аргументов. =, где - любая перестановка аргументов . 1.7 Полные системы функций Определение. Система функций алгебры логики называется полной в классе R, если любая функция , принадлежащая R, может быть представлена суперпозицией функций . Определение. Система функций, являющаяся полной в классе R, называется базисом. Или: Базисом называется полная система ФАЛ, с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций. Определение. Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций , образующих этот базис, превращает систему функций в неполную. В силу теоремы 1.1, общее число различных функций, зависящих от n аргументов, равно . Поэтому существует тривиальная полная система , состоящая из всех функций этого класса. Т.к. любая ФАЛ может быть представлена в СНДФ или СНКФ, то, следовательно, будет верным и утверждение о полноте системы, состоящей из трех функций: отрицания, конъюнкции, и дизъюнкции. Воcпользовавшись правилом де-Моргана: и видим, что в СНДФ и СНКФ можно заменить конъюнкцию () через отрицание ( ) и дизъюнкцию (), или дизъюнкцию через конъюнкцию и отрицание. Т.е. базисы { , } и {, } являются минимальными. Из того факта, что всякая ФАЛ представима в СНПФ следует, что базис , , является полным. Из этой системы можно исключить отрицание, т.к. . Если в СНПФ произвести такую замену, то получим представление функции через { , , 1}. Такое представление носит название полинома Жегалкина (полином по ). Аналогично, из соотношений 1.27 и 1.33 следует, что полную систему функций образуют {, , }. Кроме того, из последней системы можно исключить конъюнкцию (), (т.к. ), а отрицание выразить через импликацию и константу нуля (). Т.е. { , 0 } также образуют базис. Теорема 1.7 Функция Шеффера образует в полную систему. Доказательство: Имеем: ; . Т.к. отрицание и конъюнкция образуют в множестве полную систему, следовательно и функция Шеффера образует полную систему. Теорема 1.8 Функция Пирса (Вебба) образует в полную систему. Доказательство: Имеем: ; . А так как отрицание и дизъюнкция образуют полную систему, следовательно и функция Пирса образует полную систему. Теорема Поста-Яблонского (без доказательства) Для того чтобы система ФАЛ была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию: не сохраняющую нуль; не сохраняющую единицу; не являющейся линейной; не являющейся монотонной; не являющейся самодвойственной. Применим теорему для доказательства, например, полноты системы функций {, }. Функция (отрицание) не сохраняет константы нуля и единицы и не является монотонной. Функция (дизъюнкция) не является самодвойственной и линейной. В таблице 1.2 приведена принадлежность элементарных функций тому или иному из классов, используемых в теореме Поста-Яблонского. Таблица 1.2
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||