В этом и следующем разделах мы работаем с булевыми функциями, которые используются в интерпретациях формул логики высказываний.
Определение 10 (Интерпретация). Символы л,и (``ложь'', ``истина'') называются истиностными значениями. Интерпретация пропозициональной сигнатуры s есть функция из s в {л,и}.
Если s конечна, тогда интерпретация может быть определена таблицей её значений, например:
| p | q | (3) | |
| л | и |
Семантика логики высказываний, которую мы собираемся ввести, определяет какие истиностные значения назначены формуле F интерпретацией I.
Прежде всего нам надо связать функцию с каждой пропозициональной связкой – функцию из {л,и} в {л,и} с унарной связкой и функцию из {л,и}ґ {л,и} в {л,и} с каждой бинарной связкой. Функции определяются следующими таблицами:
| x | (x) | x | y | &(x, y) | Ъ(x, y) | Й(x, y) | |
| л | л | л | л | и | |||
| л | и | л | и | л | и | и | |
| и | л | и | л | л | и | л | |
| и | и | и | и | и | |||
Для любой формулы F и любой интерпретации I истиностное значение FI , назначенное формуле F интерпретацией I, определяется как значение соответствующих булевых функций, а именно, следующим образом:
- FI = I(F) если F – атом,
- (F )I = (FI),
- (F Д G)I = Д(FI,GI) для каждой бинарной связки Д.
Заметим, что это определение рекурсивно: (F)I определяется через FI и (F Д G)I – через FI и GI.
Если FI = и, мы говорим, что формула F истинна при интерпретации I (символически I |= F ).
2.10 Найдите формулу F такую, что (3) – единственная интерпретация, при которой F истинна.
Если рассматриваемая сигнатура конечна, тогда множество интерпретаций тоже конечно, и значения FI для всех интерпретаций можно представить в виде конечной таблицы. Эта таблица называется таблицей истинности формулы F. Например, предыдущая задача может быть сформулирована следующим образом: найти формулу, таблицей истинности которой является
| p | q | |
| л | л | л |
| л | и | и |
| и | л | л |
| и | и | л |
2.11 Для любых формул F1,...,Fn (n і 1) и любой интерпретации I
(F1 & ··· & Fn)I = и тогда и только тогда, когда FI1 = ··· = FIn = и.
2.12 Сформулируйте и докажите подобный факт для дизъюнкции F1 Ъ ··· Ъ Fn.
В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура конечна: s = { p1, ..., pn}.
2.13 Для любой интерпретации I существует формула F такая, что I – единственная интерпретация, при которой F истинна.
2.14 Для любой функции a из интерпретаций в истинные значения существует формула F такая, что для всех интерпретаций I: FI = a(I).
Другими словами, любая таблица истинности может быть представлена пропозициональной формулой. В этом смысле множество пропозициональных связок, которое мы ввели ``полно''.
Нормальные формы
Определение 11 (Эквивалентность). Формула F эквивалентна формуле G, если FI = GI для любой интерпретации I.
В задачах 2.16, 2.18 и 2.20 мы вводим несколько ``нормальных форм'' таких, что любая пропозициональная формула может быть эквивалентно трансформирована в любую из этих форм.
Дата добавления: 2015-10-05; просмотров: 911;