Основні поняття і закони алгебри логіки

Логічна (двійкова) зміна характеризує простий вислів, який містить одну закінчену думку. Вона позначається символом «х» і може приймати значення 0 або 1.

Логічна функція – це складний вислів, що складається з декількох простих, зв’язних між собою сполучними союзами. Вона записується аналітично у вигляді Основні поняття і закони алгебри логіки - student2.ruде хn, - двійкова змінна, Основні поняття і закони алгебри логіки - student2.ru; Основні поняття і закони алгебри логіки - student2.ru.

Вхідний набір – це певна комбінація значень двійкових змінних в логічній функції. Максимальне число вхідних наборів визначається виразом m=2n, де n – число змінних. Максимальне число логічних функцій n змінних визначається виразом Основні поняття і закони алгебри логіки - student2.ru .

Таблиця істинності – це представлення логічної функції у вигляді таблиці, в лівій частині якої записуються вхідні набори, а в правій – відповідні їм значення функції. Повністю визначена функція – це логічна функція, що має визначені значення 0 або 1 на всіх вхідних наборах.

Не повністю визначена функція – це логічна функція, значення якої визначені не на всіх вхідних наборах.

Робочі набори – це вхідні набори, для яких логічна функція повністю визначена.

Байдужі набори – це вхідні набори, для яких логічна функція не визначена. Частково визначену функцію можна зробити повністю визначеною (довизначити), приписавши байдужим наборам які-небудь значення функції (0 або 1).

Функції однієї змінної. Оскільки n=1 і m=2 то максимальне число функцій однієї змінної N=4, а саме: f0=0 нульова функція; f1=1 – одинична функція; f21 – функція повторення х1; Основні поняття і закони алгебри логіки - student2.ru - функція заперечення.

Функції двох змінних є основними функціями алгебри логіки. Для запису будь-якої функції досить мати: заперечення, кон’юнкцію і диз’юнкцію, які утворюють функціонально повну систему функцій. Мінімально функціонально повні системи мають одну функцію (І-НЕ АБО-НЕ) чи дві [(НЕ,І) (НЕ, АБО)].

У алгебрі логіки існують поняття: елементарна кон'юнкція/диз'юнкція, констатуента одиниці/нуля, ранг елементарної кон'юнкції/диз'юнкції, сусідні елементарні кон'юнкції/диз'юнкції.

Елементарна кон'юнкція/диз'юнкція - це кон'юнкція/диз'юнкція вхідних змінних та їх заперечення. Будь-який символ змінної в елементарній кон'юнкції/диз'юнкції може зустрічатися один раз.

Констатуента одиниці/нуля - елементарна кон'юнкція/диз'юнкція, в яку входять всі n змінних в прямому або інверсному вигляді. Констатуенту одиниці/нуля часто називають мінтермом/макстермом. Ранг елементарної кон'юнкції/диз'юнкції - число вхідних змінних в елементарної кон'юнкції/диз'юнкції. Так Основні поняття і закони алгебри логіки - student2.ru - це елементарна кон'юнкція третього рангу; Основні поняття і закони алгебри логіки - student2.ru - диз'юнкція четвертого рангу.

Булеві теореми та закони

Усі змінні, якими оперує алгебра логіки, можуть приймати тільки два значення – 0 та 1.

В алгебрі логіки визначено:

Ø відношення еквівалентності позначається знаком “=”;

Ø операції: додавання, або диз’юнкція позначається знаком “Ú ”, “+”;

Ø множення, або кон’юнкція позначається знаком “&”, “Ù”, “ · ”;

Ø заперечення або інверсія позначається надкресленням “ Основні поняття і закони алгебри логіки - student2.ru ”, або апострофом.

Алгебра логіки визначається наступною системою аксіом:

Основні поняття і закони алгебри логіки - student2.ru

Закони алгебри логіки:

1) переставний (комутативний) закон:

Основні поняття і закони алгебри логіки - student2.ru ; Основні поняття і закони алгебри логіки - student2.ru

Основні поняття і закони алгебри логіки - student2.ru ; Основні поняття і закони алгебри логіки - student2.ru

2) сполучний (асоціативний) закон:

Основні поняття і закони алгебри логіки - student2.ru

3) розподільний (дистрибутивний) закон:

Основні поняття і закони алгебри логіки - student2.ru

4) закони де Моргана:

для двох змінних:

Основні поняття і закони алгебри логіки - student2.ru

для n змінних:

Основні поняття і закони алгебри логіки - student2.ru

5) закон подвійного заперечення:

Основні поняття і закони алгебри логіки - student2.ru ; Основні поняття і закони алгебри логіки - student2.ru

6) правило склеювання:

Основні поняття і закони алгебри логіки - student2.ru

Основні поняття і закони алгебри логіки - student2.ru

7) правило поглинання:

Основні поняття і закони алгебри логіки - student2.ru ;

Основні поняття і закони алгебри логіки - student2.ru ;

Основні поняття і закони алгебри логіки - student2.ru

8) закон ідемпотентності (повторення):

Основні поняття і закони алгебри логіки - student2.ru ; Основні поняття і закони алгебри логіки - student2.ru ; і=0,…,n

Завдання для самоконтролю

  1. Закінчити кожний із виразі:
Основні поняття і закони алгебри логіки - student2.ru Основні поняття і закони алгебри логіки - student2.ru

2. Довести теорему де Моргана шляхом перевірки для всіх можливих комбінацій х1 та х2. (х1=0, х2=0; х1=1, х2=0; х1=0, х2=1; х1=1, х2=1)

х2 х1   Основні поняття і закони алгебри логіки - student2.ru   Основні поняття і закони алгебри логіки - student2.ru       х2 х1   Основні поняття і закони алгебри логіки - student2.ru   Основні поняття і закони алгебри логіки - student2.ru
                                                 
                                                 
                                                 
                                                 

3. Спростити наступні вирази:

А) Основні поняття і закони алгебри логіки - student2.ru В) Основні поняття і закони алгебри логіки - student2.ru Д) Основні поняття і закони алгебри логіки - student2.ru Ж) Основні поняття і закони алгебри логіки - student2.ru
Б) Основні поняття і закони алгебри логіки - student2.ru Г) Основні поняття і закони алгебри логіки - student2.ru Є) Основні поняття і закони алгебри логіки - student2.ru З) Основні поняття і закони алгебри логіки - student2.ru
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             

Тема для самостійного опрацювання (Лекція №8с):

Наши рекомендации