Основные понятия и определения дисциплины

Модальная логика — логика в которой кроме стандартных логических связок, переменных и/или предикатов есть модальности (модальные операторы). Модальности бывают разные; наиболее распространены временны́е («когда-то в будущем», «всегда в прошлом», «всегда» и т. д.) и пространственные («здесь», «где-то», «близко» и т. д.). Например, модальная логика способна оперировать утверждениями типа «Москва всегда была столицей России» или «Санкт-Петербург, когда-то в прошлом, был столицей России», которые невозможно или крайне сложно выразить в немодальном языке. Кроме временных и пространственных модальностей есть и другие, например «известно, что» (логика знания) или «можно доказать, что» (логика доказуемости).Обычно для обозначения модального оператора используется и двойственный к нему :

22. 
    Примеры задач NP-класса.
    

Задача о выполнимости.
Пусть х₁, х₂, …, х_n – множество логических переменных; – их отрицания или дополнения.
if x_i = true then = false
 - И;  - ИЛИ.
Дизъюнкция: х₁  х₅  …
Конъюнкция: х₄  х₃  …
Конъюнктивная нормальная форма:
E^*(x₁, …, x_n) = (x₁  x₂  x₃)  (x₁   )  (  x₄)  ( ) (*)
Задача о выполнимости заключается в определении, является ли булевская функция, записанная в КНФ, выполнимой.
Любая булевская функция может быть представлена в КНФ по правилу Де Моргана:

А(ВС)=( АВ)(АС)
Говорят, что булевская функция выполнима, если существует некоторое присваивание переменным true или false, при этом функция должна быть равна true.
Для функции (*) она будет выполнима, если ввести следующие присваивания:
(*)
Например:
Функция
f₂(x_i)=(x₁  x₂)( )( )

не является выполнимой, т. к. при любых x_i f₂(x_i)=false.

Теорема:
Задача о выполнимости является NP-полной.
for i=1 to N do
x_i  выбор (true, false)
if E(x₁, x₂, …, x_N) then успех
else неудача
Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.