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

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

• Логические выражения и операции
• Диаграммы
• Преобразование логических выражений
• Синтез логических выражений
• Логические элементы компьютера
• Логические задачи

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

Тема 1. Логические выражения и операции

Булева алгебра

Двоичное кодирование – все виды информации кодируются с помощью 0 и 1.

Задача – разработать оптимальные правила обработки таких данных.

Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).

Почему "логика"? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Логические высказывания

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

Высказывание или нет ?

• Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?
• Сейчас идет дождь.
• Жирафы летят на север.
• История – интересный предмет.
• У квадрата – 10 сторон и все разные.
• Красиво!
• В городе N живут 2 миллиона человек.
• Который час?

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

A – Сейчас идет дождь.

B – Форточка открыта.

простые высказывания (элементарные)

!

Любое высказывание может быть ложно (0) или истинно (1).

Составные высказывания строятся из простых с помощью логических связок (операций) " и ", " или ", " не ", " если … то ", " тогда и только тогда " и др.

A и B

A или не B

если A, то B

не A и B

A тогда и только

тогда, когда B

Сейчас идет дождь и открыта форточка.

Сейчас идет дождь или форточка закрыта.

Если сейчас идет дождь, то форточка открыта.

Сейчас нет дождя и форточка открыта.

Дождь идет тогда и только тогда, когда открыта форточка.

5

5

Операция НЕ (инверсия)

Если высказывание A истинно, то " не А " ложно, и наоборот.

также: , not A (Паскаль), ! A (Си)

А

не А

0

1

таблица истинности операции НЕ

1

0

Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Операция И (логическое умножение, конъюнкция)

Высказывание " A и B " истинно тогда и только тогда, когда А и B истинны одновременно.

также: A·B , A  B , A and B (Паскаль), A && B (Си)

A

B

А и B

0

1

2

3

0

0

0

0

0

1

0

1

0

1

1

1

A  B

конъюнкция – от лат. conjunctio — соединение

Операция ИЛИ (логическое сложение, дизъюнкция)

Высказывание " A или B " истинно тогда, когда истинно А или B , или оба вместе.

также: A+B , A  B , A or B (Паскаль), A || B (Си)

A

B

А или B

0

0

0

1

0

1

1

1

0

1

1

1

дизъюнкция – от лат. disjunctio — разъединение

8

8

Операция "исключающее ИЛИ"

Высказывание " A  B " истинно тогда, когда истинно А или B , но не оба одновременно .

также: A xor B (Паскаль), A ^ B (Си)

A

B

А  B

0

0

0

1

0

1

арифметическое сложение, 1+1=2

1

1

0

остаток

1

1

0

сложение по модулю 2: А  B = (A + B) mod 2

9

9

Свойства операции "исключающее ИЛИ"

0

A  A =

( A  B)  B =

A

A  0 =

A  1 =

?

A

A

0

B

0

0

1

1

1

0

А  B

1

0

0

0

0

1

0

1

1

1

1

1

0

0

0

0

0

10

10

Импликация ("если …, то …")

Высказывание " A  B " истинно, если не исключено, что из А следует B .

A – "Работник хорошо работает".

B – "У работника хорошая зарплата".

A

0

B

А  B

0

0

1

1

1

0

1

1

1

0

1

11

11

Эквиваленция ("тогда и только тогда, …")

Высказывание " A  B " истинно тогда и только тогда, когда А и B равны.

A

B

0

0

А  B

0

1

1

1

0

0

1

1

0

1

12

12

Базовый набор операций

С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию.

ИЛИ

И

НЕ

базовый набор операций

?

Сколько всего существует логических операции с двумя переменными?

13

13

Логические формулы

Система имеет три датчика и может работать, если два из них исправны.

A – "Датчик № 1 неисправен".

B – "Датчик № 2 неисправен".

C – "Датчик № 3 неисправен".

Аварийный сигнал :

X – "Неисправны два датчика".

X – "Неисправны датчики № 1 и № 2" или

"Неисправны датчики № 1 и № 3" или

"Неисправны датчики № 2 и № 3".

логическая формула

14

14

Составление таблиц истинности

A

B

0

0

A · B

0

1

1

0

1

