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

правило подстановки: если a — выводимая формула, содержащая букву A (обозначив это как a(A)), то выводима формула a(b), получающаяся из a заменой всех вхождений A на произвольную формулу b

правило заключения (modus ponens): (если a ® b и a — выводимые формулы, то b также выводимая формула)

Выводимость формул

Если формулы F₁, …, F_n, G находятся в отношении R, то формула G называется непосредственно выводимой из F₁, …, F_n по правилу R. формулы F₁, …, F_n, называются посылками правила R, а G — его следствием или заключением.

Выводом в T формулы Gиз формул A₁, …, A_n, называется всякая последовательность F₁, F₂, ..., F_m формул такая, что F_m = G, а для любого i формула F_i есть либо аксиома теории T, либо одна из исходных формул A₁, …, A_n, либо выводима из формул F₁, …, F_i-1 по одному из правил вывода.

Если существует вывод Gиз A₁, …, A_n, то говорят, что G выводима из A₁, …, A_n т.е. является теоремой формальной теории Т. Этот факт обозначается A₁, …, A_n |— G.

Формулы A₁, …, A_n называются гипотезами или посылками вывода. Переход в выводе от F_i-1 к F_i называется i-м шагом вывода.

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

В общем случае может не существовать эффективной процедуры, с помощью которой можно определить по данной формуле, существует ли ее вывод в теории 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