Шпаргалка по "Информатике"

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем  алгебры логики является живший в  ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Логическое  высказывание — это любое повествовательное пpедлoжение, в oтнoшении кoтopoгo можно oднoзначнo сказать, истинно oнo или лoжнo.

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

Предложения, не являющиеся высказываниями, называются высказывательными формами.

Каждая  логическая связка рассматривается  как операция над логическими  высказываниями и имеет свое название и обозначение:

(1) Операция, выражаемая словом “не”, называется  отрицанием и обозначается чертой  над высказыванием (или знаком ù ). Высказывание истинно, когда A ложно, и ложно, когда A истинно.

(2) Операция, выражаемая связкой “и”, называется  конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой "•" (может также обозначаться знаками Ù или &). Высказывание А•В истинно тогда и только тогда, когда оба высказывания А и В истинны.

(3) Операция, выражаемая связкой “или” (в  неразделительном, не исключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

 

 (4) Операция, выражаемая  связками “если ..., то”, “из  ... следует”, “... влечет ...”, называется  импликацией (лат. implico — тесно связаны) и обозначается знаком ®. Высказывание А ® В ложно тогда и только тогда, когда А истинно, а В — ложно.  

(5) Операция, выражаемая связками “тогда и  только тогда”, "необходимо и  достаточно”, “... равносильно ...”,  называется эквиваленцией или двойной импликацией и обозначается знаком « или ~ . Высказывание А «В истинно тогда и только тогда, когда значения А и В совпадают.

Импликацию  можно выразить через дизъюнкцию и отрицание:

А ® В = v В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А « В = ( v В) • ( v А).

Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать  и обрабатывать логические высказывания.

2. Что  такое логическая формула?

Определение логической формулы:

Всякая  логическая переменная и символы  “истина” (“1”) и “ложь” (“0”) —  формулы.

Если А и В — формулы, то , (А • В), (А v В), (А ® B), (А « В) — формулы.

Никаких других формул в алгебре логики нет.

3. Какая  связь между алгеброй логики  и двоичным кодированием?

Математический  аппарат алгебры логики очень  удобен для описания того, как функционируют  аппаратные средства компьютера, поскольку  основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Из этого  следует два вывода:

одни  и те же устройства компьютера могут  применяться для обработки и  хранения как числовой информации, представленной в двоичной системе  счисления, так и логических переменных;

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

Схема И реализует конъюнкцию двух или  более логических значений.

Схема ИЛИ реализует дизъюнкцию двух или  более логических значений.

Схема НЕ (инвертор) реализует операцию отрицания.

Схема И-НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И.

Схема ИЛИ-НЕ состоит из элемента ИЛИ и  инвертора и осуществляет отрицание  результата схемы ИЛИ.

ПРАКТИКА

5. Что  такое триггер?

Триггер — это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер  имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному  нулю.

Электронной схемы способна почти мгновенно переходить (“перебрасываться”) из одного электрического состояния в другое и наоборот.

Самый распространённый тип триггера —  так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс). Условное обозначение триггера — на рис. 5.6.

 
Рис. 5.6

Он имеет  два симметричных входа S и R и два  симметричных выхода Q и  , причем выходной сигнал Q является логическим отрицанием сигнала .

На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных  импульсов ( ).

Наличие импульса на входе будем считать  единицей, а его отсутствие —  нулем.

На рис. 5.7 показана реализация триггера с помощью  вентилей ИЛИ-НЕ и соответствующая  таблица истинности.

   Рис. 5.7

Проанализируем  возможные комбинации значений входов R и S триггера, используя его схему  и таблицу истинности схемы ИЛИ-НЕ (табл. 5.5).

Если  на входы триггера подать S=“1”, R=“0”, то (независимо от состояния) на выходе Q верхнего вентиля появится “0”. После  этого на входах нижнего вентиля  окажется R=“0”, Q=“0” и выход  станет равным “1”.

