Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 33

GATE

Рассмотрим следующую формулу a и две ее интерпретации I1 и I2

Какие из следующих утверждений верно?
(A) I1 удовлетворяет α, I2 не удовлетворяет
(B) I2 удовлетворяет α, I1 не удовлетворяет
(C) Ни I2, ни I2 не удовлетворяют α
(D) И I1, и I2 удовлетворяют α

Ответ: (D)
Пояснение: Прежде всего, обратите внимание, что в α ¬Qyy всегда ложно, потому что каждое число делится. Кроме того, не самая правая формула (∀x) [¬Px] всегда ложна, потому что, очевидно, дело не в том, что каждое число не является простым числом (в случае I1), а также в том, что каждое число не является составной номер (в случае I2). Также обратите внимание, что переменная x в этом выражении отличается от переменной x в левостороннем выражении, они независимы. Фактически, мы можем переписать α как α: (∀x) [Px⇔ (∀y) [Qxy⇔¬Qyy]] ⇒ (∀z) [¬Pz].
Давайте сначала рассмотрим I1. Итак, давайте присвоим некоторое значение x и посмотрим, удовлетворяет ли оно α. Мы можем разделить присваивания x на 3 части: когда x простое, когда x составное, когда x равно 1.

  • Когда x простое: Px истинно, Qxy также ложно для всех y, кроме 1, потому что только 1 делит x. Таким образом, формула Qxy⇔¬Qyy верна для всех y, кроме 1, но из-за ∀y вне этого вся формула ∀y [Qxy⇔¬Qyy] становится ложной, потому что это было бы верно, если бы Qxy⇔¬Qyy было истинно для каждого у.
    Так что теперь [Px⇔ (∀y) [Qxy⇔¬Qyy]] становится ложным для всех x всякий раз, когда x простое.
    Поскольку для некоторого x (где x простое), [Px⇔ (∀y) [Qxy⇔¬Qyy]] ложно, поэтому (∀x) [Px⇔ (∀y) [Qxy⇔¬Qyy]] определенно ложно , поскольку false⇒ false — это правда, поэтому α истинно в I1, и нам не нужны другие случаи x.
  • Теперь рассмотрим I2. Здесь также мы можем рассуждать так же, как мы это делали в случаях I1, здесь случай, когда x является составным, приводит к false⇒false, и поэтому α также верно в I2, поэтому опция (D) верна .

Источник: http://www.cse.iitd.ernet.in/~mittal/gate/gate_math_2003.html.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 33

0.00 (0%) 0 votes