Булева алгебра (1023551), страница 2
Текст из файла (страница 2)
Количество сомножителей в элементарном произведении называется его рангом r. Так для x3
2 1x0 ранг r = 4, а для x3 0 r = 2. Логическое произведение, являющееся функцией всех n переменных, называется конституентой единицы (составляющей единицы). Смысл этого термина будет пояснен ниже. Для n переменных существует 2n конституент единицы, причем на данном конкретном наборе лишь одна конституента единицы будет равна 1, все другие будут равны 0.
Два элементарных произведения одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, x2 1 0 и x2 1x0 являются соседними, а x2 1 0 и 2 1x0 нет.
Логическая сумма любого числа переменных из конечного набора n переменных называется элементарной, когда слагаемыми в ней являются либо переменные либо их отрицания. Например, сумма 3+x2+x1+ 0 является элементарной, а 3x2+x0; 3+
+x0 и x3+
+ 0 нет.
Количество слагаемых в элементарной сумме называется ее рангом r. Так для 3+x2+x1+ 0 r = 4, а для x3+ 0 r = 2. Логическая сумма, являющаяся функцией всех n переменных, называется конституентой нуля (составляющей нуля). Смысл этого термина будет пояснен ниже. Для n переменных существует 2n конституент нуля, причем на данном конкретном наборе лишь одна конституента нуля будет равна 0, все остальные будут равны 1.
Две элементарные суммы одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, суммы 2+x1+ 0 и x2+x1+ 0 являются соседними, а 2+x1+ 0 и 2+ 1+x0 нет.
Приоритеты логических операций
Пусть требуется определить значение истинности функции 
на наборе 11 (одиннадцать). Представив десятичное число 11 в виде двоичного числа 1011, мы определяем, что x3 = 1; x2 = 0; x1 = x0 = 1. Возникает вопрос: в каком порядке выполнять различные логические операции в рассматриваемой функции? Из законов инверсии вытекает, что старшей (первой) операцией является операция отрицания. Это значит, что операции логического умножения и сложения нельзя производить, игнорируя знак отрицания над переменными, т.е. операцию отрицания надо выполнять в первую очередь.
Операции логического умножения и сложения в силу симметричности законов булевой алгебры равноправны, однако на практике принято считать более старшей операцию логического умножения, что соответствует правилам обычной алгебры.
Итак, если в логическом выражении встречаются все три операции И, ИЛИ, НЕ то сначала выполняется операция НЕ над отдельными переменными, затем операция И и наконец ИЛИ.
Действия под групповым знаком инверсии выполняются по этому же правилу. Отклонение от этого правила должно быть обозначено скобками.
В рассматриваемом примере действия выполняются в следующемпорядке
= 
Функции алгебры логики
Функцией алгебры логики (ФАЛ) называется функция, которая, как и ее аргументы, может принимать только два значения: 0 и 1.
Формы задания функций алгебры логики
ФАЛ могут быть представлены различными способами:
1. Словесным описанием (назначением, определением).
2. Таблицей истинности.
3. Аналитическим выражением.
4. Картой Карно.
5. Переключательной схемой.
6. Диаграммой Венна.
7. Геометрическим способом (гиперкубами).
8. Диаграммой двоичного решения.
Если ФАЛ зависит от n переменных, то она может быть определена на N=2n наборах. Когда функция определена на всех этих наборах, она называется полностью определенной. Число различных, полностью определенных ФАЛ, равно
Если на некоторых наборах ФАЛ не определена, то она называется не полностью определенной. В последнем случае возможны две ситуации: либо нас не интересуют значения функции на некоторых наборах, либо на цифровое устройство никогда не поступят некоторые наборы. Имеется три возможности задать не полностью определенную ФАЛ на любом из N наборах: выбрать её значение равным 0, 1 или безразличным значением. Если исключить случай, когда ФАЛ не определена на никаком наборе, то общее число возможных способов задания не полностью определенной ФАЛ от ‘n’ переменных будет равно
Рассмотрим все перечисленные выше формы представления для полностью определенной ФАЛ, зависящей от 3-х переменных
y=ƒ(x2; x1; x0).
Словесное описание этой функции формулируется следующим образом: функция принимает истинное значение, когда либо истинна переменная x2, либо вместе истинны переменные x1 и x0.
Таблица истинности (см. табл. 1) для ФАЛ имеет следующую структуру: в столбце “№ ” указаны десятичные эквиваленты двоичных 3-х разрядных чисел, условно составленных из значений трех аргументов x2; x1 и x0 с учетом соответственно их двоичных весов 4, 2 и 1.
Чтобы быстро и без ошибок заполнить все 2n строк с различными наборами, рекомендуется заполнять их по столбцам. Так как переменная x0 имеет вес 1, то в соответствующем столбце сверху вниз записывается последовательность 0101...; x1 имеет вес 2, поэтому в соответствующем столбце записывается последовательность 0011...; для x2 – 00001111... и т. д. В столбце ‘y’записываются значения ФАЛ на каждом наборе.
| Таблица 1 | ||||
| № | x2 | x1 | x0 | y |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Рассматриваемая ФАЛ принимает значение 0 на первых трех наборах и значение 1 на остальных пяти.
Представление ФАЛ в виде таблицы истинности удобно и наглядно для n <= (46). При больших n таблицы становятся громоздкими и трудно обозримыми, что является их основным недостатком.
Аналитический способ задания ФАЛ основывается на использовании базовых логических операций И, ИЛИ, НЕ, определяемых аксиомами булевой алгебры. Ограничимся рассмотрением только двух канонических (основных) аналитических выражений ФАЛ по значениям истинности и по значениям ложности. Если ФАЛ задана по значениям истинности, то говорят, что аналитическое выражение записано в совершенной дизъюнктивной нормальной форме (СДНФ). Нормальной эта форма называется потому, что все члены выражения имеют вид элементарных произведений. Дизъюнктивной эта форма называется потому, что все они соединены знаком дизъюнкции, а совершенной потому, что все члены формулы имеют высший ранг r=n, являясь конституентами единицы.
Чтобы получить аналитическое выражение для ФАЛ, заданной таблицей истинности, в СДНФ, нужно записать логическую сумму конституент единицы для тех наборов входных переменных, на которых ФАЛ принимает единичное значение, причем, переменная берется без знака инверсии, если ее значение в наборе равно 1 и с инверсией, если ее значение в наборе равно 0.
СДНФ ФАЛ, заданной табл. 1, имеет следующий вид:
(1)
Чтобы сделать запись ФАЛ более компактной, можно заменить конституенты единицы номерами соответствующих наборов:
у = 3+4+5+6+7, (2)
либо использовать следующую запись:
у = V (3, 4, 5, 6, 7) . (3)
Если ФАЛ задана по значениям ложности, то говорят, что аналитическое выражение записано в совершенной конъюнктивной нормальной форме (СКНФ). Нормальной эта форма называется потому, что члены выражения имеют вид элементарных сумм. Конъюнктивной эта форма называется потому, что все члены формулы соединены знаком конъюнкции, а совершенной потому, что все члены формулы имеют высший ранг r=n, являясь конституентами нуля.
Чтобы получить аналитическое выражение для ФАЛ, заданной таблицей истинности, в СКНФ, нужно записать логическое произведение конституент нуля для тех наборов входных переменных, на которых ФАЛ принимает нулевое значение, причем, переменная берется со знаком инверсии, если ее значение в наборе равно 1 и без знака инверсии, если ее значение в наборе равно 0.
СКНФ ФАЛ, заданной табл. 1, имеет следующий вид:
(4)
у = 0 ∙1∙ 5)
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