Точно так же при подаче “0” на вход S и “1” на вход R на выходе появится “0”, а на Q — “1”.

Если  на входы R и S подана логическая “1”, то состояние Q и не меняется.

Подача  на оба входа R и S логического “0”  может привести к неоднозначному результату, поэтому эта комбинация входных сигналов запрещена.

Поскольку один триггер может запомнить  только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 • 210 = 8192 триггеров. Современные  микросхемы памяти содержат миллионы триггеров.

6. Что  такое сумматор?

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

Сумматор  служит, прежде всего, центральным узлом  арифметико-логического устройства компьютера, однако он находит применение также и в других устройствах  машины.

Многоразрядный  двоичный сумматор, предназначенный  для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров. Условное обозначение одноразрядного сумматора  на рис. 5.8.

 
Рис. 5.8

При сложении чисел A и B в одном i-ом разряде приходится иметь дело с тремя цифрами:

1. цифра  ai первого слагаемого;

2. цифра  bi второго слагаемого;

3. перенос  pi–1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра  ci для суммы;

2. перенос  pi из данного разряда в старший.

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

Если  требуется складывать двоичные слова  длиной два и более бит, то можно  использовать последовательное соединение таких сумматоров, причём для двух соседних сумматоров выход переноса одного сумматора является входом для  другого.

Например, схема вычисления суммы C = (с3 c2 c1 c0) двух двоичных трехразрядных чисел A = (a2 a1 a0) и B = (b2 b1 b0) может иметь вид:

10. Физические принципы  работы внешних  устройств и их  характеристики. Порты  ввода - вывода. Работа микропроцессора с внешними устройствами.

11. Классическая архитектура  ЭВМ и тенденции  их развития. Система  команд и способы  обращения к данным. Шинная архитектура.

Опр.:  Архитектура - концепция взаимосвязи элементов сложной структуры. Включает компоненты логической, физической и программной структур. Архитектура фон-Неймана - Организация ЭВМ, при которой вычислительная машина состоит из двух основных частей: линейно-адресуемой памяти, слова которой хранят команды и элементы данных, и процессора, выполняющего эти команды.

Принципы  Фон-Неймана:

Были  сформулированы в 40-х годах нашего столетия.

I принцип  - принцип произвольного доступа  к основной памяти.

Структурно  основная память состоит из дискретных элементов - ячеек, каждая из которых  может содержать упорядоченный  набор символов, называемый словом. Принцип состоит в том, что  процессору в произвольный момент времени  доступна любая ячейка, причем время  доступа (время чтения или записи информации) одинаково для всех ячеек. Чтобы обеспечить такой доступ к  ячейкам памяти, с каждой из них  связывают персональное имя и обращение к ячейке производится с помощью указания ее имени (адреса). Для этого все ячейки основной памяти пронумеровывают от 0 до N-1 и в качестве имени ячейки используют ее порядковый номер - адрес ячейки. При этом общее число ячеек (N) называют объемом основной памяти. Принцип произвольного доступа выделяет основную память среди других запоминающих устройств ЭВМ.

II принцип  - фундаментальный принцип фон-Неймана  - принцип хранимой программы.  Программа решения задачи хранится  в основной памяти наряду с  обрабатываемыми данными. Именно  это делает ЭВМ универсальным  средством обработки информации - для решения другой задачи  требуется смена в основной  памяти программы и обрабатываемых  данных. Информация, хранимая в основной  памяти, не имеет признаков принадлежности  к определенному типу. Поэтому  ЭВМ, вообще говоря, не различает,  что именно хранится в данной  ячейке памяти - число, текст или  команда. Это означает, в частности,  что над командами программы  могут выполняться такие же  действия, как над данными. Так,  команды одной программы могут  быть получены как результаты  исполнения другой программы.  На этом принципе основаны  методы трансляции программы  с одного языка программирования  на другой.