Информационно-дидактический блок (аннотация, пособия)

1.Булева алгебра и логические схемы,алгебра логики

Многие задачи, решаемые с помощью ЭВМ, являются «логическими». Для решения таких задач применяют алгебру логики.

Алгебра логики (иначе называют алгеброй суждений) как раздел математической логики впервые возник в середине ХІХ века в трудах английского математика Джорджа Буля, поэтму честь его названа Булевой алгеброй. Булева алгебра — результат стремления решить традициолнные логические задачи алгебраическими методами — хорошо освоена в информатике.

Булева алгебра составляет теоретическую основу логики, теории алгоритмов и логического проектирования.

От обычной, привычной нам алгебры, булева алгебра отличается тем, что ее логические аргументы (переменные) могут принимать лишь два значения, а основных функций в булевой алгебре всего три: логическое умножение И, логическое сложение ИЛИ и отрицание НЕ.

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

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

2.«Суждения», логические связки

Общение людей как форма обмена информацией — эточередование вопросов и ответов. Каждый вопрос "выражает потребность в знании сведений об окружающем нас предметном мире. Эти знания мы высказываем в форме суждений. Суждения могут выражать непосредственно наблю­даемые факты: «На улице дождь», «Этот треугольник — равнобедренный» и т.п. Но суждения могут выражать и утверждения о вымышленных объектах или еще не проис­шедших событиях: «Русалка на ветвях сидит», «Лето будет жарким» и т.п. В этом случае с у ж д е н и я — это некоторые высказывания которые могут быть истинными или ложными. Например, суждения « Снег белый», «5*5 = 25 » истинные, а суждения «Земля плоская», «2-2 = 5» ложные. Непосред­ственно наблюдаемые факты мы обычно принимаем за истинные. Ложные утверждения возникают чаще всего из-за стремления выдать желаемое за действительное либо из-за ошибок в рассуждениях или предположениях.

Суждения подразделяются на общие и частные. Частные суждения выражаютконкретные (частные) факты Примеры частных суждений: «2+З=4» «Сегодня был дождь», Общие суждения характеризуют свойства групп объек­тов или явлений. Примеры общих суждений: «Если прошел дождь, то на улице мокро», «Любой квадрат является параллелограммом», и т.п. Общие суждения могут оказаться истинными для ка­кой-то части объектов и ложными для других объектов. Например, утверждение «Собаки не любят кошек» справед­ливо для большого числа собак, но не для всех. Утвержде­ние «х*у>0» истинно для х =1 и у =1и в то же время ложно для х=0 при произвольном у.

Общее суждение называется тождественно истинным, если оно справедливо для любого из объектов, о которых говорится в суждении. Рассмотрим примеры. Утверждение «х²=0» справедливо для любых действительных (вещест­венных) чисел. Суждение «У кошки четыре ноги» верно для любой из кошек. Тождественно истинные суждения особенно ценны тогда, когда они выражают закономерную связь вещей. Например, утверждение «a+b = b + а» справедливо для любых веще­ственных чисел и выражает закон арифметики — «От пере­становки слагаемых сумма не меняется».

В сложных ситуациях ответы на вопросы выражаются сложносоставными суждениями с использованием связок и, или и не. Например, суждение «Этот человек умный и красивый» есть составное суждение, состоячщее совокупности простых суждений: «Этот человек умный» и «Этот человек красивый».

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

Связка и в составных сужде­ниях всегда предполагает одновременную истинность со­ставляющих суждений. Например: Красивые и умные. Суждение будет истинным, если одновременно будет и красивыми и умными. Если же в рассматривемый момент будет только либо красивым

Связка или в составных суждениях может играть двой­ственную роль. Например, во фразе «Сегодня цветок рас­пустится или не распустится» связку или можно заменить разделяющим «либо». А во фразе «Дождь будет днем или вечером» возможны три ситуации: «Дождь будет днем», либо «Дождь будет вечером»., либо «Дождь будет и днем, и вечером». В первом примере связка или играет разде­ляющую роль, а во втором — объединяющую.

Во всех машинных приложениях и математических рас­суждениях предполагается единственная трактовка всех связок. В них связка или понимается только в более широ­кой объединяющей роли. Например, в утверждении «.х = 0 или у = 0» связка или означает: либо «х = 0», либо «(у = 0», либо «х = 0 'и у = 0». Общее правило: составное суждение со связкой или в математике считается истинным, если истинно хотя бы одно из составляющих суждений, и счи­тается ложным, если ложны все его составляющие. Опровержения таких общих высказываний строятся на следующих двух правилах вывода: отрицания всеобщности и отрицания существования.

1. Отрицание всеобщности. Для отрицания общего утверждения достаточно привести хотя бы один контрпример. Например, встречавшееся раньше утверждение, что «все кошки черные», неверно. Для опровержения этого достаточно привести в пример любую кошку другого цвета. Второй пример: утверждение «Все нечетные числа простые» неверно. Опровержением служит, например, число 9. Это число нечетно, но оно не является простым, так как 9 = 3*3.

2. Отрицание существования. Для отрицания существования необходимо доказать ложность утверждаемого во всех случаях.

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

В математике логические связки являются логическими операциями характеризующие сложные высказывания. Для работы с логическими высказываниями их именуют. Например, высказывание «Николай летом поедет к морю» можно обозначит через «А», а высказывание «Николай летом поедет в горы» через «В». Тогда составное высказывание «Николай летом поедет и к морю, и в горы» можно сокращенно обозначить как «А и В». Здесь "и" – логическая связка, А, В — логические переменные, они могут принимать одно из значений: "ложь" или "истина", соответственно они обозначаются через "0" или "1".

Каждая логическая связка рассматривается как операция исполняемая с логическими высказываниями и обозначаемая определенным собственным именем.

4. Положительная и отрицательная логика. Если в электрических схемах логических элементов компьютера высокий потенциал отображает единицу, а низкий потенциал от ображает ноль, то логика называется положительным (рисунок 1,а). Если же наоборот высокий потенциал отображает ноль, а низкий потенциал от ображает единицу, то логика называется отрицательным (рисунок 1,б). Данное правило называют логическим соглашением.

Инвертирующие базисы

 

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

Элемент И – НЕ называют также: штрих Шеффера (Sheffer stroke), NAND (сокращенное от NOT AND). Алгебраическая запись функции И – НЕ.