Часть 4

План лекции

1. Основные определения  2. Логические операции  3. Законы логики

4. Формы логических функций

5. Совершенные формы записи логических функций скнф и сднф

Логика — это наука о формах и способах мышления.

Аристотель (384 — 322 гг. до н.э.)

Древнегреческий философ и учёный. Ученик Платона. С 343 г. до н.э. — воспитатель Александра Македонского. 8 335/4 г. до н.э. основал Ликей (Лицей, или перипатетическую школу). Основоположник формальной логики. Создал понятийный аппарат, который до сих пор пронизывает философский лексикон и сам стиль научного мышления.

Основными формами мышления являются:

- Понятие

- Высказывание

- Умозаключение

Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо истинно либо ложно.

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

В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «истина» (1) и «ложь» (О).

Джордж Буль (1815 — 1864 гг.)

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

Основные логические операции:

- Инверсия  - Дизъюнкция

- Конъюнкция

- Импликация

- Эквивалентность

-Неравнозначность

1. Логическое умножение (конъюнкция)

Объединение двух (или нескольких)  высказываний в одно с помощью союза «и»  называется операцией логического умножения или конъюнкцией. Составное высказывание, образованное  в результате операции логического умножения (конъюнкции), истинно тогда и только тогда,  когда истинны все входящие в него простые высказывания. Конъюнкцию принято обозначать значком  «/\» либо «&».

F=A&B

где F — функция,

А, В — логические переменные, которые могут принимать значения «истина» (1) и «ложь» (0).

2. Логическое сложение (дизъюнкция)

Объединение двух (или нескольких)  высказываний с помощью союза «или»  называется операцией логического сложения или дизъюнкцией. Операции логического сложения  (дизъюнкцию) принято обозначать значком  «v» либо знаком сложения «+».

F=AvB

где F — функция,

А, В — логические переменные, которые могут принимать значения «истина» (1) и «ложь» (О).

3. Логическое отрицание (инверсия)

Присоединение частицы «не» к  высказыванию называется операцией  логического отрицания или инверсией. Логическое отрицание (инверсия) делает истинное высказывание ложным  и, наоборот, ложное — истинным.

Операции логического отрицания  (инверсию) над логическим высказыванием А в алгебре логики принято обозначать , либо !А, либо -А.

F=A

Законы

Закон тождества

Всякое высказывание тождественно самому себе.

А=А

Закон противоречия

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

&А=0

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

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

A v =1

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

Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:

=А

Законы де Моргана

Именем английского логика XIX в.  А. де Моргана называются логические законы,  связывающие с помощью отрицания  высказывания, образованные с помощью союзов «и» и «или».

=&

=v

Закон коммутативности (переместительный)

От изменения мест переменных значение функции не меняется.

Логическое умножение: А & В=В & А

Логическое сложение: A v B =B v A

Закон ассоциативности (сочетательный)

От изменения первоочередности  вычислений значение функции не  меняется.

Логическое умножение: (А&В)&С=А&(В&C)

Логическое сложение: (AvВ)vС=Аv(ВvC)

Закон дистрибутивности

Дистрибутивность умножения относительно сложения:

ab+ac=a(b+c) — в алгебре (А & В) v (А & С)= А & (В v C)

Дистрибутивность сложения относительно умножения:

(AvB)&(AvC)=Av(B&C)

Закон идемпотентности (отсутствие степеней и коэффициентов)

Логическое умножение: А&А=А

Логическое сложение: AvA=A

Логическое умножение: А & 1=А; А & 0= 0

Логическое сложение: A v1=1; A v 0 = A

Решение логической задачи:

Определите истинность составного высказывания

(2 х 2 = 4 и 3 х 3 = 10) или (2 х 2= 5 и 3 х 3 = 9)

Замените простые высказывания логическими  переменными и установите их истинность или ложность.

А: «2 х 2 = 4» — истинно (1),

В: «3 х 3 10» — ложно (О),

С; «2x 2=5» — ложно(0),

D: «3 х 3 = 9» — истинно (1).

Замените логические связи «и» и «или» операциями  умножения и логического сложения. Тогда составное  высказывание примет вид следующего логического выражения:

(A&B)v(C&D)

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

(1&0)v(0&1)=0v0=v

Результат: составное высказывание ложно.

Для исключения неоднозначности  записи логические функции представляют  в унифицированных формах. Такими  формами являются: дизъюнктивная и  конъюнктивная.

