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

58 х У Z (((x&y)vz)=i>x) 0 - 0 1 0 - 1 0 1 - - 1 § 3. Упрощения в записях формул Введем некоторые соглашения о более экономном употреблении скобок в записях формул. Эти соглашения облегчат нам чтение сложных выражений. Во-первых, будем опускать в формуле внешнюю пару скобок. (В случае одной переменной этой внешней пары скобок нет по определению.) Во-вторых, если формула содержит вховдения только одной бинарной связки &, V, => или =, то для каждого вхождения этой связки опускаются внешние скобки у той из двух формул (соединяемых .этим вхождением) которая стоит слева. Пример, xvyvzvx пишется вместо (((xvy)vz )-vx), а y:::>y:^x=>(z=^x) пишется вместо (((y:::>y)=>x)=>{z=>x)). В-третьих, договоримся считать связки упорядоченными следующим образом: 1, v, = и будем опускать во всякой формуле все те пары скобок, без которых возможно восстановление этой формы на основе следующего правила. Каждое вхождение знака / относится к наименьшей формуле, следующей за ним; после расстановки всех скобок, относящихся ко всем вхождениям знака I каждое вхождение знака & связывает наименьшие формулы, окружающие это вхождение; затем (т.е. после расстановхси всех скобок, относящихся ко всем вхождениям знаков 1 п &) каждое вхождение знака \/ связывает наименьшие формулы, окружающие это вхождение, и аналогично для ^ и =. При применении этого правила к одной и той же связке продвигаемся слева направо. Пример. В упрощенной записи формулы x=lx&y:^zvlt скобки восстанавливаются следующими шагами: х=(]х) &y=>z v( ]t), x=((lx)&y)=>zv(]0, Xs ((Jx)cS :y)z :>(zv(Jt)), ХЩ'{{ Ix) &y) =>(z v( 11))), (x^((]x)&y)=>(zv(]t)))). Однако не всякая формула может быть записана без скобок. Например, нельзя опустить оставшиеся скобки в следующих случаях: x&(y =>z), x^(y=>z), ](xvy). Для операций +, | и J. не указаны порядки их выполнения, поэтому последовательность их выполнения устанавливается с помощью скобок.