Главная страница
Навигация по странице:

  • Определение.

    		•

    Лекции по математической логике1. Элементы математической логики


    Скачать 2.19 Mb.
    НазваниеЭлементы математической логики
    АнкорЛекции по математической логике1.doc
    Дата03.11.2017
    Размер2.19 Mb.
    Формат файлаdoc
    Имя файлаЛекции по математической логике1.doc
    ТипДокументы
    #10077
    КатегорияМатематика
    страница4 из 8
    1   2   3   4   5   6   7   8

    Искомая функция может быть определена двумя различными способами. Если в ее определяющую таблицу вместо (?) дописать «1», то полученная функция будет дизъюнкцией. Этот случай рассматривается в теореме (1). Если же (?) заменить «0», то мы получим функцию сложения по модулю 2.

    Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме

    (2) f(x1,…,xn )= …=.

    Представление функции в виде (1) будем называть дизъюнктивным, а представление в виде (2) – полиномиальным.

    Для получения представлений другого типа рассмотрим функцию Фi(x1, x2,…,xn).

    0, если номер набора равен i

    (3) Фi=

    1, в противном случае

    такие функции называют характеристическими функциями нуля. Из (1) и (3) следует

    Fi(x1,…,xn)=(x1,…,xn).

    Теорема.

    Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме

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

    где T0 – множество номеров наборов, на которых функция f обращается в нуль.

    Представление функции в виде (4) называют конъюнктивным представлением.

    Следствие. Любая таблично заданная ФАЛ может быть представлена в следующей форме

    f(x1,…,xn)= …, где ijT0 .

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

    Условимся о ряде обозначений. Введем в рассмотрение «степень» аргумента х, которую будем обозначать .

    Положим, что

    х,

    =

    , .

    Рассмотрим конъюнкцию

    (5) .

    Набор <> двоичный и существует равно 2n различных таких наборов. Таким образом, число различных конъюнкций также равно 2n.

    Сопоставим каждой конъюнкции (5) номер, определяемый номером набора <>.

    Тогда запись ()i , означает дизъюнкцию всех конъюнкций с номерами из множества δ.

    Аналогично запись

    ()i , i δ

    означает конъюнкцию всех дизъюнкций с номерами из множества δ.

    Покажем, что =1 тогда и только тогда, когда выполняется равенство

    xi=αi.

    Это вытекает из рассмотрения следующих четырех возможных случаев:

    1. ==1 2. =xi=0

    3. ==0 4. =xi=1

    Таким образом, конъюнкция , не обращается в 0 только в том случае, если одновременно выполняются следующие i равенств:

    x1=α1

    (6)x2=α2

    ……

    xi=αi

    Из (6) вытекает, что

    Fi (x1,…,xn )= , при условии, что

    i=++…+.

    Тогда на основании теоремы (1) можно утверждать, что любая функция алгебры логики, кроме нуля, может быть представлена в следующей форме:

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

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

    Представление ФАЛ в виде (7) называют совершенной дизъюнктивной нормальной формой этой функции (СДНФ).

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

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

    2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент xi входит в данный набор как «1», он вписывается в конъюнкцию, соответствующую данному набору, без изменения. Если же xi входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.

    3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.

    Пример: пусть задана функция f(x1, x2, x3) следующей таблицей:

    x1
    x2
    x3
    f(x1, x2, x3)

    0
    0
    0
    0

    0
    0
    1
    0

    0
    1
    0
    0

    0
    1
    1
    1

    1
    0
    0
    1

    1
    0
    1
    0

    1
    1
    0
    1

    1
    1
    1
    0

    Требуется получить из нее совершенно дизъюнктивную нормальную форму.

    Для нахождения ДСНФ выбираем из таблицы только те строки, в которых стоят наборы значений аргументов, обращающих функцию в единицу (это 4, 5, и 7 строки). Выписываем конъюнкции, соответствующие выбранным строкам:

    & x2&x3, x1&&, x1& x2&.

    Соединяя эти конъюнкции знаками дизъюнкции, окончательно получаем

    f(x1, x2, x3)= x2x3x1x3 x1x2.

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

    А) в ней нет двух одинаковых слагаемых;

    Б) ни одно слагаемое не содержит двух одинаковых множителей;

    В) никакое слагаемое не содержит переменную вместе с ее отрицанием;

    Г) в каждом слагаемом содержится в качестве множителя либо переменная хi, либо ее отрицание , где i=1,2,…,n.

    Д) число множителей равно числу n.

    Если вместо (1) воспользоваться соотношением (2), получим полиномиальную совершенную нормальную функцию (ПСНФ).

    Так для функции, рассмотренной в примере, ПСНФ имеет следующий вид:

    f(x1, x2, x3)= & x2&x3x1&&x1& x2&.

    Кроме представления ФАЛ в СДНФ, возможно представление ее в некоторой другой форме, двойственной по отношению к СДНФ.

    Теорема. Любая ФАЛ, кроме единицы, может быть представлена в следующей форме:

    (8) f(x1, x2, x3)= ().

    Символ означает, что конъюнкция берется только по тем наборам, <>, для которых выполняется равенство:

    f(x1, x2, x3)=0.

    Доказательство теоремы.

    На основании предыдущей теоремы имеем

    (x1, x2,…, xn)=

    или (x1, x2,…, xn)= &().

    Как известно, равенство не нарушается, если от обеих его частей взять отрицание:

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

    Согласно закону де Моргана

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

    На тех наборах, для которых f()=1 соответствующая дизъюнкция

    f()=1.

    В силу х1=1 такие наборы на значение конъюнкции не влияют и ими можно пренебречь:

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

    Теорема доказана для всех n1.

    Представление ФАЛ в виде (8) носит название совершенной конъюнктивной нормальной формы (СКНФ).

    Из теоремы вытекает алгоритм построения КСНФ:

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

    2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент xi входит в данный набор как «0», он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же xi входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.

    3. Все полученные дизъюнкции соединяются между собой знаками конъюнкций.

    Пример.

    Написать СКНФ для функции, заданной следующей таблицей.

    x1
    x2
    x3
    f(x1, x2, x3)

    0
    0
    0
    0

    0
    0
    1
    1

    0
    1
    0
    1

    0
    1
    1
    0

    1
    0
    0
    1

    1
    0
    1
    1

    1
    1
    0
    1

    1
    1
    1
    0

    f(x1, x2, x3)= (x1 x2x3)&(x1)&( ).

    Аналогично СДНФ, можно отметить необходимые и достаточные условия совершенной нормальной конъюнктивной формулы. СКНФ формулы f(x1, x2, …, xn), содержащие n различных переменных, обладают следующими свойствами:

    А) в ней нет двух одинаковых множителей;

    Б) ни один множитель не содержит двух одинаковых слагаемых;

    В) ни один множитель не содержит какой-нибудь переменной вместе с ее отрицанием;

    Г) каждый множитель содержит в качестве слагаемого или хi, или ее отрицание , где i=1,2,…,n.

    Д) число слагаемых равно числу n.

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

    Итак, если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

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

    Если какой-либо член φ дизъюнктивной (конъюнктивной) функции не содержит переменной xi , то она вводится тождественным преобразованием

    для получения СДНФ φ = φ&( xi)= φ xi,

    и для СКНФ соответственно φ=( φ xi)( φ).

    В силу тождеств φφ= φ и φ φ= φ одинаковые члены, если они появляются, заменяются одним таким членом.

    Приведем соотношения эквивалентных преобразований, полезных при упрощении формул:

    Законы склеивания

    1) ;

    2) ;

    3) ;

    4) .

    Законы поглощения

    1) ;

    2) ;

    3) .

    Правила:

    1. Если слагаемое некоторой суммы входит в другое слагаемое, то это второе слагаемое можно из суммы удалить.

    2. Если множитель некоторого произведения входит слагаемым в другой множитель, то второй множитель можно удалить.

    3. В каждом слагаемом можно удалить множитель, который равносилен отрицанию другого слагаемого.

    4. В каждом множителе можно удалить слагаемое, которое равносильно отрицанию другого множителя.

    Пример.

    1. Заданную функцию f(x,y,z)=xzxпривести к СДНФ:

    xzx= xzx(y)= xz xy x;

    2. Задана функция f(x,y,z)=(xz). Необходимо привести к СКНФ.

    f(x,y,z)=(xz)= (xz)= (xz)(z).

    Добавить к каждому члену соответственно y, x, z

    =••= .
    Полная система функций.

    Определение. Система ФАЛ (f1, f1,…, fm) называется полной, если любая функция может быть представлена суперпозицией функций f1, f1,…, fm.

    Система функций { f1, f1,…, fm }, являющаяся полной, называется базисом.

    Примеры полных систем функций: x1x2; x1x2 ; x1x2 ; x1x2=.

    Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f1 , образующей этот базис, превращает систему функций (f1, f1,…, fm) в неполную.

    Любая функция, как было показано ранее, может быть представлена в виде СДНФ или СКНФ:

    (x1, x2,…, xn)=

    (x1, x2,…, xn)= .

    Верно утверждение о полноте системы, состоящей из трех функций: конъюнкции, отрицания и дизъюнкции.
    Минимизация функций алгебры логики

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

    Пример. Пусть задана ФАЛ в СДНФ.

    f(x1, x2, x3)= & x2&x3x1& x2&x1& & x3x1& && x2& x3.

    Добавим к функции один конъюнктивный член & x2&x3. Это добавление не меняет данной функции так как xx=x:

    f(x1, x2, x3)= x2x3x1 x2x1 x3x1 x2x3x2x3.

    Преобразуем это выражение, используя сочетательные и распределительные свойства конъюнкции и дизъюнкции:

    f(x1, x2, x3)= x2 (x3) x1 ( x3)x2 x3 (x1 ).

    Используя свойство дизъюнкции, получаем:



    Аналогично предыдущему делаем дальнейшие преобразования:

    .

    Из примера видна неэкономность совершенных нормальных форм для представления ФАЛ.

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

    К настоящему времени существенные результаты в решении задачи минимизации лишь в базисе, состоящем из отрицания, конъюнкции и дизъюнкции.

    Приведем ряд определений.

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

    Определение. Ранг элементарной конъюнкции — это число элементов, образующих эту конъюнкцию. Ранг — это ''n''.

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

    Определение. ДНФ для функции f(x1, x2,…, xn), состоящей из элементарных конъюнкций ранга n, называется дизъюнктивной совершенной нормальной формой.

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

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

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

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

    Аналогичные определения можно дать для случая конъюнктивных нормальных форм.

    Дизъюнктивная (конъюнктивная) нормальная форма — это дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.



    U1,…Un — элементарные конъюнкции.

    ,

    где все различны; число r — ранг конъюнкции.
    1   2   3   4   5   6   7   8

    написать администратору сайта