1

X

0

1

1

0

0

1

2

3

0

1

0

1

0

0

1

1

1

0

0

1

Логические выражения могут быть:

• тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)
• тождественно истинными (всегда 1, тавтология)
• тождественно ложными (всегда 0, противоречие)
• вычислимыми (зависят от исходных данных)

15

15

Составление таблиц истинности

A

B

0

C

0

0

AB

0

0

0

AC

0

1

1

1

BC

0

1

1

X

0

1

0

0

1

1

1

1

1

0

1

0

0

1

2

3

4

5

6

7

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

1

1

0

0

0

1

1

0

1

1

1

1

16

16

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

Тема 2. Диаграммы

Диаграммы Вена (круги Эйлера)

A

A

A

B

B

A · B

A+B

A

A

A

B

B

B

A  B

A  B

A  B

18

18

Диаграмма МХН (Е.М. Федосеев)

Х очу

М огу

4

3

2

6

7

5

1

8

Н адо

!

Логические формулы можно упрощать!

19

19

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

Тема 3. Преобразование логических выражений

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

название

для И

двойного отрицания

для ИЛИ

исключения третьего

операции с константами

повторения

поглощения

переместительный

сочетательный

распределительный

правила де Моргана

Упрощение логических выражений

Шаг 1. Заменить операции  на их выражения через И , ИЛИ и НЕ :

Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана:

Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

Упрощение логических выражений

раскрыли 

формула де Моргана

распределительный

исключения третьего

повторения

поглощения

Логические уравнения

A=1, B=0, C=1

или

!

A=0, B=1, C – любое

2 решения: (0, 1, 0), (0, 1, 1)

Всего 3 решения!

M=1, L=1, N=1,

K – любое

2 решения

K=1, L=1,

M и N – любые

4 решения

K=1, L=1, M=0,

N – любое

2 решения

!

Всего 5 решений!

24

24

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

Тема 4. Синтез логических выражений

Синтез логических выражений

Шаг 1. Отметить строки в таблице, где X = 1 .

Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.

Шаг 3. Сложить эти выражения и упростить результат.

A

B

0

0

0

X

1

1

1

1

0

1

0

1

1

распределительный

исключения третьего

исключения третьего

распределительный

Синтез логических выражений (2 способ)

Шаг 1. Отметить строки в таблице, где X = 0 .

Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.

Шаг 3. Сложить эти выражения и упростить результат, который равен .

Шаг 4. Сделать инверсию.

A

B

0

X

0

0

1

1

1

1

0

1

0

1

1

?

Когда удобнее применять 2-ой способ?

27

27

Синтез логических выражений

A

B

0

C

0

0

0

X

0

0

0

1

1

1

1

0

1

1

1

1

0

1

1

0

1

0

0

1

1

1

0

1

1

0

1

1

Синтез логических выражений (2 способ)

A

B

0

C

0

0

0

X

0

0

0

1

1

1

1

0

1

1

0

1

1

1

1

0

1

0

0

1

1

1

1

1

0

0

1

1

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

Тема 5. Логические элементы компьютера

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

значок инверсии

&

1

НЕ

И

ИЛИ

&

1

И-НЕ

ИЛИ-НЕ

31

31

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

Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ.

И :

НЕ:

&

&

&

&

ИЛИ:

&

&

32

32

Составление схем

последняя операция - ИЛИ

И

&

1

&

&

33

33

Триггер (англ. trigger – защёлка)

Триггер – это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.

вспомогательный

выход

set, установка

1

S

R

0

Q

0

0

1

1

0

1

режим

1

хранение

обратные связи

0

сброс

1

установка 1

1

1

0

запрещен

0

0

основной

выход

reset, сброс

Полусумматор

Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа.

сумма

A

B

0

0

P

0

1

1

S

0

1

1

Σ

0 0

перенос

0 1

0 1

1 0

&

1

&

?

Схема на 4-х элементах?

&

35

35

Сумматор

Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда.

A

B

0

0

C

0

P

0

0

0

1

0

0

1

S

0

1

1

0

0

0

1

1

0

1

1

0

1

1

0

0

1

1

0

1

1

1

0

1

0

1

1

1

0

1

Σ

сумма

