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

AND (И) - логическое умножение

Команда выполняет поразрядную конъюнкцию (логическое умножение - операцию «AND») битов двух чисел; устанавливает 1 в тех битах результата, в которых у обоих исходных операндов были 1. Таблица истинности операции «AND»:

NOT (НЕ) - операция отрицания

Команда устанавливает обратное значение битов в числе (операция инверсии). Таблица истинности операции «NOT».

A
NOT A

Вопросы для самопроверки

1. Что такое алгебра логики?

2. Рассмотрите сферу использования алгебры логики в компьютерных системах.

3. Разберите процесс логического синтеза вычислительных схем.

4. Рассмотрите взаимные структурные конструкции логических схем OR, AND, NOT и NAND.

5. Назовите некоторые системы электронных элементов, на базе которых конструировались компьютеры.

6. В Что такое полевой транзистор? Рассмотрите его структуру и принцип работы.

7. Сравните между собой биполярные и униполярные транзисторы.

8. В чем основные достоинства схем на КМОП транзисторах?

9. Какие основные способы и технологии используются для обеспечения возможности повышения тактовой частоты микросхем?

10. Что представляет собой элемент оперативной памяти на полевых транзисторах?

11. В чем особенности структуры элемента флэш-памяти?

12. Что такое триггер? Нарисуйте его логическую структуру.

13. Рассмотрите принцип хранения информации на магнитных элементах FeRAM и МRAM.

14. Рассмотрите структурные логические схемы регистра, счетчика, дешифратора.

15. Выполните логические операции OR, AND, XOR и NOT над двоичными числами.

Раздел 3 Архитектура персонального компьютера

Глава 7. Основные блоки ЭВМ и их назначение

После изучения главы студент должен знать:

· структурную схему персонального компьютера,

· назначение и функции основных блоков компьютера,

· состав и функции устройств, входящих в состав микропроцессора,

· состав и иерархию запоминающих устройств ПК,

· назначение всех типов запоминающих устройств ПК,

· состав и назначение внешних устройств ПК,

· основные конструктивные компоненты ПК,

· основные функциональные характеристики ПК.

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

Структурная схема ЭВМ

Структурная схема персонального компьютера (ПК) представлена на рис. 7.1.

Рис. 7.1. Структурная схема ПК

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

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

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

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

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

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

Интерфейс (interface) - совокупность средств сопряжения и связи устройств компьютера, обеспечивающая их эффективное взаимодействие.

Порты вода-вывода (I/O ports) - элементы системного интерфейса ПК, через которые МП обменивается информацией с другими устройствами.

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

Системная шина

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

· кодовую шину данных (КШД), содержащую провода и схемы сопряжения для параллельной передачи всех разрядов числового кода (машинного слова) операнда;

· кодовую шину адреса (КША), содержащую провода и схемы сопряжения для параллельной передачи всех разрядов кода адреса ячейки основной памяти или порта ввода-вывода внешнего устройства;

· кодовую шину инструкций (КШИ), содержащую провода и схемы сопряжения для передачи инструкций (управляющих сигналов, импульсов) во все блоки машины;

· шину питания, содержащую провода и схемы сопряжения для подключения блоков ПК к системе энергопитания.

Системная шина обеспечивает три направления передачи информации:

· между микропроцессором и основной памятью;

· между микропроцессором и портами ввода-вывода внешних устройств;

· между основной памятью и портами ввода-вывода внешних устройств (в режиме прямого доступа к памяти).

Все блоки, а точнее их порты ввода-вывода, через соответствующие унифицированные разъемы (стыки) подключаются к шине единообразно: непосредственно или через контроллеры (адаптеры). Управление системной шиной осуществляется микропроцессором либо непосредственно, либо, что чаще, через дополнительную микросхему контроллерашины, формирующую основные сигналы управления. Обмен информацией между внешними устройствами и системной шиной выполняется с использованием ASCII-кодов.

Основная память

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

ПЗУ (ROM - Read Only Memory) предназначено для хранения неизменяемой (постоянной) программной и справочной информации; позволяет оперативно только считывать информацию, хранящуюся в нем (изменить информацию в ПЗУ нельзя);

ОЗУ (RAM - Random Access Memory) предназначено для оперативной записи, хранения и считывания информации (программ и данных), непосредственно участвующей в информационно-вычислительном процессе, выполняемом ПК в текущий период времени.

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

Кроме основной памяти на системной плате ПК имеется и энергонезависимая памятьCMOS RAM (Complementary Metal-Oxide Semiconductor RAM), постоянно питающаяся от своего аккумулятора; в ней хранится информация об аппаратной конфигурации ПК (обо всей аппаратуре, имеющейся в компьютере), которая проверяется при каждом включении системы.

Внешняя память

Внешняя память относится к внешним устройствам ПК и используется для долговременного хранения любой информации, которая может когда-либо потребоваться для решения задач. В частности, во внешней памяти хранится все программное обеспечение компьютера. Внешняя память представлена разнообразными видами запоминающих устройств, но наиболее распространенными из них, имеющимися практически на любом компьютере, являются показанные на структурной схеме накопители на жестких (НЖМД) и гибких (НГМД) магнитных дисках. Назначение этих накопителей: хранение больших объемов информации, запись и выдача информации по запросу в оперативное запоминающее устройство. Различаются НЖМД и НГМД конструктивно, объемами хранимой информации и временем ее поиска, записи и считывания. В качестве устройств внешней памяти часто используются также накопители на оптических дисках (CD - Compact Disk, DVD – Digital Versatile Disk), накопители на флэш-дисках и реже - запоминающие устройства на кассетной магнитной ленте (НКМЛ, стримеры) и накопители на магнитооптических дисках (НМОД).

Источник питания

Источник питания - блок, содержащий системы автономного и сетевого энергопитания ПК.

Таймер

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

Внешние устройства

Внешние устройства (ВУ) ПК - важнейшая составная часть вычислительного комплекса, стоимость которых составляет до 80–85% стоимости ПК. Они обеспечивают взаимодействие машины с окружающей средой: пользователями, объектами управления и другими компьютерами, это:

· внешние запоминающие устройства (ВЗУ), внешняя память;

· диалоговые средства пользователя;

· устройства ввода информации;

· устройства вывода информации;

· средства связи и телекоммуникаций.

К диалоговым средствам пользователя относятся:

· видеомонитор(видеотерминал, дисплей) - устройство для отображения вводимой и выводимой из ПК информации;

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

К устройствамввода информации относятся:

· клавиатура - устройство для ручного ввода числовой, текстовой и управляющей информации в ПК;

