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

1. Информатика

Лекция 5

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

Кроме обычной алгебры существует специальная,
основы которой были заложены английским
математиком XIX века Дж. Булем. Эта алгебра
занимается так называемым исчислением высказываний.
Ее особенностью является применимость для описания
работы так называемых дискретных устройств, к числу
которых принадлежит целый класс устройств
автоматики и вычислительной техники.
При этом сама алгебра выступает в качестве модели
устройства. Это означает, что работа произвольного
устройства указанного типа может быть лишь в каком-то
отношении описана с помощью построений этой
алгебры.
2

3.

Среди задач, для решения которых привлекают
компьютер, немало таких, которые принято называть
логическими.
Все знают шуточную задачу о перевозке козла, волка и
капусты с одного берега на другой. В этой задаче
властвует не арифметика, а умение логически
рассуждать. Человек прибегает к логике, когда
составляет расписания, распутывает противоречивые
показания или составляет инструкции.
В логических задачах исходными данными являются не
только и не столько числа, а сложные логические
суждения, подчас весьма запутанные. Эти суждения и
связи между ними бывают иногда столь противоречивы,
что для их разрешения привлекают вычислительные
машины.
3

4.

Аристотель основатель Формальной логики.
Описал основные формы абстрактного
мышления:
понятие, высказывание, умозаключение.
(384-328 гг. до н.э.)
Понятие — форма мышления, которая выделяет существенные
признаки предмета (класса предметов), позволяющие отличать его
от других.
Примеры: проливной дождь, круглый шар, новый компьютер.

5. Высказывание

(суждение/утверждение) — это
формулировка своего понимания окр. мира.
Высказывание
является
повествовательным
предложением, в котором что-то утверждается или
отрицается.
Высказывание может быть истинным или ложным.
Истинное высказывание - правильно отражает
реальную действительность.
Ложное - противоречит действительности.
Примеры: «У прямоугольника все углы прямые» (Истинное
высказывание).
«Компьютер был изобретен в середине XIX века (Ложное
высказывание).
5

6. Умозаключение

— форма мышления, с
помощью которого из одного или нескольких
суждений может быть получено новое
суждение.
Пример: Из высказывания:
«Равнобедренный треугольник, у кот. все углы равны»
можно путём умозаключений получить другое
высказывание
«Этот треугольник равносторонний».
6

7.

ВЫСКАЗЫВАНИЯ
Простые
(содержат только одну простую
мысль)
«Петров – врач»
«Петров – шахматист»
Составные
(содержат несколько простых
высказываний
соединённых логическими связками:
«и», «или», «не»,
«если …то», «тогда и только тогда»)
«Петров - врач и шахматист»
«Петров – не врач и не шахматист»
В алгебре простые высказывания обозначаются буквами латинского алфавита и
наз. логическими переменными.
Обозначив А = «Петров – врач»,
В = «Петров – шахматист», получим логические выражения
(функции):
F(A,B) = А и В («Петров - врач и шахматист»)
F(A,B) = не А и не В («Петров – не врач и не шахматист»)

8.

ЛОГИЧЕСКИЕ ФУНКЦИИ
Значение логической функции можно определить с помощью
специальной
таблицы
–
таблицы
истинности,
в которой перечисляются все комбинации значений логических
переменных, входящих в выражение, и определяются значения
логической функции.
А
В
F (A,B)=А и В
0
0
0
0
1
0
1
0
0
1
1
1

9. ТАБЛИЦЫ ИСТИННОСТИ

Таблица истинности – это таблица, с помощью которой
определяются значения логических выражений.
ПОРЯДОК ВЫПОЛНЕНИЯ ОПЕРАЦИЙ В ЛОГИЧЕСКИХ
ВЫРАЖЕНИЯХ
действия в скобках; инверсия (¬), конъюнкция (^),
дизъюнкция (v), импликация (→), эквивалентность(↔).

10. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

1. Отрицание (инверсия) «НЕ» ¬
от лат. inversio — переворачиваю,
2. Логич. сложение (дизьюнкция) «ИЛИ» +, v
от лат. disjunctio - различаю
3. Логич. умножение (конъюнкция) «И» ∙ , х , ^, &
от лат. conjunctio – соединяю
А
¬А
0
1
1
0
А
В
А+В
0
0
0
1
0
1
0
1
1
1
1
1
А
В
А∙В
0
0
0
1
0
0
0
1
0
1
1
1

11. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

4. Логическое следование (импликация) «ЕСЛИ
… ТО» →
от лат. implicatio — тесно связываю,
Из таблицы видно : Импликация ложна,
если из истины следует ложь,
и истинна - во всех остальных случаях.
5. Логическое равенство
(эквивалентность/равнозначность)
«ТОГДА И ТОЛЬКО ТОГДА, КОГДА…»
«НЕОБХОДИМО И ДОСТАТОЧНО » ≡ ↔
от лат. equivalents — равноценное
Из таблицы видно : Эквивалентность истинна,
если обе переменные одновременно либо истинны,
либо ложны.
А
В
А→В
0
0
1
0
1
1
1
0
0
1
1
1
А
В
А↔В
0
0
1
0
1
0
1
0
0
1
1
1

12. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

6. Строгая дизъюнкция.
Исключающее «ИЛИ»
Этой логической операции соответствует
логическая связка “либо ... либо”.
А
В
А xor
В
0
0
0
0
1
1
1
0
1
1
1
0

13.

13

14.

Законы алгебры логики
Закон противоречия говорит о том, что никакое
предложение не может быть истинно одновременно
со своим отрицанием. “Я студент” и “Я не студент”.
14

15.

Законы алгебры логики
Закон исключенного третьего говорит о том, что для
каждого высказывания имеются лишь две возможности:
это высказывание либо истинно либо ложно. Третьего
не дано. “Сегодня я получу 5 либо не получу”. Истинно
либо суждение, либо его отрицание.
15

16.

Законы алгебры логики
Закон двойного отрицания. Отрицать отрицание
какого-нибудь высказывания - то же, что утверждать это
высказывание.
16

17. Законы алгебры логики

Законы идемпотентности. В алгебре логики нет
показателей степеней и коэффициентов.
Конъюнкция одинаковых “сомножителей”
равносильна одному из них.
17

18. Законы алгебры логики

Законы коммутативности и ассоциативности.
Конъюнкция и дизъюнкция аналогичны одноименным
знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое
сложение и умножение равноправны по отношению к
дистрибутивности: не только конъюнкция
дистрибутивна относительно дизъюнкции, но и
дизъюнкция дистрибутивна относительно конъюнкции.
18

19. Законы алгебры логики

В отличие от сложения и умножения чисел логическое
сложение и умножение равноправны по отношению к
дистрибутивности: не только конъюнкция
дистрибутивна относительно дизъюнкции, но и
дизъюнкция дистрибутивна относительно конъюнкции.
19

20. Логические элементы

Современный этап промышленного развития
характеризуется тем, что разработчики систем
автоматики и вычислительной техники стремятся
использовать функциональные модули, выполняющие
определённые схемные задачи: логические
преобразования, хранение информации и т.д.
Конкретный вид электрической схемы, использованной
для реализации заданной логической функции, как
правило, не имеет существенного значения.
Техническое устройство, реализующее логическую
функцию, может рассматриваться просто как
логический элемент, внутренняя структура которого не
конкретизируется.
20

21. Логический элемент НЕ

21

22. Логический элемент ИЛИ

предназначен для “вычисления”
значения логического сложения.
Работа этого логического
элемента эквивалентна
проверке составного условия со
служебным словом “или”.
Алгоритм работы логического
элемента “или” записывается
следующим образом: “Если А=1
или В=1, то f(А,В)=1, иначе
f(А,В)=0”.
22

23. Логический элемент И

предназначен для
“вычисления” значения
логического умножения.
Работа этого логического
элемента эквивалентна
проверке составного условия
со служебным словом “и”.
Алгоритм работы
логического элемента “и”
записывается следующим
образом: “Если А=1 и В=1,
то f(А,В)=1, иначе f(А,В)=0”.
23

24. Цепочки элементов

Сигналы, вырабатываемые одним логическим
элементом, можно подавать на вход другого
элемента - это даёт возможность образовывать
цепочки из отдельных логических элементов.
24

25. Элементы И-НЕ и ИЛИ-НЕ

Связь операций И-НЕ и
ИЛИ-НЕ с основными
операциями алгебры
логики устанавливается
законами, открытыми
английским математиком
Августусом де Морганом
(1806-1871) и поэтому
носящими его имя.
25

26. Построение комбинационных схем

26