Тема лекции: Логические основы работы компьютера

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

Высказывание — объект алгебры логики

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

1. ЛОГИЧЕСКОЕ ВЫСКАЗЫВАНИЕ



Логика – наука, изучающая формы и способы мышления.

Существует три формы мышления: понятие, высказывание, умозаключение.

 Понятием называют такую форму мышления, которая фиксирует значимые признаки некоторого объекта, при этом понятие имеет два компонента – объём и содержание.

Объём понятия включает в себя множество объектов, на которое оно распространяется, а содержание понятия – множество важных признаков объекта.

 Умозаключением называют форму мышления, в результате которой из одной или нескольких суждений получают новое.

 Высказыванием называют форму мышления, в которой что-то утверждается или опровергается.

Например, «физика – увлекательный предмет» не является высказыванием, так как употреблено очень неопределённое понятие «увлекательный предмет».

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

 Алгебра логики – это раздел математической логики, изучающий высказывания и логические операции над ними.

Алгебра логики помогает нам понять внутреннее устройство компьютера. Вы уже знаете, что компьютер обрабатывает информацию только в двоичном коде. Логика помогает понять, как взаимодействуют между собой два состояния: 0 и 1. Процессор компьютера работает за счет выполнения логических операций, но о них мы узнаем позже.

Основоположники алгебры логики.

• Аристотель был первым основоположником логики. Он занимался исследованием различных форм рассуждений и ввёл понятие силлогизма. Вклад в науку отразился в его книгах «Категории», «Первая аналитика», «Вторая аналитика».

• Рене Декарт предложил использовать в логике математические методы.

• Г.В. Лейбниц рекомендовал внедрить математическую символику и первым выдвинул гипотезу о возможности использования в логике двоичной системы счисления.

• Джордж Буль определил основы булевой алгебры, разработал алфавит, орфографию и грамматику в своей работе «Математический анализ логики». Алгебра логики как наука возникла именно в трудах английского математика Джорджа Буля в середине XIX века. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

• В 1938 году Клод Шеннон применил алгебру логики для описания процесса функционирования релейно-контактных и электронно-ламповых схем. 

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

Например, предложение «Джордж Буль — основоположник алгебры логики» истинно, а «Солнце — спутник Земли» ложно.

Таким образом, обычное высказывание не всегда является логическим высказыванием

Логическое высказывание — это повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Обоснование истинности или ложности элементарных высказываний не является задачей алгебры логики. Эти вопросы решаются теми науками, к сфере которых относятся элементарные высказывания. Такое сужение интересов позволяет обозначать высказывания символическими именами (например, А, В, С) – т.е. заменять логические высказывания на логические переменные.

Логическая переменная — это переменная, которая обозначает любое высказывание и может принимать логические значения «истина» или «ложь». Для логических значений «истина» — «ложь» могут использоваться следующие обозначения:

Например, А = «монитор – это устройство для вывода информации» можно записать как А = 1.

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

Употребляемые в обычной речи логические связки (= логические операции) «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить новые высказывания.

Высказывания, образованные из других высказываний, называются составными.

Высказывание, никакая часть которого не является отдельным (самостоятельным) высказыванием, называется элементарным.

Например, из двух простых высказываний можно получить следующее составное высказывание:

«Алгебра логики является основой строения логических схем компьютеров и служит математической основой решения сложных логических задач».

Пример 2:

А = «Маша поёт в ансамбле»;

В = «Маша танцует народные танцы»;

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

А или В = «Маша поёт в ансамбле ИЛИ Маша танцует народные танцы»;

А и В = «Маша поёт в ансамбле И Маша танцует народные танцы».

Подумайте! Какая разница между первым и вторым сложными высказываниями?

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

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

2. МАТЕМАТИЧЕСКИЙ АППАРАТ АЛГЕБРЫ ЛОГИКИ

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

ОБРАТИТЕ ВНИМАНИЕ!

Вводят замену: вместо простых высказываний используют логические переменные (A, B, C, D и так далее); значения истинных высказываний обозначают 1, ложных высказываний – 0.

Математический аппарат алгебры логики имеет широкое применение: при проектировании ЭВМ, в теории автоматов, в теории алгоритмов, в теории информации, в целочисленном программировании.

В алгебре логики имеется шесть логических операций:

Рассмотрим их по порядку.

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

 Отрицание (инверсия) – это логическая операция, которая делает ложное высказывание истинным, а истинное – ложным.

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

Обозначение: НЕ А, not A, ¬A, Ā

Задается следующей таблицей истинности:

Пример: я девочка, а не мальчик

2. Конъюнкция (логическое умножение).

 Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны.

Конъюнкция - логическое умножение, логическое И.

Обозначение: И, and, &, ×, 

Задается следующей таблицей истинности:

Пример: если студент сдал и русский и математику, то он отправляется жить в общагу, а не в казарму.

3. Дизъюнкция (логическое сложение).

 Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны.

Дизъюнкция — логическое сложение, логическое ИЛИ.

Обозначение: ИЛИ, or, +, 

Задается следующей таблицей истинности:

Пример: ребенок замолчит, если ему дали игрушку или соску.

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

 Импликация – сложное логическое выражение, истинное всегда, кроме как из истины следует ложь.

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