· графические планшеты (дигитайзеры) - устройства для ручного ввода графической информации, изображений путем перемещения по планшету специального указателя (пера); при перемещении пера автоматически выполняется считывание координат его местоположения и ввод этих координат в ПК;

· сканеры (читающие автоматы) - оборудование для автоматического считывания с бумажных и пленочных носителей и ввода в ПК машинописных текстов, графиков, рисунков, чертежей;

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

· сенсорные экраны - для ввода отдельных элементов изображения, программ или команд с экрана дисплея в ПК.

Кустройствамвывода информации относятся:

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

· графопостроители (плоттеры) - устройства для вывода графической информации (графиков, чертежей, рисунков) из ПК на бумажный носитель.

Устройства связи и телекоммуникации используются для:

связи с приборами и другими средствами автоматизации (согласователи интерфейсов, адаптеры, цифро-аналоговые и аналого-цифровые преобразователи и т. п.);

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

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

ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

ФОРМЫ МЫШЛЕНИЯ

• ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.

• Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира.

• Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны.

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

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

Основные формы мышления

• Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ.

• ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер.

• Понятие имеет две стороны: содержание и объем.

Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер - это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя».

• Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

• СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях.

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

• «Берн - столица Франции»,

• «Река Кубань впадает в Азовское море»,

• «2>9», «3×5=10»

• УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение).

• Все металлы - простые вещества. Литий - металл.→ Литий - простое вещество.

• Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.

АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

Английский математик Джордж Буль (1815 - 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.

ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.

• Например: Земля - планета Солнечной системы . (Истинно) 2+8 (Ложно) 5 · 5=25 (Истинно) Всякий квадрат есть параллелограмм (Истинно) Каждый параллелограмм есть квадрат (Ложно) 2 · 2 =5 (Ложно)

Не всякое предложение является высказыванием: 1) Восклицательные и вопросительные предложения высказываниями не являются. - “Какого цвета этот дом?” - “Пейте томатный сок!” - “Стоп!” 2) Не являются высказываниями и определения. “Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны”. Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов. 3) Не являются высказываниями и предложения типа “Он сероглаз” или

• “х- 4х + 3=0” - в них не указано о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называются высказывательными формами.

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

.

• В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1 . Если высказывание истинно, то его значение равно 1, если ложно - 0.

• Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С… Луна является спутником Земли . А = 1 Москва – столица Германии . В = 0

• Сложные высказывания называются логическими функциями . Значения логической функции также может принимать значения только 0 или 1.

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

• В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.

1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ)

• соответствует частице НЕ

• обозначается черточкой над именем переменной или знаком ¬ перед переменной

• Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

• Таблица истинности инверсии имеет вид:

2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ )

• соответствует союзу ИЛИ

• обозначается знаком v или + или ║

• Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А v В v С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид:

3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ)

• соответствует союзу И

• обозначается знаком & или Λ, или ·

• Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид:

ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ

• Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими выражениями. Например:

Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Таблицы истинности

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

• При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий:

• 1) записать выражение и определить порядок выполнения операций

• 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формулеQ=2n , где n - количество входных переменных)

• 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций)

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

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

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

• Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов, а значит и строк Q=23=8 . Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения

ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ

• Правила построения логического выражения:

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

• 2. Объединитьвсе минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.

Логические функции

• Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X1,X2, ..., Xn ) аргументами которой являются логические переменные X1, X2, ..., Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0).

• Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = A&B, логическое сложение F(A,B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю.

• Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 24 = 16 различных логических функций двух аргументов.

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

ИМПЛИКАЦИЯ (ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ).

• Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом →

• Запись А → В читается как «из А следует В»

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

• Таблица истинности импликации двух суждений А и В такова:

ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА)

• Она обозначается символами ≡ или. («тогда и только тогда»).

• Запись А ≡ В читается как «А эквивалентно В».

• Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны.

• Таблица истинности эквивалентности двух суждений А и В такова:

Логические законы и правила преобразования логических выражений

• Равносильности формул логики высказываний часто называют законами логики . Законы логики отражают наиболее важные закономерно­сти логического мышления.

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

1. Закон тождества. себе:

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

• Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

• 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должнобыть ложно:

• Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”

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

• Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано.

• “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

• 4. Закон двойного отрицания. Если дважды отрицать неко­торое высказывание, то в результатемы получим исходное высказывание:

• Закон двойного отрицания.Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. “ Неверно, что 2× 2¹ 4”

5. Законы идемпотентности.

• 5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов.

• Конъюнкция одинаковых «сомножителей» равносильна одному из них:

• Дизъюнкция одинаковых «слагаемых» равносильна одному:

• 6. Законы де Моргана:

• Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых;

• отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

7. Правило коммутативности. логического умноженияи логического сложения:

• 7. Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказыва­ний можноменять местами логические переменные при опе­рацияхлогического умноженияи логического сложения:

• Логическое умножение:

• Логическое сложение:

• 8. Правило ассоциативности. Если в логическом выраже­нии используются только операция логического умножения или только операция логического сложения, то можно пре­небрегать скобками или произвольно их расставлять:

• Логическое умножение:

• Логическое сложение:

9. Правило дистрибутивности. общие слагаемые:

• 9. Правило дистрибутивности. В отличие от обычной алгеб­ры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки, как общие множители, так иобщие слагаемые:

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

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

• 12. Законы поглощения:

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

ЗАДАЧА 1.

• ЗАДАЧА 1.

• Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления.

• Батончик: «Я не делал этого. Пончик сделал это»

• Лёнчик: «Пончик не виновен. Батончик сделал это»

• Пончик: «Я не делал этого. Лёнчик не делал этого»

• Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий - один раз солгал, один раз сказал правду. Кто утаил клад?

Задачи для самостоятельного решения

ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

Логические элементы

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

Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых "ложь" и "истина". Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Были созданы устройства управления электричеством - электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока стали называть логическими элементами .

• Логические элементы - это электронные устройства, которые преобразуют проходящие через них двоичные электрические сигналы по определенному закону .

• Логические элементы имеют один или несколько входов, на которые подаются электрические сигналы, обозначаемые условно 0 , если отсутствует электрический сигнал, и 1 , если имеется электрический сигнал.

• Также логические элементы имеют один выход, с которого снимается преобразованный электрический сигнал.

• Было доказано, что все электронные схемы компьютера могут быть реализованы с помощью трёх базовых логических элементов И, ИЛИ, НЕ.

Логический элемент НЕ (инвертор)

Логический элемент ИЛИ (дизъюнктор)

Логический элемент И (конъюнктор)

