Концептуальные подходы к проведению доказательства
Методы доказательства отсутствия у заданного множества пропозициональных формул конечной характеристической матрицы – это способы, позволяющие обоснованно определить, что у рассматриваемого множества не существует конечной характеристической матрицы.
В логике существует несколько базовых методов доказательства:
- Метод редукции: путем последовательного применения логических эквивалентностей и законов де Моргана можно свести исходное множество формул к более простому виду, для которого уже известно, что оно не имеет конечной характеристической матрицы.
- Метод матричных вычислений: можно вычислить характеристическую матрицу для заданного множества формул и показать, что она не имеет конечного ранга.
- Метод доказательства от противного: предположим, что заданное множество формул имеет конечную характеристическую матрицу. Тогда можно показать, что это приводит к противоречию с логическими законами или другими свойствами логики.
- Метод построения контрпримера: можно попытаться найти конкретный пример формулы, которая не удовлетворяет условию конечности характеристической матрицы. Если такой пример будет найден, то это будет означать, что исходное множество формул не имеет конечной характеристической матрицы.
Характеристика пропозициональных формул
Пропозициональные формулы - это выражения, состоящие из пропозициональных переменных, логических операторов и скобок, которые могут быть вычислены как истинные или ложные.
В рамках математической логики производится изучение рассуждений математическими методами. Смысл всякого рассуждения состоит в том, что от одного суждения последовательно переходят к другому. Суждения в языке выражаются с помощью предложений.
Под высказываниями понимают повествовательные предложения, для которых можно определить истинность или ложность.
Из одних высказываний могут быть построены другие, более сложные. Для этого используются логические операции.
Под логической операцией понимают способ построения из данных высказываний нового сложного высказывания, при котором истинностное значение сложного высказывания зависит только от истинностных значений исходных высказываний.
Каждая логическая операция отличается собственным набором зависимости истинностного значения результата от истинностных значений исходных высказываний. Такие зависимости могут быть отражены с помощью таблицы истинности.
Логические операции – отрицание, конъюнкцию, дизъюнкцию, импликацию – называют пропозициональными операциями, а используемые для их обозначения символы – пропозициональными связками.
Пропозициональная формула определяется индуктивным образом:
- всякая пропозициональная переменная является формулой (такую формулу называют атомом),
- если А – формула, то и отрицание А является формулой,
- если А и В – формулы, то путем связывания их пропозициональной связкой также будет получена формула.
Итак, можно сформулировать основные характеристики пропозициональных формул:
- Атомарность: пропозициональная формула может быть атомарной, то есть состоять только из одной пропозициональной переменной.
- Сложность: пропозициональная формула может быть сложной, то есть состоять из нескольких пропозициональных переменных, связок и логических скобок.
- Синтаксис: пропозициональные формулы должны соответствовать правилам синтаксиса логики высказываний. Например, каждая открывающая скобка должна иметь соответствующую закрывающую скобку.
- Интерпретация: каждой пропозициональной переменной в формуле должно быть сопоставлено значение истины или лжи.
- Значение истины: каждая пропозициональная формула имеет значение истины или лжи в зависимости от значений пропозициональных переменных. Например, формула "A и B" будет истинной только в том случае, если и А, и В будут истинны.
- Эквивалентность: две пропозициональные формулы называются эквивалентными, если они имеют одинаковые значения истины для всех возможных значений пропозициональных переменных.
Существование характеристической матрицы для логики
Под логической матрицей понимают набор:
М = $\lt$m, 1, *, +, →, ~$\gt$,
где:
- m – некоторое непустое множество, выступающее в роли носителя матрицы M;
1 – одноместная, а * , +, → и ~ - двухместные операции, удовлетворяющие следующим условиям:
- если 1 → х = 1, то х = 1;
- если x → y = y → x = 1, то x = y.
Под оценкой в логической матрице М понимают произвольную функцию, сопоставляющую каждую пропозициональную переменную с некоторым элементом множества М. [/Определение]
Формулу А считают истинной в логической матрице М, если f(A) = 1, какая бы оценка f ни использовалась в М. Если же для какой-то из оценок f f(A) отлично от 1, говорят, что в матрице М формула А опровергается. Матрица М в таком случае представляет собой контрмодель для формулы А.
Логическую матрицу М называют моделью для данного пропозиционального исчисления, если все выводимые в этом исчислении формулы истинны в М.
Логическую матрицу М называют точной моделью для данного исчисления, если в нем выводимы те и только те формулы, которые истинны в этой матрице.
Пусть пропозициональное исчисление таково, что его единственным правилом вывода является MP. Тогда логическая матрица M является моделью этого исчисления, если и только если все его аксиомы истинны в M.
Пусть Γ — произвольное множество формул. Интерпретацию языка PL логики высказываний, в которой истинны все формулы множества Γ, называют моделью множества Γ. Если существует модель множества Γ, то говорят, что Γ имеет модель (или Γ совместно).
Всякое множество Γ замкнутых формул, имеющее модель, непротиворечиво.
Справедлива и обратная теорема.
Всякое непротиворечивое множество формул Γ имеет модель.
Всякое непротиворечивое множество формул Γ содержится в некотором непротиворечивом полном множестве формул.
Пусть Γ — множество формул. Тогда если всякое конечное подмножество множества Γ имеет модель, то Γ имеет модель.
