metod_15.03.04_atppp_moas_2016 (1016590), страница 4
Текст из файла (страница 4)
Например, такой полной системой является функция стрелка Пирса.Стрелка Пирса обозначается x1x2, задается эта функция следующейтаблицей истинности:x1x2001010100110x1x2Другое название этой функции ИЛИ-НЕ, что становится понятным при анализетаблицы истинности.Докажем, что функция стрелка Пирса является полной системой.Построим для этой функции СДНФ:. Глядя на этуформулу, также становится понятным, почему функцию стрелка Пирса называют ИЛИ-НЕ.Теперь выразим функции отрицание, конъюнкция и дизъюнкция черезСтрелку Пирса. По закону идемпотентностиможно выразить следующей формулой:.. Поэтому отрицаниеВоспользовавшись законом двойного отрицания и законом де Морганадля конъюнкции, легко можно выразить конъюнкцию через стрелку Пирса:Воспользовавшись законом двойного отрицания, через стрелку Пирсаможно выразить дизъюнкцию:Таким образом, мы выразили через стрелку Пирса функции системы отрицание, конъюнкция и дизъюнкция, которая является полной, тем са-мым доказав полноту системы, состоящей только из стрелки Пирса.Однако существует еще одна функция, которая является полной.
Этофункция штрих Шеффера – x1 | x2 (другое ее название И-НЕ), и выражаетсяона следующей таблицей истинности:x1x2x1 | x2001011101110Полином Жегалкина — полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающееили. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики.
Полином Жегалкина имеет следующий вид:Существует несколько способов построения полинома Жегалкина.По таблице истинностиПусть для функциизадана таблица истинности. Запишемсначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядкеувеличения количества единиц и находим коэффициенты с учётом того,что,а. За каждую подстановку находим только один коэффи-циент.Пример: Дана функцияи её таблица истинности:00000000100010000110010000101001101011101000110010101001011111001110101110111110Построим для неё полином Жегалкина:Так как, то.
Далее подставляем все остальныенаборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:Таким образом, полином Жегалкина выглядит так:Преобразование дизъюнктивной нормальной формыЭтот способ основан на том, что. Если функция задана в видеДНФ, то можно сначала убрать дизъюнкцию, используя правило Де-Моргана, авсе отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как), а нечетное число одинако-вых слагаемых равно одному такому слагаемому.
Либо же можно заменитьдизъюнкцию по следующему правилу:.Если функция задана в СДНФ, то так как при любых значениях входныхпеременных в единицу обращается не более одного члена выражения, то достаточно просто заменить все дизъюнкции исключающим ИЛИ.Пример: Дана функция вДНФ, построимполином Жегалкина.Запишем функцию так:;Сгруппируем слагаемые и воспользуемся преобразованием (1):Воспользуемся свойствами конъюнкциитем, чтои, а также, и упростим выражение:Ещё раз воспользуемся преобразованием (1):Раскроем скобку по алгебраическим правилам:Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:Заменим отрицание на прибавление :Раскроем скобки:Выкинем парные слагаемые и получим окончательную формулу:Метод треугольникаМетод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы всоответствии со следующими правилами:1.Строится полная таблица истинности, в которой строки идут в по-рядке возрастания двоичных кодов от 000...00 до 111...11.2.Строится вспомогательная треугольная таблица, в которой первыйстолбец совпадает со столбцом значений функции в таблице истинности.3.Ячейка в каждом последующем столбце получается путём сложе-ния по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строкеи строкой ниже.4.Столбцы вспомогательной таблицы нумеруются двоичными кодамив том же порядке, что и строки таблицы истинности.5.Каждому двоичному коду ставится в соответствие один из членовполинома Жегалкина в зависимости от позиций кода, в которых стоят единицы.Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке010 — член B, ячейке 000 — член 1 и т.д.6.Если в верхней строке какого-либо столбца стоит единица, то соот-ветствующий член присутствует в полиноме Жегалкина.Фактически, этот метод является модификацией метода построения потаблице истинности, описанного выше.
По сравнению с ним он удобнее тем,что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.Пример преобразования таблицы истинности в полином Жегалкина дляфункции трёх переменных P(A,B,C) показан на рисунке.Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможнымипутями влево, до столбца P таблицы истинности, делая ходы влево и влевовниз, записать значения в конечных ячейках и сложить их все между собой помодулю 2.Таким образом, в первом столбце сверху записан коэффициент,во втором —,в третьем—,в четвёртом —и так далее, то есть при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.Закон двойственностиОпределение.Формулы А и А* называются двойственными, если формула А* получаетсяиз формулы А путем замены в ней каждой операции на двойственную.Имеет место следующий закон двойственности: если формулы А и В равносильны, то равносильны и им двойственные формулы, т.е.
А* В*.В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построитьнужный процессор, имея в распоряжении элементы, реализующие конъюнкцию,дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуютли (и если существуют, то какие) другие системы булевых функций, обладающихтем свойством, что с их помощью можно выразить все другие функции.Введемврассмотрениерядклассовфункций:1. Класс функций, сохраняющих константу 0, т.е. таких функцийy=f(x1,x2...xn),чтоf(0,0...0)=0.Например,xvy(¬x).2.
Класс функций, сохраняющих константу 1, т.е. таких функцийy=f(x1,x2...xn),чтоf(1,1...1)=1.Например,xv¬(yx).3. Класс самодвойственных функций, т.е. таких функций y=f(x1,x2 ... xn), чтоf(x1,x2...xn)=¬(f(¬x1,¬x2¬xn))....4. Класс линейных функций, т.е. таких функций y=f(x1,x2 ... xn), которые могутбыть представлены в виде f(x1,x2 ... xn)=c0⊕c1x1⊕c2x2⊕...⊕cnxn, где c0, c1, c2 коэффициенты,которыемогутприниматьзначение0или1.5. Класс монотонных функций. На множестве наборов из нулей и единицBn={(x1,x2 ... xn):xi∈{0,1},i=1,2...n} введем частичный порядок следующим образом:(a1,a2...an)=(b1,b2...bn) тогда и только тогда когда a1=b1, a2=b2 ... an=bn.
Функцияf(x1,x2 ... xn) называется монотонной, если для любых двух элементов из Bn таких,что (a1,a2 ... an)=(b1,b2 ... bn) следует, что f(a1,a2 ... an)=f(b1,b2 ... bn).Система S булевых функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной.
Говорят, чтофункционально полная система S булевых функций образует базис в логическомпространстве. Базис S называется минимальным, если удаление из него любойфункциипревращаетэтусистемувнеполную.Критерий полноты (Теорема Поста): Система S булевых функций являетсяполной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную,нелинейнуюинемонотонную.В таблице приведены свойства, которыми обладают элементарные булевыфункции (символ * - отмечает свойство, которым обладает данная функция).Не сохра- Не сохраНазваниеОбозна- нимостьнимостьчениекон-кон-станты 0 станты 1НеНеНесамодвой-линей-монотон-ственностьностьностьКонст.
00Конст. 11*Отриц.¬*Конъюн.&**Дизъюн.v**Имплик.→***Эквивал.∼******Сумма помод. 2ШтрихШеффераСтрелкаПирса*⊕*****|*****↓*****Используя теорему Поста и данную таблицу можно строить базисы изэлементарных функций по следующему правилу. Выбрав любую элементарнуюбулеву функцию и дополнив ее при необходимости другими функциями так,чтобы все они вместе удовлетворяли теореме о функциональной полноте. Черезфункции этого базиса можно выразить все другие булевы функции.Построим некоторые часто используемые в приложениях базисы.1. Система функций S1={¬,&,v} образует базис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
