<<
>>

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

В алгебре логики над высказываниями можно производить определенные логические операции, в результате которых получаются новые (выходные) высказывания, значения (истинность или ложность) которых зависит как от значений входных, так и от использованных логических операций.
Конъюнкция. Соединение двух (или нескольких) высказываний в одно с помощью союза и (ок) называется операцией логического умножения, или конъюнкцией. Эту операцию принято обозначать знаками «а, &» или знаком умножения «х». Сложное высказывание А а В истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания задается табл. 1.7. Дизъюнкция. Объединение двух (или нескольких) высказываний с помощью союза или (ок) называется операцией логиче-
Таблица 1.7. Таблицы истинности конъюнкции и логической суммы высказываний

ского сложения, или дизъюнкцией.

Эту операцию обозначают знаками «| ,v» или знаком сложения «+». Сложное высказывание A v В истинно, если истинно хотя бы одно из входящих в него высказываний (см. табл. 1.7). В последнем столбце табл. 1.7 размещены результаты модифицированной операции ИЛИ — Исключающее ИЛИ (XOR). Отличается от обычного или последней строкой (см. также рис. 1.2, в). Инверсия. Присоединение частицы НЕ (not) к некоторому высказыванию называется операцией отрицания (инверсии) и обозначается -,А (или А). Если высказывание А истинно, то А ложно, и наоборот (табл. 1.8).
Таблица 1.8. Таблица истинности отрицания

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

Например, операция эквивалентности (эквиваленции) А ~ В (А= В, или А ецу В) (табл. 1.9).
Таблица 1.9. Таблицы истинности операций эквивалентности и импликации

Другим примером может служить логическая операция импликации или логического следования (А -> В, A IMP В), иначе говоря, «ЕСЛИ А, то В» (табл. 1.9). Высказывания, образованные с помощью логических операций, называются сложными. Истинность сложных высказываний можно установить, используя таблицы истинности. Например, истинность сложного высказывания А л В определяется табл. 1.10.

Таблица 1.10. Таблица истинности высказывания А л Б

Высказывания, у которых таблицы истинности совпадают, называются равносильными (тождественными). Для обозначения равносильных высказываний используют знак «=» (А = В). Рассмотрим сложное высказывание (А л В) V (А л В) — табл. 1.11.

Таблица 1.11. Таблица истинности выражения (А л В) v (А л В)

Если сравнить эту таблицу с таблицей истинности операции эквивалентности высказываний А и В (см. табл. 1.9), то можно увидеть, что высказывания (Ал В) -V (А л В) и А~ В тождественны, т. е. (А ~ В) = (А л В) V (А л В). В алгебре высказываний можно проводить тождественные преобразования, заменяя одни высказывания равносильными им другими высказываниями. Свойства логических операций. Исходя из определений дизъюнкции, конъюнкции и отрицания, устанавливаются свойства этих операций и взаимные распределительные свойства. Приведем примеры некоторых из этих свойств: • коммутативность (перестановочность): А л В = В л А, Av В = В v А\ • закон идемпотентности: АлА = A, Av А = А; • двойное отрицание: А = А; • сочетательные (ассоциативные) законы: A v (В v С) = (A v В) v С = A v В v С, А л (В л С) = (А л В) л С = А л В л С; • распределительные (дистрибутивные) законы: А л (fi v С) = (А л В) v (А л С), у4 v (fi а С) = (/4 v 5) л (A v С); • поглощение: Av (Ал В) = А, А л (A v В) = А; • склей ванне: (А л В) v (А л В) = В, (A v В) л (A v В) = В; • операция переменной с ее инверсией: А л А = О, A v А = 1; • операция с константами (0 — false, 1 — true): А л 1, A v 1= 1, А л 0 = О, A v 0 = А; • законы де Моргана: А л В = A v В (условно его можно назвать 1-й); A v В = А л В (2-й). Высказывания, образованные с помощью нескольких операций логического сложения, умножения и отрицания, называются сложными.

Истинность всякого сложного высказывания устанавливается с помощью таблиц истинности. Сложные высказывания, истинные (true) для любых значений истинности, входящих в них простых высказываний, называются тождественно-истинными. Наоборот, тождественно-ложными являются формулы, принимающие значение false для любых значений входящих в него простых высказываний. В табл. 1.12 приведено доказательство истинности дистрибутивного закона. Аналогичным образом могут быть доказаны и другие тождества.
Таблица 1.12. Доказательство истиииости дистрибутивного закона

На рис. 1.2 приведены иллюстрации к основным логическим операциям и их композициям (так называемые диаграммы Эйлера — Венна) - области истинности каждого из высказываний и результатов их объединения (дизъюнкции), пересечения (конъюнкции) и других операций. «Первый» из законов де Моргана иллюстрируется рис. 1.2, д, е. Логическое значение null. В некоторых ЯП (Visual Basic и пр.) для расширения применимости логических выражений на те случаи, когда значение одного или нескольких логических аргументов неизвестны или не определены, вводится значение null (в дополнение к false и true), как правило, такое значение присваивается компилятором логической переменной по умолчанию. С учетом значения null таблицы истинности основных логических операций приобретают вид табл. 1.13, 1.14.

где Рис. 1.2. Некоторые примеры диаграмм Эйлера — Венна: а — конъюнкция высказываний А и В (and); б — дизъюнкция высказываний А и В (or); в — исключающая дизъюнкция (ход); г — разность высказываний (А—В); д — иллюстрация к законам де Моргана (дополнение пересечения высказываний); е — иллюстрация к законам де Моргана (объединение дополнений)
Таблица 1.13.
Одноместная (унарная) операция отрицания с учетом значения null

Таблица 1.14. Некоторые двухместные (бинарные) операции с учетом значения null Побитовые операции. В некоторых современных ЯП включены операции побитового сравнения содержимого машинных слов (которые могут содержать числовые, строчные и др. данные) при этом каждый бит результата образуется в соответствии с табл. 1.15 (для бинарных операций). Унарная операция отрицания (not) в данном случае реализует очевидную замену «1» на «0», и наоборот.

Таблица 1.15. Операнды и результаты некоторых операций побитового сравнения

1.3.

<< | >>
Источник: О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ. 2008

Еще по теме Логические операции:

  1. ОПЕРАЦИЯ ИНТЕЛЛЕКТУАЛЬНАЯ
  2. ОПЕРАЦИЯ ФОРМАЛЬНАЯ
  3. ОПЕРАЦИЯ КОНКРЕТНАЯ
  4. ОПЕРАЦИЯ
  5. Логическое ударение
  6. МЫШЛЕНИЕ СЛОВЕСНО-ЛОГИЧЕСКОЕ
  7. Логическая последовательность вопросов
  8. 3.2.4. Логический анализ основных понятий
  9. По единому логическому основанию
  10. ОПЕРАЦИЯ СОЗНАТЕЛЬНАЯ
  11. 3.9. Логические ошибки
  12. Логические ошибки вопроса