Для математичного опису роботи МП-пристроїв, синтезу і аналізу схем широко використовується алгебра логіки.
Предметом розгляду алгебри логіки є висловлювання.
Біт можна розглядати як логічне висловлювання, відносно якого можна говорити про його істинність. Він може набувати значення «1, істина», якщо висловлювання справедливе, і «0, не істина», у протилежному випадку.
При такій інтерпретації відомі в логіці зв’язки кон’юнкції, диз’юнкції, заперечення та інші можуть мати уявлення на мові бітів. І навпаки, бітові операції легко описуються на мові обчислення значення висловлювань.
Прості висловлювання, істинність яких не залежить від істинності іншого висловлювання і можуть мати лише одне із двох значень 0 і 1 є двійковими змінними.
Складні висловлювання, істинність яких залежить від істинності простих висловлювань, що входять до їх складу, є логічними функціями від двійкових змінних. Складові двійкових функцій (аргументи) пов’язуються логічними операціями (аналогічно арифметичним операціям в алгебраїчних виразах).
Основними логічними операціями над двійковими змінними є логічне заперечення, логічне множення, логічне додавання, додавання за модулем 2.
Логічні операції лежать в основі обробки цифрових сигналів. А саме, за допомогою їх можна з одного або кількох сигналів на вході отримати на виході новий сигнал, який у свою чергу може бути поданий на вхід однієї або кількох наступним таким операціям. По суті, саме логічні операції у поєднанні з запам’ятовуючими елементами (наприклад, тригерами), реалізують все різноманіття можливостей сучасної цифрової техніки.
Комп’ютерні обчислення природно розглядати як деякі інформаційні перетворення, на вхід яких подаються ланцюжки бітів, які перетворюються відповідно до тієї чи іншої формули. Однією з простих моделей комп’ютерних обчислень є комбінаційна схема, яка складається з більш простих обчислювальних елементів. Відповідно до цього, перетворення, яке реалізується комбінаційною схемою, розглядається як деяка логічна функція.
Логічну функцію можна задати двома основними способами:
- за допомогою таблиці істинності; таблиця істинності – це таблиця, яка ставить у відповідність кожній можливій комбінації аргументів певне значення функції;
-
- аналітично через логічні вирази; логічний вираз визначає явну формулу, за якою можна обчислити функцію при певних значеннях змінних.
В таблиці показана таблиця істинності для логічної функції від трьох логічних змінних: M = f (A, В, С). Це функція більшості, яка приймає значення 0, якщо більшість її аргументів дорівнює 0 та значення 1, якщо більшість аргументів дорівнює 1. Така функція взагалі називається мажоритарною.
Таблиця.
Таблиця істинності для функції більшості.
| A | B | C | M |
Будь-яку логічну функцію можна означити, вказавши, які комбінації значень аргументів дають значення функції 1. Для мажоритарної функції, наведеної в таблиці, існує 4 комбінації змінних, які дають значення функції «1» (011, 101, 110, 111). Якщо вербально описати перший рядок таблиці, в якому функція має значення 1, то це може бути такий вислів: «якщо одночасно A = 0, B = 1, С = 1, то M = 1». Слово «одночасно» може бути замінене зв’язкою «і». Тоді матимемо: «якщо A = 0 і B = 1 і С = 1, то M = 1». Значення «1» функція може набути і в трьох інших випадках. Щоб і цю обставину врахувати, використовуємо зв’язку «або». Тоді остаточно формулюється вираз, який визначає одиничне значення функції: «якщо A = 0 і B = 1 і С = 1 або A = 1 і B = 0 і С = 1 або A = 1 і B = 1 і С = 0 або A = 1 і B = 1 і С = 1, то M = 1», тобто, функція М приймає значення «істина», якщо один із цих чотирьох часткових висловів «істина».
В аналітичному виразі для зображення 0-го значення змінної (аргументу або функції) прийнято зображувати над ним риску; зв’язку «і» позначають символом «Ù» або опускають як у звичайній алгебрі знак множення; зв’язку «або» позначають символом «Ú» або допускають позначення символом «+».
Використовуючи описані позначення можна записати сформульований вислів у вигляді формули:
.
Це компактний запис таблиці істинності, який описує зазначену логічну функцію.
