5723

Дискретная математика. Курс лекций

Конспект

Математика и математический анализ

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

Русский

2012-12-18

1.72 MB

14 чел.

  1.  Теория множеств

                                 § 1.1. Множество

Любое понятие дискретной математики можно определить с помощью понятия множества.

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

                                                                  (Основатель теории множеств Кантор)

Современное определение:

Множество- совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое.

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

Примеры множеств:

  1.  М1- множество всех натуральных чисел: 1,2,3…;
  2.  М2- множество всех натуральных чисел 100;
  3.  М3- множество всех решений уравнения Isin xI=1;
  4.  М4- множество всех чисел вида /2к, где к- множество всех натуральных чисел;
  5.  М5- множество всех действительных чисел (в дальнейшем R);
  6.  М6- футбольная команда «Спартак» (т.е. множество её футболистов);
  7.  М7- множество всех футбольных команд высшей лиги.

Если элемент m принадлежит множеству М, то записывается mM, если m не является элементом множества M, то это записывается mM.

Например: m=7  , тогда mM1; k=-3, тогда kM1.

Множества бывают конечными и бесконечными. Множество называют конечным, если число его элементов конечно, т.е. если существует натуральное число N, являющееся числом элементов множества.

Если множество не содержит ни одного элемента, т.е. N=0, то оно называется пустым и обозначается .

Множество называют бесконечным, если оно содержит бесконечное число элементов.

Для задания множества используют фигурные скобки { }, например, М={0,1,2,3}.

Множество М’ называется подмножеством множества М тогда и только тогда, когда любой элемент множества М’ принадлежит множеству М:

М’М(mMmM),

где - знак включения подмножества; - «если …, то …», - «если и только если …».

Например, можно записать: М2М1, М3М4, но нельзя записать М6М7, так как М6 и М7 множества разной природы.

Множества А и В равны если их элементы совпадают, иначе говоря АВ и ВА А=В.

Например: М34.

Если АВ и АВ, то А часто называют собственным, строгим или истинным подмножеством В.

АВ

Знак называется знаком строгого включения.

Число элементов в конечном множестве М называется мощностью М и часто обозначается |M|. Пустое множество имеет мощность равную 0.

Способы задания множеств:

  1.  Перечислением (списком своих элементов), например, А={a,b,d,h} означает, что множество А состоит только из четырех  элементов a,b,d,h.
  2.  Порождающая процедура описывает способ получения элементов множества из уже полученных элементов либо из других объектов.

Например, в М1, М3, М4 можно определить все элементы множества.

Символ = множеств обладает свойствами:

  1.  Если X=Y, то Y=X – симметричность;
  2.  X=X – рефлексивность;
  3.  X=Y и Y=Z, то X=Z – транзитивность.

Символ обладает свойствами:

  1.  XX – рефлексивность;
  2.  XY и YZ  XZ –транзитивность.

Истинно так же . Любое множество М содержит в себе пустое множество в качестве подмножества (хотя в природе не существует пустого множества). Из определения множества следует, что в нем не должно быть неразличимых элементов, например:

М={2,2,3,5} – 1 и 2 элемент одинаковы.

Второе свойство: местоположение элемента в множестве строго не определено.

§ 1.2. Операции над множествами

Множество часто задают графически в виде замкнутого круга, получившего название диаграмма Эйлера (или Венна).

Два множества называются совместными, если они имеют одинаковые элементы.

Графически это будет выглядеть как наложение кругов А и В.

Два множества называются несовместными, если они не имеют одинаковых элементов.

Универсальное множество- обозначается I. Универсальное множество состоит из всех элементов множеств, участвующих в операции над множествами. Графически универсальное множество изображается в виде прямоугольника, внутри которого изображаются круги Эйлера.

Операции над множествами:

  1.  Объединение множеств.

Объединением множеств А и В называют множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В. Символически это можно записать так: А В={х | хА или хВ}.

Операцию объединения иногда называют суммой множеств и обозначают А+В. Пример:

А={1,2,3,4,5} и В={2,4,6,7}, тогда  АВ={1,2,3,4,5,6,7}.

Графически объединение совместных множеств выглядит

Для несовместных множеств пример:

А={1,2,3,4} и В={5,6,7} , тогда

АВ={1,2,3,4,5,6,7}.

Операция действует для нескольких множеств:

                               n

Х1X2X3Xn=Xi .

                                             i=1

Для объединения множеств справедливы коммутативный и ассоциативный законы:

АВ=ВА                        и                          (АВ)С=АС).

Объединение множества с самим собой дает тоже множество (а не два одинаковых множества).

АА=А          

Это наглядно видно на диаграмме Эйлера

Общая площадь соответствует только А.     А                              А

Объединение множества А с пустым множеством дает само множество А:

А=А.

Объединение множества А с универсальным множеством дает универсальное множество:

АI=I.

Рассмотрим множества из § 1.1.:

М1М21    ,   М3М434     ,    М4М55  ,     М6М66  .

Обобщая выше сказанное нужно отметить, что всегда АВ). Но неверно АВ), нужно записать аВ).

  1.  Пересечение множеств.

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

АВ={х| хА и хВ}.

Пример: А={1,2,3,4,5}   В={2,4,6,7}, тогда пересечение этих множеств

АВ={2,4}.

Графически пересечение выглядит как заштрихованная одинаковая часть кругов.

Операция действует для нескольких множеств:

                               n

X1X2X3Xn=Xi

                                              i=1

Для пересечения множеств справедливы коммутативный и ассоциативный законы:

АВ=ВА       ,   (АВ)С=АС)

Пересечение множества А с самим собой дает само множество А:

АА=А.

Множества А и В находятся в общем положении, если выполняются три условия: существует элемент множества А, не принадлежащий В; существует элемент множества В, не принадлежащий А; существует элемент принадлежащий как А, так и В.

Между множествами А и В может быть пять отношений:

  1.  А=В, тогда АВ=А=В;
  2.  АВ, тогда АВ=А;
  3.  ВА, тогда АВ=В;
  4.  Когда множества А и В- несовместные, тогда АВ=;
  5.  Множества А и В находятся в общем положении.

Пересечение множества А с пустым множеством дает:

А

Пересечение множества А с универсальным множеством I дает множество А.

Рассмотрим примеры из § 1.1.:

М1М22

М3М434

М4М54

М6М66

  1.  Разность множеств.

Данная операция в отличие от операции объединения и пересечения определяется только для двух множеств. Разностью множеств А и В называют множество, состоящее из всех тех и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В. Разность множеств А и В обозначают через А\В.

А\В={x|xA и xB}      

Пример: Х={1,2,3,4,5}, Y={2,4,6,7}.

X\Y={1,3,5}

А для Y\X={6,7}

Операция разности не коммутативна, т.е. А\ВВ\А.

Если А\В=, то можно записать АВ.    

А\=А ;               А\I=.

Рассмотрим примеры из § 1.1.:

М21=  ,   М12={множество натуральных чисел>100} ,    М34=.

Симметрической разностью множеств А и В называется множество

АВ=(А\В)(В\А)

Пример:    А={1,2,3,4,5}  ,B={2,4,6,7} тогда А\В={1,3,5}    B\A={6,7}  AB={1,3,5,6,7}

Операция симметрической разности естественно уже коммутативна. Для симметрической разности действует ассоциативный закон:

АС)=(АВ)С

  1.  Операция дополнения.                        _

Операция дополнения обозначается  А – называется дополнением множества А до универсального множества I.

Формальное определение:

_

А={x|xI и xA}

Пример: I={1,2,3,4,5,6,7}  и  А={3,4,5}    тогда

_

А={1,2,6,7}.

                                                        _

Из определения следует, что А и А не имеют общих элементов.

    _                      _

АА=    ,      АА=I.                                     =

Из симметрии определения следует, что    А=А.

С помощью операции дополнения можно в удобном виде представить разность множеств.

                                                  _         _

А\В={x|xА и xB}={x|xA и xB}=AB .

Покажем это на диаграмме Эйлера

                                                 _                                                       _

                                              = B                                               = AB=A\B

Для алгебры множеств  верны законы:

1.Коммутативный  АВ=ВА  ,        АВ=ВА  ;

2.Ассоциативный  АВС=АС)=(АВ)С

                              АВС=АС)=(АВ)С ;

3.Дистрибутивный АС)=(АВ)С)

                               (АВ)С)=АС)  ;

4.Закон идемпотентности    АА=А        АА=А      , т.е. в алгебре множеств отсутствуют коэффициенты и степени;

                                                =

5.Закон двойного отрицания А=А ;

                                       ____  _   _         ___   _   _

6.Законы де Моргана     АВ=АВ        АВ=АВ  ;

                                                       _                                  _

7.Законы склеивания  (АВ)В)=А        (АВ)В)=А ;

8.Законы поглощения АВ)=А   АВ)=А;

                                        _                               _

9.Законы Порецкого АВ)=АВ        АВ)=АВ  ;

Следствием основных законов являются следующие соотношения:

                                  _                 _

АI=A  ; AI=I  ;   AA=   ;   AA=I   ;   A=   ;    A=A .

                § 1.3.Векторы и прямые произведения

Вектор- это упорядоченный набор элементов. Вектор еще называют кортежем. В кортеже каждый элемент занимает строго определенное место. Элементы, образующие кортеж, называются координатами или компонентами. В кортеже место каждого элемента является вполне определенным и не может быть произвольно изменено. Число элементов кортежа называют его длиной. Для обозначения кортежа используют круглые скобки. В кортеже элементы могут совпадать (в отличие от множества).