Функциональные схемы

Таблица истинности функциональной схемы

Логическая реализация типовых устройств компьютера

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

• Выясним, как из логических элементов разрабатываются логические устройства.

Этапы конструирования логического устройства.

• Конструирование логического устройства состоит из следующих этапов:

• 1. Построение таблицы истинности по заданным условиям работы проектируемого узла (т.е. по соответствию его входных и выходных сигналов).

• 2. Конструирование логической функции данного узла по таблице истинности, ее преобразование (упрощение), если это возможно и необходимо.

• 3. Составление функциональной схемы проектируемого узла по формуле логической функции.

• После этого остается только реализовать полученную схему.

Полный одноразрядный сумматор .

ТРИГГЕР

RS-триггер

RS-триггер

с углубленным изучением французского языка»

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

Учебное пособие по информатике

для 10 класса

Содержание

§1. Основы логики…………………………………..…….………3

§ 2. Логические операции……………………………..…..….…..5

§ 3. Логические формулы. Таблица истинности логической формулы……………………………………………..…..…...….….8

§ 4. Основные законы алгебры логики. Упрощение логических формул…………………….....……………....………11

§ 5. Решение логических задач…………………………...…….13

§ 6. Логическая функция…………………………...………..….18

§ 7. Логические основы ЭВМ. Базовые логические элементы………………………………..………………………….21

§ 8. Логические элементы компьютера. Триггер и сумматор...........................................................................................25

Вопросы для самоконтроля…………..……...…………….29

§ 1. Основы логики.

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

Сам термин «логика» происходит от древнегреческого logos , означающего «слово, мысль, понятие, рассуждение, закон».

Логика – наука о законах и формах мышления.

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

К основным понятиям логики относятся следующие.

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

Так, например, предложение "6 - четное число " следует считать высказыванием, так как оно истинное. Предложение "Рим - столица Франции " тоже высказывание, так как оно ложное.

Утверждение - это суждение, которое требуется доказать или опровергнуть.

Например, любая теорема – это утверждение, требующее доказательства.

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

Например, ход доказательства какой-либо теоремы можно назвать рассуждением.

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

В дедуктивных умозаключениях рассуждения ведутся от общего к частному. Например, из двух суждений: «Все металлы электропроводны» и «Ртуть является металлом» можно сделать вывод, что «Ртуть электропроводна».

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

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

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

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

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

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

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

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля . Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Алгебра логики рассматривает любое высказывание только с одной точки зрения - является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания . Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн. кв. км " в одной ситуации можно посчитать ложным, а в другой - истинным. Ложным - так как указанное значение неточное и вообще не является постоянным. Истинным - если рассматривать его как некоторое приближение, приемлемое на практике.

§ 2. Логические операции.

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

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

Так, например, из элементарных высказываний "Петров - врач ", "Петров - шахматист " при помощи связки "и " можно получить составное высказывание "Петров - врач и шахматист ", понимаемое как "Петров - врач, хорошо играющий в шахматы ".

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В - высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В . Здесь "и" - логическая связка, А, В - логические переменные, которые могут принимать только два значения - "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio - соединение) или логическим умножением и обозначается точкой " . " (может также обозначаться знаками  или &).

Высказывание А . В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" - ложны.

Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio - разделение) или логическим сложением и обозначается знаком v (или плюсом).

Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" - истинны.

Операция, выражаемая словом "не", называется логическим отрицанием или инверсией и обозначается чертой над высказыванием (или знаком  ).

Высказывание  А истинно, когда A ложно, и ложно, когда A истинно.

Например, "Луна - спутник Земли " (А) - истинно; "Луна - не спутник Земли " ( А ) - ложно.

Операция, выражаемая связками "если..., то", "из... следует", "... влечет...", называется импликацией (лат. implico - тесно связаны) и обозначается знаком  .

Высказывание А  В ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания?

Покажем это на примере высказываний: "данный четырёхугольник - квадрат" (А ) и "около данного четырёхугольника можно описать окружность" (В ). Рассмотрим составное высказывание А  В , понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность".

Есть три варианта, когда высказывание А  В истинно:

А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

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

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

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

Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "...равносильно...", называется эквиваленцией или двойной импликацией и обозначается знаком  или ~.

Высказывание А  В истинно тогда и только тогда, когда значения А и В совпадают.

Например, высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 5", "21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

Высказывания А и В, образующие составное высказывание А  В , могут быть совершенно не связаны по содержанию, например: "три больше двух" (А ), "пингвины живут в Антарктиде" (В ). Отрицаниями этих высказываний являются высказывания "три не больше двух" ( А), "пингвины не живут в Антарктиде" ( В). Образованные из высказываний А и В составные высказывания A  B и A   B истинны, а высказывания A   B и  A  B - ложны.

§ 3. Логические формулы. Таблица истинности логической

формулы.

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

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

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

Если А и В - формулы, то  A, А. В, А v В, А  B , А  В - формулы.

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

В п. 1 определены элементарные формулы ; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B)  C . Такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика".

Как показывает анализ формулы (A v B)  C , при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях - значение "ложь". Такие формулы называются выполнимыми .

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Например, формула А v  А , соответствующая высказыванию "Этот треугольник прямоугольный или непрямоугольный" истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями . Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А .  А , которой соответствует, например, высказывание "Катя самая высокая девочка в классе, и в классе есть девочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо А обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями . Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

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

Равносильность двух формул алгебры логики обозначается символом "=" Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

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

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

А  В =  Аv В.

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

А  В = ( А v В) . ( Вv А).

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

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

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то таких наборов восемь: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д. Т.е., если N – количество переменных, то 2 N – количество наборов значений переменных.

Таблица истинности элементарных логических формул

Конъюнкция

Дизъюнкция

Инверсия

Импликация

Эквиваленция

х

у

х · у

х

у

х  у

х

 х

х

у

х  у

х

у

х  у

0

0

0

0

0

0

0

1

0

0

1

0

0

1

0

1

0

0

1

1

1

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

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

промежуточных формул.

Примеры.

1. Составим таблицу истинности для формулы х · у   (х  у)  х, которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах - значения промежуточных формул и в последнем столбце - значение формулы.

Переменные

Формула

х

у

 х

 х · у

х  у

 (х  у)

 х · у   (х  у)

 х · у   (х  у)  х

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1 , то есть является тождественно истинной .

2. Таблица истинности для формулы: (х  у) · (х · у)

Переменные

Промежуточные логические формулы

Формула

х

у

х  у

(х  у)

 у

х · у

(х  у) · (х · у)

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0 , то есть является тождественно ложной .

