Сложные
формулы
[предыдущая глава]  [оглавление]  [следующая глава]

Из простых формул можно конструировать более сложные. Будем обозначать произвольные формулы как функции от некоторого числа аргументов, например f(A) или g(x1, x2,... xn). В скобках перечисляются переменные, входящие в формулу или целые фрагменты формулы, представляющие собой единое целое, Если список переменных неважен, то будем писать многоточие, например f(...). Эти скобки важны для того, чтобы отличить два случая:

  1. Отдельная свободная переменная f, имеющая определенную область значений (например, true и false, если переменная булева).
  2. Целая формула f(...), в которую может входить много переменных (или одна, или ни одной), каждая из которых, в принципе, может иметь свою область значений.

Для многих разделов математики приняты правила построения формул по определенным правилам. Для булевой алгебры эти правила таковы:

  1. true - булева формула (простейшая).
  2. false - булева формула (простейшая).
  3. Одна отдельная булева переменная - формула (простейшая).
    Примечание: булевой переменной называется переменная, у которой область значений состоит всего из двух объектов: true и false.
  4. Если есть булева формула f(...), то из нее можно построить формулы:
    (f(...))
    ~(f(...)).
  5. Если есть две булевы формулы (возможно одинаковые) f(...) и g(...), то из них можно построить формулы:
    (f(...) g(...))
    (f(...) g(...))
    (f(...) & g(...))
    (f(...) g(...))
    (f(...) g(...))
    (f(...) g(...))
    (f(...) | g(...))
    (f(...) g(...))
    (f(...) g(...))
    (f(...) g(...))

Таким образом, формулы строятся последовательно, шаг за шагом от простейших формул ("атомов") ко все более сложным формулам ("молекулам"), которые внутри себя содержат более простые. Каждую формулу, которая используется как составная часть для построения более сложной формулы, будем называть подформулой. Выше подформулы обозначены как f(...) и g(...).

Внешние скобки в правилах призваны соблюсти тот порядок операций, который соответствует порядку построения формулы из атомов. Для краткости лишние скобки можно убирать. Процесс убирания и восстановления скобок выглядит точно так же, как в школьной алгебре: в зависимости от порядка операций. Когда скобки отсутствуют, то в первую очередь выполняется операция "~" (первый, высший приоритет), затем "&" (второй приоритет), затем "" и "" (третий приоритет), затем все остальные (четвертый, низший приоритет). Операции одного приоритета выполняются слева направо.

Этот порядок приоритетов распространен в наиболее современной математической и компьютерной литературе. Чтобы его запомнить, обратите внимание на сходство с арифметическими операциями смены знака ("-" аналог "~"), умножения (аналогичная операция "&" иногда называется логическим умножением), сложения (аналогичные операции и иногда называются логическим сложением) и операций сравнения (значки операций и внешне похожи на значки операций сравнения =, <, ≥ и др.).

Все булевы формулы имеют одно очень важное общее свойство:

Истинность булевой формулы зависит только от истинности значений переменных.

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

Не имеет значения, какие конкретно высказывания анализируются, если мы уже определили их истинность. Как следствие, мы можем составлять таблицы истинности и для более сложных булевых формул.

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

(~X Y) & (X Y) false

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

XY(~X Y) & (X Y) false
falsefalse 
falsetrue 
truefalse 
truetrue 

Определим порядок действий, согласно скобкам и приоритетам:

1 2   4   3   5  
(~X Y) & (X Y) false

Для каждой операции определяем, откуда взять операнды. Операнд может быть взят

Для каждой операции выполняем вычисление истинности, согласно таблице истинности этой операции. Результат обозначаем промежуточной переменной. Результат последней операции будет результатом вычисления всей формулы. В данном случае порядок действий таков:

  1. Вычислить ~X, обозначить как R1.
  2. Вычислить R1 Y, обозначить как R2.
  3. Вычислить X Y, обозначить как R3.
  4. Вычислить R2 & R3, обозначить как R4.
  5. Вычислить R4 false, обозначить как R5.
  6. Принять R5 как результат вычислений.

Выполним эти действия для конкретной строки таблицы истинности, где X = true, Y = false:

  1. Вычислить ~X, обозначить как R1 = false.
  2. Вычислить R1 Y, обозначить как R2 = true.
  3. Вычислить X Y, обозначить как R3 = true.
  4. Вычислить R2 & R3, обозначить как R4 = true.
  5. Вычислить R4 false, обозначить как R5 = true.
  6. Принять R5 = true как результат вычислений.
После этого можно заполнить одну ячейку таблицы истинности:

XY(~X Y) & (X Y) false
falsefalse 
falsetrue 
truefalsetrue
truetrue 

Аналогично заполняем оставшиеся ячейки:

XY(~X Y) & (X Y) false
falsefalsefalse
falsetruetrue
truefalsetrue
truetruefalse

В принципе, процесс вычисления каждой строки таблицы мало чем отличается от вычисления арифметической формулы в школе. Так же, как в школе, требуется сначала выяснить порядок действий в зависимости от приоритета операций и скобок. Так же, как в школе, надо подставлять на место переменных конкретные значения и получать новые значения; только в обычной алгебре это - числа, а в булевой алгебре - значения истинности true и false. Сами таблицы истинности напоминают школьные функции, которые задаются таблицей. Вскоре мы увидим, что есть и другие сходные черты, например, правила подстановки формул. Недаром булева алгебра называется алгеброй.

В процессе вычисления возможна некоторая оптимизация. Вместо повторения одних и тех же действий можно ограничиться единственным вычислением, после чего использовать значение, обозначенное в промежуточной переменной. Для примера рассмотрите формулу (A ~B) & ~(A ~B) & ~~(A ~B). Составьте для нее инструкцию по вычислению и соптимизируйте ее так, чтобы не вычислять (A ~B) трижды.

Вопросы и задания для самостоятельной работы

  1. Составьте таблицу истинности для формулы (X & Y & Z).
  2. Составьте таблицу истинности для формулы (X Y Z).
  3. Составьте таблицу истинности для формулы ~(X Y).
  4. Составьте таблицу истинности для формулы ~~~~X.
  5. Составьте таблицу истинности для формулы ~Y X.
  6. Вычислите: ~(true & false false)
  7. Вычислите: true true true true true true
  8. Вычислите: X & X & Y & Y & ~Z & ~Z при X = true, Y = true, Z = false