Логические основы компьютеров

1. Логические основы компьютеров

Вопрос 1. Введение в алгебру логики
Вопрос 2. Элементарные булевы
функции
Вопрос 3. Основные законы логики
1

2. Вопрос 1. Введение в алгебру логики

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

3.

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

4.

Булева алгебра применяется в
компьютерной технике. Здесь значок 0
означает одно напряжение между
контактами схемы (скажем, 0 вольт), а
значок 1 - другое (скажем, +5 вольт).
4

5.

Второй вариант применения булевой
алгебры - логические рассуждения.
Здесь два объекта интерпретируются
как истина (будем обозначать как true)
и ложь (будем обозначать как false).
Будем называть символы true и false
булевыми величинами, а
переменные, которые их обозначают булевыми переменными.
5

6. Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или

ложно.
Высказывание или нет?
Сейчас
идет дождь.
Утки летят на север.
У квадрата – 4 стороны и все разные.
Красиво!
Который час?
6

7. Обозначение высказываний

A – Сейчас идет дождь.
B – Форточка открыта.
!
простые высказывания
(элементарные)
Любое высказывание может быть ложно (0)
или истинно (1).
Составные высказывания строятся из простых с
помощью логических связок (операций) «и», «или»,
«не», «если … то», «тогда и только тогда» и др.
AиB
A или не B
если A, то B
не A и B
A тогда и только
тогда, когда B
Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Сейчас нет дождя и форточка открыта.
Дождь идет тогда и только тогда, когда
открыта форточка.
7

8. Вопрос 2. Элементарные булевы функции

Двоичной т.е. булевой функцией от
набора двоичных переменных называется
функция, результатом которой могут быть только
значения 0 и 1.
Любую булеву функцию можно задать с помощью
таблицы, в которой всем возможным наборам
значений двоичных переменных сопоставлены
соответствующие им значения функции. Такая
таблица называется таблицей истинности
8

9.

В естественном языке: соответствует словам
"неверно, что..." и частице "не"
9

10.

10

11. В естественном языке: соответствует союзу "и”

В естественном языке: соответствует
союзу "и”
1) 10 делится на 2 (A – и.). 5 больше 3 (B – и.).
10 делится на 2 и 5 больше 3 (A & B - истина).
2) 10 не делится на 2 (A – ложь).
5 больше 3 (B - истина).
10 не делится на 2 и 5 больше 3 (A & B - ложь).
3) 10 делится на 2 (A - и). 5 не больше 3 (B - л).
10 делится на 2 и 5 не больше 3 (A & B – ложь).
4) 10 не делится на 2 (A - л). 5 не больше 3 (B - л).
10 делится на 2 и 5 больше 3 (A B - л).
11

12.

12

13. В естественном языке: соответствует союзу "или"

В естественном языке: соответствует
союзу "или"
Например, рассмотрим составное
высказывание « 2*2=4 или 3*3=10».
Первое простое высказывание истинно
(А=1), а второе высказывание ложно
(В=0), по таблице определяем, что
логическая функция принимает
значение истина (F=1), то есть данное
составное высказывание истинно.
13

14.

Примеры:
10 делится на 2 (A - и). 5 больше 3 (B - и).
10 делится на 2 или 5 больше 3 (A ИЛИ B истина).
10 не делится на 2 (A - л). 5 больше 3 (B - и).
10 не делится на 2 или 5 больше 3 (A ИЛИ B истина).
10 не делится на 2 (A - л). 5 не больше 3 (B л).
10 не делится на 2 или 5 не больше 3 (A ИЛИ
B - ложь).
14

15.

Кроме базовых логических функций
используются и другие, например
функции логического следования
(импликации) логического равенства
(эквивалентности).
15

16. Импликация (логическое следование)

«Если Вася идет гулять, то
Маша сидит дома».
A – «Вася идет гулять».
B – «Маша сидит дома».
A B 1
?
А если Вася не идет
гулять?
Маша может не сидеть дома
(пойти гулять) (B=0),
а может сидеть дома (B=1)
A
B А B
0
0
1
0
1
1
1
0
0
1
1
1
16

17. В естественном языке: соответствует обороту "если ..., то ..."

В естественном языке: соответствует
обороту "если ..., то ..."
Примеры:
Данный четырёхугольник — квадрат (A - и). Около данного
четырёхугольника можно описать окружность (B - и).
Если данный четырёхугольник квадрат, то около него можно
описать окружность (A B - и).
Данный четырёхугольник — не квадрат (A - л). Около данного
четырёхугольника можно описать окружность (B - и). Если
данный четырёхугольник не квадрат, то около него можно
описать окружность (A B - и).
Данный четырёхугольник — квадрат (A - и). Около данного
четырёхугольника нельзя описать окружность (B - л). Если
данный четырёхугольник квадрат, то около него можно описать
окружность (A B - л).
Данный четырёхугольник — не квадрат (A - л). Около данного
четырёхугольника нельзя описать окружность (B - л). Если
данный четырёхугольник не квадрат, то около него нельзя
описать окружность (A B - и).
17

18. Логическое равенство (эквивалентность)

Логическое равенство это
логическая функция от двух
переменных, которая
принимает истинное значение
тогда и только тогда, когда оба
высказывания одновременно
либо ложны либо истинны.
Обозначение эквивалентности
A~B
А
В
A
0
0
1
1
B
0
1
0
1
А B
1
0
0
1
18

19. Вопрос 3. Основные законы логики

A A
Вопрос 3. Основные законы логики
Для преобразования логических
выражений используют законы
алгебры логики:
Закон тождества
А= А
Закон непротиворечия
Закон исключенного третьего
19

20.

20

21. Таблицы истинности

Таблица истинности - это один из
способов вычислений в формальной
логике. Таблица позволяет
определить истинность какогонибудь сложного логического
высказывания по истинности его
фрагментов.
21

22.

22

23.

23