ЭЕМ логика негіздері. Логические основы ЭВМ
 Скачать 0.56 Mb.
|
ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМВ основе всех действий произведенных компьютером лежат логические выводы, основанные на математической логике. Любая интегральная схема строится с использованием триггеров и логических элементов. Логика– это совокупность правил, которым подчиняется процесс мышления. Алгебра логики возникла в середине 19 века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. Алгебра логики (математическая логика) – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Формальная логика - наука о формах и законах мышления. Основными формами мышления являются понятие, суждение и умозаключение. Понятие - это форма мышления, которая выделяет существенные признаки предмета или класса предметов, отличающие его от других. Суждение (высказывание) - это форма мышления, в которой утверждается или отрицается связь между предметом и его признаком, отношения между предметами или факт существования предмета и которая может быть либо истинной, либо ложной. Языковой формой выражения суждения является повествовательное предложение. Вопросительные и побудительные предложения суждениями не являются. Суждения рассматриваются не с точки зрения их смысла и содержания, а только с точки зрения их истинности или ложности. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных объектов. Суждения могут быть простыми и сложными. Простые суждения выражают связь двух понятий. Сложные - состоят из нескольких простых суждений. Пример: «В неделе семь дней» – истинное суждение, а «Понедельник начинается в субботу» – ложное, причем оба эти суждения являются простыми. Суждение «Земля вращается вокруг солнца и в марте наступит весна» сложное. Умозаключение - прием мышления, позволяющий на основе одного или нескольких суждений-посылок получить новое суждение (знание или вывод). Пример: Классический образец верного умозаключения: Все люди смертны. Сократ – человек. Следовательно, Сократ смертен. Примерами умозаключений являются доказательства теорем в геометрии. 1. Логическое отрицание, инверсия (от латинского inversio –переворачиваю). Отрицанием неА некоторого высказывания А называется такое высказывание, которое истинно, когда А ложно, и ложно, когда А истинно. Обозначение: , , , Читается: «не А», «не верно, что…» Таблица истинности отрицания Логическая схема «НЕ» (инвертор):
Пример: Высказывание = «Это прямоугольный треугольник» Высказывание = «Не верно, что это прямоугольный треугольник» или «Это не прямоугольный треугольник». 2. Логическое умножение, конъюнкция (от латинского conjunctio - союз, связь). Конъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В.
Определение конъюнкции в виде формулы: = min(A,B) Логическая схема «И» (конъюктор): Пример: Высказывание А = «В треугольнике есть прямой угол» Высказывание В = «В треугольнике есть острый угол» Высказывание = «В треугольнике есть прямой и острый угол» 3. Логическое сложение, дизъюнкция (от латинского disjunctio - разобщение, различие). Дизъюнкцией двух высказываний называется такое новое высказывание, которое истинно тогда и только тогда, когда истинно ХОТЯ БЫ ОДНО из этих высказываний.
Пример: Высказывание А = «В треугольнике есть прямой угол» Высказывание В = «В треугольнике есть острый угол» Высказывание = «В треугольнике есть прямой или острый угол» 4. Логическое следование, импликация (от латинского implico - тесно связываю, переплетаю) Сложное высказывание может быть образовано с помощью слов «если..., то...». Высказывание, расположенное после слова «если», называется основанием или посылкой, а высказывание, расположенное после слова «то», называется следствием или заключением. Импликацией двух высказываний называется такое новое высказывание, которое ложно тогда и только тогда, когда истинно основание и ложно заключение.
Пример: «Если в треугольнике есть прямой угол, то треугольник прямоугольный»
5. Эквивалентность, равнозначность (от латинского aequivalens – равноценные) Эквивалентностью двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания А и В истинны или оба ложны.
Таблица истинности эквивалентности Пример: «Треугольник тогда и только тогда прямоугольный, когда в нем есть прямой угол»
1. Определите, какие предложения не являются высказываниями: а) Земля входит в состав планет Солнечной системы; б) Уходя, гасите свет; в) Квадрат гипотенузы равен сумме квадратов катетов; г) Все четырехугольники – квадраты; д) Который час? е) Ура, каникулы! ж) 10+5>15; з) Джордж Буль – английский математик; и) В ОмГАУ есть факультет МОЕНД; к) В Омске более миллиона жителей. 2. Разбейте сложные высказывания на простые составляющие. Запишите сложное высказывание в алгебраической форме. а) На улице дождь, а зонта нет; Решение представлено в следующей таблице:
б) Когда живется весело, то и работа спорится; в) Если говоришь неправду, то либо ошибаешься, либо обманываешь; г) Для сохранения мира на Земле необходимо увеличить усилия всех государств в борьбе за мир; д) Все планеты Солнечной системы вращаются вокруг Солнца и имеют форму шара; е) Четырехугольник тогда и только тогда является квадратом, если все его стороны и углы равны; ж) Если два угла одного треугольника соответственно равны двум углам другого треугольника, то такие треугольники подобны; з) «В коллективе возникает хороший психологический климат тогда и только тогда, когда будут однозначно определены задачи, ответственность и компетенция каждого сотрудника» (Р.Шмидт); и) «Кабы молодость знала, Кабы старость да могла, Жизнь так часто не хромала. Жизнь бы иначе пошла» (П.Вяземский); к) «Добродетель, милый мой студент, не делится на части; или она есть, или ее нет» (О.Бальзак). 3. Из заданных простых высказываний постройте сложное высказывание. Запишите алгебраическую форму полученного высказывания. а) «Завтра будут занятия по компьютерной графике», «Я начну изучать Photoshop», «Я начну изучать CorelDraw»; Решение (один из возможных вариантов) представлено в следующей таблице:
б) «Ночи бывают лунные», «Ночи бывают безлунные»; в) «Студент получил все зачеты», «Студент сдал все экзамены», «Студент успешно прошел сессию»; г) «Законы природы можно познать», «Законы природы нельзя изменить»; д) «Лиственные деревья сбрасывают зимой листву», «Береза – лиственное дерево»; е) «Я буду готовиться к занятиям дома», «Я буду готовиться к занятиям в библиотеке»; ж) «Геометрия Евклида непротиворечива», «Геометрия Лобачевского непротиворечива»; з) «Солнечный день», «Температура 240С», «Поехали на пикник»; и) «Система линейных уравнений имеет единственное решение», «Определитель главной матрицы равен нулю»; к) «ЭВМ быстро обрабатывает информацию», «Проведенный эксперимент дал очень много информации». 4. Определите истинность или ложность суждения: а) Число либо четное, либо нечетное; б) Солнце всходит на востоке; в) Стример – это устройство ввода информации; г) Понедельник начинается в субботу; д) Ночью все кошки серые; е) Это предложение ложно; ж) В следующем году мы пойдем в горы; и) В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам; к) Суждение может быть истинным или ложным. 5. Определите истинность высказываний и тип логической операции: а) Луна – планета Солнечной системы и 17 – простое число; б) Луна – планета Солнечной системы или 17 – простое число; в) Кислород – металл или квадрат прямоугольник; г) Данное число четно или число, большее его на единицу, четно; д) Две прямые на плоскости параллельны и пересекаются; е) Эйфелева башня находится в Париже или она находится в Нью-Йорке; ж) Либо Эйфелева башня находится в Париже, либо она в Нью-Йорке; з) Произвольно взятое число либо делится на 2, либо делится на 3; и) Если Солнце всходит на юге, то оно заходит на западе; к) Если Солнце всходит на востоке, то оно заходит на западе.
Определим еще ряд важных формул, позволяющих упрощать логические выражения: 1. 2. 3. 4. Пример: Упростить логическое выражение: Решение - по закону дистрибутивности А вынесли за скобку; - по закону исключения третьего в скобках имеем 1; - свойство констант; Ответ: Пример: Упростить логическую функцию: Решение - используя свойство констант, добавим единичку; - заменяем единицу по закону исключения третьего; - раскрыли скобки; - добавим основываясь на закон идемпотентности; - группируем и выносим за скобки по закону дистрибутивности; - используем закон исключенного третьего; - свойства констант; Ответ: Пример: 1. Размер таблицы истинности определяется по количеству простых высказываний и количеству переменных и логических операций: Количество строк = 2n + 1 (n - количество простых высказываний, а еще одна строка добавляется для заголовка) Количество столбцов = количество переменных + количество логических операций 2. Построить таблицу истинности с исходными данными, учитывая все возможные сочетания логических значений 0 и 1.. 3. При построении таблиц истинности для сложных высказываний необходимо учитывать порядок выполнения логических операций в сложном логическом выражении: 1) инверсия; 2) конъюнкция; 3) дизъюнкция; 4) импликация; 5) эквивалентность. Пример: Построить таблицу истинности для логического выражения: Решение n=3 (A, B, C), следовательно в таблице истинности 9 строк и 3 переменные и 3 операции потребуют 6 столбцов.
Пример: Докажите, что выражение всегда принимает значение ИСТИНА. Доказательство представлено в следующей таблице
Пример: Доказать, что логическое выражение равносильно эквивалентности. Доказательство представлено в следующей таблице
Из таблицы видно, что высказывание верно в тех случаях, когда значения А и В одинаковые, что соответствует операции эквивалентности . Алгебра логики напрямую связана с построением функциональных схем ЭВМ. Пример: Постройте схему, работа которой описывается логической формулой Решение & 1 X Y Z Пример: Запишите логическую функцию, описывающую состояние функциональной схемы: Решение Ответ 1 & X Y Z 1 & X Y Z 1. Выберите в таблице истинности те строки, в которых значение функции равно единице. 2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выбранных строк. 3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции. 4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно нулю, то этот аргумент мы берем с отрицанием. Пример: Дана таблица истинности для некоторой логической функции F(X,Y), необходимо построить логическую функцию F: Решение 1. В таблице 2 строки, в которых значение функции равно 1; 2. Функция будет иметь вид дизъюнкции двух элементов; 3. Оба элемента дизъюнкции записываем в виде конъюнкции
4. По первой строке X=0 и Y=0, следо-вательно, оба аргумента необходимо взять с отрицанием: . По третьей строке X=1, а Y=0, значит, с отрицанием берем только Y: . Получаем функцию: Упрощаем полученную функцию: Проверка Для проверки достаточно создать таблицу истинности полученной функции: Ответ
Обычно используется следующая схема решения: 1. Вводится система обозначений для логических высказываний 2. Конструируется логическая формула, описывающая логи-ческие связи между всеми высказываниями условия задачи 3. Определяются значения истинности этой логической формулы 4. Из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении Пример: Определить, кто из подозреваемых участвовал в создании вредоносной программы, если известно: а) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал; б) если Иванов не участвовал, то Сидоров не участвовал. Решение 1. Введем следующие высказывания: И — «Иванов участвовал в создании вредоносной программы»; П — «Петров участвовал в создании вредоносной программы»; С — «Сидоров участвовал в создании вредоносной программы». 2. Переведем заданные условия на язык формальной логики: а) б) Оба высказывания истинны по условию задачи. Конъюнкция полученных высказываний соответствует условию задачи. Получаем: 3. Таблица истинности полученной функции: 4. Из таблицы видно, что функция принимает значение ИСТИНА в трех строках. В этих строках переменная И всегда принимает значение ИСТИНА, а переменные П и С имеют разные значения. Следовательно, в создании вредоносной программы принимал участие Иванов. Ответ: Иванов
Пример: Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. У двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение Исходные данные разбиваются на тройки (имя — профессия — увлечение) и составляется таблица, которая заполняется исходя из беседы друзей: Юрий не врач и не увлекается туризмом, а из слов врача понятно, что он увлекается туризмом.
Буква «а», присутствующая в слове «врач», указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы «т» и «р», встречающиеся в слове «туризм», следовательно, второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы «ю» и «р». Следовательно, окончательно имеем:
1. Составите таблицы истинности для логических выражений: а) не А и В б) не (А и В) в) (А и В) или С г) не (А и В и С) д) (А или (В и не С)) е) ж) з) и) к) 2. Упростите: а) б) в) г) д) е) ж) з) и) к) 3. Определите вид сложного высказывания, записать его структуру формулой логики высказываний, упростите полученную функцию при необходимости: а) Ни сна, ни отдыха измученной душе; б) Чай ни горячий, ни холодный; в) Я поеду в Москву, и если встречу там друзей, то мы интересно проведем время; г) Свет включен, а лампочка не горит, значит, нет электричества или перегорели пробки или перегорела лампочка; д) Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя; е) Члены финансового комитета должны избираться среди членов дирекции. Нельзя быть одновременно членом дирекции и членом библиотечного совета, не будучи членом финансового комитета. Член библиотечного совета не может быть членом финансового комитета. 3. Постройте функциональную схему: а) (А или В) и не С б) (Х или не Y) и не (Z и не Y) в) г) д) 4. Определите логическую формулу функциональной схемы, составьте таблицу истинности: а) б) & 1 А В 1 & 1 X Y Z б) д) в) е) & 1 X Y Z 1 & X Y Z 1 & X Y Z & 1 X Y Z 5. Условия работы схемы заданы таблицей истинности. Составьте формулу логической функции, упростите ее, начертите схему, путем тестирования полученной схемы проверьте правильность: а) б)
6. Упростите логическую схему: 7. Решите логическую задачу: а) Кто из абитуриентов Антипов, Белов, Соловьев и Дорофеев играет, а кто не играет в шахматы, если известно следующее:
б) Сформулируйте данный прогноз в лаконичной форме: 1 & X Y в) В студенческую команду КВН приняли трех студентов-первокурсников: Иванова, Петрова и Сидорова. Новички талантливы, умеют: петь, монтировать видео и звук, писать сценарии, пародировать, показывать пантомиму, танцевать. Известно, что:
Кто чем занимается, если известно, что каждый из новичков обладает двумя талантами. г) Вадим, Сергей и Михаил изучают различные иностранные языки: английский, немецкий и французский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает английский, Сергей не изучает английский, а Михаил не изучает французский». Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей? д) Если из четырех лекций в расписании занятий за математикой может следовать любая дисциплина, информатика может следовать только за математикой, а английский язык - только за информатикой, то какой по счету лекцией может быть история? Определить за минимум рассуждений. Одно рассуждение - простое высказывание относительно одного из перечисленных предметов. е) Студент А - отличник, у Б - пятерка или четверки, у В и Д - четверки или тройки, у Г - возможны все оценки. Какие оценки у каждого из них по контрольной работе, если все они получили различные оценки? ж) Обсуждая свои возможности по поступлению в вуз, абитуриенты Андрей, Борис и Владимир высказали следующие предположения (в виде сложного высказывания, состоящего из двух простых высказываний) вида: Андрей – «Я не смогу поступить, а Владимир - поступит»; Борис – «Владимир не поступит, а Андрей – поступит»; Владимир – «Если я поступлю, то Борис - не поступит или наоборот». После сдачи экзаменов выяснилось, что каждый высказал одно верное и одно ложное простое утверждение. 1) Кто поступил в вуз, если не смог поступить лишь один из них? 2) Кто поступил в вуз, если поступил лишь один из них? з) Виктор, Роман, Юрий и Сергей заняли на олимпиаде по информатике первые четыре места. Когда их спросили о распределении мест, они дали три таких ответа: Сергей - первый, Роман - второй; Сергей - второй, Виктор - третий; Юрий - второй, Виктор - четвертый. Как распределились места, если в каждом ответе только одно утверждение истинно? и) Квадрат, круг, ромб и треугольник вырезаны из белой, синей, красной и зеленой бумаги. Известно, что: круг не белый и не зеленый; синяя фигура лежит между ромбом и красной фигурой; треугольник не синий и не зеленый; квадрат лежит между треугольником и белой фигурой. Определите геометрическую форму зеленой фигуры. к) Борис, Виктор, Григорий и Егор встретились на конференции. Студенты приехали из разных городов: один – из Твери, другой – из Омска, третий – из Томска, а четвертый – из Казани. Из-вестно, что Борис жил в одной комнате с парнем из Казани и ни один из них никогда не был ни в Твери, ни в Томске. Григорий играл в одной команде с товарищем из Твери, а против них обычно сражался приятель из Казани. Егор и студент из Твери увлекались игрой в шахматы. Из какого города приехал Виктор. 12. Проверьте правильность следующего умозаключения. Для того чтобы Саша прошел по конкурсу в ОмГУ, достаточно, чтобы или Аня, или Вика не прошли по конкурсу в университет. Вика пройдет по конкурсу вместе с Димой. Не может быть, чтобы по конкурсу прошли и Аня, и Саша. Вывод: для того чтобы Аня прошла по конкурсу в институт, необходимо, чтобы по конкурсу прошли Дима и Саша. Математический аппарат алгебры логики очень удобен для описа-ния того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная система, а значений логических переменных тоже два. Из этого следует два вывода: 1. Одни и те же устройства компьютера могут применяться для обработки и хранения как числовых данных, представленных в двоичной системе счисления, так и логических переменных; 2. На этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера. Задача: Пусть в некотором конкурсе решается вопрос о допуске участников к следующему туру тремя членами жюри, один из которых является председателем. Решение положительно, если председатель и хотя бы один член жюри высказались за допуск участника. Необходимо разработать устройство для голосования: каждый член жюри нажимает на одну из двух кнопок «за» или «против», если все условия соблюдаются, загорается сигнальная лампочка. Решение Формально, задача сводится к следующему: требуется составить функциональную схему устройство, которое выдает 1, если участник допускается к следующему туру или 0, если участник выбывает из конкурса.
таблицы, для этого обозначим председателя жюри A, а рядовых членов жюри В и С.
2. Построим логическую функцию на основе нашей таблицы: 3. Упростим полученную функцию Имеем: Для проверки построим таблицу истинности: Таблица равна исходной, следовательно, функция построена верно. 4. Построим логическую схему для функции 1 & A B C
1. Постройте функциональную схему, содержащую 4 переключателя, которая проводит электрический ток только в том случае, если включен 4-ый переключатель и хотя бы один из трех оставшихся переключателей. 2. Постройте схему с пятью переключателями, которая проводит электрический ток только в том случае, когда замкнуто ровно 4 переключателя. 3. В комнате три стола, на каждом столе кнопки. Составьте схемы, выполняющие следующие условия: а) верхний свет в комнате зажигается нажатием кнопки на одном из столов; б) верхний свет в комнате зажигается только в случае одновременного нажатия кнопок на всех столах. 4. Судейская коллегия, состоящая из трех членов, выносит решение большинством голосов при тайном голосовании. Постройте такую схему, чтобы голосование каждого члена «за» производилось нажатием кнопки (включением выключателя) и в случае принятия решения загоралась сигнальная лампа. 5. В результате тестирования схемы (проверки всех возможных комбинаций входящих сигналов) оказалось, что выходной сигнал является тавтологией инвертора одного из входящих сигналов. Необходимо найти этот входной сигнал и упростить схему. 1 & 1 & X Y Z 6. Инженер создал некоторое устройство. В процессе разработки стало ясно, что чаще всего выходят из строя три узла устройства. О неисправности каждого узла можно судить по трем сигнальным лампочкам. Первоначально, для диагностики и ремонта устройства составлена следующая инструкция:
В процессе тестирования устройства загорелась первая лампочка. Необходимо определить, какие узлы вышли из строя, и проверить состоятельность прилагаемой инструкции. |