АРХИТЕКТУРА ЭВМ И ВС

Тема 1.4. Логические основы ЭВМ, элементы и узлы
Занятие 10. Базовые логические операции и схемы. Таблицы истинности. Схемные логические элементы ЭВМ и их классификация: регистры, вентили, триггеры, полусумматоры и сумматоры.

Англичанин Джордж Буль (1815-1864, математик-самоучка), на фундаменте, заложенном Лейбницем, создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний). В его работах логика обрела свой алфавит, свою орфографию и грамматику.
Немецкий ученый Готфрид Лейбниц (1646-1716) заложил основы математической логики. Он пытался построить первые логические исчисления (свести логику к математике), предложил использовать символы вместо слов обычного языка, поставил много задач по созданию символьной логики, его идеи оказали влияние на последующие работы ученых в этой области.
Математическая логика

Алгебра логики (высказываний) работает с высказываниями.
Различают:
Логические константы (логические утверждения) – конкретные частные утверждения (И/Л)
{Аристотель - основоположник логики}
{На яблонях растут бананы}
2. Логические переменные (предикаты) – логические высказывания, значения которых меняются в зависимости от входящих в них переменных, обозначаются заглавными латинскими буквами А, В, С, D, F,…
А = {Аристотель - основоположник логики}
В = {На яблонях растут бананы}.
Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

3. Логические функции ( логические формулы) – сложные логические выражения, образованные из простых и связанных логическими операциями И, ИЛИ, НЕ и др.)
Высказывание “Все мышки и кошки с хвостами”
является сложным и состоит из двух простых высказываний.
А=“Все мышки с хвостами” и В=“Все кошки с хвостами”
Его можно записать в виде логической функции, значение которой истинно: F(A,B)=A и B
В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только ложно (0) или истинно (1).

Логические операции
Отрицание (инверсия).
Обозначение: НЕ А, ¬А,
А={Дети любят игрушки} = {Дети НЕ любят игрушки}

2. Логическое умножение (Конъюнкция) Обозначение: И, ∧, &, •
F=A ^ B= {кит, акула, дельфин}
Таблица истинности:
F= А ∧ В

3. Логическое сложение (Дизъюнкция)
Обозначение: ИЛИ,∨, +, |
F=A V B= {Множество студентов ПИ-23 или ПИ-13}
Таблица истинности:
F= А ∨ В

4. ИМПЛИКАЦИЯ (логическое следование)
условие
следствие
ЕСЛИ, ...
ТО ...
=>
условие
следствие
Если будет дождь, то мы не пойдем на улицу.
Если я поленюсь, то получу двойку.
Если на траве роса, то скоро настанет вечер.
Обозначение: А→В, А⇒В
Таблица истинности:
Импликация - логическая связка (операция) служит для задания так называемых условных высказываний. Этой логической операции соответствуют фразы если ..., то ... или когда ..., тогда ... Импликация - двухместная операция: часть формулы до импликации называют основанием (условием) условного высказывания, а часть, расположенную за ней - следствием. Импликация является ложной только тогда, когда условие истинно, а следствие ложно.

4. ИМПЛИКАЦИЯ (логическое следование)
Обозначение: А→В, А⇒В
Например, один философ испытал сильнейшее потрясение, узнав от Бертрана Рассела, что из ложного утверждения следует любое утверждение. Он спросил: «Вы всерьез считаете, что из утверждения «два плюс два – пять» следует, что вы Папа Римский?» Рассел ответил утвердительно. «И вы можете доказать это?» − продолжал сомневаться философ. «Конечно!» − последовал уверенный ответ, и Рассел тотчас же предложил такое доказательство:
1) Предположим, что 2+2=5.
2) Вычтем из обеих частей по 2, получим 2=3.
3) Переставим правую и левую части, получим 3=2.
4) Вычтем из обеих частей по 1, получим 2=1.
Папа Римский и я – нас двое. Так как 2=1, то Папа Римский и я – одно лицо. Следовательно, я – Папа Римский [3].
Посмотрим на приведенное доказательство. Доказано ли, что 2+2=5? Нет. Может быть, доказано, что Бертран Рассел – Папа Римский? Тоже нет. А что же доказано? В точности то, что утверждалось: «Если 2+2=5, то Бертран Рассел – Папа Римский». И ничего больше.