А=(а1234) – кортеж длины 4.

Частным случаем кортежа является кортеж длиной 1 и пустой кортеж длиной 0, обозначаемый () или /\.

Кортежи равны, если они имеют одинаковую длину и элементы кортежей равны, т.е. кортежи (а1…аm) и (b1bn) равны, если m=n и a1=b1,a2=b2 ,…,am=bn.

Кортеж (a1,a2) может рассматриваться как точка на плоскости или вектор проведенный из начала координат в данную точку.

                                          Тогда компоненты а1 и а2 будут проекциями вектора

                                     На оси  1 и 2.

                                       Пр1 А=а1       Пр2 А=а2

Упорядоченное n-элементное множество вещественных чисел (а1,,, аn) рассматривается как точка в воображаемом n-мерном пространстве, называемом иногда гиперпространством, или n-мерным вектором. При этом компоненты n- элементного кортежа А будем рассматривать как проекции этого кортежа на соответствующие оси n- мерного пространства.

Прi А=аi                  i=1, … ,n.

Пусть М- множество, состоящее из кортежей одинаковой длины. Тогда проекцией множества М будет называться множество проекций кортежей из М.

Например: М={(1,2,3,4,5),(2,1,3,5,5),(3,3,3,3,3)}. Тогда Пр2 М={2,1,3}, Пр2,4М={(2,4),(1,5),(3,3)}.

                      Прямое произведение множеств.

Прямым произведением множеств А и В называют множество, обозначаемое АВ и состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству А, а вторая множеству В, элементами прямого произведения являются двухэлементные кортежи вида (а,b).

Формальное определение  

АВ={(a, b)| aA, bB}

Для прямого произведения множеств не выполняется условие перестановки сомножителей.

АВВА

Прямым произведением множеств x12,…,хr называется множество, обозначаемое х1х2хr и состоящее из всех тех и только тех кортежей длины r, первая компонента которых принадлежит х1, вторая х2 и т.д.

Пример:  А={1,2,3}     B={2,3,1}     C={3,1,2}

ABC={(1,2,3),(1,3,3),(1,1,3),…}

Частным случаем операции прямого произведения является понятие степеней множества. Пусть М- произвольное множество. Назовем s степенью множества М и обозначим через Мs прямое произведение s одинаковых множеств М.

МsММ

             s

Например: М={1,2}  тогда М2={(1,1),(1,2),(2,1),(2,2)} .

М1=М     Мо={/\}

Если А и В- множества вещественных чисел, то прямое произведение АВ графически можно изобразить в виде прямоугольника.

Координатное представление точек плоскости, предложенное французским математиком и философом Декартом, исторически первый пример прямого произведения. Поэтому иногда прямое произведение называют декартовым.

Пусть А1, А2, … ,Аn- конечные множества и |А1|=m1, |A2|=m2, … ,|An|=mn- мощности этих множеств. Тогда мощность множества А1А2Аn равна произведению мощностей множеств А1, А2, … ,Аn:

|A1A2An|=m1m2…mn

Отсюда следствие |An|=|A|n.

Если М=АВ , то Пр1 М=А , а Пр2 М=В.

                        § 1.4. Соответствия и функции

Соответствия. Соответствием между множествами А и В называется подмножество GAB.

Если (а,b)G, то говорят, что b соответствует а при соответствии G. Множество Пр1 G называется областью определения соответствия, множество Пр2G –областью значений соответствия. Если Пр1 G=А, то соответствие называется всюду определенным или полностью определенным (в противном случае соответствие называется частичным); если Пр2 G=В, то соответствие называется сюръективным.

Множество всех bB, соответствующих элементу аА, называется образом а в В при соответствии G. Множество всех а, которым соответствует В, называется прообразом b в А при соответствии G. Если СПр1 G, то образом множества С называется объединение образов всех элементов С. Аналогично определяется прообраз множества D для любого DПр2G.

Соответствие G называется функциональным (или однозначным), если образом любого элемента из Пр1 G является единственный элемент из Пр2 G. Соответствие G между А и В называется взаимно однозначным (иногда пишут «1-1-соответствие»), если оно всюду определено, сюръективно, функционально, и кроме того, прообразом любого элемента из Пр2G является единственный элемент из Пр1G.

Примеры:

1)Англо-русский словарь устанавливает соответствие между множеством английских и русских слов. Это соответствие не является функциональным ( так как одному английскому слову, как правило, ставится в соответствие несколько русских слов); кроме того, оно практически никогда не является полностью определенным: всегда можно найти английское слово, не содержащееся в данном словаре.

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

3)Соответствие телефонов и номеров. Это соответствие обладает всеми свойствами взаимно однозначного соответствия кроме - сюръективности. Так как не все номера соответствуют телефонам (есть пустые номера).

4)Множество векторов вида (n,2n) задает взаимно однозначное соответствие между множеством N натуральных чисел и множеством 2n.

Если между конечными множествами А и В существует взаимно однозначное соответствие, то |A|=|B|. Если |A|>|B|, и отображение всюду определено, то в А найдутся как минимум два элемента, которым соответствует один и тот же  элемент bВ. Если |A|<|B| и отображение сюръективно, то в В найдутся два элемента соответствующих одному и тому же аА.

          |A|=|B|                                     |A|>|B|                                      |A|<|B|

a1                             b1             a1                          b1               a1                        b1

a2                             b2             a2                          b2               a2                        b2

a3                             b3             a3                          b3               a3                        b3

a4                             b4             a4                          b4               a4                        b4

a5                             b5             a5                          b5               a5                        b5

a6                             b6             a6                                                                        b6

Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие.

Множества равномощные с N называются счетными, т.е. между множеством  существует взаимно однозначное соответствие с натуральным рядом чисел.

Множество всех действительных чисел, даже определенных на отрезке, не является счетным. Мощность несчетных множеств называется континуум; множества такой мощности называются континуальными.

Композицией соответствий называют последовательное применение двух соответствий. Композиция соответствий есть операция с тремя множествами X,Y,Z на которых определены два соответствия.

Например: Если 1 соответствие определяет распределение водителей по автомашинам, 2 соответствие определяет распределение автомашин по маршрутам, то композиция соответствий определяет распределение водителей по маршрутам.

Отображение. Отображение записывается Г: АВ. ГА- образ А в В.

a       b         c          d          e

1       2      3     4     5    6    7     8

Для нескольких подмножеств Аi можно записать

   n           n                                                                             n             n

Г(Аi)=ГАi                         ;                Г(Аi)ГАi .

    i=1        i=1                                                                          i=1          i=1

Отображение является частным случаем соответствия и поэтому для отображений также действуют понятия обратного отображения и композиции отображения.

Частным случаем отображения является случай, когда множества А и В совпадают. При этом отображение Г:АА будет представлять собой отображение множества А самого в себя и будет определяться парой (А,Г), где ГА2.

Г2А=Г(ГА)     Для любого S2  ГsА=Г(ГS-1А).

Функция. Функцией называется функциональное соответствие (однозначное соответствие). Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип АВ и обозначение fВ. Каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Можно записать f(a)=b.

Функция, для которой из                    Этот график функцией не является.

X2=X1 следует Y2=Y1.

Иногда вместо f(а) записывают fa или аf. Элемент а называется аргументом функции, b- значением функции на а. Если f(а) состоит из единственного элемента, то f называется функцией- константой.

Функции f и q равны, если их область определения- одно и то же множество А и для любого аА    f(a)=q(a).

Функция типа А1А2АnB называется n- местной функцией. В этом случае принято считать, что функция имеет n аргументов: f(a1,a2,…,an)=b, где а1А1, а2А2,…,аnAn, bB. Сложение, умножение, вычитание и деление являются двуместными функциями на R, т.е. функциями типа R2R. Таблица выигрышей лотереи задает двухместную не полностью определенную функцию, которая устанавливает соответствие между парами из N2 (серия, номер) и множеством выигрышей.

Пусть дано соответствие GАВ. Если соответствие НВА таково, что (b,а)Н тогда и только тогда, когда (а,b)G, то соответствие Н называется обратным к G и обозначается G-1.

Если соответствие, обратное к функции fВ, является функциональным, то оно называется функцией, обратной к f, и обозначается f-1. Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к fВ, требуется, чтобы каждый элемент b из области значений f имел единственный прообраз. Это означает, что для функции fВ обратная функция существует тогда и только тогда, когда f является взаимно однозначным соответствием между своей областью определения и областью значений.

Пример:  Функция y=sin(х) имеет тип RR. Отрезок [-/2 , /2] она взаимно

Пусть даны функции fВ и qС. Функция hС называется композицией функций f и q (обозначение fq), если имеет место равенство h(x)=q(f(x)). Композиция f и q представляет собой последовательное применение функций f и q; q применяется к результату f. Часто говорят, что функция h получена подстановкой f в q. Знак ○ аналогично умножению часто опускается.

Функция, полученная из f1,…,fn некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией f1,…,fn. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой.

Способы задания функций.

1.Табличный- самый простой способ задания функции. Таблица это конечные списки пар (х,f(x)). Однако таким образом могут быть заданы функции, определенные на конечных множествах. Таблицы функций, определенных на бесконечных множествах (например, тригонометрических), задают эти функции только в конечном числе точек. Для вычисления значений (приближенных!) функций в промежуточных точках служат правила интерполяции.

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

