Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

13 В отличие от табличного задания представление данной функции формулой не единственно. Например, функцию f 14 «штрих Шеффера» из таблицы 2.3 можно выразить формулами f 14 (x 1 ,x 2 )= 1 2 | x x = 1 2 x x  f 14 (x 1 ,x 2 )= 1 2 | x x = 1 2 x x (3.2) а функцию f 8 «стрелка Пирса» – формулами f 8 (x 1 ,x 2 )= 1 2 x x  = 1 2 x x  f 8 (x 1 ,x 2 )= 1 2 x x  = 1 2 x x  (3.3) Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными. Эквивалентность формул обозначается знаком равенства: 1 2 x x  = 1 2 x x  , 1 2 x x  = 1 2 x x  Эти формулы являются законом де Моргана. При снятии общего отрицания меняются конъюнкция на дизъюнкцию и ставятся отрицания над элементами 1 x и 2 x Для того чтобы выяснить, эквивалентны формулы или нет, можно по каждой формуле восстановить таблицу функции, а затем эти таблицы сравнить. Пример 3.1: Доказать истинность формулы. 1 2 x x  = 1 2 x x  Построим таблицу истинности для правой и левой части (таблица 1.3.1). Таблица 3.1. 1 x 1 x 1 2 x x  1 2 x x  1 x 2 x 1 2 x x  0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0