Операция импликации обозначается символом 

Задается следующей таблицей истинности:

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

Пример: если жена сказала вынести мусор, а муж не вынес, то он получит скалкой по голове.

Импликацию можно заменить на выражение, использующее ранее изученные операции НЕ и ИЛИ:

5. Эквивалентность (логическая равнозначность).

 Эквивалентность – сложное логическое выражение, является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

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

В логике эквиваленция обозначается символом  

Задается следующей таблицей истинности:

В разговорной речи эквивалентности соответствует связка «тогда и только тогда, когда», а в математике — «необходимо и достаточно».

Пример: если жена сказала вынести мусор, а муж не вынес, то он получит скалкой по голове.

Можно заменить эквивалентность выражением, которое включает только базовые логические операции:

6. Строгая дизъюнкция (исключающее ИЛИ).

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

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

Строгая дизъюнкция обозначается символом , операция XOR, сложение по модулю 2.

Задается следующей таблицей истинности:

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

Строгую дизъюнкцию можно представить через базовые операции следующим образом:

Если посмотреть внимательно на таблицы истинности для двух последних логических операций, то можно заметить, что «эквивалентность» — это обратная операция для операции «исключающее ИЛИ»,

т. е. 

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

При преобразовании или вычислении значения логического выражения логические операции выполняются в соответствии с их приоритетом:

1. отрицание;

2. конъюнкция;

3. дизъюнкция, строгая дизъюнкция;

4. импликация, эквиваленция.

Операции одного приоритета выполняются в порядке их следования, слева направо. Как в математике, скобки меняют порядок выполнения операций.

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

Пример.

Для какого имени истинно высказывание:

Первая буква согласная И (вторая буква согласная  четвертая буква гласная)

1) Иван 2) Пётр 3) Павел 4) Елена

Решение:

Вычислим значение логического выражения для каждого из данных слов

1) 0 И (00) = 0

2) 1 И (10) = 0

3) 1 И (10) = 1

4) 0 И (00) = 0

Ответ: 3.

3.ТАБЛИЦЫ ИСТИННОСТИ

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

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

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

Алгоритм действий:

1. Построить таблицу из X столбцов и Y строк, где X=k+m, Y=2^k

где k – количество переменных, а m – количество логических операций;

2. Первую строку таблицы заполняют слева направо, сначала переменными, а потом логическими операциями, учитывая их приоритетность.

3. В первых столбцах перечисляют все возможные комбинации входных значений (переменных)

4. Далее необходимо заполнить все остальные ячейки, выполняя последовательно перечисленные логические операции.

5. Ответом будет последний столбец таблицы.

Пример:

Дана функция F= (XY) ¬Z

Необходимо построить таблицу истинности.

Решение: Будем действовать согласно приведенному выше алгоритму.

1. Количество переменных – 3 (X, Y, Z), количество логических операций – 3 (, , ¬). Количество столбцов 3+3=6, количество строк 2³=8.

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

3. Перечислим все возможные значения входных данных. Для того, чтобы не пропустить ни одного значения, используют следующее правило: в значения первой переменной записывают сначала 4 нуля, затем 4 единицы; в значении второй переменной чередуют сначала 2 нуля, затем 2 единицы, а значение третьей переменной записывают чередованием нуля и единицы.

4. Заполним ячейки таблицы, выполняя логические операции.

5. Последний столбец таблицы и является ответом.

Здесь можно увидеть при каких входных данных логическая функция F= (XY) ¬Z принимает истинные или ложные значения.

4. ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Законы алгебры логики применяют для упрощения логических выражений.

Пример

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

5. ГРАФИЧЕСКИЙ МЕТОД

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Им было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Поэтому при решении логических задач очень часто бывает полезно вычертить некую схему = «дерево логических условий». Это «дерево» выражается в виде простого чертежа логической взаимосвязи между данными высказываниями.

Любой логический элемент имеет своё условное обозначение.

Рассмотрим их подробнее

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R_н близко к нулю. Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня. И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

Функция “ИЛИ” - логическое сложение (дизъюнкция), ее результат равен 1, если хотя бы 1 из аргументов равен 1. Здесь транзисторы включены параллельно друг другу. Если оба закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический “0”). Достаточно подать сигнал высокого уровня (“1”) на один из транзисторов, как схема начнет пропускать ток, и на сопротивлении нагрузки установится также сигнал высокого уровня (логическая “1”).

При подаче на вход схемы сигнала низкого уровня (0) транзистор будет заперт, т.е. ток через него проходить не будет, и на выходе будет сигнал высокого уровня (1). Если же на вход схемы подать сигнал высокого уровня (1), то транзистор “откроется”, начнет пропускать электрический ток. На выходе за счет падения напряжения установится напряжение низкого уровня. Таким образом, схема преобразует сигналы одного уровня в другой, выполняя логическую функцию.

Пример

ВАЖНО! Подведем итоги

Высказывание — это предложение, в отношении которого можно сказать, истинно оно или ложно.

Высказывания, образованные из других высказываний, называются составными (сложными).

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

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

Для всякой таблицы истинности можно составить соответствующее ей логическое выражение.

При решении логических задач очень часто бывает полезно вычертить схему = «дерево логических условий».

12