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

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

2. Основные понятия алгебры логики

2

3.

Алгебра логики (булева алгебра) изучает высказывания,
рассматриваемые со стороны их логических значений
(истинности или ложности), и логические операции над
ними.
Let’s start!
Основным предметом алгебры логики являются
высказывания.
Под высказыванием понимается имеющее смысл языковое
выражение, относительно которого можно утверждать, что
оно либо истинно, либо ложно.
3

4.

Являются логическими высказываниями: Сейчас осень. Летом медведи
впадают в спячку. Весной тает снег.
Не являются высказываниями: Пойдем завтра в кино? Красиво!!! В городе
N проживают 4000 человек.
4

5.

Простое высказывание - логическое высказывание, состоящее из одного
утверждения.
A – Сейчас светит солнце. B – Мы идем гулять.
Любое высказывание может быть ложно (0) или истинно (1).
Сложное высказывание - логическое высказывание, состоящее из
нескольких утверждения, объединенных с помощью "связок": союзов "и",
"или (либо)", частицы "не", связки "если, то" и др.
А и В - Сейчас светит солнце и мы идем гулять.
А или не В - Сейчас светит солнце и мы не идем гулять.
Если А, то В - Если сейчас светит солнце, то мы идем гулять.
А тогда и только тогда, когда В - Солнце светит тогда и только тогда, когда
мы идем гулять.
5

6. Операции алгебры логики

6

7.

Операция НЕ
Логическая связка ИНВЕРСИЯ (от лат. inversion переворачиваю).
Название
– отрицание не
Наш пример
с Animal/Cat/Dog
работает так, как мы хотим, потому
что ссылка/указатель
Animal
Если высказывание
A истинно, то «некласса
А» ложно,
и
не
может получить доступ к
наоборот.
методам speak() дочерних классов.
Один из способов обойти эту
так, !A
чтобы
Обозначения: непроблему
А, ¬A, not—
A сделать
(Паскаль),
(Си)
данные, возвращаемые методом
speak(), стали доступными в виде
Left Photo
Placeholder
родительской
части
класса Animal
(так же, как name класса Animal
доступен через член m_name).
Transition
Slide
Your Date Here
Your Footer Here
7

8.

Операция И
Логическая связка КОНЪЮНКЦИЯ (от лат. conjunctio связываю). Название – логическое умножение.
Высказывание «A и B» истинно тогда и только
тогда, когда А и B истинны одновременно.
Обозначения: А и В, А*В, А^B, A&B, A and B
(Паскаль), A&&B (Си)
8

9.

Операция ИЛИ (логическое сложение,
дизъюнкция)
Наш пример с Animal/Cat/Dog не
работает
как мы
хотим,
потому
Высказывание «A
или B»так,
истинно
тогда
и только
что ссылка/указатель
класса
Animal
тогда, когда истинно
А или B, или оба
вместе.
не может получить доступ к
методам speak() дочерних классов.
Обозначения: А илиОдин
В, А+B,
AvB, A orобойти
B (Паскаль),
из способов
эту
AIIB (Си)— сделать так, чтобы
проблему
данные, возвращаемые методом
speak(), стали доступными в виде
Left Photo
Placeholder
родительской
части
класса Animal
(так же, как name класса Animal
доступен через член m_name).
Transition
Slide
Your Date Here
Your Footer Here
9

10.

Операция «Исключающее ИЛИ» (сумма по модулю
2, разделительная дизъюнкция)
Высказывание «A Е B» истинно тогда, когда истинно
А или B, но не оба одновременно.
Обозначения: A Е B, A xor B (Паскаль), A^B (Си)
10

11.

Операция Импликация (" Если А, то В")
Логическая связка ИМПЛИКАЦИЯ (от лат. implicatio – тесно связывать).
Название – логическое следование.
Обозначение в алгебре высказываний: А=>B, где А – условие, В –
следствие.
В естественном языке ему соответствует оборот "если . . ., то . . .".
Обозначения: A B
А="На улице светит солнце" и В="На улице ясная погода"
11

