logo search
Diskretnaya_matematika_1_semestr

Эквивалентность формул. Свойства элементарных булевых функций.

Формулы U,W называются эквивалентными ( U=V), если они реализуют равные функции.

Принцип эквивалентности. Если в формуле некоторую подформулу земенить на эквивалентную ей формулу, то результатом будет формула, эквивалентная исходной. Принцип эквивалентности позволяет тождественно преобразовать ф-лу.

Свойства:

1) x1&x2=x2&x1

2) x1&(x2&x3)=(x1&x2)&x3

3) ,4) V,|+|^2

5)x1x2=x2 x1

x1(x2x3)=(x1x3)x2

6)Закон двойного отрицания

¬¬(х)=х

7.Закон де Моргана: ¬хÙ¬у=¬(ху); ¬х&¬у=¬(хÙу);

8) хÙх=х; 9)х&х=х; 10) x Ù¬ x =1; 11) х&¬х=0; 12) хÙх&у=х – Закон поглащения

  1.