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

  • Теорема 1.3.1.

  • Теорема 1.3.2

  • Конституенти Конституенти 21нуля одиниці

  • Теорема 1.3.3

  • Теорема 1.3.4

  • Запитання для самоконтролю

  • 1.4 БУЛЕВІ ФУНКЦІЇ. ФУНКЦІОНАЛЬНА ПОВНОТА. ПОЛІНОМИ ЖЕГАЛКІНА

    		•

    Логика. логіка. Математична логіка та теорія алгоритмів


    Скачать 1.6 Mb.
    НазваниеМатематична логіка та теорія алгоритмів
    АнкорЛогика
    Дата15.05.2022
    Размер1.6 Mb.
    Формат файлаpdf
    Имя файлалогіка.pdf
    ТипНавчальний посібник
    #530647
    страница3 из 18
    1   2   3   4   5   6   7   8   9   ...   18
    1.3 НОРМАЛЬНІ ФОРМИ ФОРМУЛ АЛГЕБРИ ВИСЛОВЛЕНЬ ТА ЇХ
    ЗАСТОСУВАННЯ.
    Кон’юнктивним (диз’юнктивним) одночленом називається кон’юнкція
    (диз’юнкція) пропозиційних змінних або їх заперечень (при цьому допускається повторення змінних). Кількість змінних в одночлені називають його рангом.
    Інша назва кон’юнктивного (диз’юнктивного) одночлена – елементарна
    кон’юнкція (елементарна диз’юнкція).
    Кон’юнктивні одночлени:
    c
    b
    a
    K



    1
    ,
    a
    a
    K


    2
    ,
    c
    K
    3
    мають ранги 3, 2, 1 відповідно.
    Диз’юнктивні одночлени:
    c
    a
    D


    1
    ,
    c
    a
    c
    a
    D




    2
    мають ранги 2 і 4 відповідно
    Диз’юнктивною нормальною формою (кон’юнктивною нормальною формою) називається диз’юнкція кон’юнктивних одночленів (кон’юнкція диз’юнктивних одночленів). Скорочений запис ДНФ та КНФ відповідно.
    Тобто ДНФ це формула виду
    p
    K
    K
    K



    2 1
    , де всі К
    і
    (і=1, 2,…,р) є кон’юнктивними одночленами (не обов’язково різними), а КНФ -
    q
    D
    D
    D



    2 1
    , де всі
    i
    D
    , і=1, 2,…,q є диз’юнктивними одночленами (не обов’язково різними).
    Будь-яка формула алгебри висловлень може бути зведена до рівносильних їй
    ДНФ та КНФ (причому неоднозначно).
    Приклад
    1.
    Побудувати
    КНФ та
    ДНФ, рівносильні формулі:
    x
    z
    y
    x
    A




    )
    (
    Розв’язання.
    Перший крок – будуємо формулу, рівносильну до А, що містить лише операції


     ,
    ,
    :
    x
    z
    y
    x
    x
    z
    y
    x
    x
    z
    y
    x











    )
    (
    )
    (
    )
    (
    Другий крок – знайдемо рівносильну формулу, в якій знак заперечення стоїть лише біля змінних:
    x
    z
    y
    x
    x
    z
    y
    x
    x
    z
    y
    x











    )
    (
    )
    (
    )
    (
    Одержана формула є ДНФ(А), що складається з двох кон’юнктивних одночленів:
    )
    (
    1
    z
    y
    x
    K



    та
    x
    K
    2
    . Щоб дістати КНФ(А) треба застосувати дистрибутивний закон диз’юнкції відносно кон’юнкції до
    ДНФ(А):

    19
    )
    (
    )
    (
    )
    (
    )
    (
    x
    z
    x
    y
    x
    x
    x
    z
    y
    x









    . Ми отримали КНФ(А), яка містить три диз’юнктивні одночлени:
    x
    x
    D


    1
    ,
    x
    y
    D


    2
    ,
    x
    z
    D


    3
    Отже, КНФ(А)=
    )
    (
    )
    (
    )
    (
    x
    z
    x
    y
    x
    x





    , ДНФ(А)=
    x
    z
    y
    x



    )
    (
    Одним із застосувань нормальних форм є встановлення типу формул алгебри висловлень (спосіб розв’язання проблеми вирішення в алгебрі висловлень).
    Теорема 1.3.1. Формула алгебри висловлень є тавтологією тоді і тільки тоді, коли кожний диз’юнктивний одночлен рівносильної їй КНФ, містить хоча б одну пропозиційну змінну разом з її запереченням.
    Теорема 1.3.2. Формула алгебри висловлень є суперечністю тоді і тільки тоді, коли кожен кон’юнктивний одночлен рівносильної їй ДНФ містить хоча б одну пропозиційну змінну разом з її запереченням.
    Застосувавши теореми 1.3.1 та 1.3.2 до формули
    x
    z
    y
    x
    A




    )
    (
    попереднього приклада визначимо її тип. Оскільки
    x
    y
    D


    2
    ,
    x
    z
    D


    3
    в
    КНФ(А) не містять деяку пропозиційну змінну разом з її запереченням, то А не тавтологія. Аналогічно, в ДНФ(А) кон’юнктивні одночлени
    z
    y
    x
    K



    1
    і
    x
    K
    2
    не містять змінну разом з її запереченням, отже формула А не є суперечністю. Значить формула А нейтральна.
    Серед багатьох ДНФ (КНФ), які рівносильні заданій формулі алгебри висловлень, існує унікальна нормальна форма, яка визначається однозначно (з точністю до порядку запису одночленів): це так звана досконала диз’юнктивна
    (кон’юнктивна) нормальна форма.
    Одночлен (кон’юнктивний або диз’юнктивний) називається правильним, якщо в нього кожна змінна(або її заперечення), зустрічається не більше, ніж один раз.
    Одночлен (кон’юнктивний або диз’юнктивний) називається повним, відносно набору змінних, якщо кожна змінна входить в нього хоч раз.
    Нормальна форма називається досконалою, якщо всі одночлени, що в неї входять, є правильними, повними і різними одночасно. Досконала ДНФ (КНФ) позначається ДДНФ (ДКНФ).
    Будувати досконалі форми для заданої формули можна за допомогою рівносильних перетворень або використовуючи таблицю
    істинності.
    Проілюструємо це на прикладі.

    20
    Приклад 2. Для формули А=
    знайти ДКНФ(А).
    Спосіб рівносильних перетворень (алгебраїчний спосіб).
    Перший крок - побудова КНФ(А):








    b
    a
    c
    c
    b
    a
    c
    b
    a
    A

















    b
    a
    c
    c
    b
    a









     

    b
    a
    c
    c
    b
    a









     








    b
    a
    c
    c
    b
    a






    b
    a
    c
    c
    b
    c
    a







    Отримана КНФ(А) не є досконалою, тому що перші два диз’юнктивні одночлени не є повними.
    Другий крок – перетворення кожного неповного (неправильного) одночлена в повний (правильний). Для цього використаємо наступні рівносильності:
    0
    ,
    0




    x
    x
    x
    x

     




     
     

    b
    c
    a
    b
    c
    a
    b
    b
    c
    a
    c
    a
    c
    a
    D















    0 1
    ,

     









    a
    c
    b
    a
    c
    b
    a
    a
    c
    b
    c
    b
    c
    b
    D















    0 2
    Третій крок – записати ДКНФ(А), де жоден одночлен не повторюється і змінні в одночленах розташовані в певному порядку:

     








    b
    c
    a
    b
    c
    a
    A










    a
    c
    b
    a
    c
    b


    b
    a
    c



     





    c
    b
    a
    c
    b
    a
    c
    b
    a
    c
    b
    a












    Отримали ДКНФ, рівносильну заданій формулі. Таким чином,
    ДКНФ(А)=

     





    c
    b
    a
    c
    b
    a
    c
    b
    a
    c
    b
    a












    Табличний спосіб.
    Перший крок - побудова таблиці істинності формули
    Другий крок – побудова конституент нуля відповідно всіх тих наборів змінних, на яких формула набуває хибного значення.
    Конституентою нуля (макстермом) називають досконалий диз’юнктивний одночлен, який набуває значення 0 тільки на відповідному наборі логічних змінних:
    ,
    2 1



    n
    x
    x
    x
    D




    де






    1
    ,
    0
    ,
    i
    i
    i
    i
    i
    x
    x
    x
    x
    x

    Третій крок - запис ДКНФ, як кон’юнкції тих конституент нуля, які перетворюються на нуль на тих наборах значень змінних, що й задана формула.
    Будуємо таблицю істинності формули
    a
    b
    c
    b
    b
    a
    c
    b
    a


    Конституенти Конституенти

    21
    нуля
    одиниці
    0 0
    0 1
    1 0
    0 0
    1 1
    1 1
    0 1
    0 0
    0 1
    0 1
    1 0
    0 0
    1 0
    0 1
    1 0
    1 0
    1 1
    1 1
    1 1
    0 0
    1 0
    1 1
    1 0
    1 1
    ДКНФ заданої формули утворюється кон’юнкцією конституент нуля , отже:
    ДКНФ(А)



     
     

    c
    b
    a
    c
    b
    a
    c
    b
    a
    c
    b
    a












    Аналогічно, ДДНФ(А) визначається диз’юнкцією конституент одиниці.
    Конституентою одиниці (мінтермом) називають досконалий кон’юнктивний одночлен, який набуває значення 1 тільки на відповідному наборі логічних змінних:
    ,
    2 1



    n
    x
    x
    x
    K




    де






    0
    ,
    1
    ,
    i
    i
    i
    i
    i
    x
    x
    x
    x
    x

    ДДНФ(А)

     
     



    c
    b
    a
    c
    b
    a
    c
    b
    a
    c
    b
    a












    Теорема 1.3.3 Формула алгебри висловлень
    )
    ,...,
    ,
    (
    2 1
    n
    a
    a
    a
    A
    є тавтологією тоді і тільки тоді, коли рівносильна їй ДДНФ(А) містить 2
    n кон’юнктивних одночленів.
    Теорема 1.3.4 Формула алгебри висловлень
    )
    ,...,
    ,
    (
    2 1
    n
    a
    a
    a
    A
    є суперечністю тоді і тільки тоді, коли рівносильна їй ДКНФ(А) містить 2
    n диз’юнктивних одночленів.
    Запитання для самоконтролю
    1. Яку формулу алгебри висловлень називають кон’юнктивним
    (диз’юнктивним) одночленом або елементарною кон’юнкцією
    (елементарною диз’юнкцією)?
    2. Що називається диз’юнктивною нормальною формою (ДНФ)?
    3. Що називається кон’юнктивною нормальною формою (КНФ)?
    4. Чи кожна формула алгебри висловлень може бути зведена до рівносильних їй ДНФ та КНФ?
    5. Який алгоритм побудови нормальних форм?

    22 6. Як застосовуються нормальні форми до проблеми вирішення алгебри висловлень?
    7. Який одночлен (кон’юнктивний або диз’юнктивний) називається правильним?
    8. Який одночлен називається повним відносно набору змінних?
    9. Яка нормальна форма (кон’юнктивна або диз’юнктивна) називається досконалою (ДДНФ, ДКНФ)?
    10. Який алгоритм побудови досконалих форм способом рівносильних перетворень?
    11. Який алгоритм побудови досконалих форм способом табличним способом?
    12. Яку формулу алгебри висловлень називаютьконституентою нуля
    (макстермом)?
    13. Яку формулу алгебри висловлень називаютьконституантою одиниці (мін термом)?
    14. Як застосовуються досконалі нормальні форми до проблеми вирішення алгебри висловлень?
    ВПРАВИ
    1.19 Побудувати ДНФ та КНФ, рівносильні формулам: a)
    b
    a
    b
    a



    ; b)


    b
    a
    b
    a



    ; c)


    c
    a
    c
    b
    a




    ;
    d)

     



    b
    a
    a
    b
    b
    a





    ;
    e)




    c
    a
    b
    c
    a




    ; f)


    c
    b
    a


    ; g)








    c
    b
    a
    c
    a
    c
    b






    1.20 Зведенням формули до ДНФ та КНФ визначити тип формули: a)


    a
    b
    a


    ; b)


    b
    a
    b
    a



    ; c)


    c
    b
    a
    b
    c
    c





    ; d)
    c
    a
    b
    c
    b
    a





    ; e)




    c
    a
    b
    c
    c
    a





    ;

    23
    f)

     


     

    c
    b
    a
    b
    c
    c
    b
    a







    ; g)








    b
    d
    c
    d
    c
    b
    a






    1.21 Перетворивши дані досконалі форми, знайти формули, які їм рівносильні та містять найменшу кількість операцій: a)
    ; b)
    ; c)
    ; d)
    1.22 Звести формули до ДДНФ та ДКНФ двома способами – табличним та алгебраїчним: a)
    b
    a
    a


    ; b)


    c
    a
    c
    b
    a




    ;
    c)

     

    c
    b
    a
    b
    c
    a
    b






    ;
    d)




    c
    b
    a
    b
    c
    a
    b






    ; e)




    b
    c
    a
    c
    a
    b
    a






    ; f)




    c
    b
    c
    b
    c
    b
    a






    ; g)




    c
    b
    b
    a
    b
    c
    a






    1.23 Знаючи ДКНФ(А) і ДКНФ(В), побудувати ДКНФ(
    B
    A
    ).
    1.24 Знаючи ДДНФ(А) і ДДНФ(В), побудувати ДДНФ(
    B
    A
    ) та ДКНФ(
    B
    A
    ).
    1.25 Знайти ранг ДКНФ, яка рівносильна формулі: а)




    1 2
    1
    n
    n
    x
    x
    x
    x





    ; б)
    n
    x
    x
    x



    2 1
    1.4 БУЛЕВІ ФУНКЦІЇ. ФУНКЦІОНАЛЬНА ПОВНОТА. ПОЛІНОМИ
    ЖЕГАЛКІНА
    Впорядкований набір


    n
    a



    ,...
    ,
    2 1

    логічних значень
     
    1
    ,
    0

    i

    називається булевим вектором, а число п – довжиною мулевого вектора
    a
    . Тоді множина
     


     


    n
    i
    s
    n
    n
    ,
    1
    ,
    1
    ,
    0
    /
    ,...
    1
    ,
    0 1






    є множиною всіх булевих векторів довжини п.
    Функція
    )
    ,...,
    ,
    (
    2 1
    n
    x
    x
    x
    f
    від n- змінних (n≥1) називається булевою, якщо кожний її аргумент і сама функція приймають значення на множині
    :

    24
     
     
    1
    ,
    0 1
    ,
    0
    :

    n
    f
    Для кожного висловлення, одержаного з n простих висловлень існує булева функція від n змінних, значення якої при відповідних значеннях змінних збігається з оцінкою висловлення – це функція істинності даного висловлення.
    В обчислювальній техніці булеві функції використовують для опису алгоритмів та дискретних пристроїв. Дискретні пристрої призначаються для перетворення дискретної інформації, що розкладається на елементарні одиниці – біти, які в пристроях реалізуються сигналами, що описуються двійковими
    (булевими) змінними.
    Булеву n-місну функцію
    )
    ,...,
    ,
    (
    2 1
    n
    x
    x
    x
    f
    можна задати: а) безпосередньо таблицею, на якій точно визначено, яке значення f відповідає кожному впорядкованій набору значень аргументів
    (таблицею істинності); б) формулою, в якій задано операції, що їх треба виконати над значеннями аргументів
    , щоб дістати значення функції, наприклад,
    1 3
    2 1
    3 2
    1
    )
    ,
    ,
    (
    x
    x
    x
    x
    x
    x
    x
    f




    (аналітичний спосіб); в) словесним описом чи характеристичною властивістю, наприклад, 1)
    «функція
    )
    ,...,
    ,
    (
    2 1
    n
    x
    x
    x
    f
    набуває значення 1 тільки тоді, коли всі аргументи набувають однакових значень» або 2)






    3 1
    3 1
    3 2
    1
    ,
    0
    ,
    1
    )
    ,
    ,
    (
    x
    x
    x
    x
    x
    x
    x
    f
    (вербальний спосіб).
    Постає питання про кількість булевих функцій від заданого числа змінних.
    1   2   3   4   5   6   7   8   9   ...   18

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