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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

;

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

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

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

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

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

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

;

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

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

;

;

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

; ; і=0,…,n

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

  1. Закінчити кожний із виразі:

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

х2 х1           х2 х1    
                                                 
                                                 
                                                 
                                                 

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

А) В) Д) Ж)
Б) Г) Є) З)

 

                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             

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