Пропозициональная переменная

Пропозициональная переменная — это переменная, областью значений которой являются истинностные значения (обычно «истина» и «ложь»). В формальной логике, в частности в исчислении высказываний, пропозициональные переменные служат для обозначения простых (атомарных) высказываний, внутренняя структура которых не рассматривается. Они являются базовыми элементами, из которых с помощью логических связок (конъюнкции, дизъюнкции, импликации, отрицания и др.) строятся более сложные формулы.

Определение и формальные свойства

В формальном языке логики высказываний пропозициональная переменная представляет собой символ (обычно латинская буква, например, \(p, q, r, s\), или буква с индексом, например, \(p_1, p_2\)), который может принимать одно из двух истинностных значений. Множество всех пропозициональных переменных образует алфавит языка. Каждая пропозициональная переменная является атомарной формулой — формулой, не содержащей логических связок и не разложимой на более простые формулы в рамках данного языка.

Интерпретация пропозициональной переменной — это приписывание ей конкретного истинностного значения. Функция, которая каждой пропозициональной переменной ставит в соответствие значение «истина» (1) или «ложь» (0), называется оценкой или пропозициональной интерпретацией. Истинностное значение сложной формулы определяется истинностными значениями входящих в неё пропозициональных переменных и семантикой логических связок.

История возникновения и развития понятия

Понятие пропозициональной переменной сформировалось в рамках математической логики в конце XIX — начале XX века, хотя идея использования символов для обозначения высказываний восходит к античной логике.

Античная и средневековая логика

Аристотель в своей силлогистике использовал буквы для обозначения терминов (например, «все A суть B»), но эти буквы обозначали классы объектов, а не высказывания целиком. Стоики, напротив, разрабатывали логику высказываний, используя порядковые номера для обозначения целых пропозиций, однако не ввели переменных в современном смысле. В средневековой логике (например, у Петра Испанского) использовались буквы для обозначения пропозиций, но формальная система оставалась неразвитой.

Возникновение алгебры логики

Решающий шаг был сделан в середине XIX века Джорджем Булем. В работе «Математический анализ логики» (1847) и «Исследование законов мышления» (1854) Буль предложил алгебраическую систему, в которой символы \(x, y, z\) обозначали классы, а операции — логические действия. Однако Буль интерпретировал переменные как классы, а не как пропозиции. Уильям Стенли Джевонс и Чарльз Сандерс Пирс впоследствии адаптировали булеву алгебру для логики высказываний, фактически используя переменные для обозначения истинностных значений.

Формализация в XX веке

В 1879 году Готлоб Фреге в работе «Begriffsschrift» («Исчисление понятий») впервые построил формальную систему логики высказываний и предикатов, в которой использовал буквы (например, \(A, B, C\)) для обозначения пропозиций. Фреге ввёл строгое различие между переменной и константой, а также определил правила подстановки. Дальнейшее развитие понятие получило в работах Бертрана Рассела и Альфреда Норта Уайтхеда в «Principia Mathematica» (1910—1913), где пропозициональные переменные стали основой для построения пропозициональных функций. В середине XX века, с развитием метаматематики и теории моделей, понятие пропозициональной переменной было окончательно формализовано в рамках синтаксиса и семантики логических исчислений.

Классификация и виды

В зависимости от контекста и используемой логической системы, пропозициональные переменные могут классифицироваться по нескольким признакам.

По типу логики

• В классической логике высказываний: переменные принимают ровно два значения — «истина» и «ложь». Это наиболее распространённый случай.
• В многозначных логиках: переменные могут принимать более двух истинностных значений (например, три значения в логике Лукасевича: «истина», «ложь», «неопределённость»).
• В интуиционистской логике: семантика переменных отличается от классической; они не подчиняются закону исключённого третьего, а их интерпретация часто строится через понятие доказуемости.
• В модальных логиках: пропозициональные переменные сохраняют те же свойства, но добавляются модальные операторы (необходимость, возможность), которые модифицируют истинностные значения формул.

