Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

6) A&(BvC) -A&BvA&C - первый закон дистрибутивности; 7) А vB&C (А vB)&(A vC) - второй закон дистрибутивности; 8) -п(А&В) „г законы де Моргана; 9) -^{А vB) ~ -А&^ В, J у ' 10) А&А ~1 ^ ' L законы идемпотентности; И) AvA-A, f 12) А v —iA ^ Т - закон исключенного третьего; 13) А&^А-П - закон противоречия; 14) А&Т-А; > свойство операций с Т и с П; 15) AvT-T; 16) А&П П 17) АуП-А; 18) AvA&B-A;^ . п т. ч . ^ законы поглощения; 19) A&(AvB)-A; j ^ 20) А^В В^ —А - закон контропозиции. Как уже указано, соотношения 1) - 20) доказываются с помощью таблиц истинности. Можно показать, что соотношения 1) - 20) будут иметь место и тогда, когда вместо пропозициональных букв 5 и С будут подставлены произвольные пропозициональные формы. Соотношения 1) - 20) позволяют находить для заданных форм равносильные упрош,енные формы или равносильные формы, имеюш,ие более удобный с некоторых позиций вид. Из соотношений 2) - 6) видно, что операция & напоминает умножение (обладает некоторыми свойствами умножения), а v - сложение, поэтому часто конъюнкцию двух высказываний называют (логическим) произведением их, а дизъюнкцию - (логической) суммой. § 5. Зависимости между пропозициональными связками Связки —1, &, V, =>, = не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие, так что при этом получаются равносильные пропозициональные формы. Например, связка = может быть выражена через связки и & иа основании соотношения А=В - (А^В) & (В^А). (1.1) Для доказательства (1.1) достаточно составить таблицы истинности и убедиться, что результируюш,ие столбцы этих таблиц совпадают. Для импликации имеем: A^B- ^AvB . (1.2) 14