WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |

Пусть для множества переменных X = {x1, …, xn} через (х с волx ной”) обозначается х или. Элементарной конъюнкцией (произведением) называется конструкция вида: U = xi1xi2 …xik, если в ней каждая буква встречается не более одного раза. Например, x1x2, x1x2x3 – элементарные конъюнкции, а x1x1, x3x2x3 – неэлементарные. Конституентой 1 называется n-местная элементарная конъюнкция, включающая все переменные из набора Х (в виде либо xi... xik, либо xi) в точности по одному разу. Общее число таких конституент равно 2n, т. е. числу наборов n-переменных.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций Ui:

D = U1 U2 … Um, не содержащая двух одинаковых конъюнкций, например:

х1х2 х1х2х3 х2х3.

Совершенная ДНФ (СДНФ) – это ДНФ, состоящая только из конституент 1, например:

х1х2х3 х1х2х3 х1х2х3 х1х2х3.

В булевой алгебре вследствие того, что при замене нуля единицей, а единицы нулем, дизъюнкция превращается в конъюнкцию, и наоборот, возникает двойственность свойств дизъюнкции и конъюнкции. Выполнив в приведенных определениях подобные замены, получим соответствующие определения для конъюнктивной нормальной формы. Например, для функции f(x1, x2, x3) элементарная дизъюнкция получается из элементарной конъюнкции инвертированием переменных и заменой операции конъюнкции на дизъюнкцию:

элементарная конъюнкция: элементарная дизъюнкция:

х1х2 х1 хконституента 1: конституента 0:

х1х2х3 х1 х2 хКонъюнктивной нормальной формой (КНФ) называется конъюнкция (х1 х2) (х1 х3).

различных элементарных дизъюнкций:

Совершенной КНФ (СКНФ) называется КНФ, состоящая только из (х1 х2 х3) (х1 х2 х3).

конституент 0:

Осуществляя такую замену, можно автоматически для любого выведенного впоследствии свойства (соотношения) получить двойственное ему свойство. Поэтому ограничимся рассмотрением утверждений лишь для ДНФ.

Теорема 1 (о приведении формулы к СДНФ). С помощью соотношений (1–16) любая формула булевой алгебры может быть приведена к СДНФ.

Пример. Преобразовать формулу f (x, y, z) = x yz xyz к СДНФ.

На основании соотношений (8, 9) приведем формулу к виду:

f (x, y, z) = x( y y)(z z ) yz(x x) xyz.

Используя соотношения (4, 1, 2, 3), последовательно придем к следующей формуле:

f (x, y, z) = (xy xy)(z z ) yzx yzx xyz = = xyz xyz xyz xyz xyz xyz xyz = = xyz xyz xyz xyz xyz xyz.

Полученная СДНФ эквивалентна исходной формуле и все выполненные шаги обратимы, т. е. от СДНФ с помощью соотношений (1–16) можно перейти к исходной формуле.

Теорема 2 (о представлении функции в СДНФ). Всякая булева функция f (x1, x2,…, xn) может быть единственным образом представлена в СДНФ.

По таблице истинности функции f (x1, x2,…, xn) легко получить ее СДНФ и СКНФ в соответствии с теоремой 2 и двойственностью свойств дизъюнкции и конъюнкции.

Каждому двоичному набору таблицы = (1,2,…,n) соответствует единственная конституента 1 вида:, обрах1 х2…хn щающаяся на этом наборе в 1 по правилу:

, если i = 1, xi xii = x, если i = 0.

i Все остальные конституенты 1 на данном наборе обращаются в 0.

Например, для функции f (x1, x2, x3) набору (0, 1, 0) соответствует x1x2xконституента 1:, а набору (1, 1, 0) –.

x1x2xОбразуя дизъюнкцию конституент 1, соответствующих всем наборам, на которых функция обращается в 1, получим СДНФ, равную данной функции.

xy f(x, y) Каждому двоичному набору таблицы = (1,2,…,n) соответствует единственная конституента 0 вида:, обращающаяся х1 х2 … хn x y f(x, y) конституенты 1 x y f(x, y) конституенты 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 на этом наборе в 0 по правилу:

, если i = 0, xi xii = x, если i = 1.

i Все остальные конституенты 0 на данном наборе обращаются в 1.

Например, для функции набору (0, 1, 0) соответствует конституента 0:

x1 x2 x3.

