Формальные символические языки

На основе законов формальной логики может быть построен некоторый формальный символический язык, который лежит в основании всех логических теорий. В этом языке могут использоваться логические константы ноль (0) и единица (1), операции отрицания (u), логического умножения (?), которое обычно называют конъюнкцией, логического сложения (+), называемого также дизъюнкцией, следования (импликации E) и равенства (?). Для кодирования смыслов используют также логические переменные. Их можно обозначать латинскими буквами p, q, r, s, t … Каждая такая буква обозначает нечто общее, что может быть в целом классе каких-то смыслов, например, суждений. Например, буквой р можно обозначить любое суждение, допустим, «Луна – спутник Земли», буквой q – суждение «Лев – травоядное животное». Первое суждение мы считаем правильным, что можно обозначить как равенство р единице, т.е. p? 1, а второе суждение – ложным, что можно выразить как равенство q нулю: q? 0. Тогда для сложных суждений мы также получим определенные значения истины или лжи (или, как говорят, истинностные значения). Например, из суждений «Луна – спутник Земли», «Лев – травоядное животное» можно образовать новое суждение «Луна – спутник Земли и Лев – травоядное животное», которое обозначается как умножение p? q (таким образом, логическое умножение обычно соответствует союзу «и» в естественном языке). Для такого сложного суждения мы получим: p? q? 1? 0? 0, т.е. оно окажется ложным. Далее из тех же простых суждений р и q, можно образовать суждение-сумму «Луна – спутник Земли или Лев – травоядное животное», т.е. p + q (логическое сложение обычно соответствует союзу «или» в естественном языке). Для него получим: p + q? 1 + 0? 1. Следовательно, это суждение будет истинным.

Простейший вариант дедуктивной логики, который носит название исчисление высказываний (суждений), примерно так и строится. Здесь вводятся логические переменные и константы, операции, и из простых суждений на основе операций строятся более сложные суждения. Зная истинностные значения простых суждений, можно определять истинностные значения сложных суждений. Возникает некоторый формальный символический язык – язык исчисления высказываний. В силу его простоты, мы можем его описать очень точно.

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

Константы: 1, 0

Переменные: p, q, r, s, t …

Операции: u,?, +, E,?

Скобки: (,)

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

• (1) Базис индукции: любая константа или переменная есть формула.
• (2) Индуктивное предположение: если А, В – уже построенные формулы, то u (А), ((А)? (В)), ((А)+(В)), ((А) E (В)) и ((А)? (В)) – также формулы.
• (3) Индуктивное замыкание: никаких иных формул нет.

Таким образом, в базисе индукции здесь определяются некоторые стартовые формулы, с которых начинается построение множества всех формул, а в индуктивном предположении указываются некоторые правила порождения (отрицание, умножение, сложение, следование и равенство) из уже построенных формул новых формул. Так, многократно обращаясь на множество сначала стартовых, а затем все новых формул, будет прирастать до бесконечности множество формул языка исчисления высказываний. Здесь мы имеем дело с использованием схемы математической индукции по отношению к формулам, а не числам. Условие (3) индуктивного замыкания требует, чтобы среди формул были только такие выражения, которые можно вывести из первых двух пунктов. В противном случае, если бы пункта (3) не существовало, то мы бы лишь утверждали, что любое выражение, вытекающее из пунктов (1) и (2), есть формула, но не наоборот, т.е. могло бы оказаться и так, что не всякая формула была бы выражением, построенным по правилам (1) и (2), что само по себе не противоречит этим пунктам.

Пусть, например, у нас в алфавите всего две переменных p и q, и нет констант. Тогда стартовыми формулами будут всего две формулы: p, q. Затем, согласно индуктивному предположению, мы можем образовать следующие новые формулы: u (p), u (q), ((p)? (p)), ((q)? (q)), ((p)? (q)), ((q)? (p)), ((p)+(p)), ((q)+(q)), ((p)+(q)), ((q)+(p)), ((p) E (p)), ((q) E (q)), ((p) E (q)), ((q) E (p)), ((p)? (p)), ((q)? (q)), ((p)? (q)), ((q)? (p)). Теперь мы можем прибавить эти формулы к формулам p и q, и вновь применить уже к этому расширенному множеству все возможные логические операции во всех возможных комбинациях. Здесь, например, появятся формулы вида ((u (p)) E (q)), (((p) E (q))+((q)? (q))), и т.д. Поскольку количество всех скобок начинает в этом случае резко возрастать, то обычно договариваются о сокращении ряда скобок. Например, пишут u р вместо u (р), или p E q вместо ((p) E (q)).

