Предыдущая лекция |   | Следующая лекция :----------------:|:----------:|:----------------: [Основные алгоритмические конструкции](./t1l2.md) | [Содержание](../readme.md#тема-1-основные-принципы-алгоритмизации-и-программирования) | [Языки программирования](./t2l1.md) # Логические основы алгоритмизации *Логика* – это наука о формах и способах мышления (первые учения – Древний Восток). Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны Джорджем Булем, который положил в основу математической логики алгебру логики (булеву, а логические значения называют булевыми). Алгебра логики используется при построении основных узлов ЭВМ, например, таких как шифратор, сумматор и др. ## Основные формы мышления Основными формами мышления являются *понятие*, *высказывание* и *умозаключение*. **Понятие** – это форма мышления, фиксирующая основные, существенные признаки объекта (например, прямоугольник, компьютер). **Умозаключение** – это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение – заключение (например, все углы равнобедренного треугольника равны → это треугольник равносторонний). Составляющей алгоритмов являются логические условия, вычисление значений которых происходит в соответствии с аксиомами алгебры логики. Основу математической логики составляет алгебра высказываний. Объектами, с которыми работает алгебра высказываний, являются повествовательные предложения, относительно которых можно сказать, истинны они или ложны. ### Логическое высказывание **Высказыванием** называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Высказываний одновременно истинных и ложных не бывает. Приведем примеры высказываний: 1. Москва - столица России 2. число 27 является простым 3. Волга впадает в Каспийское море Высказывания `1` и `3` являются истинными. Высказывание `2` - ложным, потому что число `27` составное `27 = 3 * 3 * 3`. Следующие предложения высказываниями не являются: 1. давай пойдем гулять 2. `2 * x > 8` 3. `a * x2 + b * x + c = 0` 4. который час? Подчеркнем еще раз, что отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают. Невозможно отнести неравенство `2` или уравнение `3` к высказываниям пока не определено значение `x`. При `x = 3` высказывание `2 * 3 > 8` ложно, а при `x = 5` `2 * 5 > 8` - истинно. Условимся обозначать высказывания большими буквами и, следуя Джорджу Булю, истинное (true) высказывание `A` обозначим так, `A = 1`. В том случае, когда `A` - ложное (false) высказывание, будем писать: `A = 0`. Функция `ƒ(x1, x2, ..., xn)` называется логической или булевой, если она, так же как и ее аргументы `xi`, может принимать только два значения: "истина" или "ложь". По числу переменных различают логические функции одной, двух и многих переменных. ### Способы описания логических функций Логические функции могут быть описаны различными способами: * в виде таблицы истинности; * совершенными нормальными формами; * в виде формулы. Чаще всего встречаются табличная форма представления логической функции (в виде таблицы истинности) и ее аналитическое представление (например, в виде дизъюнктивных или конънктивных форм). Из простых высказываний можно строить сложные, называемые составными высказывания, соединяя простые логическими операциями. Над простыми высказываниями определены следующие операции: 1. логическое отрицание 2. логическое умножение 3. логическое сложение 4. ~~логическое следование или импликация~~ 5. ~~эквивалентность~~ Рассмотрим некоторые из этих операций более подробно. ## Логические операции ### **Инверсия** (логическое отрицание - НЕ) - обозначение ***!***. Логическое сложение, умножение, следование и эквивалентность являются бинарными операциями ("би" - два), потому что соединяют два операнда (два высказывания). В отличие от них, логическое отрицание является унарной операцией, потому что применяется лишь к одному высказыванию. Присоединение частицы НЕ к сказуемому простого высказывания `A` называется операцией логического отрицания. Результат будет истинным, если исходное высказывание ложно, и наоборот, ложным - если исходное высказывание истинно. A |!A :-:|:-: 0 | 1 1 | 0 ### **Конъюнкция** (логическое умножение - И) – обозначение ***&*** или ***&&*** Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны. A | B | A & B :-:|:-:|:---: 0 | 0 | 0 1 | 0 | 0 0 | 1 | 0 1 | 1 | 1 Для более легкого запоминания этой функции следует придерживаться правила: функция конъюнкции ложна, если ложен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как `1`, а значение "ложь" как `0`, то эта функция будет похожа на математическую функцию умножения. Поэтому ее зачастую называют функцией логического умножения. Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции – дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный (переместительный) законы. В то же время для некоторых других логических функций тот или иной закон не действует. Некоторые из примеров таких функций мы рассмотрим ниже. Чем отличается оператор **&** от **&&**: * Оператор **&** всегда вычисляет оба операнда * Оператор **&&** вычисляет второй операнд, только если это необходимо. ### **Дизъюнкция** (логическое сложение - ИЛИ) – обозначение **|** или **||**. Результат будет истинным тогда, когда истинно хотя бы одно из высказываний. A | B | A \| B :-:|:-:|:-: 0 | 0 | 0 1 | 0 | 1 0 | 1 | 1 1 | 1 | 1 Для более легкого запоминания этой функции следует придерживаться правила: функция дизъюнкции истинна, если истенен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение "истина" как `1`, а значение "ложь" как `0`, то эта функция для двух операндов будет похожа на математическую функцию поразрядного сложения. Поэтому ее зачастую называют функцией логического сложения. Хотя здесь следует иметь в виду, что в логическом сложении сигнал переноса в более старший разряд не вырабатывается. Чем отличается оператор **|** от **||**: * Оператор **|** всегда вычисляет оба операнда * Оператор **||** вычисляет второй операнд, только если это необходимо. ### **Сложе́ние по мо́дулю 2** (исключа́ющее «ИЛИ», логи́ческая неравнозна́чность) - обозначение **`^`**. Таблица истинности: A | B | A `^` B :-:|:-:|:-: 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 Для операндов целочисленных типов оператор **`^`** вычисляет побитовое исключающее ИЛИ своих операндов. Про функцию *Сумма по модулю 2* поговорим здесь поподробнее, так она является основой для реализации устройств контроля и защиты информации. **Пример контроля** Пусть мы хотим передать некоторые данные, например, код `11001100`. Перед началом передачи код дополняется контрольным разрядом. бит данных | действие | сумма по модулю 2 :-:|:-:|:-: 1 | - | 1 1 | 1 `^` 1 | 0 0 | 0 `^` 0 | 0 0 | 0 `^` 0 | 0 1 | 1 `^` 0 | 1 1 | 1 `^` 1 | 0 0 | 0 `^` 0 | 0 0 | 0 `^` 0 | 0 В нашем примере контрольный разряд будет равен `0` (сложим `4` единицы и разделим по модулю `2`, результат `0`). Контрольный разряд передается вместе с основным кодом (`11001100`+`0`). Если в процессе передачи произойдет искажение одного разряда (например, последний разряд кода примет значение `1`), то приёмное устройство примет код `11001101` и контрольный разряд `0`, равный исходному (там искажения нет). бит данных | действие | сумма по модулю 2 :-:|:-:|:-: 1 | - | 1 1 | 1 `^` 1 | 0 0 | 0 `^` 0 | 0 0 | 0 `^` 0 | 0 1 | 1 `^` 0 | 1 1 | 1 `^` 1 | 0 0 | 0 `^` 0 | 0 1 | 1 `^` 0 | 1 Приемное устройство вычисляет контрольный разряд от принятого кода (теперь он будет равен `1`, `5 mod 2 = 1`), сравнивает его с принятым контрольным разрядом (они не совпадают) и сообщает об ошибке в передаче данных. Обычно после этого передача повторяется. Такой алгоритм только демонстрирует принцип формирования контрольных сумм. В современной технике никто, разумеется, по байтам данные не передает. Контроль обычно осуществляется на уровне пакета данных добавлением циклического кода целостности (CRC16, CRC32). **Пример защиты** >A ^ B = C, C ^ B = A !!! Почему то нигде не написано про самое интересное свойство этой функции: если к результату повторно применить аналогичное преобразование, то получим исходные данные. Эту логическую операцию можно применять для элементарной защиты передаваемой информации. Можно использовать так называемый ключ защиты, который должен быть у передающей и принимающей стороны. Пусть в нашем случае таким ключом защиты будет код `01101101`. данные | ключ | зашифрованные данные :-:|:-:|:-: 1 | 0 | 1 1 | 1 | 0 0 | 1 | 1 0 | 0 | 0 1 | 1 | 0 1 | 1 | 0 0 | 0 | 0 0 | 1 | 1 Суммируя по модулю 2 поразрядно передаваемый код и код защиты, получим, что передаваться будет код `10100001`, который отличается от исходного кода. Даже если в случае несанкционированного доступа эта информация будет перехвачена, она ничего не даст злоумышленнику. В то же время, принимающая сторона, имея тот же самый ключ защиты, восстановит исходную информацию. Если длина передаваемых данных больше длины ключа, то ключ используется повторно для следующего блока данных. **Свойства функции *сложения по модулю 2*** 1. Коммутативность. `A ^ B = B ^ A` 2. Ассоциативность. `A ^ (B ^ C) = (A ^ B) ^ C` 3. Дистрибутивность относительно конъюнкции. `A & (B ^ C) = A & B ^ A & C` 4. Идемпотентность `A ^ 0 = A` 5. Отрицание `A ^ 1 = !A` Имеют место следующие очевидные соотношения: `A ^ A = 0` `A ^ !A = 1` >Википедия знает еще несколько логических операций *Стре́лка Пи́рса* (ИЛИ-НЕ), *Штрих Ше́ффера* (И-НЕ), *Логическое следование* (импликация, "если то"), *Логическая равнозначность или эквивале́нция* (эквивале́нтность). В программировании они не используются, поэтому останавливаться на них мы не будем. ## Приоритет логических операций * Инверсия ( **!** ) * Конъюнкция ( **&** ) * Сложение по модулю 2 ( **^** ) * Дизъюнкция ( **|**) * Условная конъюнкция ( **&&** ) * Условная дизъюнкция ( **||** ) Порядок вычисления, определяемый приоритетом операторов, можно изменить с помощью скобок (()). ## Законы логических операций В алгебре логики доказано, что любую логическую функцию можно выразить только через комбинацию логических операций `И`, `ИЛИ` и `НЕ`. Для приведения логических выражений к эквивалентным, но более простым в записи используют ряд логических законов. 1. *Закон противоречия* говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. "это яблоко спелое" и "это яблоко неспелое". `А & !А = 0` 2. *Закон исключенного третьего* говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. "Сегодня я либо получу 5, либо не получу". Истинно либо суждение, либо его отрицание. `А | !А = 1` 3. *Закон двойного отрицания* заключается в том, что отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. `!(!А) = А` 4. *закон идемпотентности* говорит о том, что в алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых "сомножителей" равносильна одному из них. Дизъюнкция одинаковых "слагаемых" равносильна одному из них. `А & А = А` `А | А = А` 5. *Законы коммутативности и ассоциативности* говорят о том, что конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел. коммутативность: `А & В = В & А` `А | В = В | А` ассоциативность: `А | (В | С) = (А | В) | С` `А & (В & С) = (А & В) & С` 6. *Законы дистрибутивности* говорят о том, что логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции. `А & (В | С) = (А & В) | (А & С)` `А | (В & С) = (А | В) & (А | С)` 7. *Законы поглощения констант* утверждают, что ложь не влияет на значение логического выражения при дизъюнкции, а истина - при конъюнкции. `А & 1 = А` `А | 0 = А` 8. *Законы поглощения* показывают как упрощать логические выражения при повторе операнда. `A | (A & B) = A` `A & (A | B) = A` 9. *Законы де Мо́ргана* (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так: Отрицание конъюнкции есть не что иное, как дизъюнкция отрицаний. `!(А & В) = !А | !В` Отрицание дизъюнкции есть не что иное, как конъюнкция отрицаний. `!(А | В) = !А & !В` ## Решение логических выражений Решение логических выражений записывают в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных. Для составления таблиц истинности необходимо: * определить количество строк в таблице: **`2ⁿ`**, n–количество переменных * определить количество столбцов в таблице: количество логических переменных + количество логических операций * установить последовательность выполнения логических операций * построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных * заполнить таблицу истинности по столбцам Например, построим таблицу истинности для ассоциативного закона дизьюнкции: `А | (В | С)` * количество строк: **`2³ = 8`** * количество столбцов: **`3 + 2 = 5`** A | B | C | B \| C | A \| (B \| C) :-:|:-:|:-:|:------:|:------------: 0 | 0 | 0 | 0 | 0 0 | 0 | 1 | 1 | 1 0 | 1 | 0 | 1 | 1 0 | 1 | 1 | 1 | 1 1 | 0 | 0 | 0 | 1 1 | 0 | 1 | 1 | 1 1 | 1 | 0 | 1 | 1 1 | 1 | 1 | 1 | 1 --- **КОНТРОЛЬНЫЕ ВОПРОСЫ** 1. [Основные формы мышления.](#основные-формы-мышления) 1. [Что такое логическое высказывание?](#логическое-высказывание) 1. [Способы описания логических функций.](#способы-описания-логических-функций) 1. [Основные логические операции.](#логические-операции) 1. [Приоритет логических операций](#приоритет-логических-операций) 1. [Законы логических операций](#законы-логических-операций) 1. [Проверка законов построением таблиц истинности](#решение-логических-выражений) --- Предыдущая лекция |   | Следующая лекция :----------------:|:----------:|:----------------: [Основные алгоритмические конструкции](./t1l2.md) | [Содержание](../readme.md#тема-1-основные-принципы-алгоритмизации-и-программирования) | [Языки программирования](./t2l1.md)