Основы логики. Приоритет логических операций.
С начальной школы каждый помнит порядок действий в математике. Все знают, что, к примеру, умножение "важнее" сложения, и выполняется в первую очередь. В логике также каждая операция имеет свой приоритет.
Приоритет логических операций в порядке убывания
- Выражение в скобках.
- Отрицание.
- Конъюнкция.
- Дизъюнкция.
- Импликация.
- Эквиваленция.
К примеру, выражение A ˄ B ≡ C → D можно записать как (A ˄ B) ≡ (C → D).
Name already in use
OAP / articles / t1l3.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Логические основы алгоритмизации
Логика – это наука о формах и способах мышления (первые учения – Древний Восток).
Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны Джорджем Булем, который положил в основу математической логики алгебру логики (булеву, а логические значения называют булевыми). Алгебра логики используется при построении основных узлов ЭВМ, например, таких как шифратор, сумматор и др.
Основными формами мышления являются понятие, высказывание и умозаключение.
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта (например, прямоугольник, компьютер).
Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение – заключение (например, все углы равнобедренного треугольника равны → это треугольник равносторонний).
Составляющей алгоритмов являются логические условия, вычисление значений которых происходит в соответствии с аксиомами алгебры логики.
Основу математической логики составляет алгебра высказываний.
Объектами, с которыми работает алгебра высказываний, являются повествовательные предложения, относительно которых можно сказать, истинны они или ложны.
Высказыванием называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Высказываний одновременно истинных и ложных не бывает.
Приведем примеры высказываний:
- Москва — столица России
- число 27 является простым
- Волга впадает в Каспийское море
Высказывания 1 и 3 являются истинными. Высказывание 2 — ложным, потому что число 27 составное 27=333.
Следующие предложения высказываниями не являются:
- давай пойдем гулять
- 2*x>8
- ax2+bx+c=0
- который час?
Подчеркнем еще раз, что отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают. Невозможно отнести неравенство 2 или уравнение 3 к высказываниям пока не определено значение x. При x=3 высказывание «23>8″ ложно, а при x=5 «25>8″ — истинно.
Условимся обозначать высказывания большими буквами и, следуя Джорджу Булю, истинное (true) высказывание A обозначим так, A=1. В том случае, когда A — ложное (false) высказывание, будем писать: A=0.
Функция ƒ(x1, x2, . xn) называется логической или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: «истина» или «ложь».
По числу переменных различают логические функции одной, двух и многих переменных.
Логические функции могут быть описаны различными способами:
- в виде таблицы истинности;
- совершенными нормальными формами;
- в виде формулы.
Чаще всего встречаются табличная форма представления логической функции (в виде таблицы истинности) и ее аналитическое представление (например, в виде дизъюнктивных или конънктивных форм).
Из простых высказываний можно строить сложные, называемые составными высказывания, соединяя простые логическими операциями. Над простыми высказываниями определены следующие операции:
- логическое отрицание
- логическое умножение
- логическое сложение
- логическое следование или импликация
- эквивалентность
Рассмотрим некоторые из этих операций более подробно.
Инверсия (логическое отрицание — НЕ) — обозначение !.
Логическое сложение, умножение, следование и эквивалентность являются бинарными операциями («би» — два), потому что соединяют два операнда (два высказывания). В отличие от них, логическое отрицание является унарной операцией, потому что применяется лишь к одному высказыванию.
Присоединение частицы НЕ к сказуемому простого высказывания 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 , который отличается от исходного кода. Даже если в случае несанкционированного доступа эта информация будет перехвачена, она ничего не даст злоумышленнику. В то же время, принимающая сторона, имея тот же самый ключ защиты, восстановит исходную информацию.
Если длина передаваемых данных больше длины ключа, то ключ используется повторно для следующего блока данных.
Какая из логических операций имеет наибольший приоритет
Для образования сложных высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».
Например, 
1. Логическое умножение (конъюнкция), от лат. konjunctio – связываю:
• Объединение двух (или нескольких) высказываний в одно с помощью союза И;
• в языках программирования — And.
• Принятые обозначения: /\ , •, и, and.
• В алгебре множеств конъюнкции соответствует операция пересечения множеств. 
2. Логическое сложение (дизъюнкция), от лат. disjunctio – различаю:
• Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ;
• в языках программирования — Or.
• Обозначение: \/, +, или, or.
• В алгебре множеств дизъюнкции соответствует операция объединения множеств. 
• Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ ЯВЛЯЕТСЯ ИСТИНОЙ, ЧТО;
• в языках программирования — Not;
• Обозначение: не А, ¬А, not
• В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества. 
Приоритеты операций
Приоритеты основных логических операций соответствуют приоритетам аналогичных операций в элементарной алгебре. Приоритет исключающего ИЛИ совпадает с приоритетом дизъюнкции. Импликация и эквивалентность обладают равными низшими приоритетами.
Иерархическая последовательность логических операций:
3. Дизъюнкция, исключающее ИЛИ
4. Импликация, эквивалентность
Основные законы Булевой алгебры
Как и в элементарной алгебре, логические выражения можно упрощать, чтобы облегчить задачу последующих вычислений или решения уравнений. Эта возможность обусловлена наличием у логических операций и их комбинаций различных свойств, которые позволяют переходить от исходного выражения к тождественному, упрощая его при этом.
В качестве первого шага к упрощению рекомендуется избавиться от всех производных операций в логическом выражении. Поэтому далее будут перечислены только свойства основных логических операций.
Ассоциативность. Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:
На практике это означает, что можно опускать те скобки, которые определяют, в каком порядке должна выполняться конъюнкция в выражениях вида А1 ? А2 ?…? Аn и дизъюнкция в выражениях А1?А2?…?Аn
Коммутативность Если операция коммутативна, то результат ее применения не зависит от того, какой из операндов был первым, а какой?—?вторым. Операнды коммутативных операций можно менять друг с другом местами, получая тождественный результат.
Конъюнкция и дизъюнкция являются коммутативными операциями:
Свойство дистрибутивности одной операции относительно другой позволяет «раскрывать» скобки аналогично процедуре из элементарной алгебры. Конъюнкция и дизъюнкция дистрибутивны друг относительно друга, что выражается в следующих формулах:
Свойства единицы и нуля
Конъюнкция и дизъюнкция «по-особому» реагируют на единицу или ноль в качестве одного из операндов независимо от значения второго. Эти свойства похожи на знакомые из элементарной алгебры умножение на единицу, умножение на ноль, сложение с нулем:
Операция называется идемнотентной, если, применяя ее к двум равным операндам, получается тот же самый операнд. Идемпотентность позволяет «выкидывать» лишние повторные применения операции из формулы. Конъюнкция и дизъюнкция идемпотентны:
Если к выражению применяется с одним и тем же операндом сначала одна операция, а потом, с тем же самым операндом, поглощающая ее, то значение выражения поглощается, становясь равно операнду. Таким образом поглощающие друг друга пары операций можно «выкидывать» во время упрощения. Конъюнкция и дизъюнкция поглощают друг друга:
Законы де Моргана
Законы де Моргана позволяют применять отрицания к целой скобке, позволяя перейти к так называемым тесным отрицаниям, когда ни одно отрицание не стоит перед скобкой.
Отрицание операнда называется его дополнением. Конъюнкция или дизъюнкция операнда со своим дополнением дает однозначные результат независимо от значения операнда:
Двойное отрицание компенсирует само себя. Таким образом в форме с тесными отрицаниями у каждой переменной в выражении либо не стоит ни одного отрицания, либо только одно. А=А Советы по упрощению логических выражений.
Как уже было сказано выше, сперва рекомендуется избавиться от всех производных логических операций. Так же полезно раскрыть все скобки, перейти к форме с тесными отрицаниями. В процессе полезно применить свойства идемпотентности, поглощения, дополнений, нуля и единицы. Иногда, чтобы упростить выражение, необходимо, наоборот, что-то вынести за скобку, чтобы сократить то, что в скобках останется. В целом, необходимо добиться минимального числа переменных, операций конъюнкции и дизъюнкции. При этом в упрощенной формуле должны быть тесные отрицания и не должно быть производных операций.
I. Логические элементы компьютера
Во всех современных компьютерах применяется логическая система, изобретенная Джорджем Булем. Тысячи микроскопических электронных переключателей в кристалле интегральной схемы сгруппированы в системы «вентилей», выполняющих логические операции, т.е. операции с предсказуемыми результатами. На приведенных ниже рисунках показаны элементарные логические вентили НЕ, ИЛИ-НЕ и И-НЕ. Все остальные логические схемы компьютера могут быть построены на основе вентилей этих трех типов.