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

Разрешимые и неразрешимые формулы

В общем случае может не существовать эффективной процедуры, с помощью которой можно определить по данной формуле, существует ли ее вывод в теории T.

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

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

Полнота. Имеют место следующие метатеоремы.

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

Теорема 2: Всякая тавтология является теоремой исчисления высказываний.

Таким образом, теоремами теории Тявляются тождественно истинные формулы и только они.

Формальная теория Т (исчисление высказываний) является полной теорией

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

Из теоремы 1 следует, что теория Тнепротиворечива.

Действительно, любая теорема в Тесть тождественно истинная

формула (тавтология). Ее отрицание не есть тавтология. Таким

образом в Тнет одновременной выводимости теоремы и ее

отрицания, что соответствует определению непротиворечивости

формальной теории.

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

Теория Тразрешима как формальная теория.

Алгоритм, который определяет для любой формулы теории,

является ли эта формула теоремой теории, может состоять в

вычислении истинностных значений формулы в каждой

интерпретации. Принципиально это выполнимо за конечное время в

силу конечности числа интерпретаций и числа операций,

присутствующих в формуле.

58.Предикат: n -местный (n= 0, n >0). Предикатные формулы. Связь между предикатами, отношениями и функциями. Модель в логике предикатов.

Предикат – повествовательное предложение, содержащее предметные переменные xi ÎMi, определенные на соответствующих множествах Mi

Например: P(x,y)=«Студент x на экзамене получил отметку y». Переменные x, y являются предметными и принадлежат следующим множествам x={Иванов, Петров, Сидоров}, y={2,3,4,5}.

При замене переменных конкретными значениями (элементами множеств) предикат обращается в высказывание т.е. принимает значение «истинно» или «ложно». Например: «Студент Иванов на экзамене получил отметку 5»

Предикатом P (x ₁, …, x_n) зависящим от n переменных называется функция P: M ₁ ´ M ₂ ´…´ M_n ® B, где xi ÎMi произвольным множествам, а B — двоичное множество.

M ₁, M ₂, …, M_n – предметные области предиката, x ₁, …, x_n – предметные переменные предиката.

Алфавит алгебры предикатов

m-местная предикатная переменная — выражения вида P(x₁..x_m), где x₁..x_m предметные переменные

Логические символы &, Ú, ®, ~, Ø, $ (квантор существования), " (квантор всеобщности);

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

0-местные предикатные переменные (пропозициональные переменные) - выражения вида P(а₁..а_m), где а₁..а_m предметные константы.

Элементарной формулой называется всякая пропозициональная переменная, а также любая m -местная предикатная переменная (m > 0).

Из элементарных формул строятся предикатные формулы:

Все элементарные формулы суть формулы;

Если А и В — формулы, то выражения (А & В), (А Ú В), (А ® В), (А ~ В), ØА считаются формулами;

если А — формула, x — предметная переменная, то " x А и $ x В суть формулы.

Предикат тождества E(x₁,x₂): N ² ® B: E (a ₁, a ₂) = 1 тогда и только тогда, когда a ₁ = a ₂, xi ÎN

Предикат порядка Q (x₁,x₂): N ² ® B: Q (a ₁, a ₂) = 1 тогда и только тогда, когда a ₁ £ a ₂, xi ÎN

Предикат делимости D (x₁,x₂): N ² ® B: D (a ₁, a ₂) = 1 тогда и только тогда, когда a ₁ делится на a ₂, xi ÎN

Предикат суммы S (x₁,x₂,x₃): N ³ ® B: S (a ₁, a ₂, a ₃) = 1 тогда и только тогда, когда a ₁ + a ₂ = a ₃, xi ÎN

Предикат произведения P (x₁,x₂,x₃): N ³ ® B: P (a ₁, a ₂, a ₃) = 1 тогда и только тогда, когда a ₁ * a ₂ = a ₃, xi ÎN

Для любых Мi, где i=1...n существует взаимнооднозначное соответствие между n –местным отношением R Í M ₁ ´ M ₂ ´…´ M_n и n –местным предикатом P: M ₁ ´ M ₂ ´…´ M_n ® B:

Каждому n –местному отношению R соответствует предикат P такой, что P (a ₁, …, a_n) = 1, если и только если (a ₁, …, a_n) Î R; При этом R задает область истинности предиката P.

Всякий предикат P (x ₁, …, x_n) определяет отношение R такое, что (a ₁, …, a_n) Î R, если и только если P (a ₁, …, a_n) = 1.

Пример: 2-местному предикату тождества Е:«х1=х2» взаимнооднозначно соответствует 2-месное отношение R1- «быть равным»: (а1,а2) Î R тогда и только тогда, когда Е(а1,а2)=1