Элементарной называется конъюнкция,  в которую входят только переменные и их  отрицания, например,

x1x2; x1; * ; x1x2;

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

x1+x2; x1+; x1++.

В элементарные конъюнкции (дизъюнкции) не могут входить одинаковые переменные, а также переменные с их отрицаниями. Такие дизъюнкции (конъюнкции) должны преобразовываться. При  этом они упрощаются, а также превращаются в 0 или 1.

Дизъюнктивная нормальная форма (ДНФ) — это форма, в которой логическая функция  представляется в виде дизъюнкции элементарных  конъюнкций

Конъюнктивной нормальной формой (КНФ) называется такая форма, в которой функция представляется в виде конъюнкции элементарных дизъюнкций.

Использование нормальных форм  не устраняет полностью неоднозначности  записи логических функций.

Применяются совершенная  дизъюнктивная и совершенная  конъюнктивная нормальные формы

(СДНФ и СКНФ).

Формы СДНФ и СКНФ имеют две отличительные особенности:

1. Все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг

2. В элементарные конъюнкции (дизъюнкции) входят все те переменные или их отрицания, от которых зависит функция

Правило записи СДНФ функции по таблице истинности

Для всех наборов переменных, на которых  функция принимает единичные значения,  записать конъюнкции, инвертируя те переменные, которым соответствуют нулевые  значения. Затем конъюнкции соединить знаками  дизъюнкции.

Правило записи СКНФ функции по таблице истинности

Для всех наборов переменных, на которых  функция принимает нулевые значения, записать дизъюнкции, инвертируя те переменные,  которым соответствуют единичные значения. Затем дизъюнкции соединить знаками конъюнкции.

1. Правило поглощения

Данное правило является следствием из  распределительного закона. Оно может быть  записано в следующем виде: x1+x1x2+x1x2x3=x1

2. Правило свертки

Правило является следствием второго распределительного закона: x1+x2=x1+x2; +x1x2=+x2

3. Правило расширения

Правило записывается в следующем виде: x1x2+x3+x2x3=x1x2+x3;

Понятие расширения объясняется возможностью добавления к правой части конъюнкции х2х3.

4. Правило склеивания

Правило склеивания базируется на  понятии соседних конъюнкций. Соседними  называются конъюнкции, отличающиеся  представлением одной переменной. Например,  конъюнкции х1х2х3 и х1х3, и х1 являются попарно соседними. В первой паре конъюнкции отличаются представлением х2, а во второй — представлением х1.

Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкции склеиваются.

Пример:

Задана логическая функция в СДНФ

F = x1+  Необходимо упростить функцию. Так как конъюнкции функции соседние и отличаются представлением х„то путем их склеивания получаем

F = .

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

1. Инверсия  2. Конъюнкция  3. Дизъюнкция  4. Равнозначность

Часть 6

7. Обозначение логических элементов.

8. Двоичные сумматоры.

9. Арифметико-логическое устройство.

10. Триггеры: RS-триггер, D-триггер, JK-триггер.

11. Регистры.

12. Счетчики.

1)

2) Двоичными сумматорами называют логические устройства, выполняющие операцию сложения двух чисел, представленных в двоичном коде.

Различают следующие сумматоры:

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

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

Одноразрядные двоичные сумматоры.

В цифровых устройствах применяются одноразрядные суммирующие схемы на два и три входа, причем первую называют полусумматором, вторую - полным одноразрядным сумматором.

Рассмотрим синтез полусумматоров, имеющих два входа а и b. Выходными сигналами такого устройства являются сумма S и перенос Р, которые вырабатываются согласно таблице функционирования данного устройства.

a b S P

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

Из таблицы следует, что полусумматор описывается двумя переключательными функциями:

S = not(a)*b + a*not(b), P = a*b.

Составим таблицу функционирования полного одноразрядного сумматора:

3) Арифметико-логическое устройство (АЛУ) – важнейшая часть процессора. Оно позволяет выполнять разнообразные арифметические и логические операции над операндами.

Два многоразрядных операнда (числа, буквы, символы и т.д.), подлежащие обработке в АЛУ, подаются на входы А и В. Результат выполнения операции появляется на выходе F. Вид операции, выполняемой в АЛУ, определяется сигналами, которые подаются на входы S и M. Увеличить разрядность АЛУ можно за счет использования нескольких секций (микросхем) и двух специальных шин C0 и Cn+1.

