13. Булева алгебра и логические схемы компьютера.

Алгебра высказываний (булева алгебра)

Основные понятия

Основное понятие булевой алгебры — выказывание. Под простым

высказыванием понимается повествовательное предложение, о

котором можно сказать, истинно оно или ложно (третьего не дано).

Высказывания обозначаются латинскими буквами и могут принимать

одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА

(обозначим 1). Например, содержание высказывания А: «дважды два равно

четырем» истинно А = 1, а высказывание В: «три больше пяти»

всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать

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

высказывания А и В называются равносильными, если они имеют

одинаковые значения истинности, записывается А = В.

Логические операиии

Сложное высказывание можно построить из простых с помощью

логических операций: отрицания, конъюнкции, дизъюнкции, импликации

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

логических операций. Рассмотрим их подробней.

Операцией отрицания А называют высказывание А (или -А,

говорят не А), которое истинно тогда, когда А ложно, и ложно тогда,

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

«завтра будет снег», то А «завтра НЕ будет снега», истинность одного

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

Отрицание — унарная (т.е. для одного операнда) логическая операция. Ей

соответствует языковая конструкция, использующая частицу НЕ.

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В

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

когда истинны оба высказывания, записывается С = А л В или С = А & В

(при этом говорят С равно А и В). Примером такой операции может

быть следующая: пусть высказывание А состоит в том, что «высота

шкафа меньше высоты двери», событие В «ширина шкафа меньше

ширины двери», событие С «шкаф можно внести в дверь, если

ширина шкафа меньше ширины двери И высота шкафа меньше

высоты двери», т.е. данная операция применяется, если два

высказывания связываются союзом И.

Дизъюнкцией (логическим сложением) двух высказываний А и В

является новое высказывание С, которое истинно, если истинно хотя

бы одно высказывание. Записывается С = A v В (при этом говорят:

С равно А ИЛИ В). Пример такой операции следующий: пусть

высказывание А состоит в том, что «студент может добираться домой

на автобусе», событие В «студент может добираться домой на

троллейбусе», событие С «студент добрался домой на автобусе ИЛИ

троллейбусе», т.е. данная операция применяется, если два высказывания

связываются союзом ИЛИ.

Импликацией двух высказываний А (А называется посылкой) и В

(В называется заключением) является новое высказывание С,

которое ложно только тогда, когда посылка истинна, а заключение

ложно, записывается С = А —> В (при этом говорят: из А следует В).

Примером такой операции может быть любое рассуждение типа:

если произошло событие А, то произойдет событие В, «если идет

дождь, то на небе тучи». Очевидно, операция не симметрична, т.е.

из В —> А не всегда истинно, в нашем примере «если на небе тучи,

то идет дождь» не всегда истинно.

Импликация имеет следующие свойства:

А-»В*В -> А

А->А= 1

Зависимости межЭу логическими опероииоми

Операции не являются независимыми; одни из них могут быть

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

истинности следующие равносильности:

1. А = А закон двойного отрицания

2. А&В = В&А коммутативный закон для конъюнкции

3. AvB = BvA коммутативный закон для дизъюнкции

4. (А & В) & С = А & (В & С) ассоциативный закон для

конъюнкции

5. (AvB)vC = Av(BvC) ассоциативный закон для

дизъюнкции

6. А & (В v С) = (А & В) v (А & С) дистрибутивные законы

7. A v (В & С) = (A v В) & (A v С)

8. А&В = A v В законы де Моргана

9. AvB = А & В

10. А & А = А закон идемпотенции для конъюнкции

11. A v A = А закон идемпотенции для дизъюнкции

12. А & 1 = А закон единицы для конъюнкции

13. А & 0 = 0 закон нуля для конъюнкции

14. A v 1 = 1 закон единицы для дизъюнкции

15. A v 0 = А закон нуля для дизъюнкции

16. A v А = 1 закон исключения третьего

17. А & А = 0 закон противоречия

18. А -> В = A v В

19. А <-» В = (А -> В) & (В -> А) = ( A v В) & ( A v В ) =

= (A&B)v(A & В)