Образуя дизъюнкцию конституент 0, соответствующих всем наборам, на которых функция обращается в 0, получим СКНФ, равную данной функции.

Пример. Представим параллельно алгоритмы получения СДНФ и СКНФ для функции, заданной следующей таблицей истинности:

Получение СДНФ: Получение СКНФ:

1. По правилам, определенным выше, рядом со строками, где f(x, y) = 1, записать конституенты 1, а где f(x, y) = 0, записать конституенты 0.

2. Все полученные выражения для конституент связать операцией:

дизъюнкции для СДНФ: конъюнкции для СКНФ:

xу ху (x у) (х у) Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам булевой алгебры:

(x у) (х у) = хх ху ху уу = ху ху.

Рекомендуется использовать тот из двух алгоритмов, в котором меньше конституент, а затем упростить формулу, используя булевы операции.

Эквивалентные преобразования и минимизация формул базируются на следующих теоремах, вытекающих из теорем 1 и 2.

Теорема 3 (о представлении булевой функции формулой). Любая булева функция может быть представлена в виде формулы булевой алгебры, т.е. как суперпозиция конъюнкции, дизъюнкции и отрицания.

Действительно, в качестве формулы, представляющей любую булеву функцию f(x1, x2,..., xn) можно выбрать ее СДНФ.

Теорема 4 (об эквивалентных формулах). С помощью соотношений (1 – 16) всякую формулу булевой функции можно преобразовать в любую другую, эквивалентную ей, т. е. представляющей ту же самую булеву функцию.

Преобразовать формулу А в эквивалентную ей формулу В всегда можно через СДНФ F, которая в силу теоремы 2 будет общей для формул А и В, но на практике этот способ оказывается громоздким.



Упрощение булевых формул состоит в уменьшении количества входящих в них букв. Как известно, любую булеву функцию, отличную от 0, можно представить ее СДНФ. Элементарную конъюнкцию можно представить выражением:

где {0,1}, x0 = x, x1 = x, Ui = xi1…xirr, jj j j j xij( j = 1,2,…,r) и все различны. Число r называется рангом конъюнкции. Константа 1 считается конъюнкцией нулевого ранга.

Минимальной ДНФ (МДНФ) функции f(x1, x2,..., xn) называется ДНФ N = U1 …Uk, содержащая наименьшее число букв по сравнению с другими ДНФ, представляющими эту функцию.

Минимизация булевой формулы состоит в том, чтобы для всякой булевой функции найти представление в виде МДНФ. Все методы минимизации в классе ДНФ основываются на понятии простого импликанта.

Импликантом функции f(x1, x2,..., xn) называется элементарная конъюнкция если выполнено соотношение:

xij x1,…, xn, j = 1,…,r.

U f (x1,…, xn) 1, где {} Переменные, не вошедшие в конъюнкцию, являются несущественными для данного импликанта.

Импликант можно представить как булеву функцию g = U, которая обращается в 1 на тех наборах значений переменных, на которых равна 1 функция f. Дизъюнкция импликантов g1 gm, накрывающая в совокупности все 1 функции f, совпадает с функцией f. При уменьшении ранга (длины) элементарной конъюнкции за счет отбрасывания несущественных переменных количество накрываемых импликантом 1 увеличивается. Конституента 1 (длины n) обращается в 1 лишь в одной точке, а элементарная конъюнкция длины n – k – в 2k точках. Выгодно поэтому накрывать функцию f элементарными конъюнкциями минимальной длины.

Простым импликантом функции f(x1,..., xn) называется импликант, если элементарная конъюнкция, получающаяся из него удалением любой буквы, не является импликантом функции.

Сокращенной ДНФ функции f(x1,..., xn) называется дизъюнкция всех простых импликантов функции.

Теорема 5. Сокращенная ДНФ функции f(x1,..., xn) представляет эту функцию.

Действительно, так как для простого импликанта то дизъюнкция всех простых импликантов представляет эту функцию.

Тупиковой ДНФ функции f называется дизъюнкция простых импликантов, из которых ни один простой импликант нельзя удалить так, чтобы полученная ДНФ все еще представляла функцию f.

Булева функция f(x1,..., xn) может иметь несколько тупиковых ДНФ, а среди них обязательно содержатся все ее минимальные ДНФ (их тоже может быть несколько), т. е. такие ДНФ, которые содержат наименьшее число букв по сравнению с остальными ДНФ этой функции. Получение МДНФ можно разбить на два этапа: 1) получение сокращенной ДНФ; 2) получение тупиковых ДНФ и выбор из них МДНФ.

