3. Элементы математической логики. Исчисление высказываний, его полнота.

Чтобы задать логическое исчисление нужно задать :

1. множество символов исчисления Х;

2. множество выражений Х^* (конечная последовательность символов)

3. множество формул исчисления ;

4. множество аксиом исчисления ;

5. множество правил вывода исчисления. Это есть формальные процедуры (алгоритмы), которые по произвольным формулам и формулеА определяют выводима ли непосредственна формула А из формул . В случае, если формулаА выводима из непосредственно, этот факт записывают.

Формула А выводима в логическом исчислении, если существует последовательность формул , что последняя формула, и все формулы этой последовательности есть либо аксиомы логического исчисления, либо непосредственно следуют из предыдущих формул по правилам вывода данного исчисления. В этом случае говорят, что формулаА является теоремой исчисления и записывают |-A.

Будем говорить, что А является следствием формул (гипотез) и записывать|-A, если существует последовательность формул что последняя формула естьА и каждая формула в этой последовательности есть либо аксиома, либо одна из гипотез , либо непосредственное следствие предыдущих формул .

Свойства выводимости:

1) пусть из множества гипотез Г выводится формула А, множество ГΔ есть подмножество множества Δ, тогда формулаА есть следствие множества формул Δ |-A . Утверждение следует из того факта, что вывод формулы А из множества Г является выводом А из множества Δ, т. к. Δ .

2) пусть Г|-А , тогда конечное подмножествоГ’ множества Г такое, что Г’|-А . Это следует из того, что для формулы А по определению вывод конечен, поэтому кол-во используемых гипотез Г в этом выводе конечно, это множество и есть то конечное множество Г’ из которого следует формула А.

3) пусть Г|-А и каждая F из Г есть следствие формул Δ. Δ |-F , следовательно А есть следствие формул Δ : Δ |-A . Это следует из того, что в выводе формулы А из множества Г каждую гипотезу Г можно заменить их выводами из формул Δ , тогда получим вывод А из множества гипотез Δ.

Теперь рассмотрим конкретное исчисление- исчисление высказываний.

1) символы исчисления высказываний есть счетная последовательность , бинарная связка (семантически это фукция следствия) ; унарная связка (семантически это отрицание переменной); скобки (;).

2) выражения есть любые конечные последовательности символов исчисления

3) формулы (правильно построенные выражения).

Индуктивное Определение

пусть - переменная, тогда - есть формула..

Пусть -формулы, тогда выражения вида- ,также являются формулами.

4. аксиомы исчисления:

для любых формул A,B,L

6. правила вывода:

Modus ponens (MP): , для любых формул.

Построенное исчисление будет задавать множество тавтологий. Т.е. множество теорем ИВ и множество тождественно истинных в логическом смысле формул в базисе - есть одно и тоже множество.

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

Тавтологией назовем функцию, которая на всех наборах принимает значение 1.

Утверждение

Каждая теорема ИВ является тавтологией.

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

Чтобы это показать, докажем вначале, что каждая аксиома тавтология. Затем покажем, что правило вывода сохраняет свойство тавтологии (т.е. непосредственное следсвие двух тавтологий- есть тавтология).

Каждая аксиома исчисления высказываний является тавтологией.

Допустим противное: существует набор, при котором

тогда

противоречие . Покажем, что a2 тавтология, допустим противное

Правило МР сохраняет свойство формулы быть тавтологией, то есть непосредственное следствие двух тавтологий есть тавтология.

|-B

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

Рассмотрим тавтологию А и , покажем что формулаВ - есть тавтология. Допустим противное:

, т.к. А тавтология, не является тавтологией, получили противоречие, что и требовалось доказать.

Теоремы исчисления высказываний есть тавтологии. Аксиомы- есть тавтологии, а следствия из этих аксиом тогда также будут тавтологией в силу того, что МР сохраняет свойство тавтологии. Утверждение доказано.

Справедливо обратное утверждение.

Утверждение

Любая тавтология в базисе - есть теорема исчисления высказывания.

Перед доказательством этого утверждения необходимы некоторые рассуждения. Построим вывод некоторых теорем.

Аксиомы:

1. В исчислении высказываний выводима . Запишем аксиому а2 в виде

, заменив L на А и В на , тогда видно, что левая часть данной формулы (посылка) есть аксиома а1 ( вместоВ подставлена). Тогда по правилу вывода из этих двух формул- аксиом воводима правая часть (следствие):

,

Левая часть выведенной формулы есть аксиома а1, где вместо В стоит А, поэтому из предыдущей формулы по правилу МР выводима правая часть формулы.

Это и есть требуемая теорема.

Предложение 1:

Из формулы А для любой формулы В выводима ВА

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

и а1, по правилу МР выводима правая часть.

Из формулы А выводима любая формула, где А стоит в правой части.

Теорема дедукции:

Из множества гипотез и формулы А выводима В , тогда из множествавыводима.

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

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

При В₁ есть либо одна из гипотез Г либо аксиома, либо формула А. В первых двух случаях данное утверждение следует из предложения. В оставшемся случае выводимая формула принимает вид . Но эта теорема в исчислении, следовательно доказательство при j=1 завершено.

Пусть утверждение верно для всех . Докажем утверждение для : В_k есть либо одна из гипотез Г , либо аксиома, либо формула А, либо следует по правилу вывода из некоторых предыдущих формул В_j, B_s, где B_s имеет вид по правилу вывода . В первых трех случаях доказательство такое же, как и для j=1 . В оставшемся случае применим предположение индукции и аксиому а2: а именно: из предположения индукции следует, что из гипотезвыводятся формулыи, т.е..

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

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