5. ЭКВИВАЛЕНТНОСТЬ (равнозначность) -
Чайник греет воду тогда и только тогда, когда он включен.
Мы дышим свежим воздухом тогда и только тогда, когда гуляем в парке.
Обозначение: А~В, А↔В, А≡В, А=В
логическая связка (операция), ее аналог в разговорной речи - фразы, подобные словосочетанию тогда и только тогда, когда ... или если и только если ... Эквивалентность ставит в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Таблица истинности:

РЕШИМ ЗАДАЧИ:
Определите, в каком порядке необходимо вычислять значение логического выражения:
1) ¬ А & ¬ B
2) A & (B & C)
3) (A & B) ν (C & ¬ D)
4) A ν ¬ D ν B
5) A → (B ↔ ¬ A)
1
2
3
1
2
1
2
3
4
1
2
1
2
3
3
Приоритет логических операций:
() Операции в скобках
НЕ Отрицание
И логическое умножение
ИЛИ Логическое сложение
→ Импликация
↔ Эквивалентность

Вычисление логических выражений
Пример1.
Вычислить значение логического выражения
«(2·2=5 или 2·2=4}) и (2·2 ≠ 5 или 2·2 ≠ 4)»
Обозначим
А=«2·2=5» – ложно (0)
В=«2·2=4» – истинно (1)
Тогда (А или В) и ( или )

Задание 2. Определите истинность составного высказывания
состоящего из простых высказываний:
А={Принтер – устройство вывода информации}
В={Процессор – устройство хранения информации}
C={Монитор – устройство вывода информации}
D={Клавиатура – устройство обработки информации}
Определяем истинность составного высказывания:
А=1, В=0, С=1, D=0
Установим истинность простых высказываний:

ПОСТРОЕНИЕ ТАБЛИЦЫ ИСТИННОСТИ
ПО ЛОГИЧЕСКОМУ ВЫРАЖЕНИЮ
Таблицу, показывающую, какие значения принимает сложное высказывание при всех сочетаниях значений входящих в него простых высказываний (переменных), называют таблицей истинности сложного высказывания ( логической формулы).
По формуле логической функции легко рассчитать ее таблицу истинности, соблюдая приоритет логических операций и действия в скобках.

Порядок действий:
Количество строк в таблице Q=2n, где n - количество переменных (аргументов), здесь n = 3 (А, В, С) и тогда Q=23=8
2. Количество столбцов = число переменных + число операций (здесь 3+3=6 столбцов)
3. Выписать наборы входных переменных. Это удобнее сделать так:
разделить колонку значений первой переменной пополам и заполнить верхнюю половину 0, нижнюю половину 1.
разделить колонку значений второй переменной на 4 части и заполнить каждую четверть чередующимися группами 0 и 1 , начиная опять с группы 0.
продолжить деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами из 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа. (Можно заполнять все колонки, начиная с группы единиц.)
4. Провести заполнение таблицы истинности по столбикам, выполняя логические операции.
Пример. Построим таблицу истинности следующей функции:

Построим таблицу истинности для следующей функции:
1
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
1

Пример 1. Доказать равносильность логических выражений: и
Равносильные логические выражения
Логические выражения, у которых последние столбцы в таблице истинности совпадают, называются равносильными.
Знак «=» - равносильность.
0
1
1
1
1
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0

В булевой алгебре все логические операции могут быть сведены к трем базовым: логическому умножению, логическому сложению, логическому отрицанию.
Пример. Доказать методом сравнения ТИ, что

Пример. Доказать, пользуясь ТИ, что операция эквивалентности равносильна выражению
1
0
1
0
1
0
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1

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