Иногда для разных подмножеств множества Х функции могут быть различными функциями. Пусть А1,…,Аn- непересекающиеся подмножества Х, тогда

                    f1(x) при хА1

  f(x)=           ……                              для i=1,…,n.

                    fn(x) при хАn

3)Если А и В множества вещественных чисел, то элементы (а,b)f можно изобразить в виде точек на плоскости. Совокупность таких точек представляет собой график функции.

4)Рекурсивная процедура задает функцию f, которую вычисляют последовательно по этапам, например, n!.

5)Возможны описания функции, которые не содержат способа вычисления функции, значение определяется сразу.

  1.  если хМ

                f(x)=

  1.  если хМ

Функция времени.

В основе понятия функции времени лежит множество TR с элементами t, называемое множеством моментов времени. Время обладает особенностью- оно имеет направление, т.е. Т- упорядоченное множество.

Функция времени определяет отображения f множества моментов времени Т на множество вещественных чисел   f:TR.

Каждая пара (t,x) определяет значение функции в момент t и называется событием или мгновенным значением функции. Полная совокупность пар (t,x) представляет собой функцию времени.

Если Т=R, т.е. t может принимать любое вещественное значение от - до +, то функцию x(t) называют функцией с непрерывным временем.

Но часто не используется весь диапазон -  t  +, а используется сужение функции х(t) на интервал (t1,t2]- называемым отрезком функции x(t).

Частный случай функции времени- единичная функция или единичный скачок.

               

                 0 при t                              1   

1(t-)=

                            1 при t>

                                                                        0                                          t

Если множество Т представляет собой множество натуральных чисел

 …,-2,-1,0,1,2,…n, то говорят о функции с дискретным временем.

  х(t)

                -1    0      1     2       3                    n           t

Если вместо множества Х ввести множество функций, а вместо Y ввести Т, то отображение примет вид J:F(x)Т. Элементами множества J будут пары (f(x),t), в которых f(x)F(x), а tT. В этом случае говорят, что вещественное число tT представляет собой функционал J от функции f(x)F(x) и записывают t=J[f(x)].

Оператором L называется отображение L :XY, в котором множества X и Y являются множествами функций с элементами x(t) и y(t), так что элементами множества L будут пары (x(t),y(t)). Оператор L преобразует функцию х(t) в функцию y(t)=L[x(t)]. Примером оператора служит оператор дифференцирования p, ставящий в соответствие функции f(x) другую функцию f’(x)=df(x)/dx, что может быть записано в виде    f’(x)=p[f(x)].

                       § 1.5.Отношения

Подмножество RМn называется n-местным отношением на множестве М. Говорят, что а1, … ,аn находятся в отношении R, если (а1 ,…,аn)R. Одноместное отношение- это просто подмножество М. Такие отношения называют признаками: а обладает признаком R, если аR и RМ.

Наиболее часто встречаются двухместные, или бинарные, отношения.

Для задания бинарных отношений можно использовать любые способы задания множеств. Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на множестве М={а1,…,аm}- квадратная матрица С порядка m, в которой элемент сij, стоящий на пересечении i-ой строки и j-ого столбца, определяется следующим образом:

Сij =     1, если аi R aj ;

           0 в противном случае.

Например, для конечного множества {1,2,3,4,5,6} отношение «общий делитель, отличный от единицы» можно вывести в таблицу.

Отношение называется обратным к отношению R (обозначение R-1), если ai R-1 aj тогда и только тогда, когда aj R ai. Из определения непосредственно следует, что (R-1)-1=R. Для отношения < обратным является отношение >.

Свойства отношений. Отношения R называется рефлексивным, если для любого аМ имеет место а R а. Отношение R называется антирефлексивным, если ни для какого аМ не выполняется а R а. Отношение и «иметь общий делитель» рефлексивны, отношение < и «быть сыном» антирефлексивны. Главная диагональ матрицы рефлексивных отношений содержит только 1.

Отношение R называется симметричным, если для пары (а,b) М2 из а R b следует b R a (иначе говоря, для любой пары R выполняется либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: сij=cji для любых I и j. Отношение R называется антисимметричным, если из ai R aj и aj R ai следует, что ai=aj. Пример антисимметричного отношения- отношение : действительно, если ab и ba, то a=b. Отношение R симметрично тогда и только тогда, когда R=R-1.

Отношение R называется транзитивным, если для любых a, b, c из aRb и bRc следует aRc. Отношение = - транзитивно, a=b и b=c, следует a=c. Отношение «быть сыном»-  нетранзитивно -  а сын b, b сын  с,   не   следует   а   сын   с.   Для   любого

                                          /\

отношения R отношение R, называемое транзитивным замыканием, определяется

                                       /\

следующим образом: a R b, если в М существует цепочка из n элементов а=а12,…, аn-1, an=b,  в   которой  между   соседними  элементами выполнено R: a R a2, a2 R a3,

                                                          /\              /\

…,an-1 R b. Если R транзитивно, то R=R и R=R.

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т.д.

Отношение эквивалентности. Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Эквивалентность обозначается . Отношение равенства (=) на любом множестве является отношением эквивалентности. Равенство- минимальное отношение эквивалентности. Формулу вида (a+b)(a-b)=a2-b2 обычно называют отношением равносильности и определяют следующим образом: формулы равносильны, если они задают одну и ту же функцию.

Пусть на множестве М задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент а1М и образуем класс (подмножество М) с1, состоящий из а1 и всех элементов, эквивалентных а1; затем выберем элемент а2с1 и образуем класс с2, состоящий из а2 и всех элементов, эквивалентных а2, и т.д. Получится система классов с1, с2,…, (возможно бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т.е. ci=M. Эта система классов обладает следующими свойствами:

  1.  Она образует разбиение, т.е. классы попарно не пересекаются;
    1.  Любые два элемента из одного класса эквивалентны;
    2.  Любые два элемента из разных классов неэквивалентны.

Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности R.

Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению к R. Мощность этой системы называется индексом разбиения.

Отношение порядка. Отношение называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно:

хх – истина (рефлексивность); хy и yx   x=y (антисимметричность); xy и yz  xz (транзитивность).

Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно:

x<x ложно (антирефлексивность); x<y и y<x взаимоисключается (антисимметричность); x<y и y<z  x<z (транзитивность).

Элементы a,b сравнимы по отношению порядка R, если выполняется a R b или b R a. Множество М, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае.

Отношения и , < и > полностью упорядочивают множества. Примеры:

1)Отношение подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми являются сотрудники разных отделов;

2)Русский алфавит- строгий полный порядок.

Отношение доминирования. Если x доминирует над y, то обозначает x>>y, т.е. x значительно превосходит y. Между элементами множества имеет место отношение доминирования, если эти элементы обладают следующими свойствами:

1)Никакой индивидуум не может доминировать над самим собой, т.е. х>>х ложно;

2)В каждой паре индивидуумов в точности один индивидуум доминирует над другим, т.е. х>>y и y>>x взаимоисключается.

В отношении доминирования свойство х<<y и y<<z  x<<z не имеет место. Например, если в соревнованиях команда x победила команду y, а команда y победила команду z, то это не значит, что команда x обязательно победит команду z. Отношение доминирования, как правило, используется в отношениях людей.

                         § 1.6. Элементы общей алгебры

Функцию типа nМ будем называть n-арной операцией на множестве М; n называется арностью операции .

Множество М вместе с заданной на нем совокупностью операций, т.е. система А=(М; 1, 2, 3, … ,m, …) называется алгеброй; М называется основным, или несущим, множеством алгебры А.

Совокупность операций 1, … , m, … называется сигнатурой. Множество М’М называется замкнутым, если значения операции на аргументах из М’ принадлежат М’.

Пример: Алгебра (R; +, ) называется полем действительных чисел. Обе операции бинарные. Все конечные подмножества R, кроме {0}, не замкнуты относительно обеих операций.

Свойства бинарных алгебраических операций.

Результат применения бинарной операции к элементам a,b будем записывать не в функциональном виде (a,b), а в виде ab, как принято для арифметических операций.

Операция называется ассоциативной, если для любых элементов a,b,c

(ab)c=a(bc).

Сложение и умножение чисел ассоциативны и можно записать a+b+c, abc без скобок. Операции , тоже ассоциативны (см. § 1.2.).

Ассоциативной операцией является композиция отображений.

Операция называется коммутативной, если для любых элементов a, b

ab=ba

Сложение и умножение чисел коммутативны, а вычитание и деление некоммутативны. Операция , - коммутативны (см. § 1.2.).

Операция называется дистрибутивной слева относительно операции , если для любых a,b,c

a(bc)=(ab)(ac)

и дистрибутивной справа относительно , если

(ab)c=(ac)(bc) .

Дистрибутивность разрешает раскрывать скобки. Например, умножение дистрибутивно относительно сложения слева и справа. Сложение не дистрибутивно относительно умножения. Операции и дистрибутивны относительно друг друга   слева и справа.

                                    

  1.  Логика.

                         § 2.1. Логические функции

Математическая логика состоит из 2 множеств:

  1.  Пустое множество- , соответствующее 0;
    1.  Универсальное множество- I, соответствующее 1.

Элементы 0 и 1 в данном случае не являются числами в обычном смысле, а скорее всего являются логическими значениями: истина (1) и ложь (0).

Логическая функция f12,…,хn) – это функция , принимающая значение 0,1, от логических переменных х1, х2,…,хn. Всякая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части значения функции на этих наборах. Такая таблица называется таблицей истинности. Например:

Х1

Х2 

Х3

 f

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0

