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

1.

Михаилиди И.М.
ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

2.

ВЫСКАЗЫВАНИЯ
Высказывание - это повествовательное
предложение, про которое можно всегда
определенно сказать истинно оно или ложно
Какие из этих предложений являются
высказыванием?
1. Идет дождь
2. Два плюс два равно пяти
3. Сумма углов треугольника равна 1800
4. Сегодня четверг
5. Петр Петрович живет в Москве
6. За февралем следует октябрь
7. Москва – столица России
8. Солнце – ближайшая к Земле звезда

3.

ВЫСКАЗЫВАНИЯ
Логические значения – истина, true (1),
ложь, false (0)
Логическое высказывание - утверждение, которому
всегда можно поставить в соответствие одно из
двух логических значений: ложь (0) или истина
(1)
Логическая переменная – абстрактная величина,
которая может принимать логические значения:
истина (1) или ложь (0)

4.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Логические операции - операции над логическими
значениями и переменными, результатом
которых является одно из двух возможных
логических значений: истина (1) или ложь (0).
Логические операции:
─ конъюнкция
Λ (&)
─ дизъюнкция
V
─ инверсия
¬
─ импликация
→
─ эквивалентность ↔ (=)
Значение логической операции вычисляется по
таблице истинности

5.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Инверсия:
F = ¬A
истинна тогда и только тогда, когда операнд
ложен и наоборот
A
F = ¬A
1
0
0
1

6.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Конъюнкция:
F=AΛB
истинна тогда и только тогда, когда истинны оба
операнда
A
B
F =AΛ B
1
1
1
1
0
0
0
1
0
0
0
0
Конъюнкцию также называют логическим умножением

7.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Дизъюнкция:
F=AVB
ложна тогда и только тогда, когда оба ее
операнда ложны
A
B
F=AVB
1
1
1
1
0
1
0
1
1
0
0
0
Дизъюнкцию также называют логическим сложением

8.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Импликация:
F=A→B
ложна тогда и только тогда, когда первый ее
операнд имеет значение истина, а второй - ложь
A
B
F=A→B
1
1
1
1
0
0
0
1
1
0
0
1
Импликацию также называют логическим выводом

9.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Эквивалентность:
F=A↔B
ложна тогда и только тогда, когда один ее
операнд имеет значение истина, а второй - ложь
A
B
F=A↔B
1
1
1
1
0
0
0
1
0
0
0
1

10.

ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ
Логическое выражение – это правильно
построенная последовательность логических
переменных и логических значений,
соединенных знаками логических операций, в
котором таже могут использоваться скобки для
изменения приоритета операций.
Примеры логических выражений:
A V(B Λ D )
¬(1 Λ D ) → Z
(А=C) V A Λ (B V ¬C)

11.

ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ
Индуктивное определение логических выражений
(1) <логическое выражение> : := <логическое значение> |
< логическая переменная> | (< логическое
выражение>) |
< одноместная логическая операция> < логическое
выражение> |
< логическое выражение> < двуместная логическая
операция> < логическое выражение >
(2) < логическое значение > : := 0 |1
(3)< логическая переменная > : := А | B | C | D | E | G | H |
…|Z
(4)< одноместная логическая операция > : := ¬
(5)< двуместная логическая операция > : := V | Λ | → | ↔

12.

ПРИОРИТЕТНОСТЬ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Порядок выполнения логических операций в
логическом выражении:
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения порядка выполнения логических операций
используются скобки
Примеры:
Λ (B V D ) порядка
A Λвыполнения
BVD
Для измененияAуказанного
2
1
2
логических операций
используются1 скобки
¬(D V 1 ) → Z
¬D V 1 → Z
2
1
1
3
2
3

13.

ЗАКОНЫ ЛОГИКИ
Законы де Моргана
¬ (А V B) = ¬А Λ ¬ B
¬ (А Λ B) = ¬А V ¬ B
Закон отрицание отрицания (двойного отрицания)
¬(¬А)=A
Закон исключенного третьего
A V ¬А=1
Закон противоречия (непротиворечия)
A Λ ¬А=0

14.

ЗАКОНЫ ЛОГИКИ
Импликацию можно выразить
через дизъюнкцию и отрицание:
А → В = ¬A v В
Эквивалентность можно выразить
через отрицание, дизъюнкцию и конъюнкцию:
А ↔ В = (¬A v В) Λ (¬ В v А)
Исключающее ИЛИ (ХОR) можно выразить
через отрицание, дизъюнкцию и конъюнкцию :
A ⊻ B = ((A ∧ ¬ B) ⋁ (¬ A ∧ B))

15.

ЗАКОНЫ ЛОГИКИ
Закон дистрибутивности (распределительный) :
для дизъюнкции (логического сложения):
(А V B) Λ C = (A Λ C) V (B Λ C)
для конъюнкции (логического умножения):
(A Λ B) V C = (A V C) Λ (B V C)
Закон идемпотентности (равносильности):
для дизъюнкции:
АVA=A
для конъюнкции:
AΛA=A

16.

ЗАКОНЫ ЛОГИКИ
Закон коммутативности:
для логического сложения:
для логического умножения:
АVB=BVA
A Λ B = B Λ A.
Закон ассоциативности :
для дизъюнкции (логического сложения):
(А V B) V C = A V (B V C)
для конъюнкции (логического умножения):
(A Λ B) Λ C = A Λ (B Λ C)

17.

ЗАКОНЫ ЛОГИКИ
Законы исключения констант в логическом
выражении для дизъюнкции:
АV1=1
АV0=A
для конъюнкции:
AΛ 1 =A
AΛ 0 = 0
Закон поглощения:
для дизъюнкции: А V (A Λ B) = A;
для конъюнкции : A Λ (A V B) = A.

18.

УПРОЩЕНИЕ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ
Законы логики используются для упрощения
логических выражений.
Упрощение логических выражений заключается в
следующием:
─ убрать все скобки;
─ уменьшить количество операций в выражении;
─ уменьшить количество операндов в
выражении.
Например: (A V С Λ A) Λ (BVC) = A Λ B V A ΛC

19.

УПРОЩЕНИЕ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ
Пример 1. Упростить выражение (А V В) Λ (А V С).
Решение:
Раскроем скобки:
(А V В) Λ (А V С) =А Λ (А V С) V В Λ (А V С) =
=A Λ A V A Λ C V B Λ A V B Λ C
По закону идемпотентности A Λ A =A, следовательно:
AΛAVAΛ C V BΛAV BΛ C =AVAΛ C V BΛAV BΛ C
В выражениях А и А Λ C вынесем за скобки А и, используя
свойство 1 V С= 1 и AΛ1 =A получим
A V A Λ C V B Λ A V B Λ C = A Λ (1 V C) V B Λ A V B Λ C =
= A V B Λ A V B Λ C (или тут можно применить сразу
применить закон поглощения: A V A Λ C = A )
Аналогично предыдущему пункту вынесем за скобки А (или
применим закон поглощения A V B Λ A = A).