Пропозициональные формулы

Объектный язык и метаязык

Логика высказываний

Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.

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

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

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы ¬ (отрицание), & (конъюнкция), V(дизъюнкция) и ^ (импликация) называются пропозициональными связками; ¬ – унарная связка, а другие – бинарные.

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

Чтобы определить понятие пропозициональной формулы, нам требуется следующее вспомогательное определение.

1) Определение.Множество X строк замкнуто относительно правил построения (для логики высказываний), если

• каждый атом принадлежит X,
• для любой строки F, если F принадлежит X, то ¬F тоже принадлежит,
• для любых строк F, G и любой бинарной связки €, если F и G принадлежат X, то также принадлежит (F € G).

2) Определение (Формула).Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

Множество формул замкнуто относительно правил построения.

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

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура – это {p, q}.

3) Определение (Интерпретация).Символы л,и (``ложь'', ``истина'') называются истинностными значениями. Интерпретация может быть определена таблицей её значений, например:

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

Прежде всего нам надо связать функцию с каждой пропозициональной связкой – функцию из {л,и} в {л,и} с унарной связкой ¬ и функцию из {л,и} ^{л,и} в {л,и} с каждой бинарной связкой. Функции определяются таблицами по и,л рассмотренными выше.

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

Приведем пример, в котором покажем, как средствами таблично построенной логики высказываний можно установить, является ли правильным рассуждение: «Если философ не признает познаваемость мира (¬p), то он не является последовательным материалистом.(¬q) Если философ признает познаваемость мира (p), то он не является агностиком (r). Следовательно, если философ является последовательным материалистом (q), то он не является агностиком (r)».

Построим формулу этого высказывания, используя язык логики высказываний:

((¬p → ¬q) ^(p → r)) → ( q → r))

В состав этого высказывания входят три простых высказывания p, q , r и их отрицания, поэтому в системе двузначной математической логики нам необходимо будет построить таблицу на восемь значений по И,Л ( 2 возводим в куб и получаем восемь).

Выводы в логике высказываний строятся из конструкций, которые называются ``секвенциями''.

Секвенция – это выражение вида G |– F (``F при посылках G'') или G |– ^ (``посылки G противоречивы''), где F – формула и G – конечное множество формул.

Мы определим, какие секвенции рассматриваются ``начальными'', и опишем несколько ``правил вывода'' для порождения новых секвенций из секвенций, порождённых ранее. Начальные секвенции называются аксиомами.

Аксиомыв исчислении высказываний имеют вид

{ F } |– F.

Мы определим 12 правил вывода, и удобно вводить их постепенно.

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

Дерево доказательства определим рекурсивно:

1. Деревом доказательства является пустое дерево доказательства, состоящее только из корня – аксиомы.

2. Пусть T₁, ..., T_k – деревья доказательства с корнями R₁, ..., R_k. Тогда

3. (где S – некоторая секвенция) – дерево доказательства, если S может быть получена из R₁, ..., R_k с помощью одного из правил вывода. Корнем такого дерева является S.

Доказуемая секвенция.Если существует дерево доказательства с корнем R, то R называют доказуемой секвенцией. Если этот корень имеет вид G |– F, то говорят о выводе формулы F из G.

В соответствие с дедуктивным определением следования говорят, что F следует из G, если существует вывод F из подмножества G.

Дата добавления: 2014-02-26; просмотров: 929; Нарушение авторских прав

Мы поможем в написании ваших работ!