Наборы, на которых функция f=1, часто называют единичными наборами функции f, а множество единичных наборов- единичным множеством f. Соответственно наборы, на которых f=0, называют нулевыми наборами f.

Число наборов в таблице истинности равно 2n: для n=2- наборов будет 4, для n=3- наборов будет 8 и т.д. В таблице истинности наборы расположены в порядке возрастания двоичного кода.

Логические функции.

1. Дизъюнкция. Равносильна операции объединения над множествами I и .

Х1

Х2

Х12

0

0

0

0

1

1

1

0

1

1

1

1

Еще имеет название: логическое сложение, «ИЛИ». Обозначается знаками , +.
Значение составного высказывания =1, если хотя бы значение одного высказывания =1.
Аналогично значение определяется для нескольких переменных.

Х1

Х2

Х1Х2

0

0

0

0

1

0

1

0

0

1

1

1

2. Конъюнкция- логическое умножение, «И». Равносильна операции пересечению множеств I и . Обозначение: &, , , или как умножение без знака.

Значение составного высказывания=0, если хотя бы значение одного высказывания =0.

Х

Х

0

1

1

0

Аналогично значение определяется для нескольких переменных.

  1.  Отрицание или еще инверсия (или функция «НЕ»). Равносильна операции  

 

Х1

Х2

Х1Х2

0

0

1

0

1

1

1

0

0

1

1

1

         4.   Импликация, логическое следование. Обозначается х1х2, х1х2.  

Читается «если х1, то х2». Принимает значение 1, если нет уменьшения значений последовательности переменных х1, х2. Операция не коммутативна, т.е. (х1х2)2х1). Операцию импликации можно разложить: f1х2121х2 .

5.       Функция   Вебба    или    стрелка    Пирса.   Еще  называется отрицание

Х1

Х2

Х1Х2

0

0

1

0

1

0

1

0

0

1

1

0

дизъюнкции, «ИЛИ-НЕ».

          f1х21х212.

         Значение составного высказывания =0, если значение хотя бы одного высказывания =1.

6.     Функция Шеффера (штрих Шеффера), «И-НЕ».

Х1

Х2

Х12

0

0

1

0

1

1

1

0

1

1

1

0

f=x1|x2=x1+x2=x1x2.

Значение составного высказывания =1, если значение хотя бы одного высказывания= 0.

  1.  Функция эквивалентности или равнозначности.

Х1

Х2

Х12

0

0

1

0

1

0

1

0

0

1

1

1

  f=x1~x2=x1x2=x1x2+x1x2.

Значение составного высказывания =1, если значения высказываний равны, и значение составного высказывания =0, если значения высказываний не равны.

  1.  Функция «сложение по модулю 2» или функция неравнозначности.

Х1

Х2

Х1Х2

0

0

0

0

1

1

1

0

1

1

1

0

   f=x1x2=x1x2=x1x2=x1x2+x1x2

Значение составного высказывания будет =1, если значения высказываний не равны, и будет =0, если значения высказываний равны.

От двух переменных, на 4 наборах, получается 16 различных функций. Мы записали 8 функций, остальные 8 функций названия не имеют и легко выражаются через перечисленные функции.

Среди операций самым приоритетной является инверсия, потом конъюнкция. В остальных случаях, чтобы указать приоритет выполнения необходимо использовать круглые скобки.

Пример:

f=(x1+x2x3)(x3~(x1x2))                                                             (2.1)

       2    1       6    4   5        3

Построим таблицу истинности для этой функции.

Х1

Х2

Х3

1

2

3

4

5

6

1

0

0

0

1

1

0

1

0

0

2

0

0

1

1

1

0

0

1

1

3

0

1

0

1

1

1

1

1

1

4

0

1

1

0

0

1

0

0

1

5

1

0

0

1

1

1

1

1

1

6

1

0

1

1

1

1

0

0

0

7

1

1

0

1

1

0

1

0

0

8

1

1

1

0

1

0

0

1

1

  1.  Штрих Шеффера х2х3 ;
  2.  Дизъюнкция х1+1 ;
  3.  Неравнозначность х1х2;
  4.  Инверсия  х3;
  5.  Эквивалентность 4~3;
  6.  Импликация 25.

Наборы 2,3,4,5,8- единичные, наборы 1,6,7- нулевые. Алгебра (Р2;+,&, ) называется булевой алгеброй логических функций. Операции булевой алгебры также часто называют булевыми операциями.

Основные свойства булевых операций:

  1.  Ассоциативность:

х12х3)=(х1х23           х1+(х23)=(х12)+х3;

  1.  Коммутативность:

х1х22х1         х1221;
3.   Дистрибутивность дизъюнкции относительно конъюнкции:

х1+(х2х3)=(х12)(х13);

  1.  Дистрибутивность конъюнкции относительно дизъюнкции:

х123)=х1х21х3;

  1.  Идемпотентность:

хх=х       х+х=х;

  1.  Двойного отрицания:

х=х;

  1.  Свойства констант:

х·1=х    х·0=0     х+1=1     х+0=х     0=1          1=0;

  1.  Правила де Моргана:

х1х212     х121х2;

  1.  Закон противоречия:

хх=0;

  1.  Закон «исключения третьего»:

х+х=1.

Упрощение формул:

  1.  Поглощение:

x+xy=x     x(x+y)=x

Докажем   х+xy=x(1+y)=x·1=x

                 x(x+y)=xx+xy=x+xy=x;

  1.  Склеивание:

xy+xy=x

Докажем xy+xy=x(y+y)=x·1=x;

  1.  x+xy=x+y                           x        y

                    _           _  _           _       _

Докажем  x+xy=xy+xy+xy=xy+xy+xy+xy=x+y

                                xy+xy

4.Обобщенное склеивание:

хz+yz+xy=xz+yz

Докажем xz+yz+xy=xz+yz+xyz+xyz=xz+xyz+yz+xyz=xz+yz

Пример1:

Используя законы эквивалентности и упрощения, сократим функцию

                                                      0

xy+x(y+xz)(x(y+z)+yz)=xy+(xy+xxz)(x(y+z)yz)=xy+xy(x+(y+z))(y+z)=

                                                        0                    0

xy+xy(x+yz)(y+z)=xy+xy(xy+xz+yzy+yzz)=xy+xyxy+xyxz+xyyz=

xy+xyz+xyz=xy+xyz=y(x+xz)=y(x+z)=xy+yz

          +                         (x+z) по 3 п. упрощения

Пример 2:

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

F=(x1+x2x3)(x3~(x1x2))=(x1+x2x3)(x3~(x1x2+x1x2))=

=(x1+x2x3)(x3(x1x2+x1x2)+x3(x1x2+x1x2))=(x1+x2+x3)(x3(x1x2x1x2)+x1x2x3+x1x2x3)=

                                                                                                      0

=(x1+x2+x3)(x3(x1+x2)(x1+x2)+x1x2x3+x1x2x3)=(x1+x2+x3)(x1x1x3+x1x2x3+x1x2x3+

         0

+x2x2x3+x1x2x3+x1x2x3)=(x1+x2+x3)+x1x2x3+x1x2x3+x1x2x3+x1x2x3=

=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3=x1x3+x1x2+x2x3+x1x2x3

 § 2.2. Совершенные нормальные формы. Разложение функций по переменным

Введем обозначение х0=х, х1=х. Пусть - параметр, равный 0 или 1. Тогда х=1, если х=, и х=0, если х.

Теорема. Всякая логическая функция f(x1,x2,…,xn) может быть представлена в следующем виде:

                                        1   m

f(x1,…,xm,xm+1,…,xn)=V  x1xm f(1,…,m,xm+1,…,xn),

                             1m

где mn, а дизъюнкция берется по всем 2m наборам значений переменных х1,…,хm.

Это равенство называется дизъюнктивным разложением по переменным х1…хm (разложение Шеннона).

Например, при n=4,m=2 разложение имеет вид:

f(x1,x2,x3,x4)=x1x2f(0,0,x3,x4)+x1x2f(0,1,x3,x4)+x1x2f(1,0,x3,x4)+x1x2f(1,1,x3,x4)

                    0 0                    0  1                    1 0                    1 1

Возьмем конкретный пример для f(x1,x2,x3,x4)=x1x2x3+x1x2x3x4+x2x3x4 и разложим по полученной формуле

             0         0                             0                    0                0        0

f=x1x2(00x3+00x3x4+0x3x4)+x1x2(01x3+01x3x4+1x3x4)+x1x2(10x3+10x3x4+0x3x4)+

                      0          0

+x1x2(11x3+11x3x4+1x3x4)=x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3

При m=1 получаем разложение по одной переменной:

f(x1,…,xn)=x1f(0,x2,…,xn)+x1f(1,x2,…,xn)

Другой крайний случай- разложение по всем n –переменным (m=n). Рассмотрим пример (2.1), m=3, n=3.

                               0                                      1                                         1

f(x1,x2,x3)=x1x2x3((0+00)(0(00)))+x1x2x3((0+01)(1(00)))+x1x2x3((0+10)

                                           1                                         1                                            0

(0(01)))+x1x2x3((0+11)(1(01)))+x1x2x3((1+00)(0(10)))+x1x2x3((1+01)

                                             0                                       1                           0

(1(10)))+x1x2x3((1+10)(0(11)))+x1x2x3((1+11)(1(11)))=x1x2x30+x1x2x31+

                                                  0          0

+x1x2x31+x1x2x31+x1x2x31+x1x2x30+x1x2x30+x1x2x31=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3

