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

Определение 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; просмотров: 905;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.