Алгебра логики

Булева алгебра
Двоичное кодирование – все виды информации кодируются с помощью 0 и 1.
Задача – разработать оптимальные правила обработки таких данных.
Джордж Буль разработал основы алгебры,
в которой используются только 0 и 1
(алгебра логики, булева алгебра).
Почему "логика"?
Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Алгебра высказываний (логики) – математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно сказать истинно оно или ложно.
Например:
6 – четное число -это истинное высказывание
Число 6 больше 8 -это ложное высказывание

Сложные высказывания составляются из простых высказываний, соединенных логическими связками: «и», «или», «не» и т.д.
6 – четное число и число 6 больше 8 -это сложное высказывание
А и В = А * В = А ∧ В
Над логическим высказыванием в компьютере выполняется та или иная логическая операция.
Существует 8 основных логических операций:
Инверсия;
Конъюнкция;
Дизъюнкция;
Штрих Шеффера;
Стрелка Пирса;
Импликация;
Сложение по модулю 2 (Исключающее ИЛИ);
Эквиваленция.

Отрицание (выражается словом «НЕ» Читается «неверно, что x») или инверсия.
Обозначается чертой над высказыванием.
Функция, реализующая эту операцию,
записывается в виде
Эта функция истинна, если переменная (высказывание) ложна.
Таблица истинности для данной операции:
Устройство, реализующее эту операцию
на схемах, называется инвертором и
обозначается следующим образом

Конъюнкция (выражается словом «И») или логическое умножение (Читается «x и y»)
Обозначается *, ^, &(амперсенд).
Функция, реализующая эту операцию, записывается в виде
Эта функция истинна тогда и только тогда, когда все переменные (высказывания) истинны одновременно.
Таблица истинности для данной операции:
Устройство, реализующее эту операцию на схемах, называется конъюнктором и обозначается следующим образом:
Y = Х1 * X2 или Y = X1 ^ X2 или Y = X1 & X2.

Дизъюнкция (выражается словом «ИЛИ») логическое сложение (Читается «x или y»)
Обозначается +, v.
Функция, реализующая эту операцию, записывается в виде
Эта функция истинна тогда и только тогда, когда хотя бы одна переменная (высказывание) истинна или истинны обе переменные (высказывания) одновременно.
Составим таблицу истинности для данной операции:
Устройство, реализующее эту операцию на схемах, называется дизъюнктором и обозначается следующим образом:
Y = Х1 + X2 или Y = X1 v X2.

Импликация ( «если…то», «из…следует»)
Читается «из x следует y» или «если x, то y»
Обозначается знаком ?
Функция, реализующая эту операцию, записывается в виде.
Импликацию можно выразить через дизъюнкцию и отрицание
Функция ложна тогда и только тогда, когда Х1 истинно, а Х2 ложно.
Таблица истинности для данной операции:
Y = X1 ? X2.

Эквиваленция
(Читается «для того, чтобы x, необходимо и достаточно, чтобы y» или «x тогда и только тогда, когда y»)
Обозначается знаком ↔ или ~.
Функция, реализующая эту операцию, записывается в виде
Функция истинна тогда и только тогда,
когда значения Х1 и Х2 совпадают.
Таблица истинности для данной операции:
Y = X1 ↔ X2

Алгебра логики используется при построении основных узлов ЭВМ.
При изучении работы различных устройств компьютера приходится рассматривать такие
его сложные элементы, в которых реализуются сложные логические выражения.
Поэтому необходимо научиться определять результат этих выражений, то есть строить
для них таблицы истинности.
Построение таблицы истинности
Подсчитать кол-во переменных в выражении =n.
Число строк в таблице = 2n + заголовок.
Кол-во столбцов = n + кол-во операций.
Ввести названия столбцов: сначала переменные, затем операции в соответствии с приоритетом.
Ввести наборы значений переменных.
Вычислить значения операций для всех наборов переменных.

ПРИМЕР №1
Кол-во строк таблицы (кол-во сочетаний из 0 и 1) определяется по формуле 2п =22 = 4 , где п-число переменных в формуле две переменные A и B – два простых высказывания.
Кол-во столбцов: 2 переменные + 5 лог операций =7

ПРИМЕР №2 -Выполнить самостоятельно

Равносильные логические выражения
Равносильные логические выражения - у которых последние столбцы таблиц истинности совпадают. Обозначают “=“. А*В = В*А
Докажите равносильность выражений:
Таблица истинности для
Таблица истинности для
ПРИМЕР №3

Решение логических
задач с помощью ТИ

Задание. Решить логическую задачу с помощью таблицы истинности
На вопрос, кто из трёх учащихся изучал информатику, был получен ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто из учащихся изучал информатику?

Законы и тождества алгебры логики