При дизъюнктивном разложении функции по всем переменным остаются, те наборы переменных, на которых функция принимает значение 1.

Тогда формулу разложения по всем переменным можно записать:

                                 1    n

f(x1,…,xn)=       V       x1…xn

                 f(1n)=1

Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции.

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

Таким образом, существует взаимно однозначное соответствие между таблицей истинности f и ее СДНФ, и, следовательно, СДНФ для всякой логической функции единственна.

Единственная функция, не имеющая СДНФ, - это константа 0. Чтобы построить СДНФ по таблице функции, необходимо выбрать все наборы функции = 1. Каждый набор соответствует элементарной конъюнкции. Если значение i-ой переменной =1, то в элементарную конъюнкцию записывается сама переменная хi, а если значение i-ой переменной=0, то в элементарную конъюнкцию записывается отрицание i-ой переменной- хi.

СДНФ- это дизъюнкция элементарных конъюнкций.

Например: Рассмотрим таблицу истинности для функции (2.1) и запишем все наборы при f=1:

f=001+010+011+100+111=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3 

                                          0  0  1  0  1 0   0 1 1   1 0 0    1 1 1

Полученная СДНФ полностью соответствует вышеприведенному примеру при разложении по всем переменным.

Всякая логическая функция f(x1xn) может быть представлена в виде

                                                    m  m

f(x1,…,xm,xm+1,…,xn)=    &           (V xm V f(1m,xm+1,…,xn)

                                   1m     I=1

где mn.

Конъюнкция берется по всем 2m наборам значений переменных х1…хm.

Это равенство называется конъюнктивным разложением по переменным x1,…xm.

Например, при n=4,m=2 конъюнктивное разложение

f(x1,x2,x3,x4)=(x1+x2+f(0,0,x3,x4))(x1+x2+f(0,1,x3,x4))(x1+x2+f(1,0,x3,x4))

                     0    0                      0   1                      1    0

(x1+x2+f(1,1,x3,x4))

          1    1

Возьмем конкретный пример f(x1,x2,x3,x4)=x1x2x3+x1x2x3x4+x2x3x4  и разложим по полученной формуле.

F=(x1+x2+(00x3+00x3x4+0x3x4))(x1+x2+(01x3+01x3x4+1x3x4))(x1+x2+(10x3+10x3x4+

     0   0                                                          0       1                                                         1      0

+0x3x4))(x1+x2+(11x3+11x3x4+1x3x4))=(x1+x2+x3x4)(x1+x2+x3x4)(x1+x2+x3x4)

                                    1    1

(x1+x2+x3)

При m=1получаем разложение по одной переменной

f=(x1+f(0,x2,x3,x4))(x1+f(1,x2,x3,x4))

     0                                     1

Другой крайний случай- разложение по всем n-переменным (m=n). Например рассмотрим пример (2.1):

f(x1,x2,x3)=(x1+x2+x3+((0+00)(0(00))))(x1+x2+x3+((0+01)(1(00))))

                            0    0      0                                                           0     0     1

(x1+x2+x3+((0+10)(0(01))))(x1+x2+x3+((0+11)(1(01))))

 0     1       0                                                         0      1      1

(x1+x2+x3+((1+00)(0(10))))(x1+x2+x3+((1+01)(1(10))))

  1     0      0                                                           1    0     0

(x1+x2+x3+((1+10)(0(11))))(x1+x2+x3+((1+11)(1(11))))=

 1      1    0                                                        1     1       1

(x1+x2+x3+0)(x1+x2+x3+1)(x1+x2+x3+1)(x1+x2+x3+1)(x1+x2+x3+1)(x1+x2+x3+0)

(x1+x2+x3+0)(x1+x2+x3+1)=(x1+x2+x3)1111(x1+x2+x3)(x1+x2+x3)1=

(x1+x2+x3)(x1+x2+x3)(x1+x2+x3) .

При конъюнктивном разложении по всем переменным остаются, те наборы переменных, на которых функция принимает значение 0.

Тогда формулу разложения по всем переменным можно записать

                                 1       n

f(x1,…,xn)=       &     (x1+…+xn )

                   f(1n)=0

Такое разложение называется совершенной конъюнктивной нормальной формой (СКНФ) функции f. СКНФ содержит ровно столько элементарных дизъюнкций, сколько нулей в таблице истинности f; каждому нулевому набору соответствует дизъюнкция всех переменных или их отрицаний. Таким образом, существует взаимно однозначное соответствие между таблицей истинности f и ее СКНФ, и, следовательно, СКНФ для всякой логической функции единственна. Единственная функция, не имеющая СКНФ, константа 1.

Чтобы построить СКНФ по таблице истинности, необходимо выбрать все наборы функции равные 0. Каждый набор соответствует элементарной дизъюнкции. Если значение I-ой переменной на нулевом наборе функции соответствует 0, то в элементарную дизъюнкцию записывается сама переменная xi. Если значение I-ой переменной на нулевом наборе функции соответствует 1, то в элементарную дизъюнкцию записывается отрицание этой переменной- xi.

CКНФ- это конъюнкция элементарных дизъюнкций.

Например, рассмотрим таблицу функции f (2.1) и выпишем все наборы с значением функции f=0.

f=(0+0+0)(1+0+1)(1+1+0)=(x1+x2+x3)(x1+x2+x3)(x1+x2+x3)

Полученная СКНФ полностью соответствует выше приведенному примеру при разложении по всем переменным.

        § 2.3. Минимизация формул алгебры высказываний

Цель минимизации: сократить число операций и получить более простую функцию по отношению к исходной.

Способы минимизации:

1.С помощью эквивалентностей и упрощений. С помощью этого способа не всегда можно получить минимальную функцию.

Пример 1: f(x1,x2,x3)=x1+x2x3+(x1x2)x3+x1x2x3 =x1+x2x3+(x1+x2)x3+x1x2x3=

x1+x1x3+x1x2x3+x2x3+x2x3=x1+x2

          x1                 x2

Пример 2: f(x1,x2,x3)=(x1x2+x3)x2x3+(x1x2+x3)x2x3+x1x3+x2+x2x3=

x2x3(x1x2+x3+x1x2+x3)+x1x3x2+x2x3=x2x3+(x1+x3)x2+x2x32х31х22х32х3=

                   1                                                      

х31х22  =х32

         х2

Чтобы удачно провести минимизацию, необходимо сначала привести функцию к ДНФ.

2.Геометрическая минимизация.

Рассмотрим геометрическую интерпретацию для 2 переменных. Для этого строим квадрат со стороной =1. Углы квадрата соответствуют значениям переменных х1х2. Соответственно сторона квадрата соответствует переменной или           ее отрицанию.

  х2

01     х2       11

х1                 х1

         х2

00                10        х1

 x2

01               11

00               10

                                 X1

Пример:f(x1,x2,x3)=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3=011+111+

                                                                                                              x2x3

+111+110+101+100+100+000=x2x3+x1+x2x3

                x1                  x2x3

                011                               111

  x2

 010                      110

                              x3

                              

                 001                             101             

 000                           100      x1

            0111                                      1111

0101                                    1101

                                                                                       0110                       1110

                                                                      х2

              0011                         1011

                                                                      0100                          1100

х4         0001             1001                                                            х3

                                                                                                                                

0010                            1010

         

                                                                  0000                          1000

Каждый куб гиперкуба соответствует одной переменной:

1111+1110+1100+1101+1011+1010+1000+1001=1_ _ _=х1;

0111+0110+0100+0101+0011+0010+0000+0001=0_ _ _=х1;

0111+1111+1101+0101+0110+1110+1100+0100=_1_ _=х2;

0011+1011+1001+0001+0010+1010+1000+0000=_0_ _=х2;

0111+1111+1011+0011+0110+1110+1010+0010=_ _1_=х3;

0101+1101+1001+0001+0101+1100+1000+0000=_ _0_=х3;

0111+1111+1101+0101+0011+1011+1001+0001=_ _ _1=х4;

0110+1110+1100+0100+0010+1010+1000+0000=_ _ _0=х4.

Для 5-и переменных строится супергиперкуб. Геометрический метод позволяет успешно минимизировать функцию до 4-х переменных и требует от исследователя не только определенных навыков, но и объемного воображения.

3.Методы минимизации:

1)Метод Квайна.

Этапы метода:

1.1.По таблице истинности или с помощью разложения по всем переменным получить СДНФ. Провести склеивание элементарных конъюнкций.

Например: f=x1x2x3+x1x2x3+x1x2x3+x1x2x3

1.x1x2x3                        1-2   x1x2x3+x1x2x3=x1x2

2.x1x2x3                         1-3   x1x2x3+x1x2x3=x2x3

3.x1x2x3                         1-4   не склеивается

4.x1x2x3                         2-3   не склеивается

  1.  не склеивается
    1.  x1x2x3+x1x2x3=x1x3

Проведем склеивание  полученных конъюнкций:

1.x1x2                           1-2 не склеивается

2.x2x3                           1-3 не склеивается

3.x1x3                           2-3 не склеивается

1.2.Проверим полученную функцию на покрытие, для чего построим таблицу:

x1x2x3

x1x2x3

x1x2x3

x1x2x3

  x1x2

   +         

   +

  x2x3

   +                   

 

   +

  x1x3

   +

   +

Лишняя импликанта.

Минимальная ДНФ: x1x2+x1x3

Пример 2: Имеем таблицу функции:

x1x2x3

f

0

000

1

1

001

1

2

010

1

3

011

1

4

100

