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

59 § 4. Равносильность формул Формулы А vi в называются равносильными, если при каждой совокупности значений всех переменных, входящих в Л и В, эти формулы принимают одинаковые значения. Например, формула Ixv у равносильна формуле л: в чем легко убедиться с помощью таблиц истинности: 1 X v .У X у 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 В этих таблицах результирующие столбцы совпадают, т.е. при одинаковых значениях переменных х изначения формул Jxvy а равны, следовательно, эти формулы равносильны. Далее, формула х\^&у равносильна х. Действительно, имеем следующую таблицу: X ¥ 1 Также, очевидно, X \/7х равносильно у v/y. При определении равносильности двух формул не обязательно предполагать, что они содержат одни и те же переменные. Высказывание «А равносильно В» будем обозначать следующим образом: А ~ В. Пусть Л, В, С - произвольные формулы. Отношение равносильности формул, как легко видеть, обладает следующими свойствами; - рефлексивностью:^ ^ - симметричностью: если А ~ В, то В ^ А-, - транзитивностью; если А - В и В ~ С, та А - С. Следовательно, отношение равносильности является отношением эквивалентности на множестве формул и разбивает множество формул на непересекающиеся классы. В каждый из классов попадают равносильные между собой формулы. Формула, тождественно равная единице, называется тав?»оло2ме«. •у , X v X & у 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1