3. Таблица истинности для формулы:  (х   у)   х · z

Переменные

Промежуточные логические формулы

Формула

x

y

z

 у

х   у

 (х   у)

 х

 х · z

(х   у)   х · z

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых - 0, то есть является выполнимой.

§ 4. Основные законы алгебры логики. Упрощение

логических формул.

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

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

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

Закон

Представление

в алгебре логики

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

a  b = b  a, a  b = b  a

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

a  (b  c) = (a  b)  с,

a  (b  c) = (a  b)  c

Распределительный (дистрибутивный)

a  (b  c) = (a  b)  (a  c) ,

a  (b  c) = (a  b)  (a  c)

Правила де Моргана

 (a  b) =  a  b ,

 (a  b) =  a  b

Закон двойного отрицания (инволюции)

  а = а

Операции с переменной и ее инверсией

a   a = 0 , a  a =1

Операции с константами

a  1 = 1 , a  1 = a ,

a  0 = a , a  0 = 0

Законы идемпотентности

a  a = a , a  a = a

Законы поглощения

x  (x  y) = x , x  (x  y) = x

Законы склеивания

(x  y)  ( x  y) = y ,

(x  y)  ( x  y) = y

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

Пример 1.

 (х  у) · (х ·  у) =  х ·  у · (х ·  у) =  х · х ·  у ·  у = 0 ·  у ·  у = 0 ·  у = 0
(Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами).

Пример 2.

 х · у  (х  у)  х =  х · у   х ·  у  х =  х · (у  у)  х =  х  х = 1
(Применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией).

Пример 3.

(х  у) · (  х  у) · (  х   у) = (х  у) · ( х  у) · ( х  у) · ( х   у) = у ·  х
(Повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).

Пример 4.

 (х · у   z ) =  (х · у) ·   z =  (х · у) · z
(Сначаладобиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого применяем правило де Моргана; затем используем закон двойного отрицания);

Пример 5.

х · у  х · у · z  х · р · z = х · (у  у · z  z · р) = х · (у · (1  z )  z · р) =

= х · (у  z · р)

(Выносятся за скобки общие множители; применяется правило операций с константами);

Пример 6.

x ·  y  x · y · z  x ·  y · z  x ·  (y · z) = x · ( y  y · z   y · z   (y · z)) =

