Так как предикаты способны принимать только значения 0 и 1, то их, как и булевы переменные, можно связывать логическими операциями. В результате получаем формулы, определяющие более сложные предикаты. Так, если Р(х) означает «х - инженер», а Q(х) - «x - сотрудник нашего отдела», то Р(х) ∧ Q(х) = R(х) есть одноместный предикат «х - инженер и сотрудник нашего отдела» или проще «х - инженер нашего отдела». Очевидно, если Р - множество инженеров, а 0 - множество сотрудников данного отдела, то этот предикат соответствует пересечению Р ∩ Q. Таким образом, имеет место тесная связь между логикой предикатов и операциями над множествами.
10. Двоичная арифметика. В позиционной системе счисления с основанием m любое целое неотрицательное число a записывается последовательностью различных цифр x1x2 ... xn, что означает a = x1mn-1 + x2mn-2 + ... + xnm0. Десятичная система использует цифры 0, 1, ..., 9, например: 2907 = 2·103 + 9·102 + 0·101 + 7·100. Для двоичной системы счисления достаточно двух цифр, которые обозначаются 0 и 1. При этом последовательность x1x2 ... xn таких цифр является записью двоичного n-разрядного числа x1·2n-1 + x2·2n-2+ ... + xn·20.
Перевод целых десятичных чисел в двоичные осуществляется последовательным делением исходного числа и каждого частного на два. Получаемые при этом остатки (0 или 1), записанные в обратном порядке, и дают представление десятичного числа в двоичной системе счисления. Например:
Действительно, проверяя полученный результат, получаем 1·24 + 1·23 + 0·22 + 1·21 + 0·20 = 16 +8+2 = 26.
Дробное число переводится в двоичную систему счисления методом последовательного умножения на два. При этом каждый раз
- 69 -
после запятой двоичного числа записывается 0 или 1 соответственно целой части результата умножения. Последовательное умножение продолжается до тех пор, пока дробная часть не обратится в нуль или пока не получим требуемое количество двоичных знаков после запятой. Например, двоичное представление числа 0,3125 получается следующим образом:
Проверка полученного результата дает: 0·2-1 + 1·2-2 + 0·2-3 + 1·2-4 = 1/4 +1/16 = 5/16 = 0,3125.
Если число является смешанным, т.е. его целая и дробная части отличны от нуля, то оно переводится в двоичную систему раздельно: целая часть- последовательным делением, а дробная — последовательным умножением.
Арифметические операции над числами сводятся к операциям сложения и умножения одноразрядных чисел. В двоичной системе счисления умножение задается таблицей конъюнкции: 0·0=0; 1·0=0; 0·1=0 и 1·1=1. Сложение выполняется по правилу: 0 + 0 = 0; 1+0=1; 0+1=1 и 1+1=10 (10 — это двоичное число, соответствующее десятичному числу 2). Операции над двоичными числами выполняются по правилам, аналогичными для десятичных чисел, но эти правила предельно упрощаются (особенно для умножения). Например, десятичные операции 41 + 27 = 68 и 41·5= 205 выглядят следующим образом:
- 70 -
Как видно, умножение двоичных чисел сводится к сложению чисел, образованных сдвигом влево первого сомножителя. Поразрядное сложение осуществляется в соответствии с таблицей
причем в случае x1 = x2 = 1 образуется единица переноса в старший разряд. Операция, задаваемая этой таблицей, называется сложением по модулю 2. Если при сложении перенос не учитывается, то эта операция вместе с операцией умножения определяет на множестве двоичных чисел арифметику по модулю 2.
Задачи и упражнения
1. Подстановкой в формулу a ∨ b переменных запишите новые формулы и упростите их, если это возможно: а) a = x̅y, b = z. б) a = xy, b = xy̅; в) a = x, b = xy; г) a = x, b = x̅y; д) a = xy, b = c ∨ d, c = xz, d = yz̅.
2. Запишите таблицы соответствия для следующих формул: а) xx̅; б) xy ∨ x̅; в) (p ∨ q)(p̅ ∨ q̅); г) x̅∨̅y̅.
3. Проверьте с помощью таблиц соответствия следующие тождества: а) x̅∨̅y̅ = x̅ y̅; б) x ( x ∨ y) = x; в) x ∨ x̅ y = x ∨ y.
4. Постройте переключательные схемы для обеих частей приведенных ниже тождеств и убедитесь в том, что эти схемы функционируют одинаково:
а) xy∨x̅y∨x̅y̅=y ∨ x̅y̅
б) (x∨y)(x∨z) = x ∨ yz;
в) xyz∨xyz̅∨xy̅ = x.
5. Упростите следующие формулы: