Urok_12_Elementy_algebry_logiki

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль (1815-1864), в честь которого эта алгебра названа Булевой алгеброй или Алгеброй высказываний.
Алгебра логики

В алгебре логики высказывания обозначают буквами и называют логическими переменными.
Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0).
0 и 1 называются логическими значениями.
Алгебра логики

Таблица истинности:
Графическое представление
A
B
А&В
Конъюнкция
Конъюнкция – логическая операция, в результате которой истина будет тогда, когда оба исходных высказывания истинны.
Другое название: логическое умножение.
Обозначения: ∧ , ×, •, &, И.

Таблица истинности:
Графическое представление
A
B
АVВ
Дизъюнкция
Дизъюнкция – логическая операция, в результате которой ложь будет тогда, когда оба исходных высказывания ложны.
Другое название: логическое сложение.
Обозначения: V, |, ИЛИ, +.

Таблица истинности:
Графическое представление
A
Ā
Инверсия
Инверсия – логическая операция, в результате которой будет значение противоположное исходному.
Другое название: логическое отрицание.
Обозначения: НЕ, ¬ , ¯ .

Таблица истинности:
Импликация
Импликация – логическая операция, в результате которой истина будет тогда, когда первое высказывание не больше второго.
Обозначения: → , ⇒.

Таблица истинности:
Эквивалентность
Импликация – логическая операция, в результате которой истина будет тогда, когда оба высказывания имеют одинаковую истинность.
Обозначения: ≡, ↔.

Логические выражения
При вычислении логических выражений сначала выполняются действия в скобках.
Приоритет выполнения логических операций:
¬, &, V
(инверсия, затем конъюнкция, затем дизъюнкция).
Примеры:
НЕ (А ИЛИ В)
А & B
A V ¬B & C
Логическое выражение – это выражение содержащее логические переменные, логические значения, логические операции и скобки.

Построение таблиц истинности для логических выражений
подсчитать n - число переменных в выражении
подсчитать общее число логических операций в выражении
установить последовательность выполнения логических операций
определить число столбцов в таблице
заполнить шапку таблицы, включив в неё переменные и операции
определить число строк в таблице без шапки: m =2n
выписать наборы входных переменных
провести заполнение таблицы по столбцам, выполняя логические
операции в соответствии с установленной последовательностью

Построить таблицу истинности для выражения А V A & B
Число переменных: N = 2
Число строк: m = 22 = 4
Приоритет операций: &, V
Число столбцов: 4 (2 переменных и 2 операции)
Пример построения
таблицы истинности
Вывод: А V A & B = A

Переместительный
(коммутативный) закон
Для логического сложения:
Для логического умножения:

Сочетательный
(ассоциативный) закон
Для логического сложения:
Для логического умножения:
При одинаковых знаках скобки можно ставить произвольно или вообще опускать, как в обычной алгебре

Распределительный
(дистрибутивный) закон
Для логического сложения:
Для логического умножения:

Закон двойного отрицания
Двойное отрицание исключает отрицание

Закон исключения третьего
Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе ложно, третьего не дано.

Закон противоречия
Невозможно, чтобы противоречащие высказывания были одновременно истинными.

Закон повторения (равносильности)
Для логического сложения:
Для логического умножения:
Закон означает отсутствие показателей степени

Закон исключения констант
Для логического сложения:
Для логического умножения:

Закон общей инверсии
( законы де Моргана)
Для логического сложения:
Для логического умножения:

Упражнения (самоконтроль)
Постройте таблицы истинности для следующих логических выражений:
1) B v B & A
2) А & B & C
3) А & A
4) A v В