Непротиворечивость ив

Проблема непротиворечивости возникает при рассмотрении любого исчисления: это одна из кардинальных проблем математической логики.

Определение. Исчисление называется непротиворечивым, если в нем ни для какой формулы F не выводимы формулы F и ¬F одновременно. В противном случае исчисление называется противоречивым.

Если исчисление противоречиво, т. е. для некоторой формулы F в нем выводимы F и ¬F , то обычно в таком исчислении выводимы все формулы, и поэтому оно ценности не представляет. Покажем, что ИВ непротиворечиво.

Лемма 1. Если формула F выводима, то она тавтология.

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

Если F - тавтология, то формула F^G_А будет принимать только значение 1, какие бы значения не принимала формула G. Значит, F^G_А – тавтология. Если F, F→G –тавтологии, то G не может принимать значение 0. Значит, G – тавтология. Таким образом, из тавтологий по правилам вывода получаются только тавтологии. Следовательно, всякая выводимая формула - тавтология.

Лемма доказана.

Теорема 1. ИВ непротиворечиво.

Доказательство:

По лемме 1, если формула F выводима, то она тавтология. Но тогда формула ¬F - противоречие и поэтому она не выводима. Следовательно, ИВ непротиворечиво. Теорема доказана.

Полнота ив

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

Этот вопрос и представляет собой проблему полноты в широком смысле для ИВ.

Смысл такой постановки вопроса состоит в том, что при построении логического исчисления, предназначенного выражать содержательную логику, нам требуется знать, достаточно ли мы имеем аксиом и правил для того, чтобы вывести любую формулу, которая в содержательном понимании является тождественно истинной.

Проблема полноты в широком смысле слова решается положительным образом.

Теорема 2. Всякая тождественно истинная формула (тавтология) АВ выводима в ИВ.

В дальнейшем через U будем обозначать произвольную выводимую формулу, а через Λ- формулу, для которой ¬ Λ выводима. Иначе говоря, если в дальнейшем встретится символ U (или Λ), то при этом подразумевается, что U (соответственно ¬ Λ) есть произвольно выводимая в ИВ формула.

Введем теперь нужное для дальнейшего сокращенное обозначение.

Пусть формула F содержит ровно n переменных высказываний:

F=F(А₁, А₂, А₃, … , А_n).

Определим для нее по индукции формулу

(*)

Если n=1, то

– это формула F(U)&F(Λ).

Пусть определены формулы (*) для всех F, для которых n ≤ k. Пусть теперь формула F(А₁, А₂, А₃, … , А_k, А_k+1) содержит ровно k+1 высказываний А₁, А₂, А₃, … , А_k, А_k+1 ; через

мы обозначим формулу

По существу формула (*) может быть определена как конъюнкция всех возможных формул, полученных из F(А₁, А₂, А₃, … , А_n) всевозможными заменами переменных высказываний А₁, А₂, А₃, … , А_n на U , Λ.

Т еорема 3.

(1)

Доказательство теоремы 2:

Для доказательства рассмотрим произвольную тождественно истинную в АВ формулу F и воспользуемся теоремой 3. Так как формула F=F(А₁, А₂, А₃, … , А_n) тождественно истинна, то любая подстановка формул U , Λ вместо А₁, А₂, А₃, … , А_n в формулу F приводит к выводимой в ИВ формуле (доказать!). Следовательно в формуле

,

являющейся посылкой в (1) , все сомножители - выводимые формулы, а значит, и вся эта формула выводимая. Применив теперь к (1) правило заключения, получим, что формула F(А₁, А₂, А₃, … , А_n) выводима в ИВ.

Теорема доказана.

Итак, мы показали, что употреблявшийся нами ранее термин “выводимая в ИВ формула” совпадает с содержательным понятием тождественно истинной формулы.

Следствие. Все “правила действий” с формулами, которые выполняются в АВ, непосредственно переносятся в ИВ.

Пример. В ИВ верны утверждения:

1. ├ F&G~G&F

2. ├ FG~GF

3. ├ F&(G&С)~(F&G)&С

4. ├ F (GС)~(FG)С

5. ├ F& (GС)~F&GF&С

6. ├ FG&С~(FG) &(FС)

7. ├ (F→G)~ ¬FG

8. ├ ¬(F&G)~ ¬F  ¬G

9. ├ ¬(F  G)~ ¬F & ¬G

Не менее важное значение, чем понятие полноты в широком смысле, имеет понятие полноты логического исчисления (ЛИ) в узком смысле. ЛИ называется полным в узком смысле, если присоединение к его аксиомам какой-нибудь не выводимой в нем формулы приводит к противоречию. ИВ полно также в узком смысле. Доказательство этого факта нетрудно провести, используя конъюнктивные нормальные формы.

Теорема 4 (дедукции). Если формула F выводима из формул F₁, … , F_n , то F₁→( F₂→( F₃→(…( F_n→ F)…))) – выводимая формула.

Доказательство проведем по индукции. Сначала докажем, что оно верно, если F является либо одной из формул F_i , либо выводимой формулой ИВ. Затем покажем, что если наше утверждение верно для формул F′ и F′→F′′, то оно верно и для F′′.

Предикаты

Будем рассматривать предложения, зависящие от параметров. Например, « - простое число», « », « делится на ». Каждое из этих предложений при конкретных значениях становится высказыванием, принимающим значение «истина» или «ложь». Такого рода предложения называются предикатами.

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

Пример.

1. Предикат : « - простое число» является одноместным предикатом.

2. Предикат : « » - двуместный предикат.

3. Для каждого натурального можно рассмотреть одноместный предикат : « делится на »; в то же время предложение « делится на » является двуместным предикатом, если считать переменной, принимающей натуральные значения.