0

5

101

0

6

110

0

7

111

1

1этап: Проведем склеивание единичных значений .

  1.  x1x2x3+x1x2x3=x1x2
    1.   x1x2x3+x1x2x3=x1x3
    2.  не склеивается

         1-2   не склеивается

         1-3   x1x2x3+x1x2x3=x1x3

         1-7  не склеивается

         2-3   x1x2x3+x1x2x3=x1x2

         2-7   не склеивается

         3-7   x1x2x3+x1x2x3=x2x3

Все элементарные конъюнкции участвовали в склейках.

  1.  x1x2                      1-2  не склеивается
  2.  x1x3                      1-3  не склеивается
  3.  x1x3                      1-4  x1x2+x1x2=x1
  4.  x1x2                      1-5  не склеивается
  5.  x2x3                      2-3  x1x3+x1x3=x1

                                 2-4  не склеивается

                                 2-5  не склеивается

                                 3-4  не склеивается

                                 3-5  не склеивается

                                 4-5  не склеивается

Конъюнкция x2x3 не участвовала в склейках. Получена минимальная функция

        f=x1+x2x3

Проверка по второму этапу не требуется. Метод Квайна применим для булевых выражений средней степени сложности, а иногда и высокой.

Для булевых выражений малой и средней степени сложности наибольшее распространение получил метод карт Карно.

2)Метод карт Карно.

Карта Карно- это прямоугольная карта, состоящая из 2n клеток, где n – количество аргументов булевой функции при заполнении такой карты. В каждую клетку заносится значение функции по уникальному адресу, который записывается внизу клетки. Рассмотрим карту Карно для функции 2-х переменных (карта Карно состоит из 4 клеток).                  

x1

x2

F

 0

0

1

0

1

0

1

0

1

1

1

0

   1

   00

 0

 01

  1

  10

 0

 11

               X2

Правила склеивания:

  1.  Клетки, расположенные симметрично осям симметрии являются соседними и могут быть склеенными. Крайние склеенные клетки (клетки через ось симметрии) отличаются по адресу только в одном разряде.
  2.  Склеивается 2m клеток.

Наш пример для двух переменных: можно склеить 2 клетки 00+10. Склейка попадает на зону x1 и х1, и полностью соответствует зоне х2. Минимальная функция f=x2.

Для трех переменных карта Карно строится из 23=8 клеток.

                        Х3

                                               Х2

  0

  000

   1

  001

    1

     011

    0

     010

  0

  100

   0

  101

    1

   111

    1

   110

                     

                      1             2

                   

                       х4

                                       х3               1    Пусть дана СДНФ:

   1

  0000

   1

  0001

    1

   0011

   1

  0010

   1

   0100

   1

  0101

    1

     0111

   1

  0110 

   0

  1100

   0

  1101

    0

   1111

   0

  1110

   1

  1000  

   0

   1001

    0

   1011

   1

  1010

f=x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+

     0000            0001               0010             0011

          +x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+

   х2             0100              0101                 0111          0110

          +x1x2x3x4+x1x2x3x4

             1000                       1010

х1           1 cклейка: 0000+0001+0011+0010+

                           0100+0101+0111+0110=х1;

                                                       2                   2 склейка: 0000+0010+1000+1010=х2х4.

Для пяти переменных карта Карно состоит из 25=32 клеток.

Пусть дана СДНФ: f=x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+

+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+

+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5+x1x2x3x4x5

                                   x4                                          x3

                                                                            

      1

  1

   

      2

  1

      3

  1

      4

   1

      5

  1

 

      6

  1

      7

  1

          8

  1

      9

  1

     10

   1

     11

  1

     12

  1

    13

  1

        14

  1

       15

  1

        16

  1

        17

   1

        18

   1


    

      x5                                               x5

1 склейка: 1,2,3,5,13,15.16,18=8 клеток.     f1=x2x5

2 cклейка: 2,3,8,9=4 клетки.                         f2=x1x4x5

3 склейка: 4,10,12,17=4 клетки.                   f3=x3x4x5

4 cклейка: 6,11,10,12=4 клетки.                   f4=x2x4x5

5 cклейка: 11, 12, 14, 17=4 клетки.              f5=x1x4x5

6 cклейка: 6,7=2 клетки.                               f6=x1x2x3x5

fmin=x2x5+x1x4x5+x3x4x5+x2x4x5+x1x4x5+x1x2x3x5

Для шести переменных карта Карно состоит из 26=64 клеток.

Рассмотрим пример с уже заполненной картой Карно.

                                                        Х5

                                                                                                 Х4

                                                                                                            

      1 

   1

           2

   1

          3

   1

           4

   1

   0

   0

           5

   1

         6

  1

         7

   1

          8

   1  

          9

   1

         10

   1

   0

   0

     11

   1

        12

  1

       13

   1

         14

   1

        15

   1

         16

   1

   0

         17

   1

   0

  0

       18

   1

         19

   1

        20

   1

         21

   1

   0

   0

   0

  0

       22

   1

         23

   1

        24

   1

         25

   1

         26

   1

         27

   1

         28

   1

       29

  1

       30

   1

         31

   1

        32

   1

         33

   1

         34

   1

         35

   1

         36

   1

       37

  1

       38

   1

         39

   1

        40

   1

         41

   1

         42

   1

         43

   1

         44

   1

       45

  1

       46

   1

         47

   1

        48

   1

         49

   1

         50

   1

     51

   1

         52

   1

        53

  1

                                                                                         Х3

Х3

                                                                 

                                      Х6                                                                   Х6

  1.  склейка: 1-4,7-10,13-16,18-21,22-25,30-33,38-41, 46-49 – 32 клетки. f1=x4;
  2.  cклейка: 22-53- 32 клетки. f2=x1;
  3.  cклейка: 1,2,5-8,11,12,38,39,44-47,52,53- 16 клеток.     f3=x2x5 ;
  4.  склейка: 15,17,32,35- 4 клетки. f 4=x2x3x5x6 .

fmin=x1+x4+x2x5+x2x3x5x6  

В некоторых случаях выгодно производить склеивание не по 1, а по 0. При этом инверсия над переменной ставится в том случае, если склейка попадает в зону этой переменной и инверсия над переменной не ставится, если склейка не попадает в зону этой переменной. В результате склейки по 0 получается КНФ. Рассмотрим пример для 5-и переменных.  

                                                               

                                                             X4                                                 X3

       1

   0

          2

  0

            3

   0

         4

  0

            5

    0

           6

   0

         7

  0

          8

  0

           9

   0

         10

   0

          11

   0

         12

   0

        13

  0

          14

   0

           X2

            X1

                             X5                                                     X5

  1.  cклейка 2,3,13,14- f1=x2+x4+x5
  2.  cклейка 4,6,7,12- f2=x2+x4+x5
  3.  cклейка 8,9.10,11- f3=x1+x2+x4
  4.  cклейка 1,2- f4=x1+x2+x3+x5
  5.  cклейка 3,5,11,14- f5=x3+x4+x5

f=(x2+x4+x5)(x2+x4+x5)(x1+x2+x4)(x1+x2+x3+x5)(x3+x4+x5)

Для определения качества минимизации приняты следующие показатели- индексы простаты:

Lб- число букв переменных, встречающихся в записи ДНФ;

Lк- число элементарных конъюнкций, входящих в ДНФ;

L0- Число символов инверсии, встречающихся в записи ДНФ.

Пример: f1=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3

f2- минимизированная функция f1.

f2=x1+x2x3+x2x3

Lб1=18             Lб2=5

Lк1=6               Lк2=2

L01=8               L02=2

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

                 § 2.4. Тупиковые ДНФ

Рассмотрим два типа преобразований ДНФ:

1.Операция удаления элементарной конъюнкции согласно закону поглощения

         a+ab=a;

2.Операция удаления множителя согласно закону склеивания

        ab+ab=a.

ДНФ, которую нельзя упростить при помощи преобразований 1 и 2, называют тупиковой ДНФ.

Пример:

         f1=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3=x2x3(x1+x1)+x1x3(x2+x2)+

           +x2x3(x1+x1)+x1x3(x2+x2)=x2x3+x1x3+x2x3+x1x3

Больше упростить нельзя, поэтому полученная ДНФ является тупиковой. Исходную СДНФ можно упростить по другому:

F2=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3=x2x3+x1x3+x1x2

Данная ДНФ является также тупиковой.

F3=x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3+x1x2x3=x1x2+x2x3+x1x3

Данная ДНФ является также тупиковой.

               § 2.5. Минимизация не полностью определенных функций

Существует ряд функций, у которых на некоторых наборах значение функции не определено. Это возможно в двух случаях.

1)В принципе при работе устройства данная комбинация возникнуть не может. Например, десятичный счетчик (цифры 0-9). Для десятичного счетчика необходимо 4 разряда.

0000- 0             1010

0001- 1             1011

          0010- 2             1100

          0011- 3             1101

          0100- 4             1110

          0101- 5             1111

          0110- 6

          0111- 7

          1000- 8

          1001- 9

2)Данная комбинация возникнуть может, но на работу устройства никакого влияния не оказывает.

Неопределенные состояния доопределяются таким образом, чтобы минимизация прошла успешно.

Например:

X1

X2

X3

X4

X5

f

0

0

0

0

0

1

0

0

0

0

1

1

0

0

0

1

0

1

0

0

0

1

1

1

0

0

1

0

0

0

0

0

1

0

1

0

0

0

1

1

0

1

0

0

1

1

1

0

0

1