= x · (( y  y · z )  (y · z   (y · z )) = x · ( y  y · z  1) = x · 1 = x
(Общий множитель x выносится за скобки, комбинируются слагаемые в скобках - первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

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

§ 5. Решение логических задач.

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

средствами алгебры логики;

табличный;

с помощью рассуждений.

Познакомимся с ними поочередно.

I. Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения :

изучается условие задачи;

вводится система обозначений для логических высказываний;

конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

определяются значения истинности этой логической формулы;

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

Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

- Вот увидишь, Шумахер не придет первым, - сказал Джон. Первым будет Хилл.

- Да нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение.

Введем обозначения для логических высказываний:

Ш - победит Шумахер; Х - победит Хилл; А - победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Джон:  Ш · Х , Ник: Ш ·  А , Питер:  Х

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

( Ш · Х)·(Ш · А) · Х  ( Ш · Х)· (Ш · А)· Х   ( Ш · Х)·(Ш · А)· Х = =( Ш · Х · Ш · А ·Х) ( Ш · Х ·  (Ш · А) ·  Х) (Ш  Х) · Ш · А ·  Х = = 0  0  Ш · А ·  Х = Ш · А ·  Х

Высказывание Ш ·  А ·  Х истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

II. Решение логических задач с помощью таблиц истинности.

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

Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Виссона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

Смит самый высокий;

играющий на скрипке меньше ростом играющего на флейте;

играющие на скрипке и флейте и Браун любят пиццу;

когда между альтистом и трубачом возникает ссора, Смит мирит их;

Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение.

Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна - альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

скрипка

флейта

альт

кларнет

гобой

труба

Браун

Смит

Виссон

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

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Виссон. Оба инструмента, на которых играет Виссон, теперь определены, поэтому остальные клетки строки "Виссон" можно заполнить нулями:

скрипка

флейта

альт

кларнет

гобой

труба

Браун

Смит

Виссон

Из таблицы видно, что играть на флейте и на гобое может только Смит.

скрипка

флейта

альт

кларнет

гобой

труба

Браун

Смит

Виссон

Ответ: Браун играет на альте и кларнете, Смит - на флейте и гобое, Виссон - на скрипке и трубе.

Пример 3. Три одноклассника - Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего - регби.

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

Врач сказал, что он разделяет увлечение коллеги.

Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.

Определите, кто чем любит заниматься в свободное время и у кого какая профессия.

Решение.

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

Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.

Имя

Юра

Профессия

врач

Увлечение

туризм

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно, врач - Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени - Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:

Имя

Юра

Тимур

Влад

Профессия

физик

врач

юрист

Увлечение

бег

туризм

регби

Ответ. Влад - юрист и регбист, Тимур - врач и турист, Юра - физик и бегун.

III. Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 4. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение . Имеется три утверждения:

Вадим изучает китайский;

Сергей не изучает китайский;

Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

Ответ: Сергей изучает китайский язык, Михаил - японский, Вадим - арабский.

Пример 5. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:

Россия - "Проект не наш, проект не США";
США - "Проект не России, проект Китая";
Китай - "Проект не наш, проект России".

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз - неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия - "Проект не наш" (1), "Проект не США" (2);
США - "Проект не России" (3), "Проект Китая" (4);
Китай - "Проект не наш" (5), "Проект России" (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный - министр США, то тогда вновь получаем, что победил китайский проект, значит, оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, следует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее - российский, скрытнее - министр США.

§ 6. Логическая функция.

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

Логической функцией F от набора логических переменных (a , b , c , …) называется функция, которая может принимать только два значения: 0 и 1.

F (a , b ) = a  b - логическое умножение (конъюнкция).

F (a , b ) = a v b - логическое сложение (дизъюнкция).

F (a ) =  a - отрицание (инверсия).

F(a, b) = a  b - импликация.

F (a , b ) = a  b - эквиваленция.

Логические функции можно вычислять с помощью таблиц истинности.

Таблица истинности логической функции зависит от количества логических переменных и содержит 2 n наборов переменных.

Пример 1. Вычисление значения логической функции

F (a , b ) =  (a v b )  (a   b )

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

a

b

a v b

 (a v b )

 b

a   b

F (a , b )

Из таблицы видно, что при любых наборах логических переменных функция F (a , b ) тождественно равна нулю.

Пример 2. Вычисление значения логической функции при заданных значениях переменных.

F (a, b, c) = a v b  (a  с  b).

Вычислите: F (1, 0, 1).

Решение:

F (1, 0, 1) = 1 v 0  (1  1   0)

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

F (1, 0, 1) = 1 v 0 = 1.

Ответ: F (1, 0, 1) = 1.

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

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

Пример 3. Доказательство равенства двух логических функций.

Докажем, что функции F 1 ( a , b ) =  a v b и F 2 ( a , b ) = a  b эквивалентны.

a

b

 a

 a v b

a  b

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

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

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

Для каждой строки таблицы истинности с единичным значением построить минтерм (конъюнкцию переменных), при этом переменная должна встретиться один раз (без отрицания или с отрицанием). Если в таблице истинности переменные имеют нулевые значения в строке, то в минтерм они входят с отрицанием, а переменные, имеющие значение единица, входят в минтерм без отрицания.

Объединить все минтермы операцией дизъюнкции.

Упростить, если возможно, полученную логическую формулу.

Пример 4. Построение логической функции по заданной таблице истинности.

a

b

c

F(a, b, c)

Выберем строки, в которых функция равна 1 и построим для них минтермы:

строка 1:  a  b  c ;

строка 2:  a  b  c .

Объединим минтермы: F ( a , b , c ) =  a  b  c   a  b  c .

Упростим логическую функцию: F ( a , b , c ) =  a  b  c   a  b  c = {3} =  a  b  (  c  c ) = {6} =  a  b  1= {7} =  a  b = {4} =  ( a  b )

Итак, мы получили логическую функцию F ( a , b , c ) =  ( a  b ).

§ 7. Логические основы ЭВМ. Базовые логические элементы.

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

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

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

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

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

Логический элемент компьютера - это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Базовыми логическими элементами компьютеров для реализации логических функций являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ (называемые также вентилями ).

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

Чтобы представить два логических состояния - “1” и “0” в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт. Высокий уровень обычно соответствует значению “истина” (“1”), а низкий - значению “ложь” (“0”).

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

И (конъюнктор)

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

x

y

x . y

0

0

0

0

1

0

1

0

0

1

1

1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x . y

Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд" ), являющимся сокращенной записью английского слова and.

ИЛИ (дизъюнктор)

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

x

y

x  y

0

0

0

0

1

1

1

0

1

1

1

1

Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y

Знак "1" на схеме - от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1).

НЕ (инвертор)

x

y

 (x . y)

0

0

1

0

1

1

1

0

1

1

1

0

Схема И-НЕ состоит из элемента И И.

Связь между выходом z и входами x и y схемы записывают следующим образом: z =  (x . y), где x . y читается как "инверсия x и y".

ИЛИ-НЕ (элемент Пирса)

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

F = a · ( b   c)  (a  e · d) · ( a  b · c)

F = a · b · c  a · b · c  a · b · c · d

F = a   a · (b  c)  (  a  d  g) · (b  d) · (c   d  g · h)

§ 8. Логические элементы компьютера. Триггер и сумматор.

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

Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop , что в переводе означает “хлопанье”. Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить (“перебрасываться”) из одного электрического состояния в другое и наоборот.

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

S0

1

1

0

1

0

0

1

1

1

хранение бита

S Q

R  Q

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

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

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

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

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

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

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

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

Слагаемые

Перенос

Сумма

A

B

P

S

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

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

Что касается суммы, то наиболее подходящим логическим элементом является элемент «ИЛИ». Однако при сложении четвертой пары чисел в результате должен получаться 0, а не 1. Для того чтобы достичь необходимого результата, можно подать сигнал переноса на логический элемент «НЕ», а затем с его выхода и выхода элемента «ИЛИ» подать сигнал на элемент «И». На выходе элемента «И» мы получим требуемый сигнал.

A (0,0,1,1) P (0,0,0,1)

B (0,1,0,1)

0,0,0,1 1,1,1,0 S (0,1,1,0)

0,1,1,1

Данная схема называется полусумматором, т.к. реализует суммирование одноразрядных двоичных чисел без учета переноса из младшего разряда.

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

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

a i

b i

p i

p i-1

c i

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

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

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

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

В результате сложения получаются две цифры: цифра c i для суммы; перенос p i из данного разряда в старший.

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

Входы

Выходы

Первое слагаемое

Второе слагаемое

Перенос

Сумма

Перенос

a i

b i

p i-1

c i

p i

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

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

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

Например, схема вычисления суммы C = (с 3 c 2 c 1 c 0) двух двоичных трехразрядных чисел A = (a 2 a 1 a 0) и B = (b 2 b 1 b 0), где с 0 – младший разряд суммы, с 3 – старший разряд суммы, может иметь вид:

a 0 a 1 a 2

b 0 b 1 b 2

0 с 3

с 0 с 1 с 2

Таким образом, можно сделать вывод, что логические элементы являются строительными «кирпичиками», из которых путем конструирования логических схем строится «здание» любого современного компьютера.

Вопросы для самоконтроля:

Что изучает логика, математическая логика, алгебра логики?

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

Основные логические связки, элементарное и составное высказывания.

Перечислите основные логические операции и способы их записи.

Дайте определение логической формулы.

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

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

Понятие таблицы истинности логической формулы. Таблицы истинности элементарных формул.

Что такое упрощение формулы?

Основные законы алгебры логики.

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

Дайте определение логической функции.

Понятие эквивалентных логических функций.

Правило построения логической функции по таблицам истинности.

Определение логического элемента компьютера. Базовые логические элементы.

Триггер и сумматор. Соответствующие таблицы истинности и логические схемы.

Основные действия над числами - это сложение и вычитание.

• 1. Сложение двоичных чисел
• 0 + 0 = 0 0+1 = 1 1+0=1
• 1 + 1=0 + единица переноса в старший разряд, т.е. 1 + 1=10 2 .

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

Пример 1. Сложить в двоичной системе

• 2. Вычитание двоичных чисел осуществляется в соответствии со следующими правилами:
• 0-0 = 0 1-0=1 1-1=0 10 2 -1 = 1

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

Операции над положительными и отрицательными числами

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

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

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

Пример 1. Представьте положительное число 127ю=1111111 2 в прямом коде: 0 1111111

Пример 2. Представьте отрицательное число - 1)0 в прямом коде:

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

Пример 3. Представьте отоинательное число - 1 ш в обратном коде:

Пример 4. Представьте отпиттятетткнпе хшг.тто - 1 77 10 в обратном коде:

Код модуля числа Обратный код числа

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

Пример 5. Представьте отрицательное число - 1ю в дополнительном коде: 11111111

Пример 6. Представьте отрицательное число -127ю в дополнительном коде:

Сложение чисел в дополнительном коде

Пример 1. Выполните следующую арифметическую операцию «-5+3».

Наши действия в этом случае таковы:

3. Осуществим сложение чисел.

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

Ответ: - 2, следовательно, все действия выполнены верно.

Пример 2. Выполните следующую арифметическую операцию «5 - 3». Выполняя операцию вычитания и представляя отрицательное число в дополнительном коде, можно операцию вычитания заменить сложением.

1. Представим числа в двоичном коде:

2. Отрицательное число следует представить в дополнительном коде. Для этого инвертируем все разряды числа, кроме знакового, и в младший разряд результата добавим единицу.

3. Осуществим сложение чисел.

• 4. Если результат получился положительным, то единицу переноса из знакового разряда отбрасывают.
• 5. Полученное число следует перевести в десятичную систему счисления. Ответ: + 2, следовательно, все действия выполнены верно.

Связь между алгеброй логики и двоичным кодированием

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

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

Так, например, предложение «8 - четное число» следует считать высказыванием, так как оно истинное. Предложение «Москва - столица Бельгии» тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «студент первого курса» и «мороженое - вкусное». Первое предложение ничего не утверждает о студенте, а второе использует слишком неопределенное понятие «вкусное». Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла. Предложения типа «в городе А более миллиона жителей », «у нее голубые глаза » не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь.

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

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

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

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

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

Логический элемент компьютера - это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Простейшими логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-HE». Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем.

Работу логических элементов, как и логических функций, описывают с помощью таблиц истинности. Таблица истинности - это таблица, в которую записаны значения логической функции для каждого из 2 П наборов аргументов на входе. Например, полная таблица истинности выражения с тремя переменными содержит 2 3 =8 строчек, если заданы только 6 из них, то можно найти 2 8 " 6 =2 2 =4 разных логических выражения, удовлетворяющие этим 6 строчкам. Для того чтобы полностью определить логическую функцию, достаточно перечислить либо все наборы, при которых эта функция принимает значения, равные 1, либо все наборы, при которых эта функция принимает значения, равные 0.

Элементарные логические функции и логические элементы

Логические функции, зависящие от одной или двух переменных, называются элементарными. К основным логическим функциям относятся следующие элементарные функции: отрицание, логическое умножение, отрицание от логического умножения, логическое сложение, отрицание от логического сложения, импликация и т.д.

Функция отрицания - это логическая функция от одного аргумента, которая принимает значение 1, если аргумент равен 0, и принимает значение 0, если аргумент равен 1, и называется отрицанием (инверсией) или логической функцией «НЕ».

В обыденной речи мы часто пользуемся словом «НЕ», или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «На улице холодно». (Обозначим это высказывание А.) Если вы не согласны, вы скажете: «На улице НЕ холодно». Или: «Неверно, что на улице холодно». (Ваше высказывание обозначим В.) Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот.

Запись логической функции «НЕ» можно обозначить как F = X, где черта над переменной - признак инверсии, либо как -iX. Логическая функция «НЕ» от одного аргумента описывается таблицей истинности (табл. 8).

Таблица 8. Таблица истинности для логической функции «НЕ»

Логический элемент «НЕ» (инвертор) реализует операцию отрицания. Если на входе этого логического элемента 0, то на выходе 1, а когда на входе 1, на выходе 0.

Условное обозначение инвертора на структурных схемах приведено на рис. 12.

Рис. 12.

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

Высказывая конъюнкцию, мы утверждаем, что выполняются оба события, о которых идет речь в высказывании. Например, сообщая: «Петровы взяли отпуск за свой счет и уехали в Крым», мы выражаем в своем высказывании свое убеждение в том, что произошли оба этих события.

Функцию логического умножения называют также конъюнкцией или функцией «И». Элементарная функция логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 9).