Получение сокращенной ДНФ основано на использовании соотношений (1–16), рассмотренных теорем и понятий, а также следующих правил эквивалентных преобразований и минимизации формул с целью их упрощения.

1. Правило подстановки формулы вместо переменной. При подстановке формулы F вместо переменной х все вхождения переменной х в исходное соотношение должны быть одновременно заменены формулой F.

Например, соотношение F F = 1, полученное из закона “исклюх х = ченного третьего” ( ), верно для любых F.

2. Правило замены подформул. В булевой алгебре равенство F1 = Fозначает, что формулы F1 и F2 эквивалентны, т.е. описывают одну и ту же функцию f. Следовательно, если какая-либо формула F содержит F1 в качестве подформулы, то замена F1 на F2 не изменяет элемента функции f, над которым производят операции в формуле F. Поэтому формула F ‘, полученная из F такой заменой, эквивалентна исходной формуле F.

Пример. Возьмем соотношение правила де Моргана х1х2 = х1 хх1 х1хи подставим вместо формулу. Получим х1х3х2 = х1х3 х2, т. е.

две формулы, не эквивалентные исходным, но эквивалентные между собой. Используя снова правило де Моргана и закон двойного отрицания ( х = х ), можно получить цепочку преобразований формул, которые экви- валентны между собой:

х1х3х2 = х1х3 х2 = х1 х3 = х2 = х1 х2 х3.

2. Правила упрощения формул:

х ху = х, Поглощение: (17) х(х у) = х. (18) Докажем равенство (17), используя соотношения (9, 4, 11):

х ху = х 1 ху = х(1 у) = х 1 = х.

Равенство (18) доказывается с помощью соотношений (4, 3, 17):

х(х у) = хх ху = х ху = х.

Склеивание / расщепление: ху ху = х. (19) Доказательство склеивания:

ху ху = х( у у) = х 1 = х.

Расщепление обратно склеиванию и используется для доказательства эквивалентности преобразований сложных формул.

Обобщенное склеивание (исключение лишних членов дизъюнкции) / расщепление:

хz уz xy = хz уz. (20) Доказывается (20) с помощью расщепления (19) и поглощения (17):

хz уz xy = хz уz xy(z z ) = = хz уz xyz xyz = хz уz.

Исключение отрицания: (21) Доказывается (21) с помощью расщепления, идемпотентности ( х х = х ) и закона “исключенного третьего” ( ):

х х = х( у у) ху = ху ху ху = ху ху ху ху = = х( у у) у(х х) = х 1 у 1 = х у.

Приведение булевой формулы к ДНФ (в том числе к СДНФ) выполняется с помощью соотношений и правил (1–21). Сначала с помощью правила двойного отрицания (6) и правил де Моргана (15, 16) все отрицания “спускаются” до переменных. Затем раскрываются скобки, с помощью правила идемпотентности (3), законов противоречия (7) и “исключенного третьего” (8) удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а с помощью свойств констант (9–14) удаляются константы. С помощью правил упрощения формул (17–21) приводят формулу к сокращенной ДНФ, которая может оказаться тупиковой ДНФ или, возможно, минимальной ДНФ.





Пример. Упростить булеву формулу:

ху x( y xz)(x( y z) yz) = хy (xy xxz) (x( y z)) y z = xy xy(x ( y z))( y z ) = = xy xy(x yz )( y z ) = xy xy(x y yyz x z yz ) = = xy xyy xyyz xyz xyz = xy xyz = y(x x z ) = = y(x z ) = xy yz.

Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные. Получим СДНФ для предыдущего примера:

хy уz = хy(z z ) (x x)yz = xyz xyz xyz xyz = = xyz xyz xyz.

Получение тупиковой ДНФ состоит в нахождении простых импликантов с помощью алгоритма Блейка, суть которого заключается в следующем.

1. Формула обобщенного расщепления (21), записанная в виде:

Х z Y z = X z Y z X Y, (22) где z – буква, X, Y – элементарные конъюнкции, позволяет вводить в ДНФ новый член. После применения соотношения (22) несколько раз к исходной формуле F (пока получаются новые члены), ее можно привести к формуле F1, которая будет содержать все простые импликанты представляемой ею булевой функции f.

2. Формулу F1 необходимо освободить от всех членов, не являющимися простыми импликантами, используя операцию поглощения (17), и прийти к сокращенной ДНФ, представляемой формулой F2.

