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

Логические основы компьютера АлтГПУ, 2017 г. Алгебра логики Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. 3 Этапы развития логики Лейбниц Готфрид Вильгельм (1646-1716, немецкий ученый и математик) предложил использовать в логике математическую символику и впервые высказал мысль о возможности применения в ней двоичной системы счисления. Логика обретает символьный язык, конкретность законов, распространяется за рамки гуманитарных наук. Этапы развития логики Джордж Буль (1815-1864, английский математик-самоучка, основоположник математической логики) В 1846 году Джордж Буль подхватил идею Лейбница о создании логического универсального языка, подчиняющегося строгим математическим законам. Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую к всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется: алгебра Буля или булева алгебра. Этапы развития логики Клод Шеннон (1916 – 2001) – американский инженер и математик в 1938 г. связал Булеву алгебру (аппарат математической логики), двоичную систему кодирования и релейноконтактные переключательные схемы, заложив основы будущих ЭВМ. Логическое высказывание Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo. Логические высказывания могут быть истинными или ложными. Пример. Предложение «6 — четное число» следует считать истинным высказыванием. Предложение «Рим — столица Франции» – ложное высказывание. 7 Логическое высказывание Высказываниями не являются: восклицательные и вопросительные предложения; определения; предложения типа: «он сероглаз», «x2-4x+3=0» Высказывательная форма — это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Логическое высказывание Определите какие из следующих выражений являются высказываниями:  Число 6 – четное.  Здравствуйте!  Все роботы являются машинами.  Кто отсутствует?  Выразите 1 ч 15 мин в секундах.  А – первая буква в алфавите. Логическое высказывание Определите истинность высказываний.  Треугольник – геометрическая фигура.  У каждой лошади есть хвост.  Париж – столица Китая.  Лед – твердое состояние воды.  Все люди – космонавты. Простые и составные высказывания Логические связки – это слова и словосочетания, которые позволяют из уже заданных высказываний строить новые высказывания Пример. Слова и словосочетания “не”, “и”, “или”, ”если..., то”, “тогда и только тогда”. Высказывания, образованные из других высказываний с помощью логических связок, называются составными. Высказывания, не являющиеся составными, называются элементарными (или простыми). 11 Простые и составные высказывания Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний. В алгебре логики высказывания обозначают буквами и называют логическими переменными. Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0). 0 и 1 называются логическими значениями. 12 Простые и составные высказывания Пример. А - высказывание «Сидоров – студент», В — высказывание «Сидоров – спортсмен». Составное высказывание «Сидоров — студент и спортсмен» — А и В. «и» — логическая связка, А, В — логические переменные, которые могут принимать только два значения «истина» или «ложь». 13 Логические операции Инверсия - логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному. Другое название: логическое отрицание. Обозначения: НЕ, ¬ , ¯ . Логические операции Таблица истинности логического выражения – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения для каждой комбинации. Таблица истинности логической операции «инверсия» А 1 Ā 1 Логические операции Конъюнкция (лат. conjunctio — соединение) - логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Другое название: логическое умножение. Обозначения:  , , &, И. Таблица истинности: А В А&В 1 1 1 1 1 Логические операции Пример. Пусть А=«12 четное число», В=«12 делится на 3». Тогда А Λ В=«12 четное число и делится на 3» - истинно, т.к. А - истинно, В – истинно. 17 Логические операции Дизъюнкция (лат. disjunctio — разделение) - логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны. Другое название: логическое сложение. Обозначения: V, |, ИЛИ, +. Таблица истинности: А В 0 А V В1 1 1 1 АVВ 1 1 1 Логические операции Пример. Пусть А=«12 делится на 5», В=«12 делится на 7». Тогда А v В = «12 делится на 5 или на 7» -ложно, т.к. А ложно, В – ложно. 19 Логические операции Импликация (лат. implico — тесно связаны) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно. В естественном языке – «если ..., то», «из ... следует», «… влечет ...» Обозначение – → Таблица истинности: А В А В 1 1 1 1 1 1 1 Логические операции Эквиваленция (равносильно) – это логическая операция, ставящая в соответствие каждым двум высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истины или одновременно ложны. В естественном языке – «тогда и только тогда», «необходимо и достаточно», «... равносильно ...». Обозначение – ↔, ~. Таблица истинности: А В А↔ В 1 1 1 1 1 1 Логические операции Пример. Высказывание "24 делится на 2 тогда и только тогда, когда 4 делится на 2» - истинно. 22 Логические операции Исключающее ИЛИ – это логическая операция, ставящая в соответствие каждым двум высказываниям составное высказывание, являющееся истинным тогда, когда значения двух исходных высказываний не равны. Обозначение – . Сложение по модулю 2: А  B = (A + B) mod 2 Таблица истинности: А В А В 1 1 1 1 1 1 Логические операции Базовые набор операций: И ИЛИ НЕ Импликацию можно выразить через дизъюнкцию и отрицание: А → В = ¬ А v В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А ↔ В = (¬ А v В)  (¬ В v А). Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию: А  B = (А  ¬ В) v (¬ А  В) 24 Логические операции Логические операции в сложном логическом выражении имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция Для изменения указанного порядка выполнения логических операций используются скобки. 25 Логические операции A  B  A  B  A B A B 1 1 1 1 А¬В ¬АВ (А  ¬ В) v (¬ А  В) АB Логические операции Штрих Шеффера, «И-НЕ» A | B  A B Таблица истинности: A B А|B 1 1 1 1 1 1 1 Базовые операции через «И-НЕ»: A  A|A A  B  A | B  (A | B) | (A | B) A  B  A | B  (A | A) | (B | B) Логические операции Стрелка Пирса, «ИЛИ-НЕ» A  B  A B Таблица истинности: A B А↓B 1 1 1 1 1 Логическая формула Логическая формула Логической формулой называется 1. Всякая логическая переменная и символы "истина" ("1") и "ложь“ ("0") - формулы. 2.Если А и В - формулы, то ¬А, А Λ В, А v В, А → B, А ↔ В - формулы. 3.Никаких других формул в алгебре логики нет. 30 Таблица истинности Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Построение таблицы истинности: 1) определить число переменных (n); 2) определить число строк в таблице истинности (q=2n); 3) записать все возможные значения переменных; 4) определить порядок; количество логических операций и их 5) записать логические операции в таблицу истинности и определить для каждой значение. Логическая формула Формулы, принимающие значение "истина", при определённых сочетаниях значений входящих в них переменных, а при некоторых других сочетаниях — значение "ложь", называются выполнимыми. Пример. Формула (A v B) → C. 32 Логическая формула Задание: составить таблицу истинности для формулы и проверить является ли она выполнимой. Переменные Промежуточные логические формулы Формула Логическая формула Формулы, принимающие значение "истина" при любых значениях истинности входящих в них переменных, называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями. Пример. Формула А v ¬А. Высказывание "Этот треугольник прямоугольный или косоугольный". Формула будет истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не 34 прямоугольный. Логическая формула Задание: составить таблицу истинности для формулы и проверить является ли она тождественно истинной. Переменные Промежуточные логические формулы Формула Логическая формула Формулы, принимающие значение "ложь" при любых значениях входящих в них переменных, называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями. Пример. Формула А Λ ¬А. Высказывание "Катерина самая высокая девушка в группе, и в группе есть девушки выше Катерины". 36 Логическая формула Задание: составить таблицу истинности для формулы и проверить является ли она тождественно ложной. Переменные Промежуточные логические формулы Формула Логическая формула Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры обозначается символом "=" или символом "". логики Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы. 38 Основные законы алгебры логики Название Для И Для ИЛИ AA Двойного отрицания AA  0 A  A 1 Операции с константами A  0  0, A 1  A A  0  A, A  1  1 Повторения AA  A AA A Исключения третьего Поглощения Переместительный A (A  B)  A A  A B  A A B  B  A A B  B  A Сочетательный A  (B  C)  (A  B)  C A  (B  C)  (A  B)  C Распределительный A  B  C  (A  B)  (A  C) A (B  C)  A  B  A  C Законы де Моргана A B  A  B A B  A B Упрощение логических формул Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных. 40 Упрощение логических формул Шаг 1. Заменить операции , ,  на их выражения через И, ИЛИ и НЕ: A  B  A  B  A B A B  A B A  B  A B  A  B Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана: A  B  A  B, A B  A B Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон41 исключения третьего. Решение логических задач Решение логических задач средствами алгебры логики Схема решения: 1) изучается условие задачи; 2) вводится система обозначений для логических высказываний; 3) конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи; 4) определяются значения истинности этой логической формулы; 5) из полученных значений истинности формулы определяются значения истинности введенных логических высказываний, на основании которых делается заключение о 43решении. Решение логических задач Пример. Трое друзей спорили о результатах чемпионата по футболу. — Вот увидишь, «Динамо» не будет первым, — сказал Иван. - Первым будет «Зенит». — Победителем будет «Динамо», — воскликнул Николай. — «Спартаку» не быть первым. Петр, к которому обратился Николай, возмутился: — «Зениту» не видать первого места, а вот у «Спартака» новый тренер. По завершении чемпионата оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто победил? 44 Логический элемент компьютера Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ и другие (называемые также вентилями). Работу логических элементов (вентилей) описывают с помощью таблиц истинности. 46 Схема «НЕ» Схема «НЕ» (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z=x, где x читается как "не x" или "инверсия х". x 1 47 x 1 Схема «И» Схема «И» (конъюнктор) реализует операцию конъюнкцию. Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x  y (читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and. Х У XУ 1 1 1 1 1 48 Схема «ИЛИ» Схема «ИЛИ» (дизъюнктор) реализует операцию дизъюнкцию. Условное обозначение на структурных схемах схемы ИЛИ с двумя входами. Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y"). x 1 1 49 y 1 1 xvy 1 1 1 Схема «Импликация» Связь между выходом z этой схемы и входами x и y описывается соотношением: z = xy. Операция импликация на структурных схемах обозначается знаком «1» с инверсией на входе x. 50 x y xy 1 1 1 1 1 1 1 Схема «Эквивалентность» Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x↔y. Операция эквивалентность на структурных схемах обозначается знаком «». 51 x y x↔y 1 1 1 1 1 1 Схема «Исключающее ИЛИ» Схема «ИСКЛЮЧАЮЩЕЕ ИЛИ» реализует схему сложение по модулю 2. Связь между выходом z и входами x и y схемы записывают следующим образом: z=x у. 52 x y x y 1 1 1 1 1 1 Схема «И-НЕ» Схема «И—НЕ» (элемент Шеффера) состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Связь между выходом z и входами x и y схемы записывают следующим образом: z=x∙у, где x∙у читается как "инверсия x и y". 53 X У XУ 1 1 1 1 1 1 1 Схема «ИЛИ-НЕ» Схема «ИЛИ—НЕ» (элемент Вебба) состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ». Связь между выходом z и входами x и y схемы записывают следующим образом: z=xvу, где xvу, читается как "инверсия x или y ". 54 x y xvу 1 1 1 1 1 Анализ электронной схемы Какой сигнал должен быть на выходе при каждом возможном наборе сигналов на входах? X 1 1 Y 1 1 1 Алгоритм построения логической схемы по логическому выражению 1. Определить число логических переменных. 2. Определить количество операций и их порядок. базовых логических 3. Изобразить для каждой логической операции соответствующий ей вентиль. 4. Соединить вентили логических операций. в 56 порядке выполнения Построение логической схемы по логическому выражению Пример. По заданной логической функции построить логическую схему. Решение: Число логических переменных Количество базовых логических операций - 57 Триггер Каждый разряд двоичного числа – это часть электронной схемы - триггер. Триггер — это логическая схема, способная хранить 1 бит информации (1 или 0). Широко применяется в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю. 58 Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ. set, установка S 1 1 R reset, сброс вспомогательный выход Q S R Q Q режим 0 0 Q Q хранение обратные связи 0 1 1 сброс Q 1 0 1 1 1 установка 1 основной выход запрещен Принцип работы RS-триггера •При подаче на оба входа триггера логического нуля (S = R = 0) на обоих выходах должна установиться логическая единица. Это запрещенное состояние триггера; оно не используется, т.к. может привести к неоднозначному результату. •При S = 0 и R = 1 на выходе Q устанавливается логическая единица, в этом случае говорят, что триггер установлен в состояние 1, на выходе ¬Q - 0. •При S = 1 и R = 0 происходит сброс сигнала на выходеQ на нем устанавливается логический ноль. Говорят, что триггер установлен в состояние 0. •При S = R = 1 триггер находится в состоянии покоя — это режим хранения, т. е. на выходах Q и ¬Q остаются прежние значения сигнала. •Триггер запоминает один разряд двоичного числа. Полусумматор Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа. A S сумма A B P S Σ B P перенос P  A B S  A  B  A  B  A B A B A B & AB & A B & A B 1 1 1 1 1 1 1 1 S  A  B  A B P Сумматор Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда. перенос A B C Σ A B C P S сумма 1 1 P перенос 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 S Сумматор служит, прежде всего, центральным узлом арифметикологического устройства (АЛУ) компьютера. 64 Многоразрядный сумматор Многоразрядный сумматор - это логическая схема, способная складывать два n-разрядных двоичных числа.  A an an-1  a1 B bn bn-1  b1 C  p cn cn-1  c1 перенос a1 b1 c1 Σ p2 a2 b2 c2 Σ an bn p3 K p n cn Σ p перенос