12.

Операция Эквиваленция (" А тогда и только тогда,
когда В"). Название – логическое равенство.
Наш пример с Animal/Cat/Dog не
так, как
мыихотим,
Высказывание «Aработает
B» истинно
тогда
толькопотому
тогда,
что ссылка/указатель
класса Animal
когда
А и B равны
не может получить доступ к
методам speak() дочерних классов.
Обозначения:
«A B» обойти эту
Один из способов
проблему — сделать так, чтобы
данные, возвращаемые методом
speak(), стали доступными в виде
Left Photo
Placeholder
родительской
части
класса Animal
(так же, как name класса Animal
доступен через член m_name).
Transition
Slide
Your Date Here
Your Footer Here
12

13.

Логическая переменная – это простое высказывание, содержащее только
одну мысль. Ее символическое обозначение – латинская буква (например,
A, B, X, Y и т.д.). Значением логической переменной могут быть только
константы ИСТИНА (1) и ЛОЖЬ (0). На основании простых высказываний
могут быть построены составные высказывания.
Логическая функция - составное высказывание, которое содержит
несколько простых мыслей, соединенных между собой с помощью
логических операций.
Ее символическое обозначение – F (A, B, …).
Логические операции – логическое действие.
13

14.

1. Проанализируем составное высказывание "Если я куплю яблоки или
абрикосы, то приготовлю фруктовый пирог".
Обозначим буквой A высказывание: "Купить яблоки", буквой B высказывание: "Купить абрикосы", буквой C - высказывание: "Испечь
пирог".
2. Запишем высказывание в виде логического выражения, высказывание
"Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог"
формализуется в виде формулы: F=(A v B)=>C.
14

15.

Записывать в виде логического выражения
следующее высказывание: «Летом Петя
поедет в деревню и, если будет хорошая
погода, то он пойдет на рыбалку».
1. Проанализируем составное
высказывание. Оно состоит из следующих
простых высказываний: «Петя поедет в
деревню», «Будет хорошая погода», «Петя
пойдет на рыбалку». Обозначим их через
логические переменные:
Transition
А = Петя поедет в деревню;
В = Slide
Будет хорошая погода;
С = Петя пойдет на рыбалку.
Right Photo Placeholder
2. Запишем высказывание в виде
логического выражения, учитывая порядок
действий. Если необходимо, расставим
скобки: F=A&(B=>C).
Your Date Here
Your Footer Here
15

16.

Порядок выполнения
логических операций:
1. Операции в скобках
2. Инверсия
3. Конъюнкция
4. Дизъюнкция
5. Импликация
6. Эквиваленция
Right Photo
Placeholder
7. Операции,
имеющие
один
ранг выполняются в порядке
очередности
Transition
Slide
Your Date Here
Your Footer Here
16

17.

Каждое составное высказывание можно выразить в виде формулы - логического выражения. В
таком выражении простые высказывания - логические переменные, а логические функции знаки логических операций.
Пример: Прибор имеет три датчика и может работать, если два из них исправны. Записать в
виде логической функции ситуацию «авария»
.
A – «Датчик № 1 неисправен».
B – «Датчик № 2 неисправен».
C – «Датчик № 3 неисправен».
Аварийный сигнал:
X – «Неисправны два датчика».
X – «Неисправны датчики № 1 и № 2» или
«Неисправны датчики № 1 и № 3» или
«Неисправны датчики № 2 и № 3».
X= A^B v A^C v B^C - логическое выражение, или логическая формула или логическая
функция, выражающая работу прибора.
17

18. Построение таблиц истинности логического выражения

18

19.

Решение логических выражений принято записывать в виде таблиц
истинности – таблиц, в которых по действиям показано, какие значения
принимает логическое выражение при всех возможных наборах его
переменных.
19

20.

Пусть нам дана следующая логическая функция:
F=(AvB)&(неА v неB)
1.Представим её в более удобной форме: F=(A+B)*(неА+неB)
2. Определим количество строк и столбцов в таблице
истинности.
Кол-во строк=2n, где n-количество переменных.
В нашем случае n=2, т. к. имеем 2 переменных А и В. Таким
образом кол-во строк=22=4
Transition
Slide
Right Photo Placeholder
Кол-во столбцов = кол-во логических переменных + кол-во
логических операций.
В нашем случае кол-во столбцов=2 переменных+5 операций
(неА, неB, A+B, неА+неB, *)=7
Your Date Here
Your Footer Here
20

21.

3. Строим таблицу истинности с определенным
количеством строк и столбцов.
А именно 4 строки и 7 столбцов.
5. Заполняем таблицу истинности по столбцам,
выполняя базовые логические операции в
необходимой последовательности и в соответствии
с их таблицами истинности
21

22.

Алгоритм составления таблицы истинности:
1. Выяснить количество строк в таблице (вычисляется как 2n,
где n – количество переменных + строка заголовков
столбцов).
2. Выяснить количество столбцов (вычисляется как
количество переменных + количество логических операций).
3. Установить последовательность выполнения логических
операций.
4. Построить таблицу, указывая названия столбцов и
возможные наборы значений исходных логических
переменных.
5. Заполнить таблицу истинности по столбцам.
6. Записать ответ.
22

23.

Построим таблицу истинности для выражения
F=(AvB)&(¬Av¬B).
Наш пример с Animal/Cat/Dog не
работает2 (2
так,
как мы хотим, потому
1. Количество строк=2
переменных+строка
что ссылка/указатель
заголовков
столбцов)=5. класса Animal
не может получить доступ к
методам speak() дочерних классов.
2. Количество столбцов=2
логические
переменные
Один из
способов обойти
эту
(А, В)+ 5 логических
операций
(v,&,¬,v,¬)
= 7.
проблему
— сделать
так, чтобы
данные, возвращаемые методом
speak(),
стали
доступными
в
виде
3. Расставим порядок выполнения
операций:
Left
Photo
Placeholder
родительской части класса Animal
(так же, как name класса Animal
доступен через член m_name).
Transition
Slide
Your Date Here
Your Footer Here
23

24.

4-5. Построим таблицу и заполним ее по столбцам:
Наш пример с Animal/Cat/Dog не
работает так, как мы хотим, потому
что ссылка/указатель класса Animal
не может получить доступ к
методам speak() дочерних классов.
Один из способов обойти эту
проблему — сделать так, чтобы
данные, возвращаемые методом
доступными
6. Ответ:speak(),
F=0, пристали
A=B=0
и A=B=1 в виде
Left Photo
Placeholder
родительской
части
класса Animal
(так же, как name класса Animal
доступен через член m_name).
Transition
Slide
Your Date Here
Your Footer Here
24

25.

Построим таблицу истинности для логического
выражения F=XvY&¬Z.
1. Количество строк=23+1=(3 переменных+строка
заголовков столбцов)=9.
2. Количество столбцов=3 логические
переменные+3 логических операций = 6.
3. Укажем порядок действий:
25

26.

4-5. Построим таблицу и заполним ее по
столбцам:
6. Ответ: F=0, при X=Y=Z=0; при X=Y=0 и Z=1.
26

27. Задания

28.

Постройте таблицы истинности для
следующих логических выражений:
1. F=(AvB)&(¬A&¬B).
2. F=X&¬YvZ.
28

29.

29

30.

30

31. Равносильные логические выражения

32.

В алгебре
логики
имеется ряд
законов,
позволяющих
производить
равносильные
преобразован
ия логических
выражений.
32

33.

33

34.

Упростить логическое выражение
F=(¬AvB)&¬(A&B)
34

35.

Используя закон де Моргана, получим:
(¬AvB)&¬(A&B)=(¬AvB)&(¬Av¬B).
Применим правило дистрибутивности, т.е.вынесем общий множитель за скобки:
(¬AvB)&(¬Av¬B)=¬Av(B&¬B).
По закону противоречия во второй скобке получаем:
¬Av(B&¬B)=¬Av0.
Применяя свойства констант, получим:
¬Av0=¬A.
Таким образом, F=(¬AvB)&¬(A&B)=¬A.
35

36.

Упростить логическое выражение
F=(X=>Y)v(Y=>X).
36

37.

Используя закон де Моргана, получим:
(X=>Y)v(Y=>X)=(¬XvY)v(¬YvX).
Используя правило ассоциативности, перегруппируем
слагаемые:
(¬XvY)v(¬YvX)=(¬XvX)v(¬YvY).
По закону исключения третьего получим:
(¬XvX)v(¬YvY)=1v1=1.
Таким образом, F=(X=>Y)v(Y=>X)=1.
37

38. Элементы булевой алгебры

39.

39

40. Элементы булевой алгебры

41.

Логические схемы необходимо строить из минимально
возможного количества элементов, что в свою очередь,
обеспечивает большую скорость работы и увеличивает
надежность устройства.
Алгоритм построения логических схем:
1) Определить число логических переменных.
2) Определить количество базовых логических
операций и их порядок.
3) Изобразить для каждой логической операции
соответствующий ей вентиль.
4) Соединить вентили в порядке выполнения
логических операций.
41