0

0

0

0

0

1

0

0

1

?

0

1

0

1

0

?

0

1

0

1

1

?

0

1

1

0

0

0

0

1

1

0

1

1

0

1

1

1

0

?

0

1

1

1

1

?

1

0

0

0

0

?

1

0

0

0

1

0

1

0

0

1

0

1

1

0

0

1

1

?

1

0

1

0

0

?

1

0

1

0

1

?

1

0

1

1

0

0

1

0

1

1

1

1

1

1

0

0

0

1

1

1

0

0

1

1

1

1

0

1

0

1

1

1

0

1

1

?

1

1

1

0

0

0

1

1

1

0

1

0

1

1

1

1

0

?

1

1

1

1

1

?

Построим карту Карно. Здесь и далее доопределенные состояния обозначаются жирным курсивом.

            Х5                                                Х5                             

                                           х4                                  х3                    

1

1

1

1

1

0

0

0

0

1 6

1  7

1   8

1   9

1 10

 

1  11  

0

112

113

114

115

119

0

0

0

116

117

0

118

F1х2х31х4х53х41х2х51х4х5+ х1х2х3

                     

                    §2.6. Совместная минимизация булевых функций

Пусть имеются функции

            

Y1=f(x1,x2,…,xn)

………………….

Ym=f(x1,x2,…,xn) .

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

Поэтому проводят их совместную минимизацию.

Три способа совместной минимизации:

1.Метод совместного склеивания. Основан на использовании законов булевых функций, очень громоздкий.

2.Метод каскадов. Основан на разложении сложных функций и поиске общих элементов. Не эффективен и не дает минимальной формы.

3.Метод суперпозиций.

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

Например:

F1=(1,2,3,6)

F2=(0,2,3,6)

F3=(0,3,5,6)

X1

X2

X3

F1

F2

F3

0

0

0

0

1

1

0

0

1

1

0

0

0

1

0

1

1

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

1

0

0

1

1

1

0

1

1

1

1

1

1

0

0

0

Для   каждой функции найдем минимальную.

  1

  1

  1

  1

  1

  1

 1

  1

1

1

1

1

                   F3 = х1х2х3 + х1х2х3 + х1х3х2 + х1х2х3    

Общее число импликанта равно 9

  

                    Х3                х2 

 

     Будем считать, что функции f2 и f3 формально зависимы от четырех аргументов.

         F2 = f1х2х3 f1)

         F3 = f1х2х3 f1)

                  F1            х3

1

1

0

1

1

1

1

1

0

0

0

              Минимизируем данные функции, используя в                    качестве аргумента  и функцию f1.

Х2   Восемь значений определены таблицей    истинности.

      После до определения можно записать f2 = х1х3 + х2f1

                                                                   F1 

                                                                            Х3  

1

0

1

1

0

1

1

1

1

0

0

1

1

1

Х1       

                                                                                                                                                                                                                                                                                                     

                     

                                                                                 Х2

          F3 = x1f1 + x1f1 + x2x3f1 + x1x2x3       

Итого в совокупности получили   8 импликанта.

                                                                                      Х1

Если выразить f3 через x1, x2, x3, f2, то получим карту Карно.

              F2         Х3                               f31х33f2+x2f2+x1f2    

                                                                                                         

1

1

0

0

1

1

1

1

0

1

1

1

  Х2  

Х1

                                                               F2                             F1

                                                                                                               

1

1

1

1

1

0

1

1

1

1

0

1

0

1

1

1

1

0

1

1

1

1

1

1

    

                                  Х2

                                                         

                                                                   Х3                           Х3  

 F3 = x1f1 + x1f2 + x3f2 + x1x2x3 

В итоге мы получили также 8 импликант.

                                          §2.7. Полнота

 

Любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные) хi, операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки (,) . (S0).

Можно ли любую булеву функцию f1, х2, . . ., хn) выразить в виде суперпозиции системы S, как это возможно для случая системы {v,&,¯}.

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

Пример: Системы S1 = {&, ¯} u S2 = {V, ¯} функционально полны.

 Х1 + х2 = х1х2  ,  х1х2 = Х1 + х2  - закон де Моргана.

                                                                                                                                                                                                             

                                                                                                   

Х1х2 + х234) = в системе S1 = х1х2х2х3х4=>в системе S2 = Х1 + х2 + х2 + х3 + х4  

С точки зрения функциональной полноты систему S0 можно считать избыточной: она сохраняет свойства полноты и при удалении из нее  дизъюнкции или конъюнкции.  

 Рассмотрим пять классов булевых функций

  1.  Классом К0 – булевых функций fi1, х2, . . ., хn),  сохраняющих       константу 0, называется множество функций вида

                     fi (0, 0, . . ., 0) = 0.

  1.  Классом К1 – булевых функций fi1, х2, . . ., хn), сохраняющих константу 1, называется множеством вида

          fi (1, 1, . . ., 1) = 1.

          Пример: f = ad + bc                                                                  (2.1)

                           F (0,0,0,0) = 00 + 0 0 = 1 1 + 0 1 = 1 + 0 = 1

                           F (a,b,c,d)K0

                                               F (1,1,1,1) = 1 1 + 1 1 = 0 0 + 1 0 = 0 + 0 = 0

                           F (a,b,c,d)K1

  1.  Классом Кл – линейных булевых функций fi1, х2, . . ., хn) называется множество функций вида

                fi1, х2, . . ., хn) = с0∑сixi          c0, сi = 0,1           I = 1,2, …, n

                               где ∑  сложение по модулю 2 для всех i.

Доказательство линейности функции будем проводить от обратного, т.е. предположим что функция линейна и определим все коэффициенты с0, сi на соответствующих наборах хi = 1. После этого проверим остальные наборы.

               Пример (2.1). Переменные a,b,c,d  дают функцию

               f = с0⊕саа⊕сbb⊕ссс⊕сdd   

               Определим с0 при наборе (0,0,0,0)

               f= 0 0 + 0 0 = 1 1 + 0 1 = 1 + 0 = 1    

                    с0⊕са0⊕сb0⊕сс0⊕сd0 = 1 => с0⊕0 = 1 => с0 = 1.                 

       

        0

Определим са при наборе (1, 0, 0, 0)   

F = 1 0 + 0 0 = 0 1 + 0 1 = 0    

1⊕ са1⊕сb0⊕сс0⊕сd0 = 0 => 1⊕ са1 = 0 => 1⊕ са = 0 =>са = 1      

                        

              0

Определим сb при наборе (0, 1, 0, 0)

  

F = 0 0 + 1 0 = 1 1 + 1 1 = 1  

1⊕1 0⊕сb1⊕сс0⊕сd0 = 1 => 1⊕ 0⊕сb1 = 1 => 1⊕сb =1=> сb = 0     

                              

                                                0                       1

Определим сс при наборе (0, 0, 1, 0)         

F = 0 0 + 0 1 = 1 1 + 0 1 = 1  

1⊕10⊕00⊕сс1⊕сd0=1=1⊕0⊕0⊕сс1⊕0 =1=>1⊕сс = 1=>сс = 0

 

Определим сd при наборе (0, 0, 0, 1)

F = 0 1 + 0 0 = 1 0 + 0 1 = 0  

1⊕10⊕00⊕00⊕сd1 = 0 = 1⊕0⊕00сd=0 =>1⊕сd = 0=>сd = 1

                                                                           0

На пяти наборах ((0,0,0,0),(1, 0, 0, 0),(0, 1, 0, 0),(0, 0, 1, 0),(0, 0, 0, 1)) определили коэффициенты с0=1,ca = 1, сb = 0, сс = 0, сd = 1.

Если на остальных 11 наборах условия сохранится, то функция F линейна.

Возьмем набор (1,1,1,1) и проверим на линейность

F = 11 + 11 = 00 + 10 = 0

1⊕1 1⊕01⊕01⊕11 = 1⊕1⊕0⊕0⊕1 = 1 0

Условие не выполняется,  значит, функция f* - нелинейная.

F (a,b,c,d) )Kл

  1.        Классом Кс -самодвойственных булевых функций fi1, х2, . . ., хn) называется множество булевых функций вида

         fi1, х2, . . ., хn) = fi1, х2, . . ., хn)

         Для функции (2.1) построим таблицу функций (табл.2.1).

         Наборы 0-15, 3-12, 4-11, 6-9 – самодвойственные.

А наборы 1-14, 2-13, 5-10, 7-8 – несамодвойственные, поэтому функция F – несамодвойственная.

Для определения несамодвойственности функции достаточно определить один набор, не удовлетворяющий этому условию.

N

N

a

a

b

c

c

d

F

F*

0

0

0

0

0

1

1

0

0

0

1

0

2

0

0

1

0

1

3

0

0

1

1

0

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

0

10

10

1

0

1

0

1

11

11

1

0

1

1

0

12

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

0

15

1

1

1

1

0

                                                                                            Таблица 2.1

    5.   Классом Км – монотонных булевых функций      fi1, х2, . . ., хn)   называется множество булевых функций вида

       (*1, *2, . . ., *n)(1, 2, . . ., n)↔(σ*i σi, i=1,2, …, n)

            f(*1, *2, . . ., *n)f(1, 2, . . ., n)

Для тестирования функции F(пример 2.1) на монотонность построим гиперкуб (рис.2.1). Вершиной куба будет набор функций F. Ребро куба образуется, если (*1, *2, *3, *4)(1, 2, 3, 4). В вершине гиперкуба проставим значении функции на данном наборе.

