Тавтологии алгебры логики

и исходная формула превратятся в конкретное высказывание.

Превращение формулы логики предикатов в высказывание

описанным выше способом называется интерпретацией

формулы этой формулы на множестве M.

Пример 1 интерпретации формулы логики предикатов

Дадим интерпретацию формуле (x)(y)(P(x, у)).

Пусть M  множество всех мужчин, а вместо предикатной

переменной Р(х, у) подставим конкретный предикат на М:

«х есть отец у».

Исходная формула превратится в следующее ( ложное)

высказывание (x)(y)(х есть отец у) — «у каждого мужчины

есть сын».

Формулы, в которых нет свободных предметных переменных,

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

предметные переменные, — открытыми.

Данная формула  замкнутая.

Пример 2 интерпретации формулы логики предикатов

Дадим интерпретацию открытой формуле

(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, она превращается в выполнимый предикат.

Формула логики предикатов называется тождественно истинной