Логические основы эвм

ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

Вы теперь знаете, как компьютер «запоминает» информацию. Ещё интереснее вопрос: как он «думает». Вы также знаете, что создатели компьютерных средств при разработке методов кодирования, хранения, поиска информации в качестве базовых моделей - образцов для подражания выбирают то, как эти операции выполняются человеком. Полностью реализовать мышление человека компьютерными средствами в ближайшее время вряд ли удастся, но простейшие модели мышления реализованы уже сейчас: работа процессора и устройств памяти компьютера реализована на тех же логических операциях, которые свойственны простейшим формам мышления человека. Эти формы мышления исследуются в такой области науки, как формальная логика, язык которой основан на двоичном алфавите: истина (1) и ложь (0). Применению формальной логики в компьютере и построению моделей функционирования основных устройств ЭВМ посвящена эта глава.

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

§ 1. Логические операции

ПОНЯТЬ

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

Немного истории.

Впервые самые общие закономерности логики как науки о формах мышления были сформулированы выдающимся древнегреческим философом Аристотелем (IV до н.э.). Это его слова «Корни учения горьки, но плоды сладки» можно считать девизом всех познающих мир. Это его совету: «Догонять тех, кто впереди, и не ждать тех, кто позади», - следуют те, кто хочет преуспеть в учении.

Аристотель создавал логику как науку о доказательстве истины, стремился придать логическим рассуждениям математическую строгость и стройность. Он стал применять символы-буквы для обозначения различных объектов в логических рассуждениях, стремясь свести размышление (умозаключение) к вычислениям. Именно он впервые вывел «правильные» формы умозаключений – силлогизмы.

Пример силлогизма Аристотеля:

Исходные истинные суждения: Все люди смертны

Сократ – человек

Вывод силлогизма: Сократ смертен.

Создать «азбуку понятий», чтобы облегчить процесс человеческого мышления, решил другой великий ученый – немецкий философ и математик Готфрид Вильгельм Лейбниц (1646 – 1716). Он разрабатывал универсальный язык символов, который должен быть кратким и сжатым, а знаки должны заключать максимум смысла и передавать идеи как можно более естественным образом. Ему принадлежит идея логического исчисления, то есть четко сформулированные правила действий со словами и предложениями, сродни арифметическим правилам действий с числами. В соответствии с этими правилами простые элементы логических рассуждений (понятия) обозначаются буквами, сложные элементы (предложения) – формулами, а умозаключения – уравнениями. «Единственное средство улучшить наши умозаключения – сделать их, как у математиков, наглядными, и если среди людей возникнет спор, нужно сказать «Посчитаем!»; тогда без особых формальностей можно будет увидеть, кто прав», - писал Лейбниц.

Лейбниц заложил идейный фундамент математической логики, а над постройкой самого здания – практической реализацией этих идей работали и работают многие учёные. Итогом их труда стало создание компьютера, а одним из первых был ирландский логик и математик Джордж Буль (1815 – 1864). Он искал пути законов мы применения алгебраических методов к логическим рассуждениям при решении логических задач. «Исследование законов мышления, на коих основаны математические теории логики и вероятностей».

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

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

Рассмотрим основные положения алгебры логики.

Любое рассуждение состоит из отдельных суждений, каждое из которых может быть истинным или ложным.

Пример

Истинные суждения:

А=«День сменяет ночь»=1

В=«Земля и Луна вращаются вокруг Солнца»=1

С=«Если звёзды зажигают – значит – это кому-нибудь нужно»=1

D=«Суждение либо истинно, либо ложно»=1

Ложные суждения:

Е=«Чтобы стать умнее, учиться не нужно»=0

F=«Суждения могут быть одновременно истинными и ложными»=0

G=«Он – родной сын бездетных родителей»=0

Высказывания, не являющиеся суждениями в алгебре логики:

«Выполни эту просьбу» (приказ, распоряжение).

«Завтра будет хорошая погода» (вероятностное высказывание, предсказание).

«Почто, о боги, в этом мире должно быть дважды два – четыре?» (вопрос).

Если суждение А истинно, то будем обозначать А = 1, если суждение А ложное, то будем обозначать А = 0.

Суждения могут быть простыми и сложными.

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

Логическое отрицание (инверсия)

Пример

Исходное суждение: «Все школьники - отличники» (А = 0). Инверсия: «Неверно, что все школьники отличники» ().

Исходное суждение: «В лесу растут деревья» (А = 1). Инверсия: «В лесу не растут деревья» ().

Суждение = «Неверно, что он не знает китайского языка» тождественна суждению А = «Он знает китайский язык».

Логическое умножение (конъюнкция)

Пример

Исходные суждения: А = «Каждый человек имеет право на образование» = 1; В = «Все школьники - отличники» = 0. Конъюнкция: АВ = «Каждый человек имеет право на образование и все школьники отличники» = 0.

Исходные суждения: А = «Существует растровая графика» = 1; В = «Существует векторная графика» = 1. Конъюнкция: АВ = «Существуют растровая и векторная графика» = 1.

Обычно конъюнкция означает одновременность событий, о которых идёт речь в суждениях. Но многозначность русского языка приводит к тому, что союз «и» используется, например, и для обозначения последовательных действий. Если нет уверенности, что сложное суждение является конъюнкцией, можно проверить, выполняется ли для входящих в него простых суждений закон коммутативности.

Пример

Суждение Х = «Прозвенел школьный звонок и начался урок» не является логическим умножением высказываний А = «Прозвенел школьный звонок» и В = «Начался урок», поскольку не выполняется закон коммутативности: суждение АВ не совпадает по смыслу с суждением ВА = «Начался урок и прозвенел школьный звонок».

Логическое сложение (дизъюнкция)

Пример

А = «Он склонен к гуманитарным наукам»; В= «Он склонен к точным наукам». АВ = «Он склонен к гуманитарным или точным наукам»

Логическое следование (импликация)

Пример

Рассмотрим суждение «Если на улице идёт дождь (А), то асфальт мокрый (В)». Асфальт может быть сухим (В=0), когда нет дождя (А=0). Асфальт может быть мокрым (В=1), когда нет дождя (А=0), например, дождь уже закончился, но земля еще не просохла. Асфальт может быть мокрым (В=1), во время дождя (А=1). Но не может быть, чтобы асфальт был сухим (В=0) во время дождя (А=1).

Логическое равенство (эквивалентность)

Пример

Суждения А=«Данное число кратно двум» и В=«Данное число чётно» являются эквивалентными, потому что для каждого конкретного числа они или оба истинны, или оба ложны.

Суждения А= «Если он выполнит все задания, то получит пятёрку» и В= «Он не выполнил все задания или получил пятёрку» тоже эквивалентны, потому что формула , описывающая эти высказывания, является законом алгебры логики.

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

ЗНАТЬ

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

Логическое отрицание – инверсия – образуется добавлением частицы «не» к глаголу или с помощью оборота «неверно, что». Инверсия истинна только тогда, когда исходное суждение ложно. Обозначается: ¬А, , not A.

Логическое умножение – конъюнкция – образуется с помощью соединительного союза «и». Конъюнкция истинно только тогда, когда истинны все входящие в неё суждения. Обозначается: AB, AB, A and B.

Логическое сложение – дизъюнкция – образуется с помощью союза «или». Дизъюнкция истинна, когда истинно хотя бы одно входящее в неё простое суждение. Обозначается: AB, AB, A or B.

Логическое следование – импликация - образуется с помощью оборота речи «если…, то…». Импликация ложна только тогда, когда из истинного суждения следует ложное суждение. Обозначается: AB, A  B.

Логическое тождество – эквивалентность – образуется с помощью оборота речи «…тогда и только тогда, когда…». Эквивалентность истинна, когда значения истинности простых суждений совпадают. Обозначается: A = B, A  B, A  B.

УМЕТЬ

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

Определите значение истинности следующих простых суждений:

а) А = Урок длится 45 минут;

б) В = Процессор является устройством обработки информации;

в) С = Переименуй данный файл;

г) D = Оперативная память является устройством кодирования информации;

д) E = Что такое сканер?

Определите значение истинности следующих сложных суждений:

а) W = Неверно, что существует векторный способ кодирования изображений;

б) V = Для кодирования чисел в компьютере используется непозиционная система счисления и двоичный алфавит;

в) X = Компьютер является или не является кибернетической системой;

г) Y = Если компьютер является кибернетической системой, то для его изучения можно применять модель «чёрного ящика»;

д) Z = Текст можно отобразить на экране дисплея тогда и только тогда, когда дисплей включен и текст находится в оперативной памяти.

7