Основные логические операции компьютера. Логические основы построения компьютера

Учитель : Сабитов А.Н

Дата: 25.10.2016

Класс: 8Б

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

Цели работы

Учебная

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

познакомить учащихся с понятиями: базовые логические элементы;

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

закрепить на практике;

развивающая

развитие логического мышления;

продолжать способствовать развитию ИКТ - компетентности:

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

воспитательная

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

воспитывать такие качества личности, как активность, самостоятельность и аккуратность в работе

методы обучения

словесный, наглядный, практический

Тип урока:

урок изучения нового материала

Вид урока:

комбинированный

Формы обучения:

фронтальная, индивидуальная

Программно-дидактическое обеспечение

ПК, презентация по теоретическому материалу, плакат, задания тестового типа

Межпредметные связи

с профессией

План урока

    Организационный этап (проверка явки, посадки, готовности)

    Объявление темы урока.

    Мотивация темы. Вопросы учащимся

      почему актуальна тема «Основы логики»;

      какое значение имеет эта тема для изучения последующих дисциплин и для будущей профессиональной деятельности;

      цели урока и план урока

    Постановка целей урока, знакомство с формой занятия.

    Активизация знаний:

    формы мышления

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

    Новый материал:

    принципы работы компьютера;

    логические элементы компьютера.

    Закрепление материала

Учащиеся выполняют обучающее задание на компьютерах. Задание тестового типа: файл Логика_тесты . Лист Сигнал.

Для учащиеся, быстро справившиеся с заданием, программа-тренажер «Логика» с сайта Константина Полякова.

    Подведение итогов урока, выставление оценок за работу на уроке.

    Домашняя работа. Повторить логические операции, выучить логические элементы компьютера.

Принципы работы компьютера

    двоичное кодирование информации;

    программное управление работой ЭВМ (идея Чарльза Бэббиджа);

    принципы фон Неймана.

Принципы работы компьютера (принципы фон Неймана)

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

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

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

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

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

Средством обработки двоичных сигналов в компьютере являются логические элементы.

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

И , ИЛИ , НЕ , И-НЕ , ИЛИ-НЕ

и другие (называемые также вентилями), а также триггер.

Триггер – это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ

Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице , а другое - двоичному нулю

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


ФОРМЫ МЫШЛЕНИЯ ЛОГИКА это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений. Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны. Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики). В основе логических схем и устройств ПК лежит специальный математический аппарат, использующий законы логики. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции.


Основные формы мышления Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ. ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер. Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя». Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров. СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях. Суждениями обычно являются повествовательными предложениями, которые могут быть или истинными или ложными. «Берн столица Франции», «Река Кубань впадает в Азовское море», «2>9», «3×5=10» УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение). Все металлы - простые вещества. Литий - металл. Литий - простое вещество. Один из углов треугольника равен 90º. Этот треугольник прямоугольный. 9», «3×5=10» УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение). Все металлы - простые вещества. Литий - металл. Литий - простое вещество. Один из углов треугольника равен 90º. Этот треугольник прямоугольный.">


АЛГЕБРА ВЫСКАЗЫВАНИЙ В основе работы логических схем и устройств персонального компьютера лежит специальный математический аппарат - математическая логика. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции. Английский математик Джордж Буль (г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.




Высказывания могут быть простыми и сложными. Высказывание считается простым, если никакую его часть нельзя рассматривать как отдельное высказывание Некоторые высказывания можно разложить на отдельные части, при этом каждая такая часть будет самостоятельным высказыванием. Например, высказывание Сегодня в 4 часа дня я был в школе, а к 6 часам вечера пошел на каток состоит из 2 частей. Высказывание может состоять и из большего количества частей. Высказывание, которое можно разложить на части, будем называть сложным, а неразложимое далее высказывание - простым. Сложное высказывание получается путем объединения простых высказываний логическими связками НЕ, И, ИЛИ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок. Например, даны простые высказывания: На улице идет дождь. На улице светит солнце. На улице пасмурная погода. Составим из них сложные высказывания: На улице идет дождь и на улице светит солнце. На улице светит солнце или на улице пасмурная погода. Неверно что на улице идет дождь.


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


БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.


1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ) соответствует частице НЕ обозначается черточкой над именем переменной или знаком ¬ перед переменной Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Таблица истинности инверсии имеет вид: A 01 10


2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) соответствует союзу ИЛИ обозначается знаком v или + или Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А v В v С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид: AB А V В


3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) соответствует союзу И обозначается знаком & или Λ, или · Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид: ABА & В


ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими выражениями. Например: Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.


Таблицы истинности Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных). При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий: 1) записать выражение и определить порядок выполнения операций 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формулеQ=2 n, где n - количество входных переменных) 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций) 4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных. 5) заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности Теперь мы можем определить значение логической функции для любого набора значений логических переменных.


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




ABC


ABC Задание. Постройте таблицу истинности для данного логического выражения:


