5.1.4. Исчисление высказываний и естественный язык
Связки естественного языка не, и, или, если – то на первый взгляд однозначно описываются функциями истинности.
“Хорошая погода или идет дождь”. “Идет дождь или хорошая погода”. Эти фразы воспринимаются как синонимы.
“Ему стало страшно, и он убил чужака”, “Он убил чужака, и ему стало страшно”. Эти две фразы не воспринимаются как синонимы, поскольку связка “и” подчеркивает временной и причинный аспекты.
Логическая дизъюнкция является неразделительной. Она истинна, если истинным является хотя бы один из двух аргументов. В естественном языке или может быть исключающей. “Целое число четно или не четно”. Здесь одна ветвь альтернативы истинна, а другая – ложна.
Связки, изложенные выше, можно обобщить на n-арные. В исчислении высказываний важную роль играет полная система связок {¬, }. Через функции этой системы можно выразить связки: , , . Действительно,
p q = ¬ p q,
p q = ¬(p ¬ q),
p q = (p q) (q p).
Будем считать, что и, л являются связками, зависящими от пустого множества аргументов.
5.1.5. Выполнимость и общезначимость формулы
Формула А выполнима, если существует интерпретация i, на которой А принимает значение и.
Формула не выполнима, если не существует интерпретации, на которой она принимает значение и.
Формула общезначима, если она принимает значение и на любой интерпретации i.
Формула, которая не является ни общезначимой, ни невыполнимой, называется нейтральной.
Общезначимые формулы в исчислении высказываний называют тавтологиями.
Если А – формула, то выражение |= А означает, что А есть тавтология.
Пусть Е – множество формул, выражение Е |= А означает, что при всякой интерпретации i, на которой истинны все формулы из Е, формула А также истинна. А называется логическим следствием из Е.
Тавтология – логическое следствие из пустого множества формул.
Пусть В – формула, В |= А, то есть А – логическое следствие из В.
В |= А тогда и только тогда, когда B A есть тавтология или формально:
B |= A |= (B A).
Пусть
,…,
– гипотезы, описывающие некоторую
предметную область, а С
– заключение, которое из них выводится,
тогда имеем
{ ,…, ) |= C |= ( ,…, ) C. (1)
5.1.6. Проблема выводимости
Фундаментальная проблема математической логики – проблема дедукции состоит в следующем: определить, является ли формула С логическим следствием формул множества Е. Мы свели ее в исчислении высказываний к выявлению условий общезначимости формулы исчисления высказываний. Инверсией общезначимой формулы является невыполнимая формула. Следовательно,
{ ,…, } |= C ( ,…, , C) |= л. (2)
В исчислении высказываний принято решать проблему выводимости формулы С, используя соотношение (2).
Если А и В – логические следствия друг друга, то они логически эквивалентны, то есть А В.
Одним из средств порождения тавтологий является подстановка. Если В – тавтология, p – элементарное высказывание, А – некоторая формула исчисления высказываний, то выражение, полученное заменой всех вхождений p на А, является тавтологией.