Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Исчисление высказываний получает теперь следующую интерпретацию. Его теоретико-множественным образом является алгебра множеств, получаемых из Р, Q, ... с помощью операций пересечения, объединения и взятия дополнения относительно некоторого универсального множества U, содержащего все Р, Q, ... и 36
Часть /. Предварительные сведения из логики и алгебры
соответствующего истине. Взятие дополнения относительно U соответствует отрицанию; пустое множество 0, являющееся дополнением для JJ, соответствует лжи.
2.1.10. Варианты исчисления высказываний
Можно строить исчисления, эквивалентные описанному выше, но с другими основными операциями.
Один из наиболее интересных вариантов исчисления высказываний получается в случае, когда используются только операции ~1 и =), Мы знаем, что
p=>q = ~lp V<7
и что
-I -I P = P,
откуда
pVq=~lp=>q.
Выражение для р Л q можно получить с помощью правила де Моргана.
Подчеркнем, что все операции исчисления высказываний могут быть выражены через одну подходящим образом выбранную операцию (см. ниже упр. 2.1.11.6).
2.1.11. Упражнения
1. Пусть даны высказывания: 'жарко = с', 'идет дождь s р\ 'воздух сухой = s'; изобразить с помощью символов следующие высказывания:
а) 'идет дождь и жарко',
б) 'жарко, но воздух не сухой',
в) 'воздух сырой или жарко',
г) 'дождь не идет или воздух сухой'.
2. Предположив, что предложение «Холодно и воздух сырой» истинно, исследовать истинностные значения предыдущих предложений.
3. Обозначим через р предложение «Самолет летит высоко» и через q — «Самолет набирает высоту». Перевести на русский язык:
а) р Aq,
б) р Aq,
в) P Aq,
г) р V q, A) P Aq, е) р V q, ж) р V q- Г л //. Общие сведения о формальных системах
37
Попытайтесь выразить полученные переводы с помощью более простых символических выражений.
4. Пусть р означает «У меня есть проигрыватель», a q — «У меня есть пластинки». Переведите на русский язык, а затем упростите выражение
PVq Л Р.
5. Исходя из двух переменных или выражений, можно построить формулу <npWq», где W задается следующей таблицей:
P 0 PWq
0 0 0
0 1 1
1 0 1
1 1 0
и соответствует разделительному или (т. е. строгой дизъюнкции: либо одно, либо другое, но не то и другое вместе).
Дайте теоретико-множественную интерпретацию операции W. Является ли эта операция ассоциативной?
6. Аналогичный вопрос для операции |, которая называется «штрихом Шеффера» (или несовместимостью) и определяется следующей таблицей:
P я P\q
0 0 1
0 1 1
1 0 1
1 1 0
Проверить следующие тавтологические эквивалентности:
P = P I Р. р V q = (p\p)\(q\q), р Л q = (p\q)\(p\q),
PZD q = p\(q\q).
§ 2.2. ПОНЯТИЕ ФОРМАЛЬНОЙ СИСТЕМЫ
Исторически понятие формальной системы развилось на основе понятия аксиоматической теории, о котором поэтому мы скажем здесь несколько слов. 38
Часть /. Предварительные сведения из логики и алгебры
Частично аксиоматизированным было уже изложение геометрии в «Началах» Евклида, однако полностью аксиоматический подход четко оформился лишь в конце 19 века.
2.2.1. Аксиоматическая теория
Внутренняя логическая связность некоторой математической теории и ее адекватность для описания того или иного круга физических явлений — это две совершенно разные вещи. Данный факт был осознан математиками, когда им пришлось объяснять возможность одновременного существования евклидовой геометрии и различных неевклидовых геометрий.
Чтобы построить и логически развивать некоторую математическую теорию, необходимо абстрагироваться от природы объектов, которые она рассматривает (вернее, от природы объектов, которые, так сказать, мотивировали извне создание этой теории). В то же время необходимо самым тщательным образом уточнить с помощью аксиом основные отношения, связывающие эти объекты друг с другом.
«Мы мыслим три различные системы вещей; вещи первой системы мы называем точками; вещи второй системы мы называем прямыми; вещи третьей системы мы называем плоскостями»,— писал Давид Гильберт в своих «Основаниях геометрии»; в устных беседах он добавлял: «Конечно, эти вещи можно было бы называть не точками, прямыми и плоскостями, а, скажем, столами, стульями и пивными кружками».
Вся существенная информация о точках и прямых содержится в следующих аксиомах:
1.1. Прямая есть множество точек.
1.2. Через любые две точки можно провести некоторую прямую.
1.3. Через две точки можно провести только одну прямую.
1.4. На любой прямой имеются по крайней мере две точки.
1.5. Существуют по крайней мере три точки, не принадлежащие одной прямой.
Исходя из аксиом, можно доказывать теоремы, например:
Теорема. Любые две различные прямые могут иметь только одну общую точку.
Каким именно способом выводятся теоремы из аксиом в рамках аксиоматической теории, об этом в большинстве случаев специально не говорят. Считается, что это делается в соответствии с правилами логики, которые основаны на здравом смысле и усваиваются на примерах. Эти правила к тому же представляются «очевидными», например: если некоторое высказывание истинно, то его отрицание ложно.
