Лекція №2. Основні поняття і закони алгебри логіки Елементи математичної логіки



Скачати 36.52 Kb.
Дата конвертації20.11.2016
Розмір36.52 Kb.


Розділ 1. Основи цифрової техніки
Тема 1.1. Логічні основи ЕОМ
Лекція №2. Основні поняття і закони алгебри логіки
Елементи математичної логіки

Теоретичною основою комп’ютерної схемотехніки є алгебра логіки – наука, яка використовує математичні методи для розв’язання логічних задач.

Розробка основ алгебри логіки пов'язана з ім'ям ірландського математика Дж. Буля (1815-1864), тому існують і інші назви: алгебра Буля або булева алгебра.

Булева алгебра – найкращий засіб опису, аналізу, проектування і реалізації цифрових систем.

В алгебрі логіки зміни приймають тільки два значення «0» або «1».

Таким чином, булеві 0 і 1 представляють стани змінної напруги, або так звані логічні рівні. Будемо користуватися позначеннями «0» – низький рівень напруги (Low), а «1» – високий рівень напруги (High). Булева алгебра – це відмінний спосіб вираження зв’язків між входами і виходами схем.


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

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

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

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

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

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

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

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

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

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

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



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

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

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

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


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

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

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

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

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



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

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



,

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



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



 

4) закони де Моргана для двох змінних:



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





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



;

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



;

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



; ; ;

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



; ; і=0,…,n



База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка