Равносильные преобразования

1.

Лекция 1.4.Новая. Равносильные преобразования.
I. Основные равносильности.
1) x & x x ( x & x & ... & x x)
2) x x x ( x x ... x x)
3) x & 1 x;
– законы идемпотентности;
4) x 1 1;
5) x & 0 0;
6) x 0 x;
7) x & x 0
– закон противоречия;
8) x x 1 – закон исключенного третьего;
9) x x – закон снятия двойного отрицания;
10) x & ( y x) x
11) x ( y & x) x – законы поглощения.
Лекция 1.4.Нов.Равнос.преобр
1

2.

II. Равносильности, выражающие одни логические
операции через другие.
1) x y ( x y ) & ( y x);
2) x y x y;
3) x & y x y
4) x y x & y
– закон де Моргана;
5) x & y x y ;
6) x y x & y.
Лекция 1.4.Нов.Равнос.преобр
2

3.

III. Равносильности, выражающие основные законы
алгебры логики.
1) x & y y & x – коммутативность конъюнкции;
2) x y y x – коммутативность дизъюнкции;
3) x & ( y & z ) ( x & y ) & z – ассоциативность конъюнкции;
4) x ( y z ) ( x y ) z – ассоциативность дизъюнкции;
5) x & ( y z ) ( x & y ) ( x & z )
–
дистрибутивность
конъюнкции относительно дизъюнкции;
6) x ( y & z ) ( x y) & ( x z ) –
дистрибутивность
дизъюнкции относительно конъюнкции.
Лекция 1.4.Нов.Равнос.преобр
3

4.

Основные
равносильности.
Равносильности, выражающие
одни операции через основные законы
другие.
алгебры логики
1) & x & ... & x x) 1) x y ( x y ) & ( y x);
2) x x ... x x) 2) x y x y;
3) x & 1 x;
4) x 1 1;
5) x & 0 0;
6) x 0 x;
7) x & x 0
8) x x 1
3) x & y x y
4) x y x & y
5) x & y x y ;
1) x & y y & x –
2) x y y x –
3) x & ( y & z ) ( x & y ) & z
4) x ( y z ) ( x y ) z
5) x & ( y z ) ( x & y ) ( x & z )
6) x ( y & z ) ( x y ) & ( x z )
6) x y x & y.
9) x x
10) x & ( y x) x
11) x ( y & x) x
Лекция 1.4.Нов.Равнос.преобр
4

5.

Формулы
логики
высказываний
(как
и
алгебраические) подчиняются следующим законам:
1) рефлексивным А ≡ А для любой формулы А;
2) симметричным, то есть, если А ≡ В, В ≡ А для
любых формул А и В;
3) транзитивным, то есть, если А ≡ В и В ≡ С, то А ≡
С для любых формул А, В, С.
Используя равносильности I, II, III и их свойства,
можно часть формул алгебры логики или всю формулу
заменить равносильной ей формулой. Равносильные
преобразования формул применяются для приведения
формул к заданному виду, для упрощения формул.
Рассмотрим некоторые наиболее распространенные
соглашения о записи формул.
Лекция 1.4.Нов.Равнос.преобр
5

6.

1. Не заключать в скобки формулу или часть ее,
стоящую под знаком отрицания, то есть писать
p q&r
вместо ( p q) & r . Операция инверсии
является наиболее приоритетной среди основных
операций.
2. Считать, что знак конъюнкции связывает
аргументы формулы «сильнее» знаков дизъюнкции,
импликации и эквиваленции, то есть писать
p & q r вместо ( p & q) r ;
p q & r вместо p (q & r ) ;
p & q r & s вместо ( p & q) (r & s) .
Лекция 1.4.Нов.Равнос.преобр
6

7.

3. Считать, что знак дизъюнкции связывает сильнее
знаков импликации и эквиваленции, то есть писать
p q r вместо ( p q) r ;
p q r вместо p ( q r ) .
4. Считать, что знак импликации связывает сильнее,
чем знак эквиваленции, то есть писать
p q r вместо ( p q) r .
5. Опускать внешние скобки, то есть скобки, которые
заключают внутри себя все остальные символы,
составляющие формулу. Так, формулу ( p & (q r ))
писать p & (q r ) .
Лекция 1.4.Нов.Равнос.преобр
7

