Презентации лекций / Презентация лекции 3 ДМ 20
.pdf
Пример
Сравнить функции, заданные формулами:
и
2)
и 
1
2
3
21
1
2
3
22
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Основныеравносильности: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
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 ; |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||
|
дистрибутивные законы |
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
7. |
x x x; |
|
|
|
|
|
|
8. |
x x x; |
|
|
|
законы идемпотентности |
|
|||||||||||||||||||||||||||||||
9. |
|
|
|
|
|
|
|
|
|
|
; |
|
|
|
10. |
|
|
|
|
|
|
|
; |
|
|
|
|
|
|
|
|
|
|||||||||||||
x y |
x |
|
y |
|
|
|
x y |
x |
y |
|
|
|
|
|
законы де Моргана |
|
|||||||||||||||||||||||||||||
11. |
x 0 x ; |
|
|
12. |
x 1 x ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
законы нуля |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13. |
x 0 0; |
|
|
14. |
x 1 1; |
|
|
|
|
|
законы единицы |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
15. |
x x y x; |
|
|
16. |
x x y x; |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
законы поглощения |
|
|||||||||||||||||||||||||||||||||||||||
17.x x 0; |
|
|
18. |
x x 1; |
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
законы отрицания |
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20. ̅= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
19. |
x |
x. |
|
|
закон двойного отрицания |
|
|
|
|
закон Порецкого |
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23
Важные обозначения:
1
2
3
24
Пример
Упроститьформулу:
1
2
3
25
Переменная xi называется фиктивной переменной функции f x1,...,xn ,
если на всех наборах 1,..., i 1, i 1,..., n значений переменных x1,...,xi 1,xi 1,...,xn выполняются равенства
f ( 1,..., i 1,0, i 1,... n ) f ( 1,..., i 1,1, i 1,... n ).
В противном случае переменная xi называется существенной.
Действуемвсоответствиисопределением:
Сравниваем значения функции на всевозможных парах наборов, отличающихся друг от друга значением переменной
на наборах каждой такой пары
значения функции одинаковы
есть по крайней мере одна пара, на наборах которой значения функции различны
переменная
фиктивная
переменная
существенная
1
2
3
26
Пример
Определить, какиеиз переменных функции существенные, а какие фиктивные:
1)
2)
.
1
2
3
27
Операцияудаления (введения) фиктивной переменной
|
Пусть для функции |
f x1,x2 ,...,xn |
переменная xi является фиктивной. |
|
Возьмем таблицу истинности функции f . Вычеркнем из нее все строки, в которых |
||
|
xi 1, а также вычеркнем столбец переменной xi . Полученная таким образом |
||
|
таблицабудетзадаватьнекоторуюфункцию |
g x1,...,xi 1,xi 1,...,xn ,причемналюбом |
|
. |
наборе 1,..., i 1, i , i 1,..., n значенийпеременных x1,...,xi 1,xi ,xi 1,...,xn дляфункций |
||
|
f и g выполнено равенство |
f 1,..., i 1, i , i 1,..., n g 1,..., i 1, i 1,..., n . Про |
|
|
функцию g говорят, что она получена из функции f путем удаления фиктивной |
||
|
переменной, а про функцию |
f говорят, что она получена из g путем введения |
|
|
фиктивной переменной. |
|
|
1
2
3
28