Таблица 9. Таблица истинности для логической функции «И»

При записи логической функции «И» возможны следующие варианты: F=X AY;

F=XY, где знаки «Л», «&», « » - знаки, обозначающие операцию логического умножения. Все варианты записи равнозначны.

Рис. 13.

Логический элемент «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах конъюнкции с двумя входами представлено на рис. 13.

Функцией логического сложения п аргументов называется логическая функция, которая принимает значение 0 только в том случае, когда все аргументы равны 0 (т.е. при наборе п нулей), и 1 во всех остальных случаях (т.е. когда хотя бы один аргумент равен единице).

Функцию логического сложения называют также дизъюнкцией или логической функцией «ИЛИ». Сообщая: «Петров смотрит телевизор или смотрит в окно», мы имеем в виду, что хотя бы одно Петров делает. При этом Петров может одновременно смотреть телевизор и смотреть в окно. И в этом случае дизъюнкция будет истинна.

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

Таблица 10. Таблица истинности для логической функции «ИЛИ»

Рис. 14.

При записи логической функции «ИЛИ» возможны следующие варианты:

где знаки «V», «+» обозначают операцию логического сложения.

Логический элемент «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе элемента «ИЛИ» будет единица, на ее выходе также будет единица. Условное обозначение на структурных схемах логического элемента «ИЛИ» с двумя входами представлено на рис. 14.

Функция отрицания от логического умножения «И-НЕ» принимает значение 0, когда все аргументы равны 1, и 1 - во всех остальных случаях. Функция отрицания от логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 11).

Таблица 11. Таблица истинности для функции отрицания от логического умножения

При записи функции отрицания от логического умножения возможны следующие варианты:

Рис. 15.

Логический элемент «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата функции И. Условное обозначение на структурных схемах логического элемента «И-НЕ» с двумя входами представлено на рис. 15.

Функция отрицания от логического сложения принимает значение 1, когда все аргументы равны 0, и значение 0 - во всех остальных случаях.

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

Таблица 12. Таблица истинности для функции отрицания от логического сложения

При записи функции отрицания от логического сложения возможны следующие варианты:

Рис. 16.

Логический элемент «ИЛИ-HE» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата логической функции «ИЛИ». Условное обозначение на структурных схемах логического элемента «ИЛИ-HE» с двумя входами представлено на рис. 16.

В сложных выражениях с использованием логических операций «И», «ИЛИ», «НЕ» сначала выполняется операция отрицания «НЕ», затем операция конъюнкции «И». В последнюю очередь выполняется операция дизъюнкции «ИЛИ». Для того чтобы изменить указанную последовательность выполнения операций, в выражениях следует использовать скобки. Кроме перечисленных функций, одной из важнейших операций является импликация (следование), которая обозначается -> и описывается соответствующей таблицей (табл. 13).

