Аксиоматическая теория L исчисления высказываний

Лекция 3

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

Истинностная функция = Истинностная таблица!

Логически эквивалентные формы порождают одну и ту же истинностную функцию (Доказали?)

Всякая истинностная функция порождается некоторой пропозициональной формой, содержащей лишь связки (доказали и научились строить ДНФ!).

Как строить КНФ? Пример:

х1	х2	f(x1,x2)	ДНФ	КНФ
и	и	л
л	и	и
и	л	л
л	л	и

Для порождения истинностной функции f достаточно любой пары пропозициональных связок из следующих: , или одиночных связок

{Конъюнкция отрицаний }, {Штрих Шеффера }

Определение: Пусть пропозициональная форма содержит лишь связки . Тогда называется двойственной к , если получается из заменой на &, а & на .

Утверждения:

У1). ;

У2). ;

У3). Если , то – закон двойственности.

Первое утверждение очевидно. Из второго утверждения легко получить третье. Действительно, если двойственная пропозициональная форма выражается через исходную формулу, то эквивалентные пропозициональные формы при навешивании на них отрицания и при подстановке вместо аргументов аргументы с навешенными на них отрицаниями остаются эквивалентными.

Если формула представляет собой ДНФ, то двойственная к ней – КНФ, но какой-то другой формулы. Поэтому для получения КНФ формулы можно построить двойственную формулу для КНФ от двойственной к

Теорема 1: Для того, чтобы формула была тождественно истинной необходимо и достаточно, чтобы каждая элементарная сумма ее конъюнктивной нормальной формы содержала по крайней мере два слагаемых, одно из которых является отрицанием другого.

Теорема 2: Для того, чтобы формула была тождественно ложной необходимо и достаточно, чтобы каждое элементарное произведение ее дизъюнктивной нормальной формы содержало по крайней мере два сомножителя, одно из которых является отрицанием другого.

Определение: Формула называется выполнимой, если существует набор значений, входящих в нее переменных, при которых она принимает значение «истина» (то есть формула не является тождественно ложной).

Вопрос. Как убедиться, что данная формула является выполнимой? (разрешимость свойства «быть выполнимой» по отношению к формуле)

Способ 1. – построить истинностную таблицу и проверить.

Способ 2 – по теореме 2 убедиться, что формула не является тождественно ложной.

Формальная аксиоматическая теория (исчисление)

Формальная (аксиоматическая) теория считается определенной, если:

(1). Задано не более чем счетное множество символов (алфавит). Конечные цепочки символов – выражения (слова) теории .

(2). Выделено подмножество выражений (слов) теории , называемых формулами .

(3). Выделено некоторое подмножество формул , называемых аксиомами теории .

(4). Задано конечное множество R₁,..., R_n отношений между формулами, называемых правилами вывода.

Если выполнены пункты (1). И (2)., то задан формальный язык.

Если определены все 4 пункта, то задано исчисление.

Определения.

· Правила вывода позволяет установить «непосредственное следование» некой формулы из конечного (определенного каким-либо правилом вывода) набора указанных формул.

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

· Формула называется теоремой теории , если существует вывод в , в котором является последней формулой цепочки.

· Теория называется эффективно аксиоматизированной, если существует процедура, указывающая, является ли данная формула аксиомой (разрешимость свойства «быть аксиомой» для формулы).

· Теория называется разрешимой, если для любой формулы существует алгоритм, определяющий, является ли формула теоремой теории .

· Формула называется следствием множества формул Г в (обозначается ) если существует последовательность формул , что есть , и каждая формула этой последовательности либо есть аксиома, либо элемент Г, либо является непосредственным следствием некоторых предыдущих формул по одному из правил вывода.