Формулы логики предикатов

одно из важнейших ее понятий и инструментов 

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

yi, zi …(iN).
2. Нульместные предикатные формулы: P, Q, Pi, Qi

…(iN).
3. Nместные предикатные переменные P(x,…), Q(y,…).
4. Символы логических операций: , , , ↔, —.
5. Кванторы: , .
6. Вспомогательные символы: скобки - ( , ), запятая - , .

Каждая nместная предикатная переменная P(x1,…,xn) есть
формула, в которой

все предметные переменные свободны.
3. Если F  формула, и x  свободная предметная переменная,
то (x)(F), ( x)(F)  формулы, в которых переменная x 
связанная, а остальные свободные (если нет других кванторов).
4. Если F, F1, F2  формулы, то
 тоже формулы, причем предметные переменные, свободные
(или связанные) в одной из формул F, F1, F2, такие же и в новых
формулах.
5. Других формул нет.

формулу логики предикатов вместо каждой
предикатной

переменной подставить конкретный предикат,
определенный на некотором выбранном множестве М, то
формула превратится в конкретный предикат, заданный над
множеством М.
Если подставить вместо свободных предметных переменных
конкретные предметы из множества М, то полученный предикат
и исходная формула превратятся в конкретное высказывание.
Превращение формулы логики предикатов в высказывание
описанным выше способом называется интерпретацией
формулы этой формулы на множестве M.

(x)(y)(P(x, у)).
Пусть M  множество всех мужчин, а

вместо предикатной
переменной Р(х, у) подставим конкретный предикат на М:
«х есть отец у».
Исходная формула превратится в следующее ( ложное)
высказывание (x)(y)(х есть отец у) — «у каждого мужчины
есть сын».
Формулы, в которых нет свободных предметных переменных,
называются замкнутыми, а формулы, содержащие свободные
предметные переменные, — открытыми.
Данная формула  замкнутая.

открытой формуле
(z)(P(x, у, z) Q(x, у,

z))  R.
Пусть множество М  множество N всех натуральных чисел.
Вместо предикатных переменных Р(х, у, z) и Q(x, у, z)
подставим трехместные предикаты «х∙у = z» и «х + у = z»,
вместо нульместного предиката R подставим (ложное)
высказывание «2 =5».
Формула превратится в двухместный предикат (от переменных
х, у): (z)(x ∙ y = z  х+ y = z)  (2 = 5).
Так как одноместный предикат от z: (m ∙ n = z  m+ n = z)
выполним, то двухместный предикат (z)(x ∙ y = z  х+ y = z)
при интерпретации превращается в истинное высказывание,
поэтому исходная формула превращается в ТЛ предикат на N.

множестве М, если при некоторой подстановке вместо

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

Формула логики предикатов называется тождественно истинной
(тождественно ложной) на множестве М, если при всякой
подстановке вместо предикатных переменных любых
конкретных предикатов, заданных на этом множестве, она
превращается в ТИ (ТЛ) предикат.

или тавтологией ( противоречием), если при всякой

подстановке вместо предикатных переменных любых
конкретных предикатов, заданных на любых множествах,
она превращается в ТИ (соответственно ТЛ) предикат.
Пример. Формула является противоречием,
т. е. тождественно ложной.
От противного: пусть на некотором множестве М имеется
предикат A(х), такой, что эта формула превращается в
истинное высказывание при некотором aM:
Тогда A(a) ложно, а из истинности (y)A(y) следует, что A(a)
истинно. Противоречие. Следовательно данная формула  ТЛ.

из
тавтологий алгебры высказываний, и тавтологии алгебры
высказываний

образуют часть тавтологий логики предикатов.

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

де Моргана для кванторов). Следующие
формулы логики предикатов являются

тавтологиями

1.

2.

1.

.

2. .

Тавтологии 1 и 2 вытекают из теоремы 2 по закону
двойного отрицания.

формулы логики предикатов
являются тавтологиями:

.
2.
3.
4.

(законы удаления квантора общности и введения
квантора существования). Следующие

формулы логики
предикатов являются тавтологиями:
а) (х)(Р(х))  Р(у);
б) Р(у)  (х)(Р(х)).

Следующие формулы логики предикатов являются тавтологиями:

1. (x)(y)(P(x, у)) ↔ (y)(x)(P(x, у)).

2. (x)(y)(P(x, у)) ↔ ( y)(x)(P(x, у)).

взгляда на
тавтологии, выраженного в теоремах 1

— 5, можно
считать, что буквы Р и Q представляют собой
произвольные формулы логики предикатов, а не
просто n  местные предикатные переменные,
представляющие собой на основании определения
формул элементарные или атомарные формулы.
Получаемые формулы также будут тавтологиями
логики предикатов.

логики предикатов, нужно выполнить действия:
1. Определить множество M,

об элементах которого идет
речь в предложении.
2. Ввести предикаты соответствующей местности на M,
выражающие свойства элементов из M.
3. С помощью логических операций и кванторов записать
предложение на языке логики предикатов.

существуют, по крайней
мере, 4 точки, не принадлежащие одной плоскости.

Решение. Рассмотрим 2 множества: точек и плоскостей
пространства. Определим предикаты: T(x)  x  точка,
P(x)  x  плоскость, R(x,y)  x = y, L(x,y)  x  y. Символическая запись предложения: