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

  • 4.4. Двойственность. Принцип двойственности.

  • 4.5. Булева алгебра (алгебра логики). Полные системы булевых функций

  • 4.6. Нормальные формы Определение 4.4.

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

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

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

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

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

    		•

    Дискретная математика для 1 курса. Тема Множества


    Скачать 0.62 Mb.
    НазваниеТема Множества
    АнкорДискретная математика для 1 курса.docx
    Дата12.08.2017
    Размер0.62 Mb.
    Формат файлаdocx
    Имя файлаДискретная математика для 1 курса.docx
    ТипКонтрольные вопросы
    #8403
    страница7 из 10
    1   2   3   4   5   6   7   8   9   10

    Правило равносильных преобразований


    Пусть для формул A и B справедливо утверждение A B. Пусть CA – формула, содержащая A в качестве своей подформулы. Пусть CB получается из CA заменой A на B. Тогда CA CB.

    Пример 4.5.

    Пусть A = xy, B = xVy.

    Равносильность 12 позволяет утверждать, что AB.

    Пусть CA = (x y) & z, т.е. A есть подформула CA. Тогда CB = (xVy) & z и CA CB, т.е. (x y) & z (xVy) & z.
    4.4. Двойственность. Принцип двойственности.
    Символы &, V называются двойственными.

    Формула А* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, V на двойственные.

    Например,

    A = xV(y&z);

    A* = x & (yVz).

    Теорема 4.1. (Принцип двойственности).

    Если A B, то A* B

    Доказательство принципа двойственности можно найти, например, в [3].

    Принцип двойственности можно использовать для нахождения новых равносильностей. Например, для 1-го закона поглощения (равносильность 6а) имеем:

    A&(AVB)  A.

    Следуя принципу двойственности, получим новую равносильность:

    AVA&B A (2- ой закон поглощения).
    4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
    Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества.

    Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.

    Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {, &, V} является полной. Также полными являются следующие системы функций:

    а){, V}; б) {, &}; в) {, }.

    Полнота систем {, V} и {, &} следует из полноты системы {, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A&B(AVB); AVB (A&B).

    Поэтому система {, &, V} может быть сокращена на одну функцию:

    Полнота системы {, } следует из полноты системы {, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:

    AB AVB.
    4.6. Нормальные формы
    Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.

    Пример 4.6.

    x, y, x&y, x1&x2&(x3) – элементарные конъюнкции.

    xVy, x1&x2 Vx1&x2 – не элементарные конъюнкции.

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

    Пример 4.7.

    x, x&y, x V x&(y), x1&x2&(x3) V x1&(x2)&x3 V x1&x2&(x3) – ДНФ.

    (xVy)&x – не ДНФ.

    Определение 4.6. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания.

    Пример 4.8.

    x&y, x&y V x&y – СДНФ функции двух переменных.

    xVx&y, xVy – не СДНФ.

    Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.

    Пример 4.9.

    x, y, xVy, x1Vx2V(x3) – элементарные дизъюнкции.

    x&y, (x1Vx2) & (x1Vx2) – не элементарные дизъюнкции.

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

    Пример 4.10.

    x, x&y, x & x&(y), (x1Vx2)&(x3)&(x1Vx2Vx3) – КНФ.

    x&y V x – не КНФ.

    Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания.

    Пример 4.11.

    xVy, (xVy) &(xVy) – СКНФ функции двух переменных.

    x &(xVy), x&y – не СКНФ.

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

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

    Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)).

    Шаг 1. Все подформулы A вида BC (т.е. содержащие импликацию) заменяем на BVC или на (B&C) (в соответствии с равносильностью 12 раздела 4.3).

    Шаг 2. Все подформулы A вида B C (т.е. содержащие эквивалентность) заменяем на (A&B) V (A&B) или на (AVB)&(AVB) (в соответствии с равносильностью 13).

    Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).

    Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

    Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).

    Шаг 6. для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.

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

    Пример 4.12.

    Приведем к ДНФ и КНФ рассмотренную ранее в примере 4.4 формулу f(x1, x2, x3) = (x2 x3) (x1Vx2).

    1. Устранив импликацию, получим:

    (x2 Vx3) (x1Vx2).

    2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим:

    (x2&x3) (x1Vx2).

    3. Устранив эквивалентность, получим:

    (x2&x3) & (x1Vx2) V (x2&x3) & (x1Vx2).

    4. Применив закон де Моргана ко второму члену дизъюнкции, получим

    (x2&x3) & (x1Vx2) V (x2Vx3) & (x1& x2).

    5. Применив закон дистрибутивности 3а, получим

    (x2&x3&x1 V x2&x3&x2) V (x2&x1&x2 V x3&x1&x2).

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

    x1&x2&x3 V x2&x3 V x1&x2 V x1&x2&x3.

    7. Применив 2–ой закон поглощения (6б), вместо x1&x2&x3.V x2&x3 запишем x2&x3, а вместо x1&x2 V x1&x2&x3 запишем x1&x2 и в результате получим ДНФ нашей формулы:

    f(x1, x2, x3) x2&x3 V x1&x2

    При приведении к КНФ применим закон дистрибутивности 3б и получим:

    x2&x3 V x1&x2  x2Vx1) & (x2Vx2) & (x3Vx1) & (x3Vx2).

    Учитывая, что. x2Vx2 1(равносильность 11)и применив свойство 9а, получим окончательно КНФ для f(x1, x2, x3)

    f(x1, x2, x3)  x1Vx2) & (x1Vx3) & (x2Vx3).

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

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

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

    Доказательство этих теорем состоит в указании алгоритма приведения формулы А к СДНФ и СКНФ.

    Алгоритм 4.2. (Алгоритм приведения формулы булевой функции к СДНФ)

    Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.

    Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:

    A&A  0, B&0  0, СV0  С.

    Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&AA.

    Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание x, то на основании 1- го закона расщепления (равносильность 7а) заменяем С на (С&x) V (C&x).

    Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная xi, либо ее отрицание xi.

    Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС  С.

    Пример 4.13.

    Найдем СДНФ формулы из примера 4.4:

    f(x1, x2, x3) = (x2x3) (x1Vx2).

    1. Найденная ранее в примере 4.12 ДНФ формулы f(x1, x2, x3) имеет вид:

    x2&x3 V x1&x2.

    2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре):

    f(x1, x2, x3) x2&x3&x1 V x2&x3&x1V x1&x2&x3 V x1&x2&x3).

    1. После применения шага 5 получим:

    f(x1, x2, x3) x1&x2&x3 V x1&x2&x3 V x1&x2&x3 V x1&x2&x3.

    4. Шаг 6 не требуется. Найденное выражение формулы f(x1, x2, x3) является СДНФ этой формулы.

    Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &.

    Пример 4.14.

    Найдем СКНФ формулы из примера 4.4:

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

    1. Найденная в примере 4.12 КНФ формулы f(x1, x2, x3) имеет вид:

    f(x1, x2, x3) x1Vx2) & (x1Vx3) & (x2Vx3).

    2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом:

    x1Vx2  x1Vx2Vx3) & (x1Vx2Vx3).

    x1Vx3 (x1Vx3Vx2)&(x1Vx3Vx2).

    x2 Vx3 (x2Vx3Vx1) & (x2Vx3Vx1).

    Поэтому имеем:

    f(x1, x2, x3) x1Vx2Vx3)&(x1Vx2Vx3)&x1Vx3Vx2)&(x1Vx3Vx2)&(x2Vx3Vx1)&(x2 V x3Vx1).

    3. Применив шаг 5, получим:

    f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1 Vx2Vx3).

    4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3):

    f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3)&(x1Vx2Vx3).
    1   2   3   4   5   6   7   8   9   10

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