КАДР
Глава 5. Исчисление высказываний и исчисление предикатов
В исчислении высказываний мы встречаемся с известными нам ранее объектами, а именно с формулами алгебры логики. Однако теперь формулы рассматриваются не как способ представления булевых функций, а как составные высказывания, образованные из элементарных высказываний. С помощью формул исчисления высказываний представляются знания о некоторой предметной области (логический способ представления знаний). На основании такого описания из имеющихся знаний формальным путем получаются новые знания. Исчисление предикатов обладает более богатыми возможностями для представления знаний, однако получение новых знаний в рамках исчисления предикатов требует больших вычислительных затрат.
Пусть
D
= {
}
– множество функций из
.
Базис
индукции.
Каждое выражение
где
,
называется формулой над D.
Индуктивный
переход.
Пусть
и
– выражения, являющиеся либо формулами
над D,
либо символами переменных. Тогда
выражение
– формула над D.
5.1. Исчисление высказываний
5.1.1. Словарь исчисления высказываний
Словарь состоит из следующих объектов:
1) бесконечного счетного множества высказываний, каждое из которых обозначается строчными буквами латинского алфавита, возможно снабженными индексами, и
2) логических связок.
Высказывания представляют собой предложения, которые могут быть истинными или ложными.
Перечислим логические связки.
1. Отрицание – унарная связка, обозначаемая как ¬, – , ~, not, не.
2. Конъюнкция – бинарная связка, обозначаемая как , &, and, и.
3. Дизъюнкция – бинарная связка, обозначаемая как , or, или.
4. Импликация – бинарная связка, обозначаемая как , , , ~.
5. Эквивалентность – бинарная связка, обозначаемая как , , , ~.
КАДР
5.1.2. Синтаксис исчисления высказываний
Словарь исчисления высказываний позволяет получать сложные (составные) высказывания из простых (элементарных). Сложные высказывания называют формулами.
Определение формулы.
1. Всякое высказывание (элементарное) является формулой.
2. Если А и В – формулы, то
¬ А, (А В), (А В), (А В), (А В) – формулы.
Скобки используются для определения порядка, в котором применяются правила построения формул. Логические формулы, как и арифметические, имеют древовидную структуру.
Если при построении формулы А формула В используется как элемент в правиле 2, то формула В является подформулой формулы А.
Множество формул является множеством всех слов в исчислении высказываний. Для удобства в формулах могут использоваться квадратные и фигурные скобки.
5.1.3. Семантика исчисления высказываний
Высказывания могут быть либо истинными (и), либо ложными (л). Семантическая область исчисления высказываний представляется множеством {и, л}.
Интерпретировать формулу – значит приписать ей одно из двух значений истинности: и или л. Значение истинности формулы определяется ее структурой и значениями истинности составляющих формулу (элементарных) высказываний. Значения истинности элементарных высказываний задаются при описании ими предметной области.
Связки исчисления высказываний есть известные элементарные булевы функции. Таблицы этих функций есть семантика связок.
Под интерпретацией i будем понимать приписывание значений истинности всем элементарным высказываниям формулы. Задав интерпретацию i, по таблицам истинности найдем интерпретацию I формулы, то есть ее значение истинности.
Интерпретация, при которой значение формулы есть истина (и), называется моделью формулы.
Литера – это элементарное высказывание или его отрицание. Литеры p и ¬ p противоположны.
КАДР