Занятие 2 (часть 1) Логические формулы. Законы алгебры логики. - презентация

1 Занятие 2 (часть 1) Логические формулы. Законы алгебры логики

2 Определение 1 Логической переменной называется переменная, значением которой может быть любое высказывание. Пример: x, у, x 1, y 1, x k, у n

3 Определение 2 Логической формулой является: 1) любая логическая переменная, а также каждая из двух логических констант 0 (ложь) и 1 (истина); 2) если А и В формулы, то В и А*В тоже формулы, где знак «*» означает любую из логических бинарных операций. Пример: (х & у) z Формуле приписывается одно из двух значений 0 или 1.

4 Определение 3 Формулы А и B, зависящие от одного и того же набора переменных x 1, х 2, х 3, … x n, называют равносильными или эквивалентными, если на любом наборе значений переменных x 1, х 2, х 3, … x n они имеют одинаковые значения. Пример: А = В

5 Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, v и отрицание.

6 Законы алгебры логики

7 Законы коммутативности x & у = y & x x v у = y v x

8 Законы ассоциативности (x & у) & z = x & (у & z) (x v у) v z = x v (у v z)

9 Законы поглощения (нуля и единицы) x v 0 = x x & 1 = x

10 Законы дистрибутивности x & (у v z) = (x & у) v (x & z) x v (у & z) = (x v у) & (x v z)

11 Закон противоречия x & x = 0

12 Закон исключенного третьего x v x = 1

13 Законы идемпотентности (равносильности) x & x = x x v x = x

14 Закон двойного отрицания x = x

15 Законы де Моргана x & у = x v y x v у = x & у

16 Законы поглощения x v (x & y) = x x & (x v y) = x

17 Любой из законов алгебры логики может быть доказан с помощью таблиц истинности.

18 Доказательство первого закона де Моргана x & у = x v y xyx & у xyx v y

19 Законы алгебры логики можно доказать путем логических рассуждений.

20 Доказательство первого закона поглощения x v (x & у )= x Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна по определению дизъюнкции. Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула x, или формула (x & у), или обе эти формулы одновременно. Если x ложна, тогда (x & у) ложна, следовательно, x может быть только истинной.

21 Законы алгебры логики можно доказать путем тождественных преобразований.

22 Доказательство первого закона поглощения x v (x & у )= x x v (x & у ) = (x & 1 ) v (x & у ) = x & (1 v y) = x

23 Определение. Формула А называется тавтологией (или тождественно истинной), если она истинна при любых значениях своих переменных. Пример: х v х (закон исключенного третьего)

24 Определение. Формула А называется тождественно ложной, если она ложна при любых значениях своих переменных. Пример: х & х

25 Приоритет логических операций 1. Отрицание. 2. Конъюнкция. 3. Дизъюнкция (строгая и нестрогая). 4. Импликация и эквивалентность.

26 Задачи

27 Рассмотрите два сложных высказывания: F 1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3}; F 2 = {если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3}. Формализуйте эти высказывания, постройте таблицы истинности для каждой из полученных формул и убедитесь, что результирующие столбцы совпадают.

28 Решение x = {одно слагаемое делится на 3}; y = {сумма делится на 3}; z = {другое слагаемое делится на 3}. F 1 = x & y z F 2 = x & z y

29 xyzx & yF1F1 x & zyF2F

30 Формализуйте высказывания и постройте таблицы истинности: F 1 = {если все стороны четырехугольника равны и один из его углов прямой, то этот четырехугольник является квадратом}; F 2 = {если все стороны четырехугольника равны, а он не является квадратом, то один из его углов не является прямым}.

31 Решение x = {все стороны четырехугольника равны}; y = {один угол четырехугольника прямой}; z = {четырехугольник является квадратом}. F 1 = x & y z F 2 = x & z y

32 xyzx & yF1F1 x & zyF2F

33 Докажите следующие соотношения: 1) a b = a v b 2) a ~ b = a & b v a & b 3) a b = a & b v a & b 4) a b = b a 5) a ~ b = (a b) & (b a) 6) a b = a ~ b

34 a b = a v b

35 ab a b aa v b a b = a v b

36 a ~ b = a & b v a & b

37 aba ~ ba & b a & b v a & b a ~ b = a & b v a & b

38 a b = a & b v a & b

39 ab a b a & b a & b v a & b a b = a & b v a & b

40 a b = b a

41 ab a b ab b a a b = b a

42 a ~ b = (a b) & (b a)

43 aba ~ b a bb aa b & b a

44 a b = a ~ b

45 aba ba ~ b a b = a ~ b

46 Найдите x, если (x v a) v (x v a) = b

47 Решение (x v a) v (x v a) = = (x & a) v (x & a) = = (x & x) v (a & a) = = x & 1 = x x = b

48 Какие формулы являются тавтологиями? 1) a & a 2) a (b a) 3) (a & b) a

49 a & a aa

50 a (b a) ab b aa (b a)

51 (a & b) a abb & a (a & b) a

52 Является ли формула тождественно ложной? a & (a b) & (a b)

53 ab a b b a & (a b) & (a b)