АВ Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак =. Например:


ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ Правила построения логического выражения: 1. Для каждой строки таблицы истинности с единичным значением функции построить минтерм. Минтермом называется произведение, в котором каждая переменная встречается только один раз либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 без отрицания. 2. Объединить все минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.


Пример. Дана таблица истинности: X1X2X3F Для второй строки X1=0, Х2=0, X3=1. Эту строку описывает минтерм Для третьей строки X1=0, Х2=1, X3=0. Эту строку описывает минтерм Для шестой строки X1=1, X2=0, X3=1. Эту строку описывает минтерм Объединяя термы, получим булево выражение F = В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю. Построим логическое выражение для F. Найдем строки, в которых F=1. Это вторая, третья и шестая.


Логические функции Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X1,X2,..., Xn) аргументами которой являются логические переменные X1, X2,..., Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = A&B, логическое сложение F(A,B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю. Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 2 4 = 16 различных логических функций двух аргументов. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности:


АргументыЛогические функции АВ F1F1 F2F2 F3F3 F4F4 F5F5 F6F6 F7F7 F8F8 F9F9 F10F10 F 11 F 12 F 13 F 14 F 15 F Легко заметить, что здесь логическая функция F2 является функцией логического умножения, F8 функцией логического сложения, F13 функцией логического отрицания для аргумента А и F11 функцией логического отрицания для аргумента В. В обыденной и научной речи кроме базовых логических связок «и», «или», «не» используются и некоторые другие: «если... то...», «... тогда и только тогда, когда...» и др. Не­которые из них имеют свое название и свой символ, и им со­ответствуют определенные логические функции.


ИМПЛИКАЦИЯ (ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ). Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом Запись А В читается как «из А следует В» Импликация двух высказываний истинна всегда, кроме случая, если первое высказывание истинно, а второе ложно. Таблица истинности импликации двух суждений А и В такова: АВА В В программировании эту операцию обозначают «IMP».


ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА) Она обозначается символами или. («тогда и только тогда»). Запись А В читается как «А эквивалентно В». Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны. Таблица истинности эквивалентности двух суждений А и В такова: АВА В В программировании эту операцию обозначают «EQV». В алгебре высказываний все логические функции могут быть сведены путём логических преобразований к трём базовым логическим операциям: инверсии, дизъюнкции и конъюнкции


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


1. Закон тождества. Всякое высказывание тождественно самому себе: Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. Это яблоко спелое и Это яблоко не спелое


3. Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означа­ет, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. Сегодня я получу 5 либо не получу. Истинно либо суждение, либо его отрицание. 4. Закон двойного отрицания. Если дважды отрицать неко­торое высказывание, то в результате мы получим исходное высказывание: Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. Неверно, что 2× 2¹ 4


5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них: Дизъюнкция одинаковых «слагаемых» равносильна одному: 6. Законы де Моргана: Смысл законов де Моргана (Август де Морган () - шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых; отрицание логического произведения эквивалентно логической сумме отрицаний множителей.


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


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




ЗАДАЧА 1. Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления. Батончик: «Я не делал этого. Пончик сделал это» Лёнчик: «Пончик не виновен. Батончик сделал это» Пончик: «Я не делал этого. Лёнчик не делал этого» Суд установил, что один из них дважды солгал, другой дважды сказал правду, третий один раз солгал, один раз сказал правду. Кто утаил клад? Возможные варианты Высказывания Батончика Высказывания Лёнчика Высказывания Пончика Соответствие условию задачи БЛП¬Б¬БП¬П¬ПБ¬П¬П¬Л¬Л В первом варианте один солгал дважды, а двое сказали правду дважды, что не соответствует условию задачи. В третьем варианте все один раз сказали правду и один раз солгали, что также не соответствует условию задачи. Во втором варианте один дважды солгал, другой дважды сказал правду, а третий один раз сказал правду, а один раз солгал, что соответствует условию задачи. Следовательно клад утаил Пончик. Решение: Введём обозначения: Б –клад утаил Батончик, П - клад утаил Пончик, Л - клад утаил Лёнчик. Рассмотрим три возможных варианта – виноват Батончик, виноват Пончик, виноват Лёнчик. При таких вариантах получаем следующие значения высказываний трёх обвиняемых.


Задача 2. В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита? Высказывания 1-ого болельщика Высказывания 2-ого болельщика Соответствие условию задачи Н1М2Л2Р4Р3Н Из анализа таблицы видно, что условию задачи соответствует только последняя строка, значит первое место заняла Наташа, второе – Люда, третье – Рита, а Маша –четвёртое. Решение: Введём обозначения: Н1 – Наташа на 1 месте, М2 – Маша на 2 месте, Л2 – Люда на 2 месте, Р4 – Рита на 4 месте, Р3 – Рита на 3 месте, Н2 – Наташа на 2 месте. Занесём возможные варианты высказываний трёх болельщиков в таблицу с учётом того, что каждый из болельщиков оказался прав только в одном из своих прогнозов:


Задача 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей? Возможные варианты высказываний Соответствие условию задачи ВК¬ СК¬ МАВКСКМА Проанализируем строки в трёх последних столбцах. Условию задачи соответствует только вторая строка, значит Сергей изучает китайский язык, Михаил – японский (так как он не изучает арабский), тогда Вадим изучает арабский язык. Решение: Введём обозначения: ВК – Вадим изучает китайский язык, СК – Сергей изучает китайский язык, МА - Михаил изучает арабский язык. Занесём в таблицу возможные варианты значений высказываний с учётом условия задачи, что одно из утверждений верно, а два - ложны:


Задача 4. Три одноклассника Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение: Здесь исходные данные разбиваются на тройки (имя профессия увлечение). Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист. ИмяЮра Профессия врач Увлечение туризм Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем: ИмяЮраТимурВлад Профессияфизикврачюрист Увлечениебегтуризмрегби Ответ. Влад юрист и регбист, Тимур врач и турист, Юра физик и бегун.


Задачи для самостоятельного решения Задача 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок. Вот увидишь, Шумахер не придет первым, сказал Джон. Первым будет Хилл. Да нет же, победителем будет, как всегда, Шумахер, воскликнул Ник. А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился: Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину. По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки? Задача 2. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний: 1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем. 2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место. 3) Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним. 4) Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м. 5) Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м. Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет. Как распределились места между командами? Задача 3 Три дочери писательницы Дорис Кей Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: Джуди живет не в Париже, а Линда не в Риме; парижанка не снимается в кино; та, кто живет в Риме, певица; Линда равнодушна к балету. Где живет Айрис, и какова ее профессия?




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


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


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