20. A v (А & В) = А законы поглощения

21. А & (A v В) = А

22. А&(А vB) = A&B

23. Av (A & В) = Av В

Одну и ту же зависимость между логическими переменными

можно выразить различными формулами. Поэтому важно иметь

возможность приводить формулы с помощью эквивалентных

преобразований к некоторому стандартному виду. Существует несколько

стандартных форм, к которым приводятся логические выражения с

помощью эквивалентных преобразований (формул 1—23).

Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет

вид Al v A2 v ... v An, где каждое из составляющих высказываний

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

В = ( А1 & А2 & A3) v (А4 & А5).

Вторая — конъюнктивная нормальная форма (КНФ), имеет вид

А1 л А2 а ... a An, где каждое из составляющих есть

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

В = ( Al v А2 v A3) & (А4 v А5) & А6.

Табличное и алгебраическое задание булевских функиий .

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

всех наборов значений аргументов. Каждый аргумент может иметь два

значения: 0 и 1, следовательно, п аргументов могут принимать 2П

различных наборов.

Билет 14. Элементы организации основных блоков компьютера.

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

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

Структура компьютера – это некоторая модель, устанавливающая состав, порядок и принципы взаимодействия входящих в неё компонентов.

  Персональный компьютер – это настольная или переносная ЭВМ, удовлетворяющая требованиям общедоступности и универсальности применения.

Достоинствами ПК являются:

1) Малая стоимость, находящаяся в пределах доступности для индивидуального

покупателя

2) Автономность эксплуатации без специальных требований к условиям окружающей среды

3) Гибкость архитектуры. Обеспечивающая её адаптивность к разнообразным применениям в сфере управления, науки, образования, в быту

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

5) высокая надёжность работы (более 5 тыс. ч наработки на отказ)

  Структура персонального компьютера

Рассмотрим состав и назначение основных блоков ПК.

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

В состав микропроцессора входят: 

1) устройство управления (УУ) – формирует и подает во все блоки машины в нужные моменты времени спецификой выполняемой операции и результатами предыдущих операций; формирует адреса ячеек памяти. Используемых выполняемой операцией, и передаёт эти адреса в соответствующие блоки ЭВМ; опорную последовательность импульсов устройство управления получает от генератора тактовых импульсов

2) арифметико–логическое устройство (АЛУ) – предназначено для выполнения всех арифметических и логических операций над числовой и символьной информацией (в некоторых моделях ПК для ускорения выполнения операций к АЛУ подключается дополнительный математический процессор)

3) микропроцессорная память (МПП) – служит для кратковременного хранения, записи и выдачи информации, непосредственно используемой в вычислениях в ближайшие такты работы машины. VGG строится на регистрах и используется для обеспечения высокого быстродействия машины, ибо основная память (ОП) не всегда обеспечивает скорость записи, поиска и считывая информации, необходимую для эффективной работы быстродействующего микропроцессора. Регистры – быстродействующие ячейки памяти различной длины (в отличие от ячеек ОП, имеющих стандартную длину 1 байт и более низкое быстродействие)

4) интерфейсная система микропроцессора – реализует сопряжение и связь с другими устройствами ПК; включает в себя внутренний интерфейс МП, буферные запоминающие регистры и схемы управления портами ввода – вывода (ПВВ) и системной шиной. Интерфейс (Interface) – совокупность средств сопряжения и связи устройств компьютера, обеспечивающая их эффективное взаимодействие. Порт ввода – вывода (I/O – Input / Output port) – аппаратура сопряжения, позволяющая подключить к микропроцессору другое устройство ПК.

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

Системный блок обычно включает в себя системную плату, блок питания, накопители на дисках, разъёмы для дополнительных устройств и платы расширения с контроллерами – адаптерами внешних устройств.

На системной плате (часто её называют материнской платой), как правило, размещаются:

Микропроцессор

Математический сопроцессор

Генератор тактовых импульсов

Блоки (микросхемы) ОЗУ и ПЗУ

Адаптеры клавиатуры, НЖДМ и НГМД

Контроллер прерываний

Таймер, и др.