В формальном языке обычно можно проверить только по внешней форме, является ли та или иная последовательность букв алфавита этого языка его определенным выражением, или нет. Например, чтобы проверить, является ли формулой языка исчисления высказываний последовательность букв u (p E (q + r)) (с учетом сокращений скобок), мы должны начать проверку с самых элементарных формул, входящих в это выражение, постепенно поднимаясь все выше, пока не дойдем до всего выражения в целом. Здесь:

1. Переменные p, q, r являются формулами по базису индукции.
2. Если q, r – формулы, то, согласно индуктивному предположению, и (q + r) – тоже формула.
3. Если p и (q + r) – формулы, то, согласно индуктивному предположению, и (p E (q + r)) – тоже формула.
4. Наконец, если (p E (q + r)) – формула, то, согласно индуктивному предположению, и u (p E (q + r)) – тоже формула.

Так мы доказываем, что выражение u (p E (q + r)) есть формула языка исчисления высказываний.

Подобная проверка не сможет подтвердить, например, что выражение pp является формулой языка исчисления высказываний, т.к., хотя р – это формула, но из формул р и р мы никакими способами, указанными в индуктивном предположении, не сможем получить выражения рр.

В общем случае любые последовательности букв алфавита называются выражениями языка, а некоторые специальные последовательности, выстраиваемые на основе индуктивных правил, - правильно построенными выражениями языка. Формулы – пример правильно построенных выражений (правильно построенных формул) в языке исчисления высказываний.

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

Для построения формальной логики, среди всех формул языка выделяют некоторое множество формул, которые называют аксиомами языка. Выделяют также некоторые правила логического вывода, которые позволяют от одного множества формул (посылок) переходить к другому множеству формул (заключениям). Например, в языке исчисления высказываний в качестве аксиом могут приниматься формулы, выражающие законы непротиворечия, исключенного третьего, тождества и т.д. В качестве правила логического вывода во многих дедуктивных теориях используется так называемое правило отделения, или modus ponens, которое выглядит следующим образом:

p, p E q

q

Как и ранее, правило вывода здесь изображено в виде дроби, где над чертой написаны посылки, под чертой – заключение. Правило отделения позволяет от формул p и (p E q) перейти к формуле q. Это правило удовлетворяет условию переноса истинности: если p? 1 и, (p E q)? 1, то q? 1.

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

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

Во многих суждениях используется логическая структура вида «Для любого х верно, что Р(х)», где Р – некоторое свойство. Например, в такой форме могут быть записаны заключения в различных индуктивных выводах (см. выше). Отрицанием суждения «Для любого х верно, что Р(х)» является суждение «Существует такой х, что u Р(х)» - именно в такой форме могут быть записаны контрпримеры для индуктивного заключения. Оборотам «Для любого х верно, что …» и «Существует такой х, что …» сопоставляют специальные логические структуры – квантор всеобщности " х (символ " взят от англ. «А ll» - все) и квантор существования $ х (от англ. «Exist» - существовать) соответственно. В этом случае суждение вида «Для любого х верно, что Р(х)» записывается как " хР(х), а суждение «Существует такой х, что Р(х)» - как $ хР(х). Обогащение языка исчисления высказываний переменными для объектов (типа x, y, z, …), переменными для предикатов (типа P, Q, R,…) и кванторами по объектным переменным (типа " х, $ х) приводит к построению более сложного и мощного формального языка, который называется языком исчисления предикатов первого порядка (поскольку предикаты и кванторы здесь берутся по объектным переменным, которые еще называют переменными первого порядка). Формулы с кванторами определяются таким образом, что " хР(х)? 1 равносильно тому, что Р(а 1)? 1 и Р(а 2)? 1 и Р(а 3)? 1 и т.д., где а 1, а 2, а 3, … - все частные значения объектной переменной х. Истинность формулы $ хР(х), т.е. верность равенства $ хР(х)? 1, равносильна тому, что Р(а 1)? 1 или Р(а 2)? 1 или Р(а 3)? 1 и т.д., т.е. используется логическое сложение (союз «или») вместо логического умножения (союза «и»). В этом смысле кванторные формулы предполагают бесконечные конъюнкции и дизъюнкции формул языка исчисления высказываний, так что переход от исчисления высказываний к исчислению предикатов – это некоторая разновидность перехода от конечного к бесконечному в логике.