Ребра, на которых условие монотонности не выполняется, обозначим пунктирной линией.

Для определения немонотонности достаточно найти хотя бы одно пунктирное ребро гиперкуба.                                                               

                                                                          1111                                                                      

                                       1110               1101                  1011              0111

                    1100              1010            0110            1001             0101           0011

                                         1000                0100                  0010              0001               

                                                                           0000

                                                              Рис. 2.1                                                             

              Функция F- немонотонная. Например:  (1000)(0000) , а

                                                                              F(1000)<(0000).

Критерий полноты. Система S булевых функций fi является полной тогда и только тогда, когда выполняется, пять условий: существуют функция fiS, не сохраняющая константу нуль: fi K0; функция fiS, не сохраняющая константу единицу: fi K1; нелинейная функция, несамодвойственная функция и немонотонная функция в системе S.

Используя критерий полноты и метод Петрика, построим возможные базисы для двух переменных (х12).

Построим все булевы функции от двух переменных (табл.2.2).

                                                                                                               Таблица 2.2

Перем.

                                          Булевы функции

Х1

Х2

F0

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

0

0

1

1

0

1

0

1

0

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

 

Функция f0 1, х2) = 0 – константа нуль.

Функция f11, х2) = х1, х2 – конъюнкция.

Функция f21, х2) = х1х2 = х12 = х1→х2 = х1→х2 –левая  коимпликация (читается «не если х1, то х2»).

Функция f31, х2) = х1.

Функция f41, х2) = х1 х2 = х12 = х1←х2 = х1←х2 - правая коимпликация.

Функция f51, х2) = х2.

Функция f61, х2) = х1 х2+ х1 х2= х1 х2 сложение по модулю два или функция неравнозначности, неэквивалентности.

Функция f71, х2) = х1 + х2 – дизъюнкция.

Функция f81, х2) = х1 х2 = х12 = х1 ↓х2 – стрелка Пирса, ИЛИ-НЕ.

Функция f91, х2) = х1 х2 + х1 х2 = х12 – функция эквивалентности, равнозначности.

Функция f101, х2) = х2 – отрицание х2.

Функция f111, х2) = х12 = х1 ←х2 – правая импликация.

Функция f121, х2) = х1 - отрицание х1.  

Функция f131, х2) = х12  = х1→х2 – левая импликация.

Функция f141, х2) = х12 = х1 х2 =  х1ιх2 функция Шеффера.

Функция f151, х2) =1 – константа единица.

Для нахождения всех базисов в булевой функции двух переменных  построим двухмерную таблицу, каждой строке которой взаимно однозначно сопоставим  одиннадцать функций (функции f3 f4 f5 f10 f11 не рассматриваем), столбцу - класс: К0, К1, Кл, Кс, Км  и в клетке (i, j) ставим 1, если i-я функция не принадлежит j-му классу, в противном случае клетку(i, j)оставляем пустой (табл.2.3).

                                                                                 Таблица 2.3

Идентификатор        строки

Функция

 fi

              Классы

К0

К1

Кл

Кс

Км

a

b

c

d

e

g

k

m

n

p

r

0

1

2

6

7

8

9

12

13

14

15

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Методом Петрика определим все покрытия столбцов строками этой таблицы:

(g+k+m+n+p+r)(a+c+d+g+m+p)(b+c+e+g+n+p)(a+b+c+d+e+g+k+n+p+r)(c+d+g+k+m+n+p)=g+p+abk+kc+an+cn+dn+ake+kbd+ked+mc+mn+bm+me+cr+rbd+red=g+p+kc+ an+cn+dn+mc+mn+bm+me+cr+abk+ake+kbd+ked+rbd+red.

Каждое из полученных покрытий πi порождает базис Bi  .

π1 = {g}↔B1={↓} базис Вебба (Пирса).

π2 = {p}↔B2={|} базис Шеффера.

π3 = {k,c}↔B3={→,~}.

π4= {a,n}↔B4={→,0} –импликативный базис.

π5= {с,n}↔B5={→,→}.

π6= {d,n}↔B6={→,}.

π7= {m,c}↔B7={→,¯} – коимпликативный базис.

π8 = {m,n}↔B8={→,‾} – импликативный базис.

π9 = {b,m}↔B9={&,‾} – конъюнктивный базис Буля.

π10= {m,e}↔B10={+,‾} – дизъюнктивный базис Буля.

π11= {c,r}↔B11={→,1} – коимпликативный базис.

π12= {a,b,k}↔B12={~,&,0}.

π13= {a,k,e}↔B13={~,+,0}.

π14= {k,b,d}↔B14={,&,~}.

π15= {k,e,d}↔B15={,+,~}.

π16= {r,b,d}↔B16={,&,1} – базис Жегалкина.

π17= {r,e,d}↔B17={,+,1}.

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

Каждому сложному высказыванию в базисе {+,&,‾} соответствует эквивалентное высказывание в любом из этих базисов.

Например: a+bc=abc=ab+c=a→(bc).

Получена функция в импликативном базисе {→,‾} –В8.

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

Например:

F   = х1х2 + х2х3 + х1х3 = х1 + х2 + х2 + х3 + х1 + х3 .

Полученная функция соответствует базису В10 {+,‾}, но не соответствует базису B1{↓} .

Для того, чтобы функция F соответствовала В1 необходимо ввести двойную инверсию на всю функцию F

F= х1 + х2 + х2 + х3 + х1 + х3 .

F в базисе B2{|} будет иметь вид

F= х1х2 + х2х3 + х1х3 = х1х2 ▪ х2х3 ▪ х1х3 .

Инверсию можно представить в базисе В1 и В2 

Х1 = Х1+ Х1 = Х1▪ Х1 .    

Часто используется базис В16  - базис Жегалкина.

B16={,&,1},  который определен двумя бинарными операциями и &.

В базисе Жегалкина дизъюнкция и отрицание выражаются  х = х1 ; х1 + х2 = х1▪х2 =( х11)( х21)1.

Для упрощения формулы можно использовать следующие соотношения

 х⊕у=у⊕х ; х(у⊕z)=ху⊕хz ; х⊕х=0 ; х⊕0=х,

тогда дизъюнкция = х1▪х2х1⊕х211= х1▪х2х1⊕х2.

                                                 0

Примеры:

  1.  12)(х2+ х1х3)=( х1х2 х1 х2)(х1х2х3х1х3х2)=(х1х2х1х2)( х1х32⊕1)  

х1 х3 х21)=(х1х2х1х2)(х1х2х3х1х3х1х3х21)= х1х2х3х1х2х1х2х1х2х3

                                                                 0                                          0

                                                                                                            0                                                                                                         

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

                  

                        0        0     

2)  х1х21х3= х1▪х1▪х2х3 х1х2 х1х3= х1х2 х1х3= х12⊕1)1⊕1) х3= х1х2 х1 х1х3х3.

                                  0

     3)  х1х21х2= х1х2▪х1▪х2 х1х2( х11)( х21)=х1х2 х1х2х1х21=х1х21

                                                                                       

                                                                               0

                                §2.8. Логические схемы

Базисные элементы, согласно ГОСТ2.743-72, графически изображают в виде прямоугольников, в которых инверсные входы и выходы изображают в виде не заштрихованных кружков (или крестиков).

Вход                                      Выход    

                                              В верхней левой части прямоугольника ставят значение

                                              функции:

                                         1-дизъюнкция, & -конъюнкция, М2 – сложение по модулю 2,

                                         ≡  - эквивалентность.      

1) дизъюнкция                     2) конъюнкция     3) Элемент Вебба или  4)Элемент

Пирса                      Шеффера

                                                                                                                                                

х1                                                                                          

                              f                      х2    

        f=x1+x2 – «или»       f=x1x2 – «и»             f=x1+x2 – «или-не»    f=x1x2  – «и-не»     

5) Отрицание           6) Импликация   7) Сложение по mod 2       8) Эквивалентность      

     f=х                            f=x1+x2=x1x2             f=x1x2                           f=x1x2

        Более сложные элементы графически изображают в виде композиций перечисленных элементов.

                                                                                                        Сумматор

                                                                                                            

                                                  

                                                                                                          S=x1x2      

            F = х1х2 + х3х4                                                                       P= x1x2= перенос

Построим логическую схему для функции f1х2х3) = х1х2 + х2х3 + х1х3

х1     х2       х3

                                                                             

       Та же функция, но до минимизации имеет вид

  f1х2х3) = х1х2х3 + х1х2х3 + х1х2х3 + х1х2х3 + х1х2х3 + х1х2х3       

          Х1   Х2   Х3 

C целью снижения номенклатуры логических элементов необходимо строить схемы на базе (унификация)

Например: f1х2х3) на базе «ИЛИ - НЕ»(функция Вебба)

f1х2х3) = х1х2 + х2х3 + х1х3 = х1 + х2 + х2 + х3 + х1 + х3

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

                             8 элементов ИЛИ - НЕ

Построим логическую схему на базе И – НЕ для той же функции

F=x1x2+x2x3+x1x3=x1x2x2x3x1x3

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

                           7 элементов И – НЕ.

Построим логическую схему f1х2х3) на базе Жегалкина.

f1х2х3) = х1х2 + х2х3 + х1х3 . 

После известных преобразований и упрощений функция в базе Жегалкина примет вид       

f= х1х2х1х3х2х3х2⊕1.

Для построения идеально подходит одноразрядный сумматор ОС-2, имеющий 2-е функции выхода Sу и Р=ху

      х1     х2   х3