Проблема повноти, несуперечності, розв'язності числення висловлювань. Незалежність аксіом числення висловлювань.

Полнота исчисления высказываний

Теорема 1. Всякая выводимая в исчисления высказываний (ИВ) формула является тождественно истинная (тавтология) алгебры высказываний.

Если |- F, то |= F (|= - тожд. истинная).

Док-во. Пусть формула F выводима. Следовательно существует последовательность формул (В ₁, В ₂,…, В _п = F).

? F – тавтология??

1.n=1 Все аксиомы являются тавтологиями

2.S<= n (Все формулы с длиной s<=n являются тавтологией)

3.S= n+1 (В ₁, В ₂,…, В _п, В _п+1)

В _п+1 – может быть аксиомой, либо получена из 2 предшествующих формул (В _i; В _j) по MP

В _j =В _i -> В _п+1

Теорема 2. Всякая тождественно истинная формула алгебры высказываний выводима в исчислении высказываний.

Если |= F, то |- F.

Теорема (о полноте ИВ) Формула исчисления высказываний выводима в ИВ (является теоремой ИВ) тогда и только тогда,, когда она является тавтологией алгебры высказываний.

Непротиворечивость ИВ

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

Теорема. ИВ непротиворечивая теория.

Следует из теоремы о полноте. Формулы A и ØA одновременно не могут быть выводимыми.

Разрешимость ИВ

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

Теорема. ИВ есть разрешимая теория.

Независимость аксиом ИВ

Аксиома А системы аксиом ∑ наз. Независящей от остальных аксиом этой системы, если её нельзя вывести из остальных аксиом этой системы (∑\{А}).

№3. Алфавіт мови логіки предикатів. Визначення терма, формули мови першого порядку. Вільні та зв'язані входження змінних. Терм, вільний для змінної у формулі.

n-местным предикатом, определенным на множествах , ,…, , называется предложение, содержащее n переменных , ,…, и превращающееся в высказывание при подстановке вместо этих переменных конкретных высказываний из множеств , ,…, соответственно.

Множеством истинности предиката , заданного на множествах , ,…, , называется совокупность всех упорядоченных n систем таких, что при их подстановке предикат превращается в истинное высказывание .

Два предиката P и Q являются равносильными, если их множества истинности совпадают.

 

Алфавит языка теории первого порядка состоит из:

1. Предметные константы , , ,…, ,…

2. Предметные переменные , , , …, ,…

3. Функциональные символы (буквы из середины алфавита) , , ,…, , …

4. Предикатные символы , , ,…, , …

5. Символы логических операций , , , , , ,

6. Вспомогательные символы (),

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

Основными конструкциями языка первого порядка являются термы и формулы.

 

Индуктивное определение терма:

1.Каждая переменная есть терм.

2.Каждая константа есть терм.

3.Если - это k-местный функциональный символ, а - термы, то - терм.

(Правило порождения терма)

 

Элементарной (атомарной) формулой называется выражение , где - термы, а - n-местный предикатный символ.

 

Индуктивное определение формулы языка первого порядка:

1. Каждая элементарная формула есть формула.

2. Если - формула языка первого порядка, то - также формула.

3. Если , - формулы, то , , , - формулы.

4. Если - формула, а - переменная, то выражения , - также формулы.

5. Любое вхождение переменной в формулу или называется связанным вхождением переменной , а предметная переменная называется связанной.

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

6. Предметная переменная (вхождение предметной переменной) называется свободной (свободным вхождением), если она (оно) не находится в области действия квантора по этой переменной.

7. Формула, не содержащая свободных переменных, называется замкнутой.

(подчеркнуто свободное вхождение)

Терм свободен для переменной в формуле , если никакое свободное вхождение переменной в формулу не находится в области действия кванторов по переменным, входящим в терм .

- свободен

- не свободен