Работу четырехразрядного АЛУ можно описать выражением:

в этой формуле индексами i отмечены номера разрядов операндов A и B и выходного сигнала F.

Если на управляющие входы такого АЛУ подать сигналы M = 1, S3 = 1, S2 = 0, S1 = 1, S0 = 1, то АЛУ будет выполнять логическое умножение Ai и Bi. Этот результат получается при подстановке исходных данных в приведенную формулу. Изменяя пять управляющих сигналов M, S3,…S0, можно «заставить» такое АЛУ выполнить 32 различные операции (16 логических и 16 арифметических).Так присутствие на управляющих входах двоичного числа M = 0, S3 = 1, S2 = 0, S1 =0, S0 = 1 заставит АЛУ выполнить арифметическое сложение чисел, поступивших на шины A и B, и к полученному результату прибавить значение переноса из предыдущей секции, то есть Fi = Ai + Bi + C0.

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

Триггер типа RS "запоминает", на какой из двух входов (R или S) поступил последний сигнал: если на вход R, триггер находится в нулевом состоянии (Q = 0 и /Q = 1), а если на вход S, то в единичном состоянии (Q = 1 и /Q = 0). ( S(set) – установить в 1; R(reset) – сбросить в 0; R&S=0 – хранить содержимое)

Работа RS-триггера характеризуется следующей таблицей состояний:

Rn Sn Qn+1 /Qn+1

0 0 Qn /Qn

0 1 1 0

1 0 0 1

1 1 неопределенное состояние

Состояние D-триггера считывается с информационного входа D во время прихода тактового импульса на второй вход С.

Триггер типа JK отличается от триггера RS тем, что допускается на входе два одновременно высоких сигнала. При этом состояние триггера меняется на противоположное.

5) Регистр – многоразрядное устройство , состоящее из элементов памяти, способное выполнять следующие функции:

•обнуление регистра

•установка регистра в некоторый код (начальное условие),

•передача информации (например, из одного регистра в другой),

•хранение информации,

•прием информации,

•преобразование прямого кода в обратный код и наоборот,

•преобразование последовательного кода в параллельный код и наоборот,

•поразрядная дизъюнкция,

•поразрядная конъюнкция,

•поразрядное сложение по модулю 2.

Наиболее часто регистры предназначаются для приема, хранения и передачи информации. Последняя в регистре хранится в виде двоичного кода, каждому разряду которого соответсвует свой элемент памяти(разряд регистра), выполненный на основе триггеров RS-, JK- или D-типа.

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

Цифровую схему, выполняющую функцию счёта, можно собрать из триггеров. В связи с очень широким применением таких схем фирмы-изготовители выпускают счетчики в виде монолитных ИС.

6) Почти каждая сложная цифровая система содержит несколько счетчиков. Назначение счетчиков очевидно: это подсчет числа некоторых событий или временных интервалов, либо упорядочение событий в хронологической последовательности. Кроме того, счетчики могут выполнять и не столь очевидные функции: их, например, можно использовать для адресации, в качестве делителей частоты и элементов памяти.

Недостатком является то , что задержка последовательного счетчика равна mt, где m – число разрядов последовательного счетчика, t – задержка триггера. Т.е. последовательный счетчик – медленное устройство. Каждый старший разряд формируется только после получения информации от предыдущего младшего разряда. Этот недостаток можно устранить, используя параллельные счетчики.

Часть 7

1.О понятии архитектура ЭВМ.

2.Классическая архитектура, принципы фон Неймана.

3.Совершенствование и развитие внутренней структуры ЭВМ.

4. Основной цикл работы ЭВМ.

5. Способы указания адреса расположения информации.

6. Система команд и способы обращения к данным.

7. Классификация средств вычислительной техники.

8. Состав и назначение основных элементов компьютера.

1.О понятии архитектура ЭВМ.

Электронная вычислительная машина (ЭВМ) - комплекс технических и программных средств, предназначенный для автоматизации подготовки и решения задач пользователя. Программные средства ЭВМ взаимосвязаны и объединяются в одну структуру.

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

Архитектура ЭВМ - это многоуровневая иерархия аппаратурно-программных средств, из которых строится ЭВМ. Каждый из уровней допускает многовариантное построение и применение. Конкретная реализация уровней определяет особенности структурного построения ЭВМ.