ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА
ФОРМЫ МЫШЛЕНИЯ
ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.
Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира.
Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны.
Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики).
В основе логических схем и устройств ПК лежит специальный математический аппарат, использующий законы логики. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции.
Основные формы мышления
Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ.
ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер.
Понятие имеет две стороны: содержание и объем.
Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.
СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях.
Суждениями обычно являются повествовательными предложениями, которые могут быть или истинными или ложными.
«Берн - столица Франции»,
«Река Кубань впадает в Азовское море»,
«2>9», «3×5=10»
УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение).
Все металлы - простые вещества. Литий - металл.→ Литий - простое вещество.
Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.
Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер - это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя».
АЛГЕБРА ВЫСКАЗЫВАНИЙ
В основе работы логических схем и устройств персонального компьютера лежит специальный математический аппарат - математическая логика. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции.
Английский математик Джордж Буль (1815 - 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.
ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.
Например: Земля - планета Солнечной системы . (Истинно) 2+8 (Ложно) 5 · 5=25 (Истинно) Всякий квадрат есть параллелограмм (Истинно) Каждый параллелограмм есть квадрат (Ложно) 2 · 2 =5 (Ложно)
“х- 4х + 3=0” - в них не указано о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называются высказывательными формами.
Высказывательная форма - это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Не всякое предложение является высказыванием: 1) Восклицательные и вопросительные предложения высказываниями не являются. - “Какого цвета этот дом?” - “Пейте томатный сок!” - “Стоп!” 2) Не являются высказываниями и определения. “Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны”. Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов. 3) Не являются высказываниями и предложения типа “Он сероглаз” или
.
В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 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-триггер
Логика – наука, изучающая законы и формы мышления. Алгебра логики это математический аппарат, с помощью которого записывают, упрощают, преобразовывают и вычисляют логические высказывания. Это раздел математики, который изучает высказывания с точки зрения их логических значений и логических (операций)связок. Впервые АЛ, как математический аппарат возникла в середине 19 века в трудах английского математика Джорджа Буля и с тех пор носит название «булева алгебра».
Логическое высказывание это любое повествовательное предложение, в отношение которого можно сказать однозначно истинно оно или ложно. Рим – столица Италии (истина), 5 – четное число (ложь). Кроме того, в АЛ используются и сложные высказывания, которые содержат несколько простых мыслей, соединенных между собой (связками) логическими операциями.
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:
НЕ - Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказываниеистинно, когда 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" ложно, а высказывание "10 делится на 2 или 10 делится на 3", - истинно.
Логический элемент компьютера - это часть электронной логической схемы, которая реализует элементарную логическую функцию.
Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, (называемые также вентилями), а также триггер. Имеется один или несколько входов и один выход.
Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем.
Работу логических элементов описывают с помощью таблиц истинности.
Таблица истинности - это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений входных сигналов (операндов) и соответствующие им значения выходного сигнала (результата операции) для каждого из этих сочетаний.
Схема И
Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис 1.
Таблица истинности схемы И
Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.
Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x . y
(читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.
С
Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.
Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис.2. Обозначение - знак "1" на схеме Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y").
Таблица истинности схемы ИЛИ
С
Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z = , гдечитается как "не x" или "инверсия х".
Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на структурных схемах инвертора - на рисунке 3
Таблица истинности схемы НЕ
Лекция № 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 - тесно связаны) и обозначается знаком . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.
Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: "данный четырёхугольник - квадрат" (А ) и "около данного четырёхугольника можно описать окружность" (В ). Рассмотрим составное высказывание , понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание истинно:
- А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
- А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
- 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. Таблица истинности для формулы :
1. Понятие, суждение, умозаключение.
Логика изучает внутреннюю структуру процесса мышления, который реализуется в таких естественно сложившихся формах мышления как понятие, высказывание и умозаключение.
Мышление всегда осуществляется через понятия, высказывания и умозаключения.
Понятие – это форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их от других.
Существенными называются такие признаки, каждый из которых, взятый отдельно, необходим, а все вместе достаточны, чтобы с их помощью отличить данный предмет от всех остальных и сделать обобщение, объединив однородные предметы в множество.
Примеры понятий:
Единичные понятия: самая высокая гора в Европе, этот стол, Москва и т.д.
Общие понятия: красота, металл, доброта, глупость, лес, коллектив и т.д.
Абстрактные понятия: вес, жесткость, цвет, вселенная, человечество и т.д.
Конкретные понятия: круг, дом, пламя, битва и т.д.
Любое понятие характеризуется содержанием и объемом.
Объем понятия – множество предметов, к которым прилагается понятие.
Высказывание – это формулировка своего понимания окружающего мира. Высказывание является повествовательным предложением, в котором что-либо утверждается или отрицается. По поводу высказывания можно сказать, истинно оно или ложно. В русском языке высказывания выражаются повествовательными предложениями:
Алупкинский дворец находится в Крыму.
Кащей Бессмертный – скупой и жадный.
В русском языке высказывания выражаются повествовательными предложениями:
в математической логике – утверждение, истинность которого (в общем случае) зависит от значений входящих в него переменных.
Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение.
Рассуждение – цепочка фактов, общих положений и умозаключений. Умозаключение представляет собой переход от сведений, которыми мы располагаем до рассуждения (посылок или условий), к выводам. Правильный способ умозаключений из истинных посылок всегда ведет к истинным выводам.
Примеры индуктивных рассуждений:
Правильны ли полученные выводы?
1)
1
– нечетное и простое число,
3
– нечетное и простое число.
5
– нечетное и простое число
Вывод: все нечетные – простые числа.
2). 1=1,1+3=4,1+3+5=9,1+3+5+7=16,1+3+5+7+9=25, и т.д.
Вывод: квадрат любого числа К равен сумме К первых нечетных чисел.
3). Fe, Си, Zn. Pt – твердые тела
Вывод: все металлы-твердые.
4) В Аргентине, Эквадоре, Венесуэле говорят по-испански.
Вывод: все страны Латинской Америки – испаноязычные
2. Алгебра логики
– определяет правила записи, вычисления значений, упрощения и преобразования высказываний.
В алгебре логики высказывания обозначают буквами и называют логическими переменными .
Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1 ), а если ложно – нулём (В = 0 ).
0 и 1 называются логическими значениями .
Высказывания бывают простые и сложные.
Высказывание называется простым , если никакая его часть сама не является высказыванием.
Сложные (составные) высказывания строятся из простых с помощью логических операций.
Логические операции.
Конъюнкция – логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны .
Другое название: логическое умножение.
Дизъюнкция – логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны .
Другое название: логическое сложение .
Обозначения: V, |, ИЛИ, +.
Инверсия – логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному.
Другое название: логическое отрицание.
Обозначения: НЕ, ¬ , ¯ .
Импликация – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно , а следствие (второе высказывание) ложно .
В естественном языке – “Если A, то B”;
Обозначение –
Логическая эквивалентность (равнозначность) – это логическая операция, ставящая в соответствие каждым двум высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истины или одновременно ложны.
В естественном языке – “Тогда и только тогда и в том и только том случае”;
Обозначение – ↔
Логические операции имеют следующий приоритет:
инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность
В 10-х классах учатся 50 человек. Факультатив по математике посещают 36 человек, по физике – 20 человек, на тот и другой факультатив записаны 10 учеников.
Какое количество учащихся не посещают факультативы?
36 – 10 = 26 – число учеников посещающих математику, и не посещающих физику.
20 + 26 = 46 – число учеников, посещающих математику или физику.
50 – 46 = 4 – число учеников, которые не посещают никаких факультативов.
3. Построение таблиц истинности сложных высказываний.
Свойства логических операций.
Справочный материал:
Решение логических задач упрощением логических выражений.
На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как эти места распределились между победителями, то мнения разошлись:
Даша: Андрей был первым, а Володя – вторым.
Галя: Андрей был вторым, а Борис – третьим.
Лена: Боря был четвертым, а Сережа – вторым.
Известно, что каждая девочка в одном утверждении ошиблась, а в другом была права. Кто из мальчиков какое место занял?
Введем обозначения:
4. Базовые логические элементы компьютера
Дискретный преобразователь, который после обработки входных двоичных сигналов выдает на выходе сигнал, являющийся значением одной из логических операций, называется логическим элементом.
Базовые логические элементы реализуют три базовые логические операции:
- логический элемент “И” (конъюнктор) – логическое умножение;
- логический элемент “ИЛИ” (дизъюнктор) – логическое сложение;
- логический элемент “НЕ” (инвертор) – логическое отрицание.
Любая логическая операция может быть представлена в виде комбинации трех базовых, поэтому любые устройства компьютера, производящие обработку и хранение информации, могут быть собраны из базовых логических элементов.
Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы.
Есть импульс – логическое значение сигнала 1, нет импульса – значение 0.
Анализ электронной схемы.
Какой сигнал должен быть на выходе при каждом возможном наборе сигналов на входах?
Решение. Все возможные комбинации сигналов на входах А и В внесём в таблицу истинности. Проследим преобразование каждой пары сигналов при прохождении их через логические элементы и запишем полученный результат в таблицу.
Заполненная таблица истинности полностью описывает рассматриваемую электронную схему.
В инвертор поступает сигнал от входа В. В конъюнктор поступают сигналы от входа А и от инвертора. Таким образом, F= А & ¬ B
Полусумматор и сумматор.
Арифметико-логическое устройство процессора (АЛУ) содержит в своем составе
такие элементы как сумматоры. Они позволяют складывать двоичные числа.
Сложение в пределах одного разряда (без учета возможной пришедшей
единицы из младшего разряда) можно реализовать схемой, которая называется
полусумматором. У полусумматора два входа (для слагаемых) и два выхода
(для суммы и переноса).
В отличие от полусумматора сумматор учитывает перенос из предыдущего
разряда, поэтому имеет не два, а три входа.
(trigger-защелка, спусковой крючок) – это устройство, позволяющее запоминать, хранить и считывать информацию.
Каждый триггер хранит 1 бит информации, те он может находиться в одном из двух устойчивых состояний –логический “О” или логическая “1”.
Триггер способен почти мгновенно переходить из одного электрического состояния в другое и наоборот
Логическая схема триггера выглядит следующим образом:
Входы триггера расшифровываются следующим образом – S (от английского Set – установка) и R (Reset – сброс). Они используются для установки триггера в единичное состояние и сброса в нулевое. В связи с этим такой триггер называется RS-триггер.
Выход Q называется прямым, а противоположный – инверсный. Сигналы на прямом и инверсном выходах, конечно же, должны быть противоположны.
Пусть для определенности на вход S подан единичный сигнал, a R=0. Тогда независимо от состояния другого входа, который подсоединен к выходу Q (иначе говоря, вне зависимости от предыдущего состояния триггера), верхний по схеме элемент ИЛИ-НЕ получит на выходе 0 (результат ИЛИ равен 1, но его инверсия – 0). Этот нулевой сигнал передается на вход другого логического элемента, где на втором входе R тоже установлен 0. В итоге после выполнения логических операций ИЛИ-НЕ над двумя входными нулями этот элемент получает на выходе 1, которую возвращает первому элементу на соответствующий вход. Последнее обстоятельство очень важно: теперь, когда на этом входе установилась 1, состояние другого входа (S) больше не играет роли. Иными словами, если даже теперь убрать входной сигнал S, внутреннее распределение уровней сохранится без изменения.
Поскольку Q = 1, триггер перешел в единичное состояние, и, пока не придут новые внешние сигналы, сохраняет его. Итак, при подаче сигнала на вход S триггер переходит в устойчивое единичное состояние.
При противоположной комбинации сигналов R = 1 и S = 0 вследствие полной симметрии схемы все происходит совершенно аналогично, но теперь на выходе Q уже получается 0. Иными словами, при подаче сигнала на R-триггер сбрасывается в устойчивое нулевое состояние.
Таким образом, окончание действия сигнала в обоих случаях приводит к тому, что R = 0 и S = 0.
У
чебный элемент
Тема: «Логические основы обработки информации.» - 9 -
Предмет: «Информатика»
Изучив данный учебный элемент, Вы узнаете:
о принципах обработки информации компьютером;
логические основы работы компьютера:
основные логические операции;
логические схемы элементов компьютера;
примеры решения задач по данной теме.
Оборудование, материалы и вспомогательные средства:
персональный компьютер;
мультимедиа проектор;
презентация урока;
раздаточный материал.
Сопутствующие учебные элементы и пособия:
Учебник И.Г. Семакин, Т.Ю. Шеина, Л.В. Шестакова – 10 класс
Логические основы обработки информации основаны на Логике
Логика – это наука о формах и способах мышления.
Основные формы мышления
Высказывание
Умозаключение
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.
Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо истинно, либо ложно.
Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений(посылок) может быть получено новое суждение (заключение
В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «истина»(1) и «ложь»(0)
К базовым логическим операциям относятся:
Логическое умножение (конъюнкция) – «И»
Логическое сложение (дизъюнкция) – «ИЛИ»
Логическое отрицание (инверсия) – «НЕ»
Логическое умножение «И» на формальном языке принято обозначать значком «&» либо «^». Пример: высказывание F=A & B
Таблица истинности логического умножения
Пример. «2*2 =4 И 3*3 =10» по таблице определяем (А = 1), (В = 0), значит F = 0 – данное высказывание ложно
Логическое сложение «ИЛИ» на формальном языке алгебры логики обо значают «+» либо «v»
Пример: высказывание F=A V B
Таблица истинности логического сложения
| F=A V B |
||
Пример: «2*2 = 4 ИЛИ 3*3 = 10» по таблице определяем (А = 1), (В = 0), значит F = 1 – данное высказывание истинно
Логическое отрицание в алгебре логики обозначают Ā
Пример: F = Ā
Таблица истинности логического отрицания
Таблица истинности - Импликация (логическое следование )
Таблица истинности - Эквивалентность (равнозначность)
Компьютер выполняет арифметические и логические операции при помощи так называемых базовых логических элементов , которые также еще называют вентилями.
Вентиль «И» – конъюнктор
Реализует конъюнкцию
Вентиль «ИЛИ» – дизъюнктор
Реализует дизъюнкцию
Вентиль «НЕ» – инвертор
Реализует инверсию
Любая логическая операция может быть представлена через конъюнкцию, дизъюнкцию и инверсию.
Любой сколь угодно сложный элемент компьютера может быть сконструирован из элементарных вентилей.
Вентили оперируют с электрическими импульсами:
Импульс имеется – логический смысл сигнала «1»
Импульса нет – логический смысл сигнала «0»
Н
а входы вентиля подаются импульсы – значения аргументов
, на выходе вентиля появляется сигнал – значение функции
Пример.
Сумматор двоичных чисел
Все математические действия в компьютере сводятся к сложению двоичных чисел. Основу микропроцессора составляют сумматоры двоичных чисел
Триггер
Важнейшая структурная единица оперативной памяти и регистров процессора. Состоит из двух логических элементов «ИЛИ» и двух логических элементов «НЕ»
Логическая схема триггера
Работа триггера
В обычном состоянии на входы триггера S и R подан сигнал «0» и триггер хранит «0».
При подаче сигнала «1» на вход S триггер принимает значение на выходе Q значение «1»
При подаче сигнала «1» на вход R триггер возвращается в свое исходное состояние – хранит «0».
Построение таблиц истинности логических выражений
При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:
инверсия
конъюнкция
дизъюнкция
импликация и эквивалентность
Для изменения порядка действий используются скобки.
Задание 1
Выполнить логические операции:
(1 v 1) v (1 v )
((1 v 0) v 1) v 1
(0 v 1) v (1 v 0)
(0 & 1) & 1
1 & (1 & 1) & 1
((1 v 0) & (1 & 1)) & (0 v 1)
((1 & 0) v (1 & 0)) v 1
((1 & 1) v 0) & (0 v 1)
((0 & 0) v 0) & (1 v 1)
Задание 2
Построить таблицу истинности для логического выражения:
A & (B v B & C)
Задание 3
Доказать, что логические выражения A & B иA v B равносильны.
Дать определение науке «Логика».
Назвать логические операции.
Как изображаются логические схемы?
Рассказать о работе триггера.
Иванилова Т.С.
Липецкий политехнический техникум