8.

Соглашения 1-5, а также опускание знака
конъюнкции, значительно упрощают запись формул.
Например, формула
((( p & q) r ) (( p q) r )) ,
записанная с учетом этих соглашений, будет
выглядеть так:
pq r ( p q r ) .
При чтении формула может быть названа по
«последней» операции, знак которой слабее всех
остальных знаков операций, входящих в формулу. Так,
записанная выше формула представляет собой
импликацию.
Лекция 1.4.Нов.Равнос.преобр
8

9.

Пример. Доказать равносильность p q p & q .
Решение. Для доказательства равносильности
подвергнем левую часть формулы равносильным
преобразованиям: p q p q p & q p & q . По
шагам использовались следующие равносильности:
II.2, II.4, I.9. Таким же образом вы должны оформлять
индивидуальные задания, указывая номер формулы над
знаком тождественности.
Пример. Необходимо упростить формулу:
( x x) x;
Ответ: Х.
Лекция 1.4.Нов.Равнос.преобр
9

10.

Кроме представленных функций существуют и две
дополнительные: штрих Шеффера и штрих Лукасевича
или стрелка Пирса.
Штрихом Шеффера двух высказываний х и y
называют новое высказывание, обозначаемое х|у «х не
совместно с у», которое ложно только тогда, когда оба
данные высказывания истинны. Все основные операции
над высказываниями можно выразить через штрих
Шеффера.
x | y x & y x y;
x x | x; x & y ( x | y ) | ( x | y );
x y ( x | x) | ( y | y ).
Лекция 1.4.Нов.Равнос.преобр
10

11.

Таблица истинности x|y
x y x&y x & y x y
0 0 0
1
1
1 0 0
1
1
0 1 0
1
1
1 1 1
1
1
Штрихом Лукасевича (стрелкой Пирса) двух
высказываний х и у называется новое высказывание
x y «ни х, ни у», которое истинно, когда оба данные
высказывания ложны. Операции над высказываниями
можно выразить через штрих Лукасевича.
x y x y; x x x; x y ( x y ) ( x y ); x & y ( x x) ( y y ).
Лекция 1.4.Нов.Равнос.преобр
11

12.

Таблица истинности x y
x
0
1
0
1
y x y x y
0
0
1
0
1
0
1
1
0
1
1
0
Лекция 1.4.Нов.Равнос.преобр
12

13.

Индивидуальное задание 1.
С помощью равносильных преобразований упростить
формулу
и доказать равносильность через таблицу истинности
1. ( x x) y .
9. ( x y )( y y )( y z ) .
2. x y ( x y) & x .
10. x( x y )( x z ) .
3. ( x y ) & ( x y ) .
11. x1x2 x1x2 x3 x1 x1x4 .
4. ( x y) & ( y z ) ( z x) .
12. ( x & y x ) & x xy .
5. x ( x & y )
13. ( xy xyz ) ( x xy y ) .
6. xy xy xy
14. ( yz x )( x y z ) .
7. x ( y z )
15. x y ( z x) & yx .
8. ( x y ) & ( z t )
16. x y ( z x )
Лекция 1.4.Нов.Равнос.преобр
13

14.

p q ( p q) p .
17. ( x & y ) ( y & z ) .
24.
18. ( x & y x ) & x xy .
25. pq pq pq .
19. xyz x yz xyz xy .
26. pq pq pq .
20. pq pr qr q r
27.
(a b c )(bc a ) .
21. pqr pqr pq .
28.
(ab c) (ab a bc) .
22. ( p q)( q p ) .
29.
( x & y ) ( x & z ) & x ( y & x)
23. ( p q ) p q
30.
.
x & ( y x) & ( x y ) & ( x y ) x y
Лекция 1.4.Нов.Равнос.преобр
14