Она важна для понимания того, как представляется информация в цифровых автоматах.
Это часть дискретной математики.
Многозначные логики (Я. Лукасевич, 1878 – 1956) изучают функции, определенные на дискретном (счетном, конечном) множестве значений. Для нас представляет интерес частный случай – двузначная (бинарная) алгебра логики. Это связано с тем, что логические устройства для двоичной логики наиболее просто технически реализуемы.
Бинарная логика (и соответственно бинарная, Булева алгебра – по имени ее автора английского математика Джорджа Буля, 1815-1864) имеет дело с величинами и с функциями, значения и аргументы которых определены на множестве всего двух значений. Эти два значения обозначают словами «истина» (true) и «ложь» (false) или цифрами 1 и 0 соответственно.
Логическая переменная – величина, которая в N-ичной логике может принимать одно из N дискретных значений. Поскольку в двоичной (Булевой) алгебре логическая переменная принимает только два различных значения, результаты алгебры логики используют для анализа свойств двоичной системы счисления, в которой цифра в каждом разряде числа может принимать лишь два значения: 0 или 1.
В дальнейшем, говоря о логических переменных, будем иметь в виду двоичную логику.
Логические функции (операции). Это функциональные зависимости между величинами, логическими переменными, которые могут принимать только значения 0 и 1 (в двоичной логике). В обычном математическом анализе изучают функции, определенные на множестве вещественных чисел, и там количество возможных функций бесконечно. Для двоичной же алгебры при конечном и весьма малом числе аргументов, количество возможных функций оказывается также невелико.
Для одной входной переменной x существует всего четыре очень простые логические функции (эти понятия и названия используются в описаниях устройств цифровой вычислительной техники):
| Значения аргумента: | x=0 | x=1 | Формула | Наименование функции |
| Значения функции: | y=0 | Тождественный нуль | ||
| y=x | Повторение | |||
| y=Ùx | Инверсия | |||
| y=1 | Тождественная единица |
Для двух входных переменных возможно четыре комбинации двух аргументов x0, x1, и существует 16 вариантов поведения выходной величины y (16 логических функций):
| Значения аргумента: | x0=0 x1=0 | x0=1 x1=0 | x0=0 x1=1 | x0=1 x1=1 | Формула | Наименование функции | |
| Значения функции | y=0 | Тождественный нуль | |||||
| y=x0 & x1 | Конъюнкция («И», «AND») | ||||||
| y=Ùx0 & x1 | Импликация | ||||||
| y=x1 | x1 (не зависит от x0) | ||||||
| y=x0 & Ùx1 | Импликация | ||||||
| y=x0 | x0 (не зависит от x1) | ||||||
| y=x0 Å x1 | Исключающее «ИЛИ» (логическая неравнозначность, «XOR») | ||||||
| y=x0 Ú x1 | Дизъюнкция («ИЛИ», «OR») | ||||||
| y=Ù( x0 Ú x1) | «ИЛИ-НЕ» | ||||||
| y=(x0 & x1) Ú (Ùx0 & Ùx1) | Логическая равнозначность (инверсия исключающего «ИЛИ») | ||||||
| y=Ùx0 | Инверсия x0 (не зависит от x1) | ||||||
| y=Ùx0 Ú x1 | ‑‑‑ | ||||||
| y=Ùx1 | Инверсия x1 (не зависит от x0) | ||||||
| y=x0 Ú Ùx1 | ‑‑‑ | ||||||
| y=Ù(x0 & x1) | «И-НЕ» | ||||||
| y=1 | Тождественная единица |
Примечание: В формулах использованы символы, общепринятые для обозначения логических операций:
Ù ‑ инверсия (отрицание), Ú ‑ дизъюнкция, & ‑ конъюнкция, Å ‑ исключающее ИЛИ.
Правила вычисления значений суммы S в данном разряде и переноса P в следующий разряд для двоичной системы счисления, которые рассмотрены ранее, можно записать простыми формулами булевой алгебры:
S=b0 Å b1; P=b0 & b1
Пользуясь этими формулами, и используя простейшие логические элементы, весьма просто построить одноразрядный двоичный сумматор (ссылка на книгу Танненбаума).
Три из перечисленных в таблице функций:
1) конъюнкция (логическое умножение, функция «И»)
2) дизъюнкция (логическое сложение, функция «ИЛИ)
3) функция «исключающее ИЛИ» (логическая неравнозначность)
‑ далее будут упоминаться при рассмотрении системы команд и операций с битовыми полями.
Две функции двух переменных (№8, «ИЛИ-НЕ» и №14 «И-НЕ») уникальны в том отношении, что каждая из них в одиночку обладает свойством функциональной полноты. Используя только элементы, реализующие одну из этих функций, можно построить любое, сколь угодно сложное логическое устройство.
Функции более чем двух входных переменных могут быть получены последовательным применением (суперпозицией) нескольких функций двух переменных, например:
y2 = x0 & x1 & x2 & x3 = y0 & y1 где y0 = x0 & x1, y1 = x2 & x3
- функция четырех переменных получается использованием трех функций двух переменных. Это положение будет проиллюстрировано при рассмотрении логических элементов далее.