По роли в синтаксисе

• Свободные переменные: в формуле пропозициональная переменная является свободной, если она не связана никаким квантором (в логике высказываний кванторы отсутствуют, поэтому все переменные являются свободными; в логике предикатов пропозициональные переменные могут быть связаны кванторами по пропозициональным переменным, что встречается редко).
• Связанные переменные: в некоторых расширениях логики высказываний (например, в пропозициональной логике с кванторами по пропозициональным переменным) переменная может быть связана квантором.

Применение в логике и информатике

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

Математическая логика

• Исчисление высказываний: пропозициональные переменные служат атомами, из которых строятся формулы. Задача выполнимости (SAT) — одна из центральных в теории сложности вычислений — заключается в поиске такой оценки пропозициональных переменных, при которой данная формула становится истинной.
• Теория доказательств: пропозициональные переменные используются в аксиомах и правилах вывода. Например, в гильбертовском исчислении аксиома \(p \to (q \to p)\) содержит пропозициональные переменные \(p\) и \(q\).
• Теория моделей: интерпретация пропозициональных переменных определяет модель (или структуру) для языка логики высказываний.

Информатика и программирование

• Булева алгебра и цифровая схемотехника: пропозициональные переменные соответствуют булевым переменным, которые принимают значения 0 и 1. Логические схемы (вентили, триггеры, сумматоры) реализуют булевы функции, заданные таблицами истинности, где каждая строка соответствует одной из возможных комбинаций значений пропозициональных переменных.
• Логическое программирование: в языках типа Prolog пропозициональные переменные используются для представления фактов и правил, хотя чаще применяются предикаты.
• Верификация программ: методы проверки моделей (model checking) используют пропозициональные переменные для описания состояний системы и свойств, которые должны быть выполнены. Формулы темпоральной логики (LTL, CTL) строятся на основе пропозициональных переменных, обозначающих атомарные утверждения о состояниях.
• Искусственный интеллект: в системах, основанных на знаниях, пропозициональные переменные используются для представления фактов. Задачи автоматического доказательства теорем и планирования часто сводятся к проверке выполнимости пропозициональных формул.

Лингвистика и философия

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

Примеры

1. Простая формула: \(p \land q\). Здесь \(p\) и \(q\) — пропозициональные переменные. Формула истинна только в том случае, если обе переменные принимают значение «истина».
2. Тавтология: \(p \lor \neg p\). Эта формула истинна при любом значении переменной \(p\) (закон исключённого третьего).
3. Противоречие: \(p \land \neg p\). Формула ложна при любом значении \(p\).
4. Задача SAT: дана формула \((p \lor q) \land (\neg p \lor \neg q)\). Она выполнима: например, при \(p = 1, q = 0\) или \(p = 0, q = 1\).

Интересные факты

• В классической логике высказываний существует ровно \(2^n\) различных оценок для \(n\) пропозициональных переменных, что соответствует числу строк в таблице истинности.
• Проблема выполнимости булевых формул (SAT) была первой задачей, доказанной NP-полной в 1971 году Стивеном Куком. Это означает, что для неё не известен эффективный (полиномиальный) алгоритм решения, но если бы такой алгоритм был найден, то многие сложные задачи (например, в криптографии, планировании, биоинформатике) стали бы решаемы за разумное время.
• В некоторых неклассических логиках, например, в линейной логике, пропозициональные переменные могут иметь дополнительные свойства, связанные с ресурсами (например, переменная может быть использована только один раз).

Источники

1. Готлоб Фреге. «Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens» (1879).
2. Джордж Буль. «Исследование законов мышления» (1854).
3. Бертрам Рассел, Альфред Норт Уайтхед. «Principia Mathematica» (1910—1913).
4. Стивен Кук. «The Complexity of Theorem-Proving Procedures» (1971).
5. Эллиот Мендельсон. «Введение в математическую логику» (1964).
6. Джон Г. Кемени. «Математическая логика» (1958).