ВУЗ:
Составители:
17
• отрицание. Операцию отрицания называют инверсией или дополнением. Для ее
обозначения используют черту над соответствующем выражением. Постулаты,
определяющие операцию отрицания, приведены в таблице 2.2.
Для обозначения эквивалентности логических выражений используется знак
равенства «=».
Таблица 2.1 Таблица 2.2
Операции дизъюнкции и конъюнкции. Операция инверсии.
A B F = A+B
F = A
⋅
B
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1
2.2. Основные аксиомы и законы алгебры-логики
Для рассмотренных логических операций справедлив ряд аксиом (тождеств) и
законов, основные из которых даны в таблице 2.3. Следует отметить, что
алгебраические выражения тождеств и законов в таблице 2.3. заданы парами, и
взаимной заменой операций И, ИЛИ и символов 0 и 1 из одного выражения
получается другое. Используя данные тождества и законы, можно получать новые
логические выражения, а также доказывать справедливость тех или иных законов на
основании других.
Таблица 2.3
Основные аксиомы и законы алгебры-логики
1+A = 1.
0⋅A = 0.
(2.1)
0+A = A
1
⋅
A = A
(2.2)
A+A = A
A
⋅
A = A
(2.3)
A+
A
= 1
A⋅
A
= 0
(2.4)
Аксиомы (тождества)
AA =
(2.5)
Законы коммутативности
A+B = B+A
A
⋅
B = B
⋅
A
(2.6)
Законы ассоциативности
A+B+C = A+(B+C)
A
⋅
B
⋅
C = A
⋅
(B
⋅
C)
(2.7)
Законы дистрибутивности
A(B+C) = (A
⋅
B)+(A
⋅
C)
A+(B
⋅
C) = (A+B)
⋅
(A+C)
(2.8)
Законы дуальности (теоремы
Де-Моргана)
B
A
B
A
⋅=+
B
A
B
A
+=⋅
(2.9)
Законы поглощения
A+A
⋅
B = A
A
⋅
(A+B) = A.
(2.10)
Например, с помощью второго закона дистрибутивности (2.8) и тождества (2.4)
получаем соотношение:
A
F =
A
0 1
1 0
18
BABAAABAA +=+⋅+=⋅+ )()( (2.11)
Используя первый закон дистрибутивности (2.8), тождества (2.1), (2.2) и закон
коммутативности (2.6), получаем доказательство справедливости второго закона
поглощения (2.10)
ABAABAABAABAA
=
+
=
+
=
+
=
+
)1()( .
Применение данных тождеств и законов позволяет производить упрощение
логических функций, т.е. находить для них выражения, имеющие наиболее простую
форму.
Используя законы ассоциативности, любую логическую функцию многих
переменных (k >2) можно представить в виде комбинации функции двух переменных.
Полный набор
162
2
2
= логических функций двух переменных дан в таблице 2.4.
Каждая функция обозначает одну из 16 возможных логических операций над двумя
переменными А, В и имеет собственное название и условное обозначение.
Таблица 2.4
Полный набор логических функций для двух переменных
A 0 0 1 1
B 0 1 0 1
Условное обозначение и
алгебраическое выражение
Название функции
F
0
0 0 0 0 F
0
= 0 Постоянный ноль
F
1
0 0 0 1 F
1
= AB Конъюнкция
F
2
0 0 1 0
BABAF =→=
2
Запрет
F
3
0 0 1 1 F
3
= A Тождественность А
F
4
0 1 0 0
BAABF =→=
4
Запрет
F
5
0 1 0 1 F
5
= B Тождественность В
F
6
0 1 1 0
BABABAF +=⊕=
6
Исключительное ИЛИ
(неравнозначность)
F
7
0 1 1 1 F
7
= A+B Дизъюнкция
F
8
1 0 0 0
BABAF +=↓=
8
Стрелка Пирса
(ИЛИ-НЕ)
F
9
1 0 0 1
BAABBAF +=⊕=
9
Равнозначность
(исключительное
ИЛИ-НЕ)
F
10
1 0 1 0
BF =
10
Инверсия В
F
11
1 0 1 1
BAABF +=→=
11
Импликация от В к А
F
12
1 1 0 0
AF =
12
Инверсия А
F
13
1 1 0 1
BABAF +=→=
13
Импликация от А к В
F
14
1 1 1 0
ABBAF == /
14
Штрих Шеффера
(И-НЕ)
F
15
1 1 1 1 F
15
= 1 Постоянная единица
• отрицание. Операцию отрицания называют инверсией или дополнением. Для ее
обозначения используют черту над соответствующем выражением. Постулаты,
A + A ⋅ B = ( A + A ) ⋅ ( A + B) = A + B (2.11)
определяющие операцию отрицания, приведены в таблице 2.2. Используя первый закон дистрибутивности (2.8), тождества (2.1), (2.2) и закон
Для обозначения эквивалентности логических выражений используется знак коммутативности (2.6), получаем доказательство справедливости второго закона
равенства «=». поглощения (2.10)
Таблица 2.1 Таблица 2.2 A( A + B) = AA + AB = A + AB = A(1 + B) = A .
Операции дизъюнкции и конъюнкции. Операция инверсии. Применение данных тождеств и законов позволяет производить упрощение
A B F = A+B F = A⋅B A F= A логических функций, т.е. находить для них выражения, имеющие наиболее простую
0 0 0 0 0 1 форму.
0 1 1 0 1 0 Используя законы ассоциативности, любую логическую функцию многих
1 0 1 0 переменных (k >2) можно представить в виде комбинации функции двух переменных.
22
1 1 1 1 Полный набор 2 = 16 логических функций двух переменных дан в таблице 2.4.
Каждая функция обозначает одну из 16 возможных логических операций над двумя
2.2. Основные аксиомы и законы алгебры-логики переменными А, В и имеет собственное название и условное обозначение.
Для рассмотренных логических операций справедлив ряд аксиом (тождеств) и
Таблица 2.4
законов, основные из которых даны в таблице 2.3. Следует отметить, что
Полный набор логических функций для двух переменных
алгебраические выражения тождеств и законов в таблице 2.3. заданы парами, и
взаимной заменой операций И, ИЛИ и символов 0 и 1 из одного выражения A 0 0 1 1 Условное обозначение и
Название функции
получается другое. Используя данные тождества и законы, можно получать новые B 0 1 0 1 алгебраическое выражение
логические выражения, а также доказывать справедливость тех или иных законов на F0 0 0 0 0 F0 = 0 Постоянный ноль
основании других.
F1 0 0 0 1 F1 = AB Конъюнкция
Таблица 2.3
Основные аксиомы и законы алгебры-логики F2 0 0 1 0 F2 = A → B = AB Запрет
1+A = 1. F3 0 0 1 1 F3 = A Тождественность А
(2.1)
0⋅A = 0.
0+A = A F4 0 1 0 0 F4 = B → A = A B Запрет
(2.2)
1⋅A = A F5 0 1 0 1 F5 = B Тождественность В
Аксиомы (тождества) A+A = A Исключительное ИЛИ
(2.3) F6 0 1 1 0 F6 = A ⊕ B = AB + A B
A⋅ A = A (неравнозначность)
A+ A = 1 F7 0 1 1 1 F7 = A+B Дизъюнкция
(2.4)
A⋅ A = 0 Стрелка Пирса
(2.5)
F8 1 0 0 0 F8 = A ↓ B = A + B (ИЛИ-НЕ)
A=A
A+B = B+A Равнозначность
Законы коммутативности (2.6) F9 1 0 0 1 F9 = A ⊕ B = AB + A B (исключительное
A⋅B = B⋅A
A+B+C = A+(B+C) ИЛИ-НЕ)
Законы ассоциативности (2.7) F10 1 0 1 0 F10 = B Инверсия В
A⋅B⋅C = A⋅(B⋅C)
A(B+C) = (A⋅B)+(A⋅C) F11 1 0 1 1 F11 = B → A = A + B Импликация от В к А
Законы дистрибутивности (2.8)
A+(B⋅C) = (A+B)⋅(A+C)
F12 1 1 0 0 F12 = A Инверсия А
Законы дуальности (теоремы A+ B = A ⋅B (2.9) F13 1 1 0 1 F13 = A → B = A + B Импликация от А к В
Де-Моргана)
A⋅ B = A + B Штрих Шеффера
A+A⋅B = A F14 1 1 1 0 F14 = A / B = AB (И-НЕ)
Законы поглощения (2.10)
A⋅(A+B) = A. F15 1 1 1 1 F15 = 1 Постоянная единица
Например, с помощью второго закона дистрибутивности (2.8) и тождества (2.4)
получаем соотношение:
17 18
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
