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

В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и I. Переменные будем обозначать латинскими буквами х, у, z, •••, т, а также х0, х15..., хп,

Уоу Tiv, Уп и т- Д-

Отношение эквивалентности (равенства) удовлетворяет следующим свойствам:

  • • рефлексивность: х = х;
  • • симметричность: если х = у, то у = х;
  • • транзитивность: х = у и у = z, то х = z, отсюда следует принцип, если х = у, то в любой формуле, содержащей х, вместо х можно подставить у, ив результате будет получена эквивалентная формула.

Пусть X], х2 и х3 — переменные булева типа (логические переменные), способные принимать лишь два значения (True и False), которые для удобства мы будем обозначать соответственно 1 и 0.

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

Таблица 1.9. Рабочая таблица

*1

х2

Х А *2

*1 V Х2

Х -> Х2

Х © Х2

*1 ~ *2

*1

0

0

0

0

1

0

1

1

1

0

0

1

0

1

0

0

0

1

0

1

1

1

0

1

1

1

1

1

0

1

Функции имеют следующие названия и обозначения:

  • • конъюнкция (логическое умножение) — л (И);
  • • дизъюнкция (логическое сложение) — V (ИЛИ);
  • • импликация-->;
  • • сумма по модулю 2 — ©;
  • • функция эквивалентности--;
  • • отрицание (логическое отрицание)--, (НЕ).

Справедливы следующие соотношения эквивалентности между простейшими функциями:

х -э>х2 = х, / х2;

х, © х2 = (х, л х2) V (х, л х2);

х, ~ х2 = (х, л х2) V (х, л х2).

1. Конъюнкция. А а В или А ? В (логическое умножение, читается как союз «и»).

Таблица 1.10. Таблица истинности для конъюнкции

А

в

Ал В

0

0

0

0

1

0

1

0

0

1

1

1

2. Дизъюнкция. Л/ В или А + В (логическое сложение, читается как союз «или»).

Таблица 1.11. Таблица истинности для дизъюнкции

А

в

А V В

0

0

0

0

1

1

1

0

1

1

1

1

3. Отрицание. А или (->А). Иногда отрицание называют функцией Вебба или функцией Даггера.

Таблица 1.12. Таблица истинности для отрицания

А

А

0

1

1

0

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

Таблица 1.13. Таблица истинности для импликации

А

В

А-> В

0

0

1

0

1

1

1

0

0

1

1

1

5. Эквиваленция, или тождественность. А В (А ~ В) (читается: А тогда и только тогда, когда В).

Таблица 1.14. Таблица истинности для эквиваленции

А

В

А <-> В

0

0

1

0

1

0

1

0

0

1

1

1

  • 6. Штрих Шеффера. А В =Л л В (антиконъюнкция) (читается: неверно, что А и В). _
  • 7. Стрелка Пирса. А I В или А 4 В = А V В (антидизъюнкция) (читается: А стрелка Пирса В).

Аксиомы алгебры логики

х=0, еслих^І; х = 1, если* ф О,

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

Иногда вводят в рассмотрение и понятие «подформула».

Если У7 — формула, а Р — какая-либо ее связная часть, которая сама является формулой, то Р называется подформулой формулы У7. Понятие «подформула» не следует путать с понятием «связная часть формулы». Связная часть формулы — это часть формулы, которая выписана из нее без пропусков.

Например, в формуле

(АВ) -+((В +С)- В)

есть следующие подформулы: А, В, В + С, (В + С)В. Никаких других подформул данная формула не имеет. Выражение (АВ) -> — часть формулы, но подформулой не является. АВ -> В также не является подформулой, поскольку не является ее связной частью. Главной подформулой формулы У7 называется такая ее подформула, которая не является частью никакой другой подформулы формулы Т7.

Например, формула

+ В) -> (С/))

имеет две главные подформулы: (А + В) и С/).

Запись формулы часто можно упростить, используя следующие правила:

  • • внешние скобки опустить; _
  • • если подформула имеет вид (А), то скобки можно опустить. Таким образом, правила опускания скобок аналогичны соответствующим правилам опускания скобок в арифметике,

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

Пр и мер 1.19. Опустите лишние скобки в выражении ((А + (ВС)) -> ((Ж) + С)) = ((А + ВС) ->(АВ + С)) =

= А + ВСАВ + С.

Пр и мер 1.20. Восстановите опущенные скобки в формуле

(А+ ВИ ^В) + (В + С ^ И) =

= {{{А + (Вй)) -+В) + ((В + С)^ И)).

Для каждой формулы может быть построена соответствую-

щая таблица истинности. Пусть задана формула АВ -> А. Сначала составим таблицу всевозможных значений переменных А, В (оценок переменных), от которых зависит данная формула. Проведем анализ строения этой формулы: вначале выпишем саму формулу, затем ее главные подформулы, после чего под каждой подформулой выпишем главные подформулы и т. д.

Если поэтапно строить таблицу истинности для всех формул, то в результате получим таблицу истинности для исходной формулы (табл. 1.15).

Таблица 1.15. Таблица истинности

Оценка

А

В

в

АВ

АВ

АВА

т 1

0

0

1

0

1

0

/772

0

1

0

0

1

0

/773

1

0

1

1

0

1

/774

1

1

0

0

1

1

Из полученной таблицы видно, что истинные значения формулы АВ -»А совпадают со значением А, либо одновременно ложны, либо одновременно истинны. Такие формулы называются равносильными. Для обозначения равносильности пользуются обычно знаком равенства, т. е. А ВА = А.

 
< Пред   СОДЕРЖАНИЕ     След >