42.

Составить логическую схему для логического выражения:
F=¬XvY&X.
1) Две переменные – X и Y.
2) Две логические операции:
3)
Строим схему, соединяя вентили в порядке выполнения
логических операций:
42

43.

Составить логическую схему для логического выражения:
F=X&Yv¬(YvX). Вычислить значения выражения для X=1, Y=0.
1) Две переменные – X и Y.
2)
Логических операций четыре: конъюнкция, две дизъюнкции и отрицание.
Определяем порядок выполнения операций:
3)
Схему строим слева направо в соответствии с порядком выполнения логических
операций:
43

44. Триггер

45.

Триггер (trigger – защелка, спусковой крючок) –
это устройство, позволяющее запоминать,
хранить и считывать информацию. Каждый
триггер хранит 1 бит информации, т.е. он может
находиться в одном из двух устойчивых
состояний – логический «0» или логическая «1».
Триггер способен почти мгновенно переходить
из одного электрического состояния в другое и
наоборот.
45

46.

Логическая схема триггера выглядит следующим образом:
Входы триггера расшифровываются следующим образом – S (от
английского Set – установка) и R (Reset – сброс). Они используются
для установки триггера в единичное состояние и сброса в нулевое. В
связи с этим такой триггер называется RS-триггер.
Выход Q называется прямым, а противоположный – инверсный.
Сигналы на прямом и инверсном выходах, конечно же, должны
быть противоположны.
46

