Алгебра логики (булева алгебра, алгебра высказываний) – это математический аппарат, с помощью которого записывают (кодируют), упрощают, вычисляют и преобразовывают логические высказывания. Система обозначений и правил, применимая ко всевозможным объектам, от чисел до предложений, и позволяющая закодировать высказывания с помощью символов своего языка, а затем манипулировать ими. Джордж Буль ( )

ПРОСТОЕ высказывание (логическая переменная) - ни одна его часть сама не является высказыванием СЛОЖНОЕ высказывание (логическая функция) Состоит из нескольких простых, соединенных между собой с помощью логических операций это форма мышления, выраженная повествовательным предложением, в которой что-либо утверждается или отрицается о предметах, их свойствах или отношениях

Основные операции булевой алгебры Конъюнкция – И, логическое умножение Дизъюнкция – ИЛИ, логическое сложение Отрицание - НЕ Любое сложное высказывание можно записать с помощью основных логических операций И, ИЛИ, НЕ С помощью логических схем И, ИЛИ, НЕ можно реализовать любую логическую функцию, описывающую работу различных устройств компьютера.

Соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО Обозначение: неА, А, А А А F(A)= А Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Конъюнкция истинна тогда и только тогда, когда оба высказывания истинны Соответствует союзу И ( в естественном языке : и А, и В Как А, так и В; А вместе с В и др.) Обозначение:, ·, x, И, AND, АВF F(A,B)=A&B Пересечение А В А В

Дизъюнкция ложна тогда и только тогда, когда оба высказывания ложны Соответствует союзу ИЛИ Обозначение: +, ИЛИ, OR, АВF F(A,B)=A B А В Объединение А В

Дизъюнкция ложна тогда и только тогда, когда оба высказывания одновременно ложны или истинны Соответствует разделяющему ИЛИ ( в естественном языке : ЛИБО) Обозначение: ХOR АВF F(A,B)=A B А В А\В В\А

Соответствует речевому обороту ЕСЛИ… ТО ( в естественном языке : если А, то В; В, если А; В необходимо для А; А достаточно для В; Все А есть В и др. Обозначение:, АВF F(A,B)=A B Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно

Соответствует речевым оборотам ЭКВИВАЛЕНТНО; РАВНОЗНАЧНО, НЕОБХОДИМО И ДОСТАТОЧНО ДЛЯ; ТОГДА И ТОЛЬКО ТОГДА, КОГДА Обозначение: ; ; АВF F(A,B)=A B Эквиваленция истинна тогда и только тогда, когда оба высказывания одновременно либо истинны, либо ложны.

Это - таблица, в которой перечислены все возможные значения входящих логических переменных и соответствующие им значения функции. АВА и ВА или ВНе А

Построение таблиц истинности по булеву выражению: 1)Определить число переменных n. 2)Определить число строк по формуле q=2 n. 3) Записать все возможные значения переменных 4) Определить количество логических операций и их порядок. 5) Количество столбцов в таблице истинности равно числу переменных n плюс количество логических операций. 6) Записать логические операции в таблицу истинности и определить для каждой значение.

1) операция в скобках; 2) отрицание; 3) логическое умножение; 4) логическое сложение; 5) импликация; 6) эквиваленция.

Логического сложения 1)А+0=А 2)А+1=1 3)А+А=А 4)А+ А=1 (из двух противоречивых высказываний хотя бы одно истинно) Логического умножения 1) А·0=0 2) А·1=А 3) А·А=А 4) А· А=0 (невозможно, чтобы одновременно два противоположных высказывания были истинны) ТОЖДЕСТВА 5) ( А) = А (Двойное отрицание исключает отрицание)

1)А+В=В+А 2) (А+В)+С=А+(В+С) 3) (А+В)·С=АС+ВС 4) (А+В)= А · В 1)А·В=В·А 2) (А·В)·С=А·(В·С) 3) АВ+С=(А+С)(В+С) 4) (АВ)= А+ В 5)А В = В А = А + В 6) А В = АВ + (АВ) = ( А + В)(А + В) Переместительный закон Сочетательный закон Распределительный закон Закон де Моргана (закон отрицания)

1) 1+А·0 2) Х·Х·1 3) А или (неА и В) 4) F = неХ и (не(неY или Х)) 5) F = не(Х и (неХ и неY)) 6) А и (А или В) и (В или неВ) 7) (А или В) и (неВ или А) и (неС или В) Проверь себя

Задача. Даны 3 посылки: 1)Если Иван – брат Марьи или Иван – сын Марьи, то Иван и Марья – родственники. 2)Иван и Марья – родственники. 3)Иван – не сын Марьи. Можно ли вывести следствие, что «Иван – брат Марьи»?

Вводим обозначения: А – Иван – брат Марьи. В – Иван – сын Марьи. С – Иван и Марья – родственники. Запишем символически: 1)А xor В С 2)С 3) В Общая формула: (((А xor B) C) and C and B) A

Решаем задачу с помощью таблицы истинности. Число строк равно: (титул), число столбцов равно: (число операций) (((AxorB) C)and C and B) D A ((AxorB) C) and C (AxorB) C A xorB В СВ А

Формула называется тождественно- истинной, если при любых комбинациях значений для входящих в нее переменных принимает значение «истина». Вывод. Из данных 3-х посылок не следует с необходимостью заключение, что «Иван – брат Марьи». Иван может быть племянником или отцом Марьи, или дядей и т.п.

Проверь себя Назад Х 3. А+В 4. ХУ А 7. А( С + В)