1_Algebra_logiki
.pdf
Функции алгебры логики |
Существенные и фиктивные переменные |
|
||
Существенные и фиктивные переменные |
|
|
||
Cущественная переменная |
|
|
|
|
Булева функция f(x1; : : : ; xi 1; xi; xi+1; : : : ; xn) |
2 |
P2 |
зависит |
|
существенным образом от аргумента |
xi, если существуют такие значения |
|||
1; : : : ; i 1; i+1; : : : ; n переменных x1; : : : ; xi 1; xi+1; : : : ; xn, ÷òî |
|
|||
f( 1; : : : ; i 1; 0; i+1; : : : ; n) 6= f( 1; : : : ; i 1; 1; i+1; : : : ; n): |
||||
В этом случае переменная xi |
называется |
существенной, |
иначе |
|
несущественной или фиктивной. |
|
|
|
|
Равные функции
Две булевы функции f и g называются равными, если одну из них можно получить из другой, добавляя или исключая фиктивные переменные.
Эквивалентные формулы
Формулы называются эквивалентными, если представляемые (реализуемые) ими функции равны.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
9 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Утверждение
Åñëè B0 подформула формулы на эквивалентную подформулу A0
эквивалентную B.
B, то формула
при замене ее вхождения B перейдет в формулу A,
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Утверждение
Åñëè B0 подформула формулы на эквивалентную подформулу A0
эквивалентную B.
B, то формула
при замене |
åå |
вхождения |
B перейдет |
â |
формулу A, |
B = C[B1; : : : ; B0; : : : ; Bn] = C[B1; : : : ; A0; : : : ; Bn] = A åñëè B0 = A0
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
10 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Дистрибутивные законы
3.(x1 _ x2) x3 = (x1 x3) _ (x2 x3)
4.(x1 x2) _ x3 = (x1 _ x3) (x2 _ x3)
5.(x1 x2) x3 = (x1 x3) (x2 x3)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики Тождества алгебры логики
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Дистрибутивные законы |
Правила Де Моргана |
|||
3. (x1 _ x2) x3 = (x1 x3) _ (x2 x3) |
|
|
|
|
6. (x1 _ x2) = x1 x2 |
||||
|
|
|
|
|
4. (x1 x2) _ x3 = (x1 _ x3) (x2 _ x3) |
7. (x1 x2) = x1 _ x2 |
|||
5. (x1 x2) x3 = (x1 x3) (x2 x3) |
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики Тождества алгебры логики
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Дистрибутивные законы |
Правила Де Моргана |
||||
3. (x1 _ x2) x3 = (x1 x3) _ (x2 x3) |
|
|
|
|
|
6. (x1 _ x2) = x1 x2 |
|||||
|
|
|
|
||
4. (x1 x2) _ x3 = (x1 _ x3) (x2 _ x3) |
7. (x1 x2) = x1 _ x2 |
||||
5. |
(x1 x2) x3 = (x1 x3) (x2 x3) |
8. x = x |
|||
|
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики Тождества алгебры логики
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Дистрибутивные законы |
|
Правила Де Моргана |
||||
3. (x1 _ x2) x3 = (x1 x3) _ (x2 x3) |
|
|
|
|
||
6. (x1 _ x2) = x1 x2 |
||||||
|
|
|
|
|||
4. (x1 x2) _ x3 = (x1 _ x3) (x2 _ x3) |
7. (x1 x2) = x1 _ x2 |
|||||
5. |
(x1 x2) x3 = (x1 x3) (x2 |
x3) |
8. x = x |
|||
|
|
|
|
|
||
9. |
x1 _ 1 = 1 |
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |
Функции алгебры логики |
Тождества алгебры логики |
Эквивалентные соотношения (тождества) алгебры логики
Свойство ассоциативности
1. ((x1 x2) x3) = (x1 (x2 x3)) = x1 x2 x3, 2 f_; ^; g
Свойство коммутативности
2. (x1 x2) = (x2 x1), 2 f_; ^; ; "; #; g
Дистрибутивные законы
3.(x1 _ x2) x3 = (x1 x3) _ (x2 x3)
4.(x1 x2) _ x3 = (x1 _ x3) (x2 _ x3)
5.(x1 x2) x3 = (x1 x3) (x2 x3)
Правила Де Моргана
6.(x1 _ x2) = x1 x2
7.(x1 x2) = x1 _ x2
8.x = x
9. x1 _ 1 = 1 |
10. x1 _ 0 = x1 |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
11 / 50 |