47.

47

48. Архитектура ПК

49.

ПК имеет открытую магистрально-модульную архитектуру:
• персональный компьютер состоит из отдельных функциональных блоков (модулей);
• информационная связь между модулями осуществляется посредством
информационной магистрали (системной шины);
• отдельные модули компьютера соответствуют открытым стандартам и могут быть
заменены или дополнены другими, их состав можно изменить или расширить.
Основные компоненты архитектуры:
• центральный процессор
• информационная магистраль
• внутренняя память (постоянная и оперативная)
• внешняя память
• периферийные устройства (устройства ввода-вывода).
49

50.

Системный блок ПК содержит все основные устройства компьютера:
• материнскую плату
• адаптеры
• блок питания
• дисководы (для гибких магнитных дисков, компакт-дисков)
• винчестер
• разъемы для подключения периферийных устройств.
Микропроцессор - вычислительное устройство на сверхбольшой интегральной
схеме (в кристалле сверхчистого кремния созданы миллионы транзисторов и др.
элементы, образующие логические блоки процессора (арифметико-логическое
устройство, устройство управления, регистры памяти).
Чипсет (основа материнской платы) - микросхема, которая позволяет процессору
обмениваться информацией с памятью (северный мост) и периферией (южный мост).
Материнская (системная) плата - большая печатная плата несущая на себе главные
компоненты компьютерной системы (центральный микропроцессор, оперативную
память, микросхема BIOS, центральную шину).
50

51.

Оперативная память - печатная плата с микросхемами реализующими запись - хранение- чтение
информации.
• Статическая память образована триггерами (при считывании записанного в ячейку памяти ее
значение не меняется).
• Динамическая память образована конденсаторами (медленнее, менее энергоемка).
BIOS (Basic Input-Output System, базовая система ввода-вывода). - энергонезависимое постоянное
запоминающее устройство, в которое записаны программы, реализующие функции ввода-вывода,
тестирования компьютера в момент включения и др.
Системная шина - кабель, состоящий из электропроводов для передачи информации между
устройствами компьютера.
• По шине данных передается обрабатываемая информация.
• По шине адресов - передаются адреса памяти и внешних устройств, к которым обращается
процессор.
• По шине управления предаются управляющие сигналы.
Количество одновременно передаваемых бит - разрядность шины.
К слотам (гнездам-разъемам) на материнской плате подключаются другие платы (контроллеры и
платы расширения).
51

52.

Контроллеры (адаптеры) преобразуют форму представления данных и управляющих
сигналов, которыми обмениваются различные устройства ПК. Оформлены в виде
микросхем на печатных платах подключаемых к материнской плате и устройствам:
1.
2.
3.
4.
5.
контроллер дисков - формирует импульсы при записи-чтении данных на диск и
управляет работой подвижных частей дисководов;
контроллер ввода-вывода (адаптер портов) - обслуживает принтеры,
манипуляторы, сканеры и т.д., которые подсоединяются нему через специальные
схемные устройства - порты (параллельные и последовательные);
видеоадаптер (видеокарта, видеоплата) - преобразует набор данных, подлежащих
отображению на экране в видеосигнал;
аудиокарта (звуковая плата) - преобразует аналоговые сигналы звуковой частоты в
цифровые коды и обратно.
сетевая карта (сетевая плата, сетевой адаптер) - осуществляет передачу данных из
ПК в компьютерную сеть и обратно, преобразуя их в соответствии со стандартами
сети.
Платы расширения - дополнительные электронные устройства
52

53.

1.
2.
3.
4.
5.
6.
7.
8.
9.
Открытая архитектура компьютера подразумевает следующие правила
модульности:
Центральный процессор наиболее часто применяется от компании Intel или
аналогичные ему, кроме того могут использоваться совместимые с ними
программно процессоры других производителей.
В память материнской платы зашит BIOS (базовая система ввода-вывода).
Начальный системный запуск изначально регламентирован.
Организация памяти представлена в виде набора модулей, которые имеют
разные параметры.
Работает процедура выполнения операции определения конфигурации.
Персональный компьютер снабжён системным реестром и специальным
разделом памяти для сохранения параметров конфигурации.
Организована работа механизма прерывания программы и прямого доступа
к памяти.
Каждый модуль компьютера имеет свой индивидуальный адрес.
Для операции ввода данных и отображения её на экране дисплея
53
применяется специальное кодирование.

54. Принцип программного управления

54

55.

Сущность программного управления заключается в
том, что сигналы управления работой отдельных
частей компьютера вырабатываются внутри
компьютера в процессе вычислений. Источником
информации о требуемых типах сигналов на каждом
шаге вычислений является код команды,
считываемый из памяти компьютера.
Команда указывает, какую операцию и над какими
данными необходимо выполнить.
Последовательность команд, реализующих
заданный алгоритм (т.е. заданную
последовательность действий), представляет собой
программу решения задачи на компьютере.
55

56.

Совокупность всех команд, которые может
выполнить компьютер, представляет собой систему
команд данного компьютера. В системе команд
обычно содержится более 200 команд. Команда
изображается в виде двоичного кода и имеет
структуру, которую иллюстрирует рисунок
КОП – код операции. Для его представления, как
правило, используется один байт.
Операнды – данные, которые участвуют в операции
(А1, А2 и т.д.).
56

57.

Команды в ЭВМ могут быть одноадресными,
двухадресными и трехадресными (в машинах с так
называемой естественной адресацией команд).
57

58.

Таким образом, в команде, кроме кода операции,
указывается, по какому адресу в памяти находится каждый из
операндов, а также по какому адресу необходимо поместить
результат операции. В большинстве операций при
двухадресной структуре команд (структура команд, в которой
имеется два поля адреса) результат записывается на место
первого операнда.
Как правило, адресная часть (А1 + А2) команды занимает от 1
до 5 байтов, а вся команда – от 2 до 6 байтов.
В системе команд могут быть выделены следующие
основные типы команд:
1)арифметические (сложение, вычитание, умножение,
деление);
2)логические (логические сложение и умножение, отрицание,
сравнение и др.);
3)передачи управления;
4)обработки адресов (специальные);
5)ввода/вывода.
58

