Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков
 Скачать 14.49 Mb.
|
Х = Х, X V X Я х , ( i A i ) v y = y. Тавтологией, или тождественно истинной, называется формула, принимающая значение 1 при всех значениях входящих в нее переменных. Пример. Тождественно истинные формулы: X V X, i D ( i D у). Тождественно ложной называется формула, принимающая значение 0 при всех значениях входящих в нее переменных. \ Пример. Тождественно ложная формула: х л х Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А ** В — тавтология, и об ратно, если формула Л +* В — тавтология, то формулы А и В равносильны. 116 Глава 4. Логические основы информатики Важнейшие равносильности алгебры логики можно разбить на три группы: □ основные равносильности; □ равносильности, выражающие одни логические операции через другие; □ равносильности, выражающие основные законы алгебры логики. Используя приведенные далее равносильности, можно часть формулы или формулу полностью заменить равносильной ей формулой. Такие преобразования формул называются равносильными. Равносильные преобразования используются для доказательства равносиль ностей, для приведения формул к заданному виду, для упрощения формул. Формула А считается проще равносильной ей формулы В , если она содержит меньше символов, меньше логических операций. При этом обычно операции экви валентности и импликации заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям. 4.2.3. Основные равносильности 1. X А X = X. 2. X V X Ш х. 3. X А 1 ■ X. 4. x v 1 = 1. 5. х д 0 я 0. 6. i v 0 = 1 7. х а х = 0 — закон противоречия. 8. i v i s l - закон исключения третьего. 9. i s х — закон снятия двойного отрицания. 10 ХА ( y v x ) = x . 11 ХУ (у А х ) = х . 4.2.4. Равносильности, выражающие одни логические операции через другие 1. ( х = у ) = ( х Э у ) ( у Dx) . 2. х Э у в х v у. 3. X А у = ХУ у. 4. X V у = Х А у. 5. X А у S х V у. 6. X У у = X А у. Из равносильностей этой группы следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание. 4.2. Алгебра логики 117 Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула, как отрицание х, не мо жет быть выражена с помощью операции конъюнкции. Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией являет ся, например, операция Штрих Шеффера. Эта операция обозначается символом | и определяется следующей таблицей истинности: X У Л у 1 1 0 1 0 1 0 1 1 0 0 1 Очевидно, имеют место равносильности: 1. х = х \ х . 2. х л у = ( х \ у ) \ ( х \ у ) . Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию Штрих Шеффера. Отметим также, что х \ у ■ х д у. 4.2.5. Равносильности, выражающие основные законы алгебры логики 1. х л у = у а х — коммутативность конъюнкции. 2. х у у = у у х — коммутативность дизъюнкции. 3. х а (у a z) s (х а у) a z — ассоциативность конъюнкции. 4. х у (у у z) = (x у у) у z — ассоциативность дизъюнкции. 5. х а (у у z) = ( х а у) у (х a z) — дистрибутивность конъюнкции относительно дизъюнкции. 6. х у (у a z) = ( х у у) а (х у z) — дистрибутивность дизъюнкции относительно конъюнкции. 4.2.6. Решение логических задач методами алгебры логики Суть применения методов алгебры логики к решению логических задач состоит в том, что конкретные условия логической задачи необходимо представить в виде формул алгебры логики. В дальнейшем путем равносильных преобразований полу ченную формулу упрощают. Полученная в результате преобразований упрощенная формула, как правило, приводит к ответу на вопрос задачи. 118 Глава 4. Логические основы информатики Пример. Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили: 1. Антон был вторым, а Борис — пятым. 2. Виктор был вторым, а Денис — третьим. 3. Григорий был первым, а Борис — третьим. 4. Антон был третьим, а Евгений — шестым. 5. Виктор был третьим, а Евгений — четвертым. Впоследствии выяснилось, что каждый зритель ошибся в одном из двух своих высказываний. Каково было истинное распределение мест в турнире? Обозначим участника первой буквой его имени, нижний индекс около буквы (цифра) будет обозначать номер места, которое он занял в турнире, то есть в вы ражении Ху имеем, что X — это участник турнира, а у — номер места, которое он занял в турнире. Обозначим буквой L истинное распределение мест в турнире (1 = 1). Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то дизъюнкции этих высказываний будут истинными: Л2 у Б5= 1. В -2 v Дз = 1. Г{ vf t-l . А3 v Е6= 1. B3 v E Aml . Тогда будет истинной формула L ■ (Л2 v Б5) а ( В2 v Дз) л (Г, v Б3) л (Л3 v Е6) л (В3 v ЕА). Исходя из данных условия, можно начать преобразования. Поскольку одно из входящих в дизъюнкции высказываний обязательно истинно, а второе обязатель но ложно, то за отправную точку в преобразованиях можно принять пару ^ v б5 = 1 . В этой паре высказывание Гх является истинным, а Б3 — ложным, поскольку на первое место нет других претендентов. Тогда, используя равносильность х v О ■ х у получаем Гх v 0 = Ги и формула приводится к виду 1 з ( А , v Б5) л (В2 v Д5)л Г х л(А, v £6) л(В3 vE 4). Поскольку вариант Б3 оказался ложным, а других претендентов на пятое место нет, то истинным будет вариант Б5. Тогда в первой по счету паре, применив ту же равносильность, что и на предыдущем шаге, мы также оставляем одно высказы вание, и основная формула принимает вид L = Б5 а (В2 v Д 3) л Г{ л (А3 v Е^) л (2?3 v ЕА). Продолжая эти равносильные преобразования, приводим формулу к виду L = Б5 а В2 а Г х л А3 а Е4. Отсюда следует, что Б5 = 1, В2 = 1, Г = 1, А3 = 1, ЕА = 1, то есть первым был Григо рий, вторым — Виктор и т. д. Это и является ответом на вопрос, поставленный в задаче. 4.2. Алгебра логики 119 4.2.7. Булева алгебра Без булевой алгебры было бы невозможно создание таких устройств, как со временные компьютеры, в состав центральных процессоров которых входят мил лиарды электронных переключателей. Рассмотрим непустое множество М элементов любой природы (г, г/, 2 ,...}, в ко тором определены отношение равенства (=) и три операции: сложение (+), умно жение (•) и отрицание О , подчиняющиеся следующим законам: □ Коммутативные законы: х + у = у + х; х - у = у - х . □ Ассоциативные законы: x + ( y + z ) - ( x + y) + z; x - ( y - z ) - ( x - y ) - z . □ Дистрибутивные законы: ((х + г/) • z) = (х • z) + (г/ • z); ( ( x- y ) + z ) - ( x + z ) - ( y + z). □ Законы идемпотентности: х + х = х; □ Закон двойного отрицания: х = х. □ Законы де-Моргана: x T y = x- J; Х ' У = Х + у а Законы поглощения: х + (г/ • х ) = х; х - ( у + х) = х. Такое множество М называют булевой алгеброй. Если под основными элементами х, г/, 2 ,... подразумевать высказывания, под операциями сложения, умножения и отрицания булевой алгебры — соответственно, дизъюнкцию, конъюнкцию и отрицание алгебры высказываний, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей алге бры высказываний, все аксиомы булевой алгебры выполняются. В тех случаях, когда для некоторой системы аксиом удается подобрать конкрет ные объекты и конкретные соотношения между ними так, что все аксиомы выпол няются, говорят, что найдена интерпретация, или модель, данной системы аксиом. Значит, алгебра логики является интерпретацией булевой алгебры. Булева алгебра имеет и другие интерпретации. Например, если под основными элемен тами х, г/, г,... множества М подразумевать множества, под операциями булевой 120 Глава 4. Логические основы информатики алгебры — соответственно, объединение, пересечение и дополнение множеств, а под знаком равенства — знак равенства множеств, то мы приходим к алгебре множеств. Нетрудно убедиться, что и в алгебре множеств все аксиомы булевой алгебры выполняются. Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каково количество функций п переменных? Очевидно, каждую функцию ал гебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2п строк. Следовательно, каждая функция п переменных принимает 2п значений, состоящих из нулей и единиц. Таким обра зом, функция п переменных полностью определяется набором значений из нулей и единиц длины 2п. Общее же количество наборов, состоящих из нулей и единиц длины 2п равно 22”. Значит, количество различных функций алгебры логики п переменных равно 22”. В частности, различных функций одной переменной четыре, а различных функ ций двух переменных — шестнадцать. Выпишем все функции алгебры логики одной и двух переменных. Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид X f i x ) /г ( * ) /з ( * ) М х ) 1 1 1 0 0 0 1 0 1 0 Из этой таблицы следует, что две функции одной переменной будут постоян ными: f \ ( x ) = 1 и f 4(x) = 0, a f 2(x) я х и / 3(г) = х. Таблица истинности для всевозможных функций двух переменных имеет вид X У / /« / з Л л /б f j л /9 /и /1 2 /1 3 и /l5 /1 6 1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 Ясно, что аналитические выражения этих функций могут быть записаны сле дующим образом: 4.3. Построение коммутационных схем на основе алгебры логики 121 /,з = г/элг; / 2 = х ч у; / з ^ у э х ; fi =хэу; f n = x v у; f u в х э у ; / 15 = х л у; />6 = 0. 4.3. Построение коммутационных схем на основе алгебры логики Среди технических средств автоматизации значительное место занимают устройства релейно-контактного действия. Они широко используются в технике автоматического управления, в электронно-вычислительной технике, и т. д. Эти устройства (их в общем случае называют переключательными, или ком мутационными, схемами) содержат сотни реле, полупроводниковых элементов и других переключающих элементов. Описание и конструирование таких схем в силу их большого объема представляет трудную задачу. Еще в 1910 году физик П. С. Эренфест указал на возможность применения ап парата алгебры логики при исследовании релейно-контактных схем. Однако его идеи начали реализовываться значительно позже, когда создание общей теории конструирования таких схем стало остро необходимым. Использование алгебры логики в конструировании коммутационных схем оказалось возможным в связи с тем, что каждой схеме можно поставить в соот ветствие некоторую формулу алгебры логики и каждая формула алгебры логики реализуется с помощью некоторой схемы. Это обстоятельство помогает выявить возможности упрощения заданной схемы, изучая соответствующую формулу, а упрощение формулы затем реализовать как упрощение схемы. В то же время еще до построения схемы можно заранее описать с помощью формул те функции, которые схема должна выполнять. Рассмотрим, как устанав ливается связь между формулами алгебры логики и переключательными схемами. Под переключательной схемой понимается схематическое изображение неко торого устройства, состоящего из □ переключателей; □ соединительных проводников; □ входов в схему и выходов из нее. Переключателями могут быть электромеханические устройства (выключатели, переключатели, кнопки), электромагнитные реле, полупроводниковые элементы и т. п., а входами и выходами — клеммы, на которые подается электрическое на пряжение. Коммутационной схемой принимается в расчет только два состояния каждого переключателя, которые называются «замкнутым» и «разомкнутым». 122 Глава 4. Логические основы информатики Рассмотрим схему переключения, состоящую из источника питания и электри ческой лампочки (рис. 4.1). Рис. 4 .1 . Схема с последовательным соединением переключателей Присвоим значение 1 переключателям р и q, если они замкнуты (то есть элек трический ток проходит через них). В противоположной ситуации присвоим им значение 0. Присвоим значение 1 схеме, когда лампочка светится (то есть элек трический ток через нее проходит). Заметим, что при последовательном соеди нении элементов цепи p n q , как это имеет место на приведенной схеме, лампочка загорается и значение схемы становится равным 1 только в том случае, когда оба переключателя замкнуты, то есть когда и р, и q имеют значение 1. Таким образом, схема соответствует высказыванию р д q. Такое расположение переключателей называется логическим элементом p u q , или схемой логического умножения. Этот логический элемент обозначается символом, изображенным на рис. 4.2. Рис. 4 .2 . Элемент логического умножения Рассмотрим схему переключения, показанную на рис. 4.3, где переключатели р и q соединены параллельно. Рис. 4 .3 . Схема с параллельным соединением переключателей Отметим, что лампочка загорается и значение схемы становится равным 1, когда один из двух переключателей (р или q) замкнут, то есть либо р = 1, либо q = 1 (либо оба они равны 1). Эта схема соответствует высказыванию p v q . Такое 4.3. Построение коммутационных схем на основе алгебры логики 123 расположение переключателей называется логическим элементом р или q , или схемой логического сложения. Этот логический элемент обозначается символом, изображенным на рис. 4.4. p v q Рис. 4 .4 . Элемент логического сложения Предположим, имеется схема с одним переключателем р, который обладает та ким свойством, что лампочка загорается тогда и только тогда, когда переключатель разомкнут. Следовательно, схема имеет значение 1, когда р равно 0, и значение О, когда р равно 1. Эта схема соответствует р, а соответствующий логический элемент называется логическим элементом не, или инвертором (рис. 4.5). Р -------------------Р Рис. 4 .5 . Инвертор Пример. Схема на рис. 4.6 содержит логический элемент р г/ за которым следует инвертор, так что схема соответствует выражению р д q. Заметим, что инвертор отрицает всю предшествующую ему схему. Р- Я - Рис. 4 .6 . Логическая схема р л q Пример. Схема на рис. 4.7 содержит соединение логического элемента р или q с логическим элементом не г посредством логической схемы умножения. Следо вательно, она соответствует выражению (p v q ) л г. Из трех логических элементов, соответствующих выражениям сложения, ум ножения и отрицания в булевой алгебре, можно строить электронные логические схемы любой сложности. На практике часто встречаются обозначения, принятые для цифровых микро схем: & 1 1 — «и», — «или», — •— «не» 124 Глава 4. Логические основы информатики Вопросы для самопроверки 1. Почему изучение логических основ так важно для понимания информатики? 2. Дайте определение понятию простого высказывания. Приведите примеры. 3. Является ли предложение «Который сейчас час?» простым высказыванием с точки зрения математической логики? 4. Какие логические операции над высказываниями вам известны? 5. Дайте определение конъюнкции и дизъюнкции, приведите примеры. 6. Дайте определение импликации и эквивалентности, приведите примеры. 7. Дайте определение формулы алгебры логики. 8. Какие формулы алгебры логики называются равносильными? 9. Приведите формулы законов идемпотентности. 10. Приведите формулы законов поглощения. 11. Как записывается и чем примечательна логическая операция Штрих Шеффера? 12. Какими формулами записываются законы идемпотентности в булевой алгебре? 13. Дайте определение функции Буля. 14. Что такое «переключательная (коммутационная) схема»? 15. Нарисуйте коммутационную схему, реализующую логическую операцию И. 16. Нарисуйте коммутационную схему, реализующую логическую операцию ИЛИ. 17. Чем важна булева алгебра для информатики и компьютерной техники? Литература 1. Аляев Ю. А.у Тюрин С. Ф. Дискретная математика и математическая логика. М.: Финансы и статистика, 2006. 2. Верещагин Н. К., Плиско Н. К., Успенский В. А. Вводный курс математической логики. М.: Физматлит, 2004. 3. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2003. Глава 5 Информационные системы и технологии 5.1. Основные сведения об информационных системах 5.2. Структура и классификация информационных систем 5.3. Основные сведения об информационных технологиях 5.4. Виды информационных технологий В прошлом информация считалась сферой бюрократической работы и огра ниченным инструментом для принятия решений. Сегодня информацию рассма тривают как один из основных ресурсов развития общества, а информационные системы (И С ) и технологии (И Т) — как средство повышения производительности и эффективности работы людей. Наиболее широко информационные системы и технологии используются в производственной, управленческой и финансовой деятельности, хотя относи тельно необходимости их внедрения и активного применения начались подвижки в сознании людей, занятых и в других сферах. Это определило угол зрения, под которым будут рассмотрены основные области их применения. Главное внимание уделяется рассмотрению информационных систем и технологий с позиций ис пользования их возможностей для повышения эффективности труда работников информационной сферы производства и поддержки принятия решений в органи зациях (фирмах). 126 Глава 5. Информационные системы и технологии 5.1. Основные сведения об информационных системах 5.1.1. Понятие информационной системы Под системой понимают любой объект, который одновременно рассматривается и как единое целое, и как объединенная в интересах достижения поставленных целей совокупность разнородных элементов. Системы значительно различаются между собой как по составу, так и по достигаемым целям. Информационные системы обеспечивают сбор, хранение, обработку, поиск и вы дачу информации, необходимой в процессе принятия решений в любой области деятельности. Они помогают анализировать проблемы и создавать новые продукты. Современное понимание информационной системы предполагает использова ние персонального компьютера в качестве основного технического средства перера ботки информации. В крупных организациях наряду с персональным компьютером в состав технической базы информационной системы может входить мэйнфрейм или суперЭВМ. Кроме того, техническое воплощение информационной системы само по себе ничего не будет значить, если не учтена роль человека, для которого предназначена производимая информация и без которого невозможно ее получение и представление. В Н И М А Н И Е -------------------------------------------------------------------------------------------------------------- |