Алгебра высказываний

Теория

Высказывания и их истинностные значения. Логические операции ∨, ∧, →, ∼, ¬. Пропозициональные операции и связки. Пропозициональные формулы: пропозициональные переменные и шаг индукции (X ∨ Y , X ∧ Y , X → Y , ¬X). Язык и метаязык. Истинностные функции и пропозициональные формулы. Утверждение: каждая истинностная функция соответствует некоторой пропозициональной формуле.

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

  1. дизъюнкция (соответствует союзу или“);
  2. конъюнкция (соответствует союзу ”и“);
  3. импликация (соответствует фразе типа”       если ..., то );
  4. эквиваленция (соответствует фразе типа” ... тогда и только тогда”      , когда ...);
  5. отрицание (соответствует союзу не“).           ”

Первые четыре из этих операций бинарные, последняя унарная. Относительно указанных операций можно сказать лишь, что они формируют новое высказывание. При этом, зная, истинны или ложны исходные высказывания, можно сказать, является ли истинным вновь образованное высказывание. Введенные пять операций мы будем называть логическими или пропозициональными.
Мы имеем дело с некоторой алгебраической системой, и для нее можно ввести свой математический язык — язык алгебры высказываний. В этом языке из заданного набора символов — алфавита языка — по определенным правилам составляются последовательности, называемые словами или фразами, формулами.
Алфавит языка алгебры высказываний составляют множество пропозициональных переменных, множество функциональных символов (символов операций, или логических связок) ∨, ∧, →, ∼, ¬ и множество служебных символов (две круглые скобки). Формулы языка вводятся индуктивно.
База индукции: пропозициональные переменные представляют собой формулы.

Шаг индукции: если X и Y — формулы, то формулами являются (X ∨Y ), (X ∧Y ), (X →Y ),
(X ∼ Y ), (¬X).
Договоримся о следующих обозначениях. Будем обозначать: пропозициональные переменные — строчными латинскими буквами конца алфавита (x, y, z ит.д.); какие-либо формулы — прописными латинскими буквами конца алфавита (X, Y , Z и т.д.). Как и в теории булевых функций, для сокращения количества скобок в формулах договоримся о таком же приоритете операций. Это соглашение не относится к самому языку ми служит лишь для удобства.
В наших рассуждениях будут встречаться формулы, которые относятся к введенному языку, но, кроме того, придется использовать и дополнительные обозначения и символику, чтобы рассуждать не в рамках языка, а о самом языке и его формулах. Так, обозначения переменных — это элемент языка алгебры высказываний, а обозначения формул уже выходят за рамки языка.

Дополнительное соглашение о приоритете операций также выходит за рамки языка. В этом случае говорят о расширении рассматриваемого языка или о метаязыке. На практике язык и метаязык тесно переплетаются, и разделить их не просто.
Слова языка алгебры высказываний, называемые пропозициональными формулами, — лишь цепочки символов, составленные по определенным правилам. Они получают содержательный смысл, если ввести какую-либо интерпретацию рассматриваемого языка. Естественная интерпретация — ввести область изменения каждой пропозициональной переменной как множество всех высказываний и сопоставить каждому символу соответствующую логическую операцию. Тогда каждая формула будет определять правило, по которому из некоторого набора исходных высказываний, обозначенных переменными, мы получим новое высказывание. Сама подстановка вместо переменных конкретных высказываний уже выходит за рамки рассматриваемого языка. Отметим, что формулы алгебры высказываний имеют и другие интерпретации. Например, пропозициональные переменные можно рассматривать как булевы переменные, а функциональные символы увязать с соответствующими булевыми операциями. Такая интерпретация позволяет получить исходя из истинности высказываний истинность сложного высказывания. Формула будет определять булеву функцию, которую называют истинностной функцией. Именно истинностные функции и следует рассматривать как главную цель изучения в алгебре высказываний, поскольку она позволяет судить об истинности сложных, запутанных высказываний.

Теорема 2.1. Каждая булева функция является истинностной функцией некоторой формулы алгебры высказываний.

◀ Язык алгебры высказываний совпадает с языком булевой алгебры, построенным на множестве и зпяти булевых функций ∨, ∧, →, ∼, ¬. Поскольку это множество содержит стандартный базис в B и, следовательно, полно, любая булева функция может быть представлена формулой над заданным множеством. Эту формулу можно рассматривать как формулу алгебры высказываний. При этом булева функция будет истинностной функцией указанной формулы. ▶