Тождественные преобразования исчисления предикатов

Замкнутые и открытые формулы

Формулы исчисления предикатов

Определение терма

Кванторы исчисления предикатов

Алфавит исчисления предикатов

Определение формальной теории PL

В исчислении предикатов первого порядка (формальной теории PL) как и в любой формальной теории необходимо определить:

· алфавит;

· формулы;

· аксиомы;

· правила вывода.

Алфавит – система множеств А = áР, Х, F, W ñ, где

Р = { Q,R,S,T …} множество предикатных букв, обозначающих предикаты;

Х = { x, y, z,…,a, b, c,… } – множество предметных переменных и предметных констант;

F = { f, j, g, y } – множество функциональных букв;

W = {Ú, Ù, É, ~, ", $} – множество операций.

" квантор общности обозначает «для каждого» или «для всех».

Записывается:

(" х Î М) (R (x) = 1 – для всякого х из множества М имеем R (x) истина.

Сокращенно: " х R (x).

Пример: " х ((x + 1)² = x² + 2 х + 1).

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

Записывается:

($ х Î М) (R (x) = 1 – существует х из множества М, для которого имеем R (x) истина.

Сокращенно: $ х R (x).

Пример: " х ((x + 1)² = 4). Истина для х = 1 и х = – 3.

Выражение, определяющее утверждение R (x), называется областью действия квантора.

В исчислении предикатов первого порядка квантор применяется к предметным выражениям.

1. Всякая предметная переменная или константа есть терм (термин).

2. Если f – функциональная буква, а h₁, h₂, …, h_n – термы, то

f (h₁, h₂, …, h_n) тоже терм.

3. Других термов нет.

Определение: Если Р – предикатная буква и Q₁, Q₂, …, Q_n – термы, то Р (Q₁, Q₂, …, Q_n) называется элементарной формулой.

Определение:

1. Всякая элементарная формула – есть формула.

2. Если А и В формулы, то формулой является А · В, где

· Î {Ú, Ù, É, ~} – операция исчисления предикатов.

3. Если А – формула, то ù А – тоже формула.

4. Если х – предметная переменная, а Р – предикатная буква, то

" х Р (x) и $ х Р (x) тоже формулы – кванторные выражения.

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

Определение: всякая формула без свободных переменных называется замкнутой, в противном случае – открытой.

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

Законы исчисления предикатов определяют эквивалентные преобразования над формулами. Формулы называются эквивалентными, если в любой предметной области их таблицы истинности совпадают.

· В исчислении предикатов выполняются все законы исчисления высказываний.

· В исчислении предикатов существуют 4 дополнительных группы тождеств.

Дата добавления: 2014-01-06