Логический элемент И (конъюнктор) Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается: На выходе этого элемента будет сигнал 1 только в том случае, когда на все входы поступает сигнал 1. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. Другие логические элементы построены из трех простейших базовых элементов и выполняют более сложные логические преобразования информации. вход 1вход 2выход


Рассмотрим еще два логических элемента, которые играют роль базовых при создании более сложных элементов и схем. Логический элемент И-НЕ выполняет логическую функцию штрих Шеффера (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается: Логический элемент ИЛИ-НЕ выполняет логическую функцию стрелка Пирса (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается:. Логический элемент И-НЕ Логический элемент ИЛИ-НЕ вход 1вход 2выход вход 1вход 2выход


Функциональные схемы Сигнал, выработанный одним логическим элементом, можно подавать на вход другого элемента, это дает возможность образовывать цепочки из отдельных логических элементов функциональные схемы. Функциональная (логическая) схема – это схема, состоящая из логических элементов, которая выполняет определённую функцию. Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет. Ясно, что элемент И осуществляет логическое умножение значений ¬А и В. Над результатом в элементе НЕ осуществляется операция отрицания, т.е. вычисляется значение выражения: Таким образом структурной формулой данной функциональной схемы является формула: Важной формой описания функциональных схем является структурная формула. Покажем на примере, как выписывают формулу по заданной функциональной схеме.


Таблица истинности функциональной схемы Для функциональной схемы можно составить таблицу истинности, то есть таблицу значений сигналов на входах и выходах схемы, по которой можно понять какую функцию выполняет данная схема. Таблица истинности - это табличное представление логической (функциональной) схемы в котором перечислены все возможные сочетания значений входных сигналов вместе со значением выходного сигнала для каждого из этих сочетаний. Составим таблицу истинности для данной логической схемы: А (вход 1) В (вход 2) С (выход) Начертим таблицу: количество столбцов = количество входов + количество выходов, количество строк = 2 количество входов. В данной таблице 3 столбца и 4 строки. Заполним первые столбцы всеми возможными вариантами входных сигналов


Рассмотрим первый вариант входных сигналов: А=0, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. Рассмотрим второй вариант входных сигналов: А=0, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=0), запишем в таблицу. Рассмотрим третий вариант входных сигналов: А=1, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу.


Рассмотрим четвёртый вариант входных сигналов: А=1, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. В результате получаем таблицу истинности данной логической схемы: А (вход 1) В (вход 2) С (выход) Задание. Построить таблицу истинности для данной логической схемы и записать формулу для данной схемы:


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


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


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


Попробуем, действуя по этому плану, сконструировать устройство для сложения двух двоичных чисел (одноразрядный полусумматор). Пусть нам необходимо сложить двоичные числа А и В. Через P и S обозначим первую и вторую цифру суммы: A + B = PS. Вспомните таблицу сложения двоичных чисел. 1. Таблица истинности, определяющая результат сложения, имеет вид: СлагаемыеПереносСумма АВРS Сконструируем функции P(A,B) и S(A,B) по этой таблице: Преобразуем вторую формулу, пользуясь законами логики:


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


Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором. Логика работы одноразрядного сумматора на три входа или полного сумматора приведена в таблице, где А, В - суммируемые двоичные цифры, Pо - перенос из младшего разряда, S - образующаяся сумма данного разряда и осуществляет перенос P в следующий старший разряд. Полный одноразрядный сумматор. СлагаемыеПеренос из младшего разряда СуммаПеренос АBP0P0 SP Формула переноса:. Формула для вычисления суммы:




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


ТРИГГЕР Триггер - электронная схема, применяемая для хранения значения одноразрядного двоичного кода. Воздействуя на входы триггера, его переводят в одно из двух возможных состояний (0 или 1). С поступлением сигналов на входы триггера в зависимости от его состояния либо происходит переключение, либо исходное состояние сохраняется. При отсутствии входных сигналов триггер сохраняет свое состояние сколь угодно долго. Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое. Существуют разные варианты исполнения триггеров в зависимости от элементной базы (И-НЕ, ИЛИ-НЕ) и функциональных связей между сигналами на входах и выходах (RS, JK, T, D и другие). Самый распространённый тип триггера - это RS-триггер (S и R соответственно от английских set - установка, и reset - сброс). Условное обозначение RS-триггера:


RS-триггер RS-триггер построен на 2-х логических элементах: ИЛИ - НЕ либо И – НЕ. Как, правило, триггер имеет 2 выхода: прямой и инверсный Q и. Как он работает? Пусть на вход элемента 1 подан сигнал 1, а на вход элемента На выходе элемента 1 независимо от того, какой второй сигнал поступит на вход, будет 1, т.к. это элемент ИЛИ (по свойствам дизъюнкции). Пройдя через элемент 2 сигнал примет значение 0 (Q=0). Следовательно, и на втором входе элемента 3 установится сигнал 0. На выходе элемента Пройдя через элемент 4 сигнал изменится на 1. Следовательно, = 1. Убедимся, что данное устройство сохраняет информацию. Запомните, что S=0, R=1, Q=0, =1. В момент прекращения входных сигналов (S=0, R=0) на выходе =1. Это напряжение подается на вход элемента 1. На выходе элемента 1 сохраняется 1, и на Q - сигнал 0. На входах элемента 3 - 0, следовательно =1. Таким образом, при отсутствии на внешних входах сигналов 1 триггер поддерживает постоянное напряжение на своих выходах. Чтобы изменить напряжение на выходах триггера, надо подать сигнал 1 на вход элемента 3. Тогда Q=1, =0. РЕГИСТРЫ РЕГИСТРЫ. Функциональная схема компьютера, состоящая из триггеров, предназначенная для запоминания многоразрядных кодов и выполнения над ними некоторых логических преобразований называется регистром. Упрощенно регистр можно представить как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа. С помощью регистров можно выполнять следующие операции: установку, сдвиг, преобразование. Основными типами регистров являются параллельные и последовательные (сдвигающие). Совокупность регистров, используемых ЭВМ для запоминания программы работы, исходных и промежуточных результатов называется оперативной памятью (ОП). Регистры содержатся в различных вычислительных узлах компьютера - процессоре, периферийных устройствах и т.д. Регистр - это устройство, предназначенное для хранения многоразрядного двоичного числового кода, которым можно представлять и адрес, и команду, и данные.


РЕГИСТРЫ Существует несколько типов регистров, отличающихся видом выполняемых операций. Некоторые важные регистры имеют свои названия, например: сдвиговый регистр - предназначен для выполнения операции сдвига; счетчики - схемы, способные считать поступающие на вход импульсы. К ним относятся Т-триггеры (название от англ. tumble - опрокидываться). Этот триггер имеет один счетный вход и два выхода. Под действием сигналов триггер меняет свое состояние с нулевого на единичное и наоборот. Число перебрасываний соответствует числу поступивших сигналов; счетчик команд - регистр устройства управления процессора (УУ), содержимое которого соответствует адресу очередной выполняемой команды; служит для автоматической выборки программы из последовательных ячеек памяти; регистр команд - регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные - для хранения кодов адресов операндов. В ЭВМ применяются регистры 8, 16, 32, 48 и 64 разрядов.


ШИФРАТОРЫ И ДЕШИФРАТОРЫ Шифратор и дешифратор являются типовыми узлами ЭВМ. Шифратор (кодер) - это логическое устройство, которое преобразует единичный сигнал на одном из входов в n-разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации (например в клавиатуре), для преобразования десятичных чисел в двоичную систему счисления. Дешифратор (декодер) - это логическое устройство, преобразующее двоичный код, поступающий на его входы, в сигнал только на одном из его выходов. Дешифраторы широко применяются в устройствах управления, в системах цифровой индикации с газоразрядными индикаторами, для построения распределителей импульсов по различным цепям и т.д. Схема используется для перевода двоичных цифр в десятичные. Дешифратор двоичного n-разрядного кода имеет 2 n выходов, т.к. каждому из 2 n значений входного кода должен соответствовать единичный сигнал на одном из выходов дешифратора.

Современные направления в разработке новых конструкционных материалов.

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

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

· знакопеременные напряжения в элементах;

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

· а с другой – постоянство температуры в шахте и руднике и в подавляющем числе случаев сравнительно ограниченный срок службы выработок (5-15 лет вместо 60-100 лет для поверхностных сооружений) расширяют области их применения.

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

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

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

Так, например, предложение “ 6 - четное число ” следует считать логическим высказыванием, так как оно истинно.

Алгебра логики рассматривает любое высказывание только с точки зрения - является ли оно истинным или ложным.

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

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



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

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

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

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

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

Правило выполнения операции : Высказывание А В истинн о тогда и только тогда, когда оба высказывания А и В истинны , иначе оно ложно . Например, высказывание

“10 делится на 2 и 5 больше 3” истинно, а высказывания

“10 делится на 2 и 5 не больше 3”, ложны.

3. Операция, выражаемая связкой “или ” называется дизъюнкцией или логическим сложением и обозначается в логических формулах словом “OR ” , или знаком U , Ú или плюсом "+ " .

Правило выполнения операции: Высказывание А U В ложно тогда и только тогда, когда оба высказывания А и В ложны , иначе оно будет истинно .

Например, высказывание

“10 не делится нацело на 2 или 5 не больше 3” - ложно,

а все три высказывания: “10 делится на 2 или 5 больше 3”,“10 делится на 2 или 5 не больше 3” или “10 не делится на 2 или 5 больше 3” - будут истинны.

4. Операция , выражаемая связками вида “если.., то… ”, “из... следует … ” или “... влечет... ”, называется импликацией и обозначается в формулах знаком à.

Правило выполнения операции : Высказывание А à В ложн о тогда и только тогда, когда А истинно , а В - ложно .

Каким образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: “данный четырёхугольник - квадрат ” (А ) и “около данного четырёхугольника можно описать окружность ” (В ). Рассмотрим составное высказывание А à В , понимаемое как “если данный четырёхугольник квадрат, то около него можно описать окружность ”.

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

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

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

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

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

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

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

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

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

В выражениях без скобок сначала выполняется операция отрицания (“ не ”), затем конъюнкция (“ и ”), потом - дизъюнкция (“или ”) и в последнюю очередь - сначала импликация , а затем эквиваленция .

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

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

В качестве примера рассмотрим высказывание “если я куплю яблоки или абрикосы, то могу приготовить фруктовый пирог ”. Это высказывание формализуется в виде формулы (A Ú B ) à C . Как показывает анализ формулы

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

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

Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

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

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

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

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

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

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

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

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

4. Что такое логический элемент компьютера?

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

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

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

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

Работа логических элементов описывается с помощью таблиц истинности.

Лекция № 3.

ЛОГИЧЕСКИЕ основы компьютера.

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

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

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

В каком виде записываются в памяти компьютера и в регистрах процессора данные и команды?

Что такое логический элемент компьютера?

Что такое схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ?

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

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

Какие основные законы выполняются в алгебре логики?

Как составить таблицу истинности?

Как упростить логическую формулу?

Что такое переключательная схема?

Как решать логические задачи?

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

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

Что же такое логическое высказывание?

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

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

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

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

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

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

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

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

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

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

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

НЕ Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. "Луна - спутник Земли " (А); "Луна - не спутник Земли " ().

И "и", называется конъюнкцией (лат. 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" - истинны.

ЕСЛИ-ТО Операция, выражаемая связками "если..., то", "из... следует", "... влечет...", называется импликацией (лат. implico - тесно связаны) и обозначается знаком . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

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

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

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

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

РАВНОСИЛЬНО Операция, выражаемая связками "тогда и только тогда ", "необходимо и достаточно ", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком или ~. Высказывание истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания "24 делится на 6 тогда и только тогда, когда 24 делится на 5", "21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

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

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

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

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

С х е м а И

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

Таблица истинности схемы И

x y x . y

С х е м а ИЛИ

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

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

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

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

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

z = x v y (читается как "x или y" ).

Таблица истинности схемы ИЛИ

x y x v y

С х е м а НЕ

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

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

z = , x где читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на структурных схемах инвертора - на рисунке 5.3

Таблица истинности схемы НЕ

x

С х е м а И-НЕ

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

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

Условное обозначение на структурных схемах схемы И-НЕ с двумя входами представлено на рисунке 5.4.

Таблица истинности схемы И-НЕ

x y

С х е м а ИЛИ-НЕ

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

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

Условное обозначение на структурных схемах схемы ИЛИ-НЕ с двумя входами представлено на рис. 5.5.

Таблица истинности схемы ИЛИ-НЕ

Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок.

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

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


Рис. 5.6

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

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

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


Рис. 5.7

S R Q
запрещено
хранение бита

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

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

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

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

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


Рис. 5.8

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

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

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

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

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

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

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

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

Входы Выходы
Первое слагаемое Второе слагаемое Перенос Сумма Перенос

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

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

Примеры.

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

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

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

2. Таблица истинности для формулы :

«Полученное целое частное меньше 2?»

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

«Есть переизбыток?» «Да» «Нет»

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

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

Логическое высказывание - это любое повествовательное предло­жение, в отношении которого можно однозначно сказать, истинно оно или ложно. Например, предложение «6 - четное число» следует считать высказыванием, так как оно истинное; предложение «Рим - столица Франции» - тоже высказывание, так как оно ложное.

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

Высказываниями не являются, например, предложения: «Сту­дент 204 группы», «Здравствуйте!», «В колледже более 1000 уча­щихся», «Хороший студент», - так как невозможно судить об их истинности или ложности (или нужны дополнительные сведения, чтобы предложение стало высказыванием, например: «Петров - хороший студент» или «в колледже № 15 г. Самары более 1000 учащихся»).

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

Заметим, что зачастую трудно установить истинность высказы­вания. Например, высказывание «Площадь поверхности Индий­ского океана равна 75 млн км 2 » в одной ситуации можно посчи­тать ложным, а в другой - истинным (ложным - так как указан­ное значение неточное и вообще не является постоянным; истин­ным - если рассматривать его как некоторое приближение, прием­лемое на практике).

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

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

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

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

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

Операция отрицания. Операция, выражаемая словом НЕ, назы­вается отрицанием, или инверсией, и обозначается чертой над высказыванием. Высказывание А истинно, когда А ложно, и лож­но, когда А истинно. Например: «Луна - спутник Земли» (А); «Луна - не спутник Земли» (А).

Пусть А = «Два умножить на два равно четырем» - истинное высказывание, тогда высказывание, образованное с помощью опе­рации логического отрицания - «Два умножить на два не равно четырем», - ложное высказывание.

Образуем высказывание F, являющееся логическим отрицани­ем А:

Истинность такого высказывания задается таблицей истинно­сти функции логического отрицания (табл. 2.6).

Таблица 2.6 Таблица истинности функции логического отрицания

А F

Операция конъюнкции.

Операция, выражаемая связкой И, на­зывается соединением, или конъюнкцией, или логическим ум­ножением, и обозначается знаком «&» (может обозначаться зна­ком «л» или « »). Высказывание F = А&В истинно только тогда, когда оба высказывания А и В истинны. Например, высказывание «10 делится на 2 И 5 больше 3» истинно, а высказывания «10 делится на 2 И 5 не больше 3», «10 не делится на 2 И 5 больше 3», «10 не делится на 2 И 5 не больше 3» ложны.

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

Таблица 2.7

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

А В F

Рассмотрим, например, составное высказывание «2 2 = 4 И 3 *3 = 10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0). По табл. 2.7 определяем, что логиче­ская функция принимает значение «ложь» (F = 0), т.е. данное со­ставное высказывание ложно.

Операция дизъюнкции. Операция, выражаемая связкой ИЛИ, называется разделением, или дизъюнкцией (от лат. disjunctio - разделение), или логическим сложением, и обозначается знаком «v» (или «+»). Высказывание F = A v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание «10 не делится на 2 ИЛИ 5 не больше 3» ложно, а высказывания «10 делится на 2 ИЛИ 5 больше 3», «10 делится на 2 ИЛИ 5 не больше 3», «10 не делится на 2 ИЛИ 5 больше 3» истинны.

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

Таблица 2.8

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

А в F

Операция импликации. Операция следования, выражаемая связками «если..., то», «из... следует», «... влечет...», называется импликацией и обозначается знаком «->». Высказывание А-> В лож­но тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере следующих высказыва­ний: «Данный четырехугольник - квадрат» (А) и «Около данного четырехугольника можно описать окружность» (В). Рассмотрим составное высказывание F = А-»В, под которым понимается: «Если данный четырехугольник - квадрат; то около него можно опи­сать окружность».

Существуют три варианта, когда высказывание А-*В истинно:

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

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

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

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

Функцию F можно определить, используя таблицу истинности (табл. 2.9): F = A^B

Таблица 2.9

Таблица истинности логической функции импликации

А в F

Операция логического следования несколько отличается от обычного понимания слова «следует». Если первое высказывание (предпосылка) ложно, то независимо от истинности или ложно­сти второго высказывания (вывода) составное высказывание истин­но. Из неверной предпосылки может следовать что угодно.

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

Докажем методом сравнения таблиц истинности, что операция импликации А-> В равносильна логическому выражению A v В (табл. 2.10).

Таблица 2.10

Таблица истинности логического выражения A v В

А в А A vB
I

Табл. 2.10 полностью совпадает с табл. 2.9.

Операция эквиваленции. Операция равенства, выражаемая связ­ками «тогда и только тогда», «необходимо и достаточно», «...рав­носильно...», называется эквиваленцией, или двойной имплика­цией, и обозначается знаками «<-»» или «~». Высказывание А <-> В истинно тогда и только тогда, когда значения А и В совпадают. Например, истинны высказывания: «24 делится на 6 тогда и толь­ко тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» - и ложны высказывания: «24 де­лится на 6 тогда и только тогда, когда 24 делится на 5», «21 делит­ся на 6 тогда и только тогда, когда 21 делится на 3».

Высказывания А и В, образующие составное высказывание F = А<-»В, могут быть совершенно не связаны по содержанию.

Составное высказывание F = А<-> В имеет таблицу истинности (табл. 2.11).

Таблица 2.11

Таблица истинности составного высказывания А<->В

А в F

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

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

F=AoB = (AvB)&(BvA).

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

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

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

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

Двойное отрицание исключает отрицание.

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

Для логического сложения

A v В = В v А;

Для логического умножения

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания. В обычной алгебре a + b = b + a;a-b = b-a.

3. Сочетательный (ассоциативный) закон:

Для логического сложения

(A v В) v С = A v (В v С);

Для логического умножения

(А&В)&С = А&(В&С).

При одинаковых знаках скобки можно ставить произвольно или опускать.

В обычной алгебре (а + Ь) + с = а + (Ь + с) = а + b + с;

(а Ь) ■ с = а (Ь с) = а b с.

4. Распределительный (дистрибутивный) закон:

Для логического сложения

(A v В) & С = (А&С) v (B&C);

Для логического умножения
(А&В) v С = (A v C)&(B v С).

Данный закон определяет правило выноса общего высказыва­ния за скобку.

В обычной алгебре справедлив распределительный закон толь­ко для сложения: (а + Ь) с = а с + b с.

5. Закон общей инверсии (законы де Моргана):

Для логического сложения

Для логического умножения

6. Закон идемпотентности (от лат. idem - тот же самый + potens -сильный (дословно - равносильный)):

Для логического сложения

Для логического умножения

Закон означает отсутствие показателей степени.

7. Закон исключения констант:

Для логического сложения

Avl = l;AvO = A;

Для логического умножения

А&1 = А; А&0 = 0.

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

Невозможно, чтобы противоречащие высказывания были од­новременно истинными.

9. Закон исключения третьего:

Из двух противоречащих высказываний об одном и том же пред­мете одно всегда истинно, а второе - ложно; третьего не дано.

10. Закон поглощения:

Для логического сложения:

Для логического умножения

А&(А v В) = А.

11. Закон исключения (склеивания):

Для логического сложения

(A&B)v(A&B) = B;

Для логического умножения

(AvB)&(AvB) = B.

12. Закон контрапозиции (правило перевертывания):

(А*+В) = (ВвА).

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

Пример 1. Найдите X, если XvAvXvA=B.

Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

(Х&А) v (Х&А).

Согласно распределительному закону для логического сложе­ния

Согласно закону исключения третьего и закона исключения констант

Х&1 = X. Полученную левую часть приравняем правой:

Окончательно получим: X = В.

Пример 2. Упростите логическое выражение (AvBvC)&

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

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

(A v В v C)&A v В v С = (A v В v С)&(А&В&С).

Согласно распределительному (дистрибутивному) закону для логического сложения

(A v В v С)&(А&В&С) = (А&А) v (В&А) v (С&А) v (A&B) v v (B&B) v (C&B) v (А&С) v (В&С) v (С&С).

Согласно закону противоречия »

(А&А) = 0; (С&С) = 0.

Согласно закону идемпотентности

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

О v (A&B) v (A&B) v В v (C&B) v (C&B) v (C&A) v (A&C) v 0.

Согласно закону исключения (склеивания)

(A&B) v (А&В) = В; (C&B) v (C&B) = В.

OvBvBvBv (C&A) v (A&C) v 0.

Согласно закону исключения констант для логического сложе­ния и закону идемпотентности

Подставляем значения и получаем:

Согласно распределительному (дистрибутивному) закону для логического умножения

(C&A) v (А&С) = (С v А) & (С v С) & (A v A) & (A v С). Согласно закону исключения третьего

(CvC) = l;(AvA) = l. Подставляем значения и окончательно получаем:

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

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

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

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

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

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

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

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

Высокий уровень обычно соответствует значению «истина» (1), а низкий - значению «ложь» (0).

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

Работу логических элементов описывают с помощью таблиц истинности (аналогично таблицам истинности функций).

Рассмотрим структурные схемы логических элементов компь­ютера и их таблицы истинности (табл. 2.12).

Схема И реализует конъюнкцию двух или более логических значений. На выходе схемы И будет 1 тогда и только тогда, когда на всех входах будут 1. Когда хотя бы на одном входе будет 0, на выходе также будет 0;

Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном из выходов схемы или будет 1, на ее выходе тоже будет 1;

Схема НЕ (инвертор) реализует операцию отрицания. Связь Между входом х этой схемы и выходом z можно записать соотно­шением z= х. Если на входе схемы 0, то на выходе 1. Когда на Входе 1, то на выходе 0;

Схема И-НЕ состоит из элемента И и инвертора и осуществ­ляет отрицание результата схемы И. Связь между выходом z и выхо­дами х и у схемы записывают следующим образом: z = х & у;

Таблица 2.12

Структурные схемы логических элементов компьютера и их таблицы истинности

Условное обозначение Структурная схема Таблица истинности
И
X Y X У х&у
& X&Y
ИЛИ
X У xvy
X_ Y XvY
НЕ
Х_ () X X X
И-НЕ
X У х&у
X Y & <
X&Y
ИЛИ-НЕ
X У xvy
X Y 1 (
XvY

Схема ИЛИ-НЕ состоит из элемента ИЛИ и инвертора и оС уществляет отрицание результата схемы ИЛИ. Связь между вы­ходом z и входами х и у схемы записывают следующим образом: z = xVy.

Триггер

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

Триггер можно построить их двух логических элементов ИЛИ и двух элементов НЕ (рис. 2.3, а). Им соответствует таблица истин­ности (табл. 2.13).

Самый распространенный тип триггера - RS -триггер (от англ. set - установка + reset - сброс). Он имеет два симметричных вхо­да R и S и два симметричных выхода Q и Q. На каждый из двух выходов могут подаваться входные сигналы в виде импульсов (на­личие импульса на входе будем считать единицей, а его отсут­ствие - нулем). В обычном состоянии на входы R и S триггера подан сигнал 0 и триггер хранит 0. Для записи 1 на вход S (устано­вочный) подается сигнал 1. Последовательно рассмотрев прохож­дение сигнала по схеме, видно, что триггер переходит в СОСТОЯ­ВШИ"

Рис. 2.3. Схема триггера: а - на элементах ИЛИ и НЕ; б - на элементах ИЛИ-НЕ

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

S R Q Q
Запрещено
Хранение бита

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

Для того чтобы сбросить информацию и подготовиться к при­ему новой, подается сигнал 1 на вход R (сброс), после чего триггер возвращается к исходному (нулевому) состоянию. Если на входы R и S подана логическая 1, то состояние Q и Q не меняется, подача на оба входа логического 0 может привести к неординарному ре­зультату, и поэтому эта комбинация входных сигналов запрещена.

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

2.2.5. Сумматор двоичных чисел

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

При сложении двоичных чисел образуется сумма в текущем разряде; при этом возможен перенос единицы в старший разряд. Обозначим слагаемые - А, В, перенос - Р и сумму - S.

Таблица 2.14

Таблица сложения одноразрядных двоичных чисел

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

где Р - перенос; А и В - множители.

Для определения суммы можно применить следующее выраже­ние:

S = (AvB)&(A&B).

Построим таблицу истинности для данного логического выра­жения и убедимся в правильности нашего предположения (табл. 2.15).

Таблица 2.15

Таблица истинности функции F = (A v В) & (А & В)

А В AvB А&В А&В (AvB)&(A&B)

Рис. 2.4. Схема полусумматора двоичных чисел

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

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

Анализ логической формулы для суммы показывает, что на выходе должен стоять элемент логического умножения И, кото­рый имеет два входа. На один из входов подается результат логи­ческого сложения исходных величин A v В, т. е. на него должен подаваться сигнал с элемента логического сложения ИЛИ.

На второй вход требуется подать результат инвертированного логического умножения исходных сигналов А&В, т.е. на второй вход подается сигнал с элемента НЕ, на вход которого поступает сигнал с элемента логического умножения И (рис. 2.4).

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

Контрольные вопросы

1. Связано ли появление алгебры логики с разработкой персонально­го компьютера?

2. Назовите основные логические операции.»

3. Приведите примеры предложений, которые не являются логиче­ским высказыванием.

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

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

6. Назовите приоритеты логических операций.

7. Сформулируйте отрицание следующих высказываний: «2 > 5»;
«10 < 7»; «а = 2».

8 Изобразите в декартовой системе координат области (|х| < 1) и

9. Определите истинность составного высказывания «(А & В) & (С v D)»,
состоящего из простых высказываний: А = «Принтер - устройство выво­
да информации», В = «Процессор - устройство хранения информации»,
С = «Монитор - устройство вывода информации», D = «Клавиатура -
устройство обработки информации».

10.Докажите, используя таблицы истинности, что операция эквива­лентности равносильна логическим выражениям А <-» В = (А & В) v (А & В) и A<->B = (AvB)&(AvB).

11.Докажите, используя таблицы истинности, что логические выра­жения A v В и А & В равносильны.

12.Какие логические функции двух аргументов имеют свои названия?

13.Какое существует число логических функций трех аргументов?

14.Упростите следующие логические выражения:

(AvA)&B; A&(AvB)&(BvB).

15. Приведите примеры из повседневной жизни:

если (не а и не Ь), то (с или d); (а или Ь) тогда и только тогда, когда (с или не d).

16.Проследите на логической схеме триггера, что происходит при поступлении сигнала 1 на вход R.

17.Какое число базовых логических элементов необходимо для хране­ния 512 Мбайт информации?

Похожие статьи