Пример 1. Упростить логические выражения:
Здесь для первых двух скобок применена формула склеивания
1.
2. Пример 2. а) (Аv¬A)&B=
1&B=B
b) (A&(AvB)&(Bv¬B)=
A&(AvB)&1=A&(A&B)
Пример 3. Доказать справедливость законов де Моргана:
A&B
AvB
1
1
1
0
0
0
0
1
0
1
1
1
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
1
1
1
0

Вопросы для размышления:
Ученый, заложивший основы математической логики?
Ученый, создавший новую область науки – математическую логику?
Как по другому называется математическая логика?
Логическая константа – это…?
Логическая переменная – это…?
Логическая функция – это…?
Назовите логические операции и связки. Приведите их обозначения, диаграммы Эйлера-Венна и таблицы истинности логических операций и связок.
Что такое парадокс импликации (дополнительный вопрос)?
Приоритет логических операций (последовательность выполнения). Приведите примеры вычисления логических выражений.
Таблица истинности сложного высказывания (правила заполнения, порядок действий)?
К каким 3-м основным логическим операциям можно свести все другие логические операции?
Какие законы алгебры логики используются для упрощения логических функций?

Решение логических задач
Способы решения:
Табличный.
Графический (Графы).
Средствами алгебры логики.
Дополнительный материал

№1. Мастер спорта Седов, кандидат в мастера Чернов, перворазрядник Рыжов встретились в клубе перед началом турнира. «Обратите внимание» - заметил черноволосый – «один из нас седой, другой рыжий, а третий черноволосый. Но ни у кого цвет волос не соответствует фамилии. Забавно, не правда ли? «Ты прав» - подтвердил мастер. Какого цвета волосы у кандидата и мастера?
1. Табличный
-
-
-
-
+
+
-
-
+
Ответ:
Седов рыжий
Чернов седой
Рыжов черноволосый
2. Графический
Седов (м)
Чернов (к.м.)
Рыжов (1р.)
Седой
Черноволосый
Рыжий

Алгоритм:
Изучить условие задачи.
Выделить простые условия и обозначить их буквами.
Записать условия на языке алгебры логики.
Составить конечную формулу, для этого:
объединить логическим умножением формулы каждого утверждения,
приравнять произведение к 1.
Упростить формулу, проанализировать полученные результаты, или составить таблицу истинности, найти по ТИ значения переменных, для которых F=1, проанализировать результаты.
Решение задач средствами алгебры логики

3. Средствами алгебры логики
Выделим простые условия:
А=«Седов черноволосый»
В=«Седов рыжий»
С=«Чернов седой»
D=«Чернов рыжий»
Е=«Рыжов черноволосый»
F=«Рыжов седой»
Тогда:
АvB=1
CvD=1
EvF=1
НЕ А=1
Но,
АВ=0
СD=0
EF=0
AE=0
BD=0
CF=0
Составим логическое выражение:
(AvB)&(CvD)&(EvF)&¬A =1
Упростим:
(AvB)&(CvD)&(EvF)&¬A=
((A+B)·(C+D)) ·(E+F) ·¬A=
(AC+AD+BC+BD) ·(E+F) ·¬A=
(ACE+ADE+BCE+ACF+ADF+BCF) ·¬A
=(BCE+ADF) ·¬A =
BCE ·¬A + ADF ·¬A
BCE ·¬A =1 Следовательно,
Ответ:
B=1, Седов рыжий
C=1, Чернов седой
E=1, Рыжов черноволосый

№2. В каждой из двух аудиторий может находиться либо каб. Информатики, либо каб. Экономики. Таблички: на первой - «По крайне мере в одной из аудиторий размещается кабинет информатики», на второй - «Кабинет экономики находится в другой аудитории». Известно, что надписи либо обе Истинны, либо обе Ложны. Найдите кабинет информатики.
Решение.
А=«В 1-ой ауд. каб. Информатики»
В=«Во 2-ой ауд. каб. Информатики»
=«В 1-ой ауд. каб. Экономики»
=«Во 2-ой ауд. каб. Экономики»
X=(АvB)
Y=Не А
Сл-но, В=1 и
Ответ: «В 1-ой ауд. каб. Экономики»
«Во 2-ой ауд. каб. Информатики»

№3. В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.
Один считает, что первой будет Наташа, а Маша будет второй.
Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.
Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
(В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)
Решение:
А=«Наташа 1 м.»
В=«Маша 2 м.»
С=«Люда 2м.»
D=«Рита 4 м.»
E=«Рита 3м.»
F=«Наташа 2 м.»
АvB=1, CvD=1, EvF=1
Но, A&F=0
B&C=0
B&F=0
C&F=0
D&E=0
(АvB)&(CvD)&(EvF)=1
(АvB)&(CvD)&(EvF)= ((А+B)(C+D))(E+F)=
(AC+AD+BC+BD)(E+F)=
(AC+AD+BD)(E+F)=
ACE+ADE+BDE+ ACF+ADF+BDF=ACE=1
A=1,C=1,E=1
1м –Наташа
2м – Люда
3м – Рита
4м - Маша
О: 1423

№4. Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:
Миша: «Я не бил окно, и Коля тоже…»
Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»
Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.
Кто разбил стекло в классе? В ответе запишите только первую букву имени.
Решение:
А=«Миша разбил»
В=«Коля разбил»
С=«Сергей разбил»
Ответ: М - Миша разбил