Общезначимые формулы

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

Естественно, что все формулы, являющиеся тавтологиями в логике высказываний, общезначимые, если высказывания заменить предикатами:

Пример. Мы имели р 1 (1)

Рассмотрим предикат P (x₁, x₂, …, x_n). Тогда

. P (x₁, x₂, …, x_n)(x₁, x₂, …, x_n) (2)

─ формула общезначимая.

Доказательство:

Зададим набор значений x₁⁰, x ₂⁰, …, x _n ⁰ , тогда.

Р (x₁⁰, x ₂⁰, …, x _n ⁰). (3) является высказыванием. В силу равенства (1) формула (3) – тавтология. А в силу произвольности набора, формула (2) – общезначимая.

Теорема. Если , то 1 и, наоборот. То есть: для того чтобы 1, необходимо и достаточно, чтобы формулы и были равносильными.

Доказательство:

Необходимость:

Пусть . Это означает, что формулы и принимают одинаковые значения при любых одинаковых наборах предметных переменных и высказываний, входящих в эти формулы. А это означает, что .

Достаточность:

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

Что и требовалось доказать.

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