перенос

перенос

Многоразрядный сумматор

это логическая схема, способная складывать два n-разрядных двоичных числа.

перенос

Σ

Σ

Σ

перенос

37

37

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

Тема 6. Логические задачи

Метод рассуждений

Задача 1. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты договора, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:

Россия — "Проект не наш (1), проект не США (2)";

США — "Проект не России (1), проект Китая (2)";

Китай — "Проект не наш (1), проект России (2)".

Один из них оба раза говорил правду; второй – оба раза говорил неправду, третий один раз сказал правду, а другой раз — неправду. Кто что сказал?

проект России (?)

проект Китая (?)

проект США (?)

Россия

Россия

Россия

(1)

(1)

(1)

(2)

(2)

(2)

США

США

США

Китай

Китай

Китай

–

–

+

+

+

+

+

–

–

–

+

+

+

+

Табличный метод

Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У них разные профессии и они живут в разных городах: одна в Ростове, вторая – в Париже и третья – в Москве. Известно, что

• Даша живет не в Париже, а Лариса – не в Ростове, парижанка – не актриса, в Ростове живет певица, Лариса – не балерина.
• Даша живет не в Париже, а Лариса – не в Ростове,
• парижанка – не актриса,
• в Ростове живет певица,
• Лариса – не балерина.

• Много вариантов.
• Есть точные данные.

Париж

Ростов

Москва

Певица

Даша

Балерина

Анфиса

Актриса

Лариса

0

1

0

1

0

0

0

1

0

1

0

0

0

0

1

0

0

1

!

В каждой строке и в каждом столбце может быть только одна единица!

40

40

Задача Эйнштейна

Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному человеку отличной от другого национальности. Каждый жилец пьет только один определенный напиток, курит определенную марку сигарет и держит животное. Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты и не держит одинаковых животных.

Известно, что:

• Англичанин живет в красном доме. Швед держит собаку. Датчанин пьет чай. Зеленой дом стоит слева от белого. Жилец зеленого дома пьет кофе. Человек, который курит Pallmall , держит птицу. Жилец среднего дома пьет молоко. Жилец из желтого дома курит Dunhill . Норвежец живет в первом доме. Курильщик Marlboro живет около того, кто держит кошку. Человек, который содержит лошадь, живет около того, кто курит Dunhill . Курильщик Winfield пьет пиво. Норвежец живет около голубого дома. Немец курит Rothmans . Курильщик Marlboro живет по соседству с человеком, который пьет воду.
• Англичанин живет в красном доме.
• Швед держит собаку.
• Датчанин пьет чай.
• Зеленой дом стоит слева от белого.
• Жилец зеленого дома пьет кофе.
• Человек, который курит Pallmall , держит птицу.
• Жилец среднего дома пьет молоко.
• Жилец из желтого дома курит Dunhill .
• Норвежец живет в первом доме.
• Курильщик Marlboro живет около того, кто держит кошку.
• Человек, который содержит лошадь, живет около того, кто курит Dunhill .
• Курильщик Winfield пьет пиво.
• Норвежец живет около голубого дома.
• Немец курит Rothmans .
• Курильщик Marlboro живет по соседству с человеком, который пьет воду.

Вопрос: У кого живет рыба?

40

40

Использование алгебры логики

Задача 3. Следующие два высказывания истинны:

1. Неверно, что если корабль A вышел в море, то корабль C – нет.

2. В море вышел корабль B или корабль C , но не оба вместе.

• 1. Неверно, что если корабль A вышел в море, то корабль C – нет. 2. В море вышел корабль B или корабль C , но не оба вместе.

Определить, какие корабли вышли в море.

Решение:

… если корабль A вышел в море, то корабль C – нет.

1. Неверно, что если корабль A вышел в море, то корабль C – нет.

2. В море вышел корабль B или корабль C , но не оба вместе.

42

42

Использование алгебры логики

Задача 4. Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Мастер по ремонту сказал, что с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось?

Решение:

A – неисправен процессор, B – память, C – винчестер

сын:

мастер:

хозяин:

Если ошибся хозяин:

Если ошибся сын:

Если ошибся мастер:

!

Несколько решений!

В общем случае:

43