Таблица 13. Таблица истинности для функции импликации

Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Рассмотрим высказывание: «Если завтра будет хорошая погода, то я пойду гулять». Здесь А= Завтра будет хорошая погода и В= Я пойду гулять. Ясно, что человек окажется лжецом лишь в том случае, если погода действительно окажется хорошей, а гулять он не пойдет. Если же погода будет плохой, то независимо от того, пойдет он гулять или нет, во лжи его нельзя обвинить: обещание пойти гулять он давал лишь при условии, что погода будет хорошей.

В обычной речи связка «если..., то» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: «если на Луне есть вода, то в зоопарке живут тигры», «если клубника - ягода, то в магазине есть хлеб».

Импликация заведомо истинна, если условие А ложно. Другими словами, из неверного условия может следовать все, что угодно. Например, высказывание «Если 2>3, то крокодилы летают» является истинным.

Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно» называется эквиваленцией или двойной импликацией и обозначается знаками, =. Эквиваленция описывается соответствующей таблицей

Таблица 14. Таблица истинности для функции эквиваленции

Например, сообщая: «Я получу паспорт тогда и только тогда, когда мне исполнится 14 лет», человек утверждает не только то, что после того, как ему исполнится 14 лет, он получит паспорт, но и то, что паспорт он сможет получить только после того, как ему исполнится 14 лет.

Таким образом, высказывание XY истинно тогда и только тогда, когда значения X и Y совпадают. Следует учитывать, что рассмотренную нами операцию - импликацию можно выразить через дизъюнкцию и отрицание:

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

Каким выражением может быть F?

Построим таблицу истинности для всех предложенных в ответе выражений:

Вычислим логические выражения для четырех предложенных ответов. Видим, что совпали значения логических выражений в столбцах X v Y v Z и F, следовательно, правильный ответ 3.

Пример 2. Для какого из указанных значений X истинно высказывание

Видно, что высказывание представляет собой отрицание выражения ((Х>2) -> -> (Х>3)). Оно истинно, когда ((Х>2) -> (Х>3)) ложно. Импликация ложна в единственном случае: левое высказывание истинно (в нашем случае Х>2 истинно для Х=3 и Х=4), а правое ложно (это справедливо для Х=1, Х=2 и Х=3). Поэтому единственный вариант, когда эта импликация ложна (следовательно, исходное выражение истинно), - третий.

Основные законы алгебры логики

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

Таблица 15. Правила преобразования логических выражений

двойного отрицания	Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание
переместительный (коммутативный)	А Л В = В Л А	А V В = В V А
сочетательный (ассоциативный)	(А Л В) Л С = А А (В Л С)	(A v В) v С = A v (В v С)
распределительный (дистрибутивный)	(А Л В) V С = (А V В) А (А VC)	Aa(BvC) = AaBvAa С
де Моргана	А В = А" + В отрицание логического произведения эквивалентно логической сумме отрицаний множителей	А + В = А -В отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых
поглощения	А А (А V В) = А	А V А А В = А
склеивания	(А V В) Л (-А V В) = В	(А А В) v (-А V В) = В
исключения третьего (операция переменной с ее инверсией)	для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно.

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

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

Под упрощением формулы, не содержащей операций импликации и эквивален- ции, понимают равносильное преобразование, приводящее к формуле, которая:

• - либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул;
• - либо содержит меньшее число вхождений переменных.

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

Пример 1.

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

Пример 2.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией).

Пример 3. Какое логическое выражение равносильно выражению

По правилу де Моргана выполним преобразование

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

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

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

6. Выполните вычитание следующих чисел:

• 7. Опишите связь между алгеброй логики и двоичным кодированием. Приведите примеры логических высказываний.
• 8. Что такое таблица истинности?
• 9. Дайте характеристику логической функции НЕ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции НЕ.
• 10. Дайте характеристику логической функции И. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции И.
• 11. Дайте характеристику логической функции ИЛИ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции ИЛИ.
• 12. Расскажите о логической операции «импликация». Приведите ее таблицу истинности.
• 13. Какое логическое высказывание эквивалентно выражению -i (A v -iB д С)?

14. Дан фрагмент таблицы истинности выражения F.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ НЕФТИ И ГАЗА ИМЕНИ И.М. ГУБКИНА

на тему: «Логические основы устройства компьютера»

Булат В.Р.

Москва, 2014

1. Что такое алгебра логики

1 Логические операции: дизъюнкция, конъюнкция и отрицание

2 Таблицы истинности

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

1 Законы алгебры логики

2 Переключательные схемы

3 Вентили

4 Сумматор и полусумматор

4.1 Полусумматор

4.2 Сумматор

5 Триггер как элемент памяти. Схема RS-триггера

5.1 RS-триггер на вентилях ИЛИ-НЕ

Список использованной литературы

1. Что такое алгебра логики

Алгебра логики (булева алгебра) - это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

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

Что такое простое логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

.1 Логические операции: дизъюнкция, конъюнкция и отрицание

Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

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

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

В этом случае достаточно, чтобы одно простое было истинным и тогда все высказывание будет истинным.

Отрицание - это унарная операция (т.е. зависящая от одного аргумента), т.к. выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.

.2 Таблицы истинности

Логические операции удобно описывать так называемыми таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B). (1, с. 125).

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

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

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

.1 Законы алгебры логики

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

1. Конъюнкция - логическое умножение (И) - and, &, ∧.

2. Дизъюнкция - логическое сложение (ИЛИ) - or, |, v.

Логическое отрицание (НЕ) - not, ¬.

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

1. Законы рефлексивности: a ∨ a = a a ∧ a = a

2. Законы коммутативности: a ∨ b = b ∨ a a ∧ b = b ∧ a

Законы дистрибутивности: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Закон отрицания: ¬ (¬ a) = a

Законы де Моргана: ¬ (a ∧ b) = ¬ a ∨ ¬ b ¬ (a ∨ b) = ¬ a ∧ ¬ b

7. Законы поглощения: a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a

2.2 Переключательные схемы

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

.3 Вентили

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

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

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

