Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы

Разрешимость формальной с-мы:

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

Интерпретация формальной системы:

Интерпретация представляет собой распространение исходных положений формальной системы на реальный мир. При интерпретации теоремы формальной системы становится обычными утверждениями о котором можно истины они или ложны.

Исчисление высказываний как формальная система. Правила вывода. Язык и интерпретация исчисления высказываний. Общезначимость, выполнимость, следование. Полнота и непротиворечивость исчисления высказываний.

Исчисление высказываний:

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

Позволяет выводить все общезначимые формулы из аксиом, не рассматривая их интерпретации.

Интерпретация языка высказываний:

Правила вывода см. вопрос 11.

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

Доказательство общезначимости:

Семантические методы:

Связь между алгеброй логики и исчислением высказываний:

Формулы исчисления высказываний можно интерпретировать как формулы алгебры логики.

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

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

Понятие предиката. Область определения и множество истинности предикатов. Интерпретация исчисления предикатов и значение формул логики предикатов. Общезначимость и выполнимость формул логики предикатов. Чистая и прикладная логика предикатов.

Предика́т (n -местный, или n -арный) — это функция с множеством значений (или «ложь» и «истина»), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».

Предикат называют тождественно-истинным и пишут:

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.

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

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I_P для него есть множество всех простых чисел.

Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является