3. Если некоторый член в формуле F2 может быть получен с помощью применения соотношения (22), возможно, неоднократного из остальных членов, то его можно исключить как лишний. В результате процесса исключения лишних членов придем к некоторой тупиковой ДНФ F3.

4. Для получения всех тупиковых ДНФ, описанный способ исключения следует применить несколько раз, изменяя порядок исключения разных членов. Нахождение минимальных ДНФ требует громоздкой работы по перебору всех тупиковых ДНФ. Поэтому на практике ограничиваются нахождением какой-нибудь одной тупиковой ДНФ, принимая ее за МДНФ.

Пример. Покажем процесс минимизации ДНФ, заданной формулой:

F = хyz xу xyz.

1. По формуле расщепления (22) для пар членов 1 и 2, 2 и 3 получим:

F1 = хyz xу yz xyz xz.

Применение соотношения (22) к любым парам членов формы F1 не приводит к появлению новых членов. Следовательно, в форме F1 содержатся все простые импликанты функции f, представляемой формой F.

2. Применение операции поглощения (17) к форме F1 (3-й член поглощает 1-й, 5-й поглощает 4-й) приводит к сокращенной ДНФ:

F2 = xу yz xz.

3. По операции обобщенного склеивания (20) 1-й член получается из двух других, т. е. является лишним, поэтому исключается:

F3 = yz xz.

Форма F3 не содержит лишних членов и, следовательно, является искомой тупиковой ДНФ. В данном случае тупиковая ДНФ является единственной – значит это минимальная ДНФ функции f.

3. КОНТРОЛЬНОЕ ЗАДАНИЕ Контрольное задание по курсу “Дискретная математика” состоит из трех частей: основные понятия теории множеств; обработка ориентированного графа; работа с булевыми функциями.

При выполнении каждой части задания в соответствии с индивидуальным вариантом, приведенным в таблицах, по каждому пункту задания необходимо привести теоретические сведения и представить его решение.

Номер варианта задания соответствует последней цифре шифра студента.

Основные понятия теории множеств Общие понятия теории множеств приведены в п. 4.2 (разд. 1).

Определение множества состоит в том, чтобы указать, какие элементы ему принадлежат. При этом элементы множества заключаются в фигурные скобки. Существуют три основные способа определения множеств.

Перечисление элементов Например, А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – множество десятичных цифр.

Этот способ пригоден для определения конечных множеств небольшого числа легко различимых элементов. Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного достаточно широкого множества U (своего для каждого случая), которое называется универсальным множеством, или универсумом.

Описание характеристического предиката Характеристический предикат (свойство, признак) – это некоторое логическое утверждение (условие) в виде формы Р(х), возвращающее логическое значение (истина или ложь).

Любая форма Р(х) определяет некоторое множество А следующим образом: А = {x | P(x)}, что читается так: “множество всех х, если Р(х) – истинно”. Таким образом, элемент а {x | P(x)}, если Р(а) – истинное высказывание, т. е. форма Р(х) является селектором (свойством), определяющим принадлежность проверяемого предмета данному множеству.

Это наиболее общий способ определения множеств.

Например, пусть N0 = {0, 1, 2, …} – множество натуральных чисел, включая 0, тогда можно задать множество десятичных цифр следующим образом:

D = {x | x N0 и x < 10}.

Возможны видоизменения основной скобочной записи. Вместо {x | x А и Р(x)} часто пишут {x А | Р(x)} – это множество всех элементов из А, обладающих свойством Р(х).

Определение множества с помощью порождающих процедур Множество может быть определено с использованием элементов уже известных множеств в результате применения к ним некоторого правила (алгоритма, процедуры, формулы, операций). Если Р(х) есть некоторое свойство, а f – функция, то через { f(x) | P(x)} можно обозначить множество всех таких у, для которых имеется х, обладающий свойством Р(х) и такой, что y = f(x).

U A Например, пусть Z – множество целых чисел, тогда C = {x2 | x Z} – B А B множество квадратов целых чисел.

Такие обозначения допускают естественные обобщения. Например, P = {(x, y) | x {a1, …, ak}, y {b1, …, bk}} – это множество всех пар, A U первая компонента которых принадлежит множеству А = {a1, …, ak}, а B А В вторая – множеству В = {b1, …, bk}.

Pages:     | 1 | 2 || 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.