Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 20

Какая из следующих формул первого порядка логически верна? Здесь α (x) — формула первого порядка с x в качестве свободной переменной, а β — формула первого порядка без свободной переменной.
(A) [β → (∃x, α (x))] → [∀x, β → α (x)]
(B) [∃x, β → α (x)] → [β → (∀x, α (x))]
(C) [(∃x, α (x)) → β] → [∀x, α (x) → β]
(D) [(∀x, α (x)) → β] → [∀x, α (x) → β]

Ответ: (с)
Объяснение:

Формула является логически действительной (или просто действительной), если она верна в каждой интерпретации. Эти формулы играют роль, сходную с тавтологией в логике высказываний. Формула является действительной, если ни один экземпляр не является ложным. Итак, достаточно привести любой пример, который дает ложное и доказать, что наша формула не верна

Выбор этого вопроса:
вариант (а)
[β → (∃x, α (x))] → [∀x, β → α (x)]
LHS: если β истинно, то существует x, для которого α (x) истинно.
RHS: для всех x, если β истинно, тогда α (x) истинно. Это то же самое, что сказать, что если β истинно, то для всех x α (x) верно. (β⟹∀x, α (х))

Так,
RHS⟹LHS и LHS⟹̸ RHS.

Вариант (б)
[∃x, β → α (x)] → [β → (∀x, α (x))]
LHS: существует такое x, что если β истинно, то α (x) истинно.
RHS: если β верно, то для всех x, α (x) верно.

Итак, RHS⟹LHS и LHS⟹̸ RHS.

Вариант (с)
[(∃x, α (x)) → β] → [∀x, α (x) → β]
LHS: если существует такой x, что α (x) истинен, то β истинен.
RHS: для всех x, если α (x) истинно, тогда β истинно.

Здесь и LHS, и RHS одинаковы, потому что β — это формула без свободной переменной, которая не зависит от x. (если β верно для одного x, это верно для каждого x и наоборот).

Итак, RHS⟹LHS и LHS⟹RHS.

Вариант (г)
[(∀x, α (х)) → & beta ; ] → [∀x, α (х) → & beta ; ]
RHS: для каждого x, если α (x) истинно, тогда β истинно.

Итак, RHS⟹LHS и LHS⟹̸ RHS
Таким образом, вариант с является правильным. потому что для варианта c LHS и RHS эквивалентны, даже если подразумевается обратное, оно остается в силе.

Это решение предоставлено Nitika Bansal .
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2008 | Вопрос 20

0.00 (0%) 0 votes