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

61 Если под JC понимать обозначение некоторого высказывания, то получаем, что двойное отрицание высказывания л: означает то же, что и высказывание я. ГТол>'ченное соотношение между 1(]х) и л: называют законом двойного отрицания. Аналогичным образом можно показать, что имеют место следующие свойства, часто называемые законами. i ; 2) х&у~ у & хЛ - законы коммутативности (перестановочности); 1 3jxvy~yvx; i 4) (х&у)с& z- х&(у& z);] > - законы ассоциативности; \ V fxvyjvz-xvfyvzj;] I 6J x&fy\/zj ~x&yvx &2 - первый закон дистрибутивности; i 7) xvy&z - (xvy)&(xvz) - второй закон дистрибутивности; j 8) 1(х&у) 4xvlу, "1 I 9) l(xvy) ~ 1х& 1у. J - ! 10) х&х~х, ~1 i 11) XVX -X _J " мдеуииоотеншносотм; I 12) xvlx - Т - закон исключенного третьего; I 13) х&1х - П - закон противоречия; \ 14) х&Т-А; 15) xvT- Т; 16) х&П~П, 17) ХУП-Х; J 18) xvx&y~x, - свойство операций с Г и сЛ; -W } ! 20) х^у ~ 1у=>1х - закон контропозщии. , I • законы поглощения; i 19) x&(xvy)^ ~- ' Kaic уже замечено, соотношения 1) - 20) доказываются с помощью таблиц истинности. Можно показать, что соотношения 1) -20) будут иметь место и тогда, когда вместо переменных х,у кг будут подставлены произвольные формулы А,В шС соответственно. Соотношения 1) - 20) позволяют находить для заданных формул равносильные упрощенные формулы или равносильные формулы, имеющие более удобный с некоторых позиций вид. Из этих же соотношений видно, что над формулами можно производить преобразования: раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя. Из соотношений 2) - б) видно, что операция & напоминает умножение (обладает некоторыми свойствами умножения), а v - сложение, поэтому часто конъюнкцию называют (логическим) произведением, а дизъюнкцию - (логической) суммой.