Соединив пару транзисторов различным способом, получают вентили ИЛИ-НЕ и И-НЕ. Эти вентили принимают уже не один, а два и более входных сигнала. Выходной сигнал всегда один и зависит от входных сигналов. В случае вентиля ИЛИ-НЕ получить высокое напряжение (логическую единицу) можно только при условии низкого напряжении на всех входах. В случае вентиля И-НЕ все наоборот: логическая единица получается, если все входные сигналы будут нулевыми. Как видно, это обратно таким привычным логическим операциям как И и ИЛИ. Однако обычно используются вентили И-НЕ и ИЛИ-НЕ, т.к. их реализация проще: И-НЕ и ИЛИ-НЕ реализуются двумя транзисторами, тогда как логические И и ИЛИ тремя.

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

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

2.4 Сумматор и полусумматор

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

Как происходит сложение? Допустим, требуется сложить двоичные числа 1001 и 0011. Сначала складываем младшие разряды (последние цифры): 1+1=10. Т.е. в младшем разряде будет 0, а единица - это перенос в старший разряд. Далее: 0 + 1 + 1(от переноса) = 10, т.е. в данном разряде снова запишется 0, а единица уйдет в старший разряд. На третьем шаге: 0 + 0 + 1(от переноса) = 1. В итоге сумма равна 1100.

.4.1 Полусумматор

Теперь не будем обращать внимание на перенос из предыдущего разряда и рассмотрим только, как формируется сумма текущего разряда. Если были даны две единицы или два нуля, то сумма текущего разряда равна 0. Если одно из двух слагаемых равно единице, то сумма равна единице. Получить такие результаты можно при использовании вентиля ИСКЛЮЧАЮЩЕГО ИЛИ.

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

Тогда сложение в пределах одного разряда (без учета возможной пришедшей единицы из младшего разряда) можно реализовать изображенной ниже схемой, которая называется полусумматором. У полусумматора два входа (для слагаемых) и два выхода (для суммы и переноса). На схеме изображен полусумматор, состоящий из вентилей ИСКЛЮЧАЮЩЕЕ ИЛИ и И.

2.4.2 Сумматор

В отличие от полусумматора сумматор учитывает перенос из предыдущего разряда, поэтому имеет не два, а три входа.

Чтобы учесть перенос приходится схему усложнять. По-сути получается, что состоит из двух полусумматоров.

Рассмотрим один из случаев. Требуется сложить 0 и 1, а также 1 из переноса. Сначала определяем сумму текущего разряда. Судя по левой схеме ИСКЛЮЧАЮЩЕЕ ИЛИ, куда входят a и b, на выходе получаем единицу. В следующее ИСКЛЮЧАЮЩЕЕ ИЛИ уже входят две единицы. Следовательно, сумма будет равна 0.

Теперь смотрим, что происходит с переносом. В один вентиль И входят 0 и 1 (a и b). Получаем 0. Во второй вентиль (правее) заходят две единицы, что дает 1. Проход через вентиль ИЛИ нуля от первого И и единицы от второго И дает нам 1.

Проверим работу схемы простым сложением 0 + 1 + 1 = 10. Т.е. 0 остается в текущем разряде, и единица переходит в старший. Следовательно, логическая схема работает верно.

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

.5 Триггер как элемент памяти. Схема RS-триггера

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

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

Триггер - устройство, способное запоминать, хранить и позволяющее считывать информацию. Он был изобретен в начале XX века Бонч-Бруевичем.

Разнообразие триггеров весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.

алгебра логика таблица компьютер

2.5.1 RS-триггер на вентилях ИЛИ-НЕ

RS-триггер «запоминает», на какой его вход подавался сигнал, соответствующий единице, в последний раз. Если сигнал был подан на S-вход, то триггер на выходе постоянно «сообщает», что хранит единицу. Если сигнал, соответствующий единице, подан на R-вход, то триггер на выходе имеет 0. Не смотря на то, что триггер имеет два выхода, имеется в виду выход Q. (Q с чертой всегда имеет противоположное Q значение.)

Другими словами, вход S (set) отвечает за установку триггера в 1, а вход R (reset) - за установку триггера в 0. Установка производится сигналом, с высоким напряжением (соответствует единице). Просто все зависит от того, на какой вход он подается.

Большую часть времени на входы подается сигнал равный 0 (низкое напряжение). При этом триггер сохраняет свое прежнее состояние.

Возможны следующие ситуации:

· Q = 1, сигнал подан на S, следовательно, Q не меняется.

· Q = 0, сигнал подан на S, следовательно, Q = 1.

· Q = 1, сигнал подан на R, следовательно, Q = 0.

· Q = 0, сигнал подан на R, следовательно, Q не меняется.

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

Как триггер сохраняет состояние? Допустим, триггер выдает на выходе Q логический 0. Тогда судя по схеме, этот 0 возвращается также и в верхний вентиль, где инвертируется (получается 1) и уже в этом виде передается нижнему вентилю.

Тот в свою очередь снова инвертирует сигнал (получается 0), который и имеется на выходе Q. Состояние триггера сохраняется, он хранит 0.

3. Практическое значение алгебры логики

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

0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0.

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

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

Сумматоры и полусумматоры являются однотактными логическими схемами. Значения их выходов однозначно определяется значениями их входов. Фактор времени в них отсутствует. Наряду с ними существуют многотактные логические схемы, в которых значения их выходов определяются не только значениями их входов, но и их состоянием в предыдущем такте. Фактор времени и определяется такими тактами. К таким логическим схемам относятся схемы памяти (триггеры). Они строятся с помощью обратной связи с выхода на вход.

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

Такая схема памяти имеет еще и другое название - триггер с раздельными входами. В такой схеме есть вход для запоминания (S) и стирания (R). Широко используется в вычислительной технике и триггер со счетным входом. Он имеет только один вход и один выход. Такая схема осуществляет деление на 2, т.е. состояние ее выхода изменяется только после подачи подряд двух входных импульсов. Соединяя триггеры со счетным выходом в последовательный каскад, можно осуществлять деление на 2, 4, 8, 16, 32, 64 и т.д.

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

В современных компьютерах микроскопические транзисторы в кристалле интегральной схемы сгруппированы в системы вентилей, выполняющих логические операции над двоичными числами. Так, с их помощью построены описанные выше двоичные сумматоры, позволяющие складывать многоразрядные двоичные числа, производить вычитание, умножение, деление и сравнение чисел между собой. Логические вентили, действуя по определенным правилам, управляют движением данных и выполнением инструкций в компьютере. (2, с.218)

Список использованной литературы

1) Угринович Н.Д. Информатика и информационные технологии: Учебник для 10-11 классов - М.:БИНОМ, 2003. - 512 с.

) Макарова Н.В., Волков В.Б. Информатика: учебник для вузов - М.: Питер, 2011. - 576 с.