Привести к предварительной нормальной форме

@auri · Регистрация: 02.07.2020

Author24 — интернет-сервис помощи студентам

Добрый вечер, мне нужно привести ∀yQ(x, y) → R(x, x) к предварительной нормальной форме.
У меня получилось:
∀yQ(x, y) → R(x, x) = ¬(∀yQ(x, y)) ∨ R(x, x) = ∀y¬Q(x, y) ∨ R(x, x)
а что делать дальше я не знаю, пример не зачитывают. В первом предикате переменная x связана с квантором, а во втором предикате x - свободная переменная и нужно произвести замену.
Можете подсказать закон преобразования по которому это можно сделать?
Заранее спасибо.

@kabenyuk · 02.07.2020, 15:16

Сообщение от auri

пример не зачитывают

Я бы тоже не зачел. Здесь можно так, например:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\small\forall y Q(x,y)\rightarrow R(x,x)\equiv\forall y Q(x,y)\rightarrow \exists yR(x,x)\equiv\exists y(Q(x,y)\rightarrow R(x,x))$

@auri · 02.07.2020, 15:57 **[ТС]**

Предикат R не содержит переменную y, поэтому его можно внести под знак квантора. Спасибо, теперь все поняла (:

@3D Homer · 03.07.2020, 18:35

Сообщение от auri

∀yQ(x, y) → R(x, x) = ¬(∀yQ(x, y)) ∨ R(x, x) = ∀y¬Q(x, y) ∨ R(x, x)

Здесь неправильно второе равенство: при проносе отрицания ∀ нужно заменить на ∃. Дальше ∃ можно свободно выносить в начало формулы, так как переменная y не входит свободно в правый член дизъюнкции.

Равносильности, которые можно использовать при приведении формулы к ПНФ, находятся на с. 76-77 в книге: Герасимов А.С. Курс математической логики и теории вычислимости. Спб.: Лема, 2011.

@auri 0 / 0 / 0 Регистрация: 02.07.2020 Сообщений: 4
		1
	Привести к предварительной нормальной форме 02.07.2020, 15:00. Показов 1182. Ответов 3 Метки логика, предикат (Все метки) Добрый вечер, мне нужно привести ∀yQ(x, y) → R(x, x) к предварительной нормальной форме. У меня получилось: ∀yQ(x, y) → R(x, x) = ¬(∀yQ(x, y)) ∨ R(x, x) = ∀y¬Q(x, y) ∨ R(x, x) а что делать дальше я не знаю, пример не зачитывают. В первом предикате переменная x связана с квантором, а во втором предикате x - свободная переменная и нужно произвести замену. Можете подсказать закон преобразования по которому это можно сделать? Заранее спасибо. 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	02.07.2020, 15:16	2
	Сообщение от auri пример не зачитывают Я бы тоже не зачел. Здесь можно так, например: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\small\forall y Q(x,y)\rightarrow R(x,x)\equiv\forall y Q(x,y)\rightarrow \exists yR(x,x)\equiv\exists y(Q(x,y)\rightarrow R(x,x))$ 0

@auri 0 / 0 / 0 Регистрация: 02.07.2020 Сообщений: 4
	02.07.2020, 15:57 [ТС]	3
	Предикат R не содержит переменную y, поэтому его можно внести под знак квантора. Спасибо, теперь все поняла (: 0

@3D Homer $Эксперт по математике/физике$ 4945 / 3564 / 1149 Регистрация: 01.09.2014 Сообщений: 9,647
	03.07.2020, 18:35	4
	Сообщение от auri ∀yQ(x, y) → R(x, x) = ¬(∀yQ(x, y)) ∨ R(x, x) = ∀y¬Q(x, y) ∨ R(x, x) Здесь неправильно второе равенство: при проносе отрицания ∀ нужно заменить на ∃. Дальше ∃ можно свободно выносить в начало формулы, так как переменная y не входит свободно в правый член дизъюнкции. Равносильности, которые можно использовать при приведении формулы к ПНФ, находятся на с. 76-77 в книге: Герасимов А.С. Курс математической логики и теории вычислимости. Спб.: Лема, 2011. 0

Опции темы