Отрицание сложных высказываний

При помощи оператора «неверно, что» могут подвергаться отрицанию не только простые, но и сложные высказывания. При этом исходное высказывание и его отрицание будут находиться в отношении противоречия. Это значит, что в тех случаях, когда исходное высказывание истинное, его отрицание будет ложным и наоборот. Рассмотрим отрицания известных союзов.

Отрицание конъюнкции. Если подвергнуть отрицанию высказывание «Шел дождь, и светило солнце», получим высказывание «Неверно, что шел дождь и светило солнце», которое по смыслу соответствует высказыванию «Или дождь не шел, или не светило солнце». Значит, отрицание конъюнкции равнозначно дизъюнкции отрицаний, что можно выразить в виде формулы: ( p ^ q) ↔ p v q

Отрицание дизъюнкции. Подвергнув отрицанию высказывание «Он или больной, или уехал в командировку», получим высказывание «Неверно, что он больной или уехал в командировку», по смыслу соответствующее высказыванию «Он не больной и не уехал в командировку». Значит, отрицание дизъюнкции равнозначно конъюнкции отрицаний, что можно выразить формулой: ( p v q) ↔ p ^ q

Отрицание импликации. Отрицанием импликативного высказывания «Если деревянный брус нагреть до 100°, то он обуглится» будет высказывание «Неверно, что если деревянный брус нагреть до 100°, то он обуглится», по смыслу соответствующее высказыванию «Деревянный брус нагрели до 100°, но он не обуглился». Значит, отрицание импликации равнозначно конъюнкции основания с отрицанием следствия, что можно выразить в символической форме:

( p → q) ↔ p ^ q

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

«Утром на газонах трава не мокрая, но ночью шел дождь». Значит, отрицание репликации равнозначно конъюнкции отрицания основания со следствием, что можно выразить формулой:

( p → q) ↔ p ^ q

Отрицание эквиваленции. Подвергнув отрицанию высказывание «Человек не может работать тогда и только тогда, когда он больной», получим высказывание «Неверно, что человек не может работать тогда и только тогда, когда он больной», смысл которого соответствует языковой конструкции «Или человек не может работать, хотя он и не больной, или он может работать, хотя и больной», что можно выразить следующим тождеством:

(p↔ q) ↔ (p ^ q) ^ (p ^ q)

Непосредственное отрицание эквиваленции равнозначно строгой дизъюнкции «Или человек может работать, или он больной»:

(p↔ q) ↔ p v q

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p q л и

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

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

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

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

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

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

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

((p → q)	^	( p → r))	→	q → r
Л И Л	И	И И И	И	И И И
Л И И	И	И И И	И	Л И И
Л И Л	Л	И Л Л	И	И Л Л
Л И И	Л	И Л Л	И	Л И Л
И Л Л	Л	Л И И	И	И И И
И И И	Л	Л И И	И	Л И И
И Л Л	Л	Л И Л	И	И Л Л
И И И	Л	Л И Л	И	Л И Л

Формула является тождественно-истинной. Рассуждение верное.

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

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

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

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

{ F } |– F.

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

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

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

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

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

T1 ... Tk

S

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

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

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