59. Автоматическое выполнение команд программы

59

60.

Под автоматическим выполнением команд программы
подразумевается обработка входных (исходных) данных,
поступивших на вход компьютера, без участия человека.
Сущность ее заключается в следующем.
Программа работы компьютера и исходные данные
заносятся в память машины. Процесс вычислений
начинается после запуска программы на выполнение.
При этом в устройство управления (УУ) компьютера
передается адрес памяти, где записана первая команда
программы. УУ вырабатывает сигналы, по которым в
памяти находится требуемая команда и из нее
извлекается код операции (КОП). Он определяет, что
должен сделать компьютер над кодами чисел, адреса
которых в памяти определены командой; адрес ячейки
памяти, куда надо отправить результат операции, и
адрес памяти, где необходимо взять код следующей
команды программы. Если анализ результата операции
требует изменения хода вычислений, то УУ
автоматически изменяет адрес памяти, по которому
извлекается код следующей команды.
60

61.

Выполнив считывание из памяти одного или двух
операндов, УУ направляет их в арифметикологическое устройство (АЛУ), где в соответствии с
КОП команды производится необходимое
преобразование информации. По мере переработки
информации промежуточные и окончательные
результаты хранятся в памяти компьютера. При
необходимости последние команды программы
могут определять операции передачи информации
из памяти в устройство вывода информации, где
информация фиксируется на некоторый носитель
информации в форме, удобной для восприятия
человеком или компьютером
61

62. Этапы постановки и решения задачи на компьютере

62

63.

Можно выделить следующие этапы постановки и решения задачи
на компьютере:
1)четкая формулировка задачи, выделение исходных данных и
формы представления результатов;
2)формальная (математическая) постановка задачи – представление
ее в виде уравнений, соотношений, ограничений;
3)выбор метода решения; метод решения определяется решаемой
задачей;
4)разработка алгоритма решения задачи;
5)выбор структуры данных; от выбора способа представления
данных зависит способ их обработки; поэтому этапы 4) и 5)
взаимосвязаны;
6)собственно программирование (запись разработанного алгоритма
на языке программирования);
7)тестирование и отладка программы (проверка правильности
работы программы и исправление обнаруженных ошибок);
8)выполнение программы на компьютере.
63

64.

Для того, чтобы
программа была понятна
компьютеру, она должна
быть составленной из
последовательности
элементарных операций,
представленных на
машинном языке – в
виде Right
совокупности
нулей
Photo Placeholder
и единиц, т.е. в так
называемых машинных
кодах.
Transition
Slide
Your Date Here
Your Footer Here
64

65.

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

66.

К основным методам автоматизации программирования можно
отнести следующие.
1) Использование языков высокого уровня, близких к естественному
человеческому языку, позволяющих автоматически однозначно
преобразовывать написанную на них программу в программу на
языке машины, т.е. в машинные коды.
2)Создание и использование библиотек стандартных программ и
подпрограмм, предназначенных для реализации часто
используемых задач.
3)Использование современных технологий программирования.
4)Использование Case-средств, предназначенных для
автоматизации процесса разработки программ.
66