Алгебра логики: основные операции и законы

1. ВЫПОЛНИЛИ:КОЛЕСНИКОВ,ЕМЕЛИН

•ТЕМА: АЛГЕБРА
ЛОГИКИ.
ВЫПОЛНИЛИ:КОЛЕСНИКОВ,ЕМЕЛИН

2.

1. Что такое алгебра логики
Алгебра логики (булева алгебра) — это математическая система, которая
работает с логическими высказываниями, принимающими только два
значения:
Истина — 1 (True)
Ложь — 0 (False)
Основатель — Джордж Буль (1847 г.). Позже Клод Шеннон применил её к
электрическим схемам (1938 г.).

3.

2. Логические операции (подробно)
A
0
Инверсия (НЕ, ¬)
0
1
A∧B
B
0
Дизъюнкция (ИЛИ, ∨)
A
0
1
Импликация (→)
Эквивалентность (
B
A
0
0
1
1
0
1
0
1
0
0
1
1
1
A
B
A→B
0
0
1
0
1
1
1
0
0
1
1
1
A
B
A∨B
0
0
0
0
0
0
1
1
¬A
1
0
)
Дополнительные операции
Штрих Шеффера (И-НЕ, ↑): ¬(A ∧ B)
0
1
1
Стрелка Пирса (ИЛИ-НЕ, ↓): ¬(A ∨ B)
1
0
1
1
1
1
• Исключающее ИЛИ (XOR, ⊕): A ⊕ B = (A ∧
¬B) ∨ (¬A ∧ B)
B
0
Конъюнкция (И, ∧)
1
A

4.

Закон
Формула
Коммутативность
A ∧ B = B ∧ A; A ∨ B = B ∨ A
Ассоциативность
(A ∧ B) ∧ C = A ∧ (B ∧ C)
Дистрибутивность
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
Де Моргана
¬(A ∧ B) = ¬A ∨ ¬B
Идемпотентность
A ∧ A = A; A ∨ A = A
Поглощение
A ∧ (A ∨ B) = A; A ∨ (A ∧ B) = A
Склеивание
(A ∧ B) ∨ (A ∧ ¬B) = A
Двойное отрицание
¬(¬A) = A
Константы
A ∧ 1 = A; A ∨ 0 = A; A ∧ 0 = 0; A ∨ 1 = 1
Исключённого третьего
A ∨ ¬A = 1
Противоречия
A ∧ ¬A = 0

5.

4. Методы упрощения выражений
Аналитический (законы алгебры)
Пример:
¬A ∧ B ∨ A ∧ B
= B ∧ (¬A ∨ A) — вынесли B
=B∧1=B
Карты Карно
Графический метод для функций до 5–6 переменных. Позволяет минимизировать ДНФ/КНФ.
Таблицы истинности
Строится таблица всех комбинаций, затем выражение приводится к СДНФ или СКНФ.

6.

5. Формы представления функций
• ДНФ — дизъюнктивная нормальная форма (сумма произведений)
• КНФ — конъюнктивная нормальная форма (произведение сумм)
• СДНФ — совершенная ДНФ (каждое слагаемое содержит все
переменные)
• СКНФ — совершенная КНФ
Пример СДНФ:
F(A,B) = ¬A∧B ∨ A∧¬B ∨ A∧B

7.

6. Применение
Цифровые схемы: вентили И, ИЛИ, НЕ, триггеры, сумматоры
Программирование: условия if, while, логические операторы &&, |
SQL: WHERE ... AND ... OR ... NOT ...
Поисковые системы: булевы запросы
ИИ: логический вывод, экспертные системы
Криптография и теория кодирования

8.

7. Пример задачи
Упростить: F = ¬(A ∧ B) ∨ A
По закону де Моргана: ¬A ∨ ¬B ∨ A
По закону исключённого третьего: (¬A ∨ A) = 1
Получаем: 1 ∨ ¬B = 1
Функция тождественно истинна.

9.

Спасибо за внимание
7. Пример задачи
Упростить: F = ¬(A ∧ B) ∨ A
1. По закону де Моргана: ¬A ∨ ¬B ∨ A
2. По закону исключённого третьего: (¬A ∨ A) = 1
3. Получаем: 1 ∨ ¬B = 1
Функция тождественно истинна.