Спирина, М.С. Дискретная математика

при любых значениях. Знак = входит в уравнение, которое, на­ пример, нужно решить. При этом только корни уравнения, буду­ чи подставлены в него, обратят его в тождество. 4.3.3. Формулы алгебры логики В математической логике, так же как и в алгебре, операции подчиняются определенным законам. С помощью этих законов (тождеств, равносильностей) можно упрощать составные выска­ зывания. Рассмотрим их для операций дизъюнкции и конъюнкции, учи­ тывая свойство двойственности. Двойственность операций (табл. 4.11) заключается в том, что если в формуле, содержащей лишь опера­ ции дизъюнкции, конъюнкции и отрицания, заменить операции л и v на v и л соответственно, а символы 1 на 0 и 0 на 1 , то получатся новые равносильности. Законы Де Моргана называют переносом отрицания через ло­ гические связки. Приведем формулы с другими операциями, которые также будем считать основными: Т а б л и ц а 4.11 Законы алгебры логики Дизъюнкция Законы Конъюнкция a v b = b v а Переместительный закон ab = Ьа a v (b v с) = = (a v b) v с Сочетательный закон а(Ьс ) = ( ab)c a(b v с) = ab v ас Распределительный закон a v ( Ьс ) = = (a v b)(a v с) a v а = а Правила идемпотент­ ности а а - а a v b=a - Ь Законы Де Моргана ab=a v Ь a v 0 = а Правила операций О I О а a v 1 = 1 с константами а 1 = a a v ab = о Законы поглощения a(a v b) = а a v ( ab ) = a v b a(a v b) = ab a v а = 1 Законы инверсии (отрицания) a • a = 0 ab v ab = а Законы склеивания (a v b) ■ (a v b) = a 152