Дискретная математика

56 и (x^(y&z)) можно представить их графиками, как на рис. 3.1 а, б и в соответственно. Иногда булеву функцию называют переключательной функцией. (0.1) (1,1) (0,0) (1,0) а) (0,1) (1,1) (0,0) (1,0) б) Рис. 3.1 (0,0,1) (0,1,1) ( 1Д1 ) (0,0,0) (1,1,1) (0,1,0) (1,0,0) (1,1,0) в) § 2. Формулы Введем понятие формулы, с помощью которых можно задавать булевы функции. Эти формулы иногда называют пропозициональными формами или фор.мулами алгебры (логики) высказываний, \/ Индуктивное определение 1) каждая булева переменная (x,y,z, ...,xj,x2. —J является формулой; 2) если-4 и В формулы, то fM), (А&В), (AvB), СА=>В), (А=В), (А IB) и (AJ-B) тоже формулы; 3) только те выражения являются формулами, для которых это следует из пп. 1) и 2). Примеры формул: х, (1у)^ ((x&y)^(lz)). Заглавные буквы латинского алфавита {А,В,С ,.,.) или те же буквы с числовыми индексами (Ai,A2,...,Bj,B2,...,Ci,C2,...) употребляются для обозначения произвольных формул. Как определено выше, каждая булева переменная может принимать значения 1 либо О, которые считаем их (истинностными) значениями. Формулы являются аналитической записью булевых функций. В предыдущем парахрафе были введены основные булевы функции, представленные в виде формул, и определены (истинностные) значения этих функций (формул). Истинностное значение формул (булевых функций) можно определить с помощью таблиц истинности. Существуют различные методы построения таблиц истинности. Первый метод состоит в подробных вычислениях.