Выразить на языке алгебры предикатов, используя S и П, утверждение x<0

@mmeexx · Регистрация: 09.10.2013

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

На множестве целых чисел Z определены предикаты П(x,y,z)=1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow$ x·y=z и S(x,y,z)=1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow$ x+y=z .Выразить на языке алгебры предикатов , используя S и П, утверждение x<0. Не получается у меня почему-то. Заранее спасибо!

@painzcupcake · 24.12.2015, 16:15

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

почему-то

Нам даны предикаты $https://www.cyberforum.ru/cgi-bin/latex.cgi?\pi (x, y, z) =1\,\Leftrightarrow \,x\cdot y = z$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta(x, y, z) =1\,\Leftrightarrow \,x+ y = z$

Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x)\, \Leftrightarrow \,x=0$ . Это легко:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x) \, \Leftrightarrow \, \forall y \, \pi(x, y, x)$

(произведение 0 с любым числом дает 0)
Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?E(x, y) \, \Leftrightarrow \, x = y$ следующим образом:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?E(x, y) \, \Leftrightarrow \, \exists x^{\prime} \exists z \, \theta(x, x^{\prime}, z) \wedge \theta(y, x^{\prime}, z) \wedge P_0(z)$

(грубо говоря, x = y, если существует число x', такое, что x + x' есть ноль и y + x' есть ноль)
Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?M (x) \, \Leftrightarrow \, x \geq 0$ . Воспользуемся теоремой Лагранжа о сумме четырех квадратов и скажем тогда, что

$https://www.cyberforum.ru/cgi-bin/latex.cgi?M (x) \, \Leftrightarrow \, \exists a \exists b \exists c \exists d \, \exists p_1 \exists p_2 \exists p_3 \exists p_4 \, \exists S_1 \exists S_2 \exists S \, :$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\pi(a, a, p_1) \wedge \pi(b, b, p_2) \wedge \pi(c, c, p_3) \wedge \pi(d, d, p_4) \wedge \theta(p_1, p_2, S_1) \wedge \theta(S_1, p_3, S_2) \wedge \theta(S_2, p_4, S) \wedge E(x, S)$

(это значит, что существуют 4 числа a, b, c, d, такие, что a² + b² + c² + d² = x; a, b, c, d, x - целые числа.
Тогда очевидно, искомый предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?L(x) \, \Leftrightarrow \, x < 0$ получается как

$https://www.cyberforum.ru/cgi-bin/latex.cgi?L(x) \, \Leftrightarrow \, \neg M(x)$

(x меньше 0, если он не больше нуля и не равен нулю)

Добавлено через 9 минут
ЗЫ. название темы очень плохое. ИМХО, лучше "Выразить предикат "x < 0" на множестве целых чисел

iifat · 24.12.2015, 16:46

(Восхищённо чеша затылок) Не, конструкция, несомненно, совершенно правильная, но привлекать такую мощную штуку как теорему о четырёх квадратах к определению положительности числа — перебор, как по мне.
В любом случае, как вариант: определяем $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x)$ предложенным способом, потом $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_1(x)$ аналогичным, а потом $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_+(x)\Leftrightarrow\exists y\forall z\forall t \theta(y,t,x)\wedge P_1(t)\wedge (P_0(y)\vee P_+(y))$ (Положительное число — число, которое получается прибавлением единицы к положительному числу либо нулю). Можно, впрочем, обойтись и без нуля: положительное число — это единица либо положительное плюс единица.

Добавлено через 1 минуту
Ах да, требовалось же определить отрицательные числа; впрочем, думаю, способ понятен.

@painzcupcake · 24.12.2015, 17:01

iifat, согласен, получилось... не самым простым способом %] Но у вас в каком-то смысле рекурсия - предикат выражается через самого себя, и "длина" формулы растет с ростом модуля x

iifat · 24.12.2015, 17:08

Не «в каком-то смысле», а вполне себе рекурсия, да. И, согласен, это — при прочих равных — недостаток. Но вы недооцениваете сложность простенького выражения «положительное число — число, которое можно представить в виде суммы четырёх квадратов»

@Mysterious Light · 25.12.2015, 10:59

И всё же, iifat, Ваше P₊ Вами не задано явно как формула логики предикатов. В отличие от решения с четырьмя квадратами, где можно подставить все формулы и получить одну длинющую формулу со свободной буквой x, эквивалентную x<0, в Вашем решении это сделать принципиально невозможно без введения комбинатора неподвижной точки или чего-то аналогичного, ибо рекурсия.

Иное дело, если бы к теории, содержащей сложение и умножение, нужно было бы добавить предикат x<0, тогда Ваше выражение можно было бы добавить к аксиомам и радоваться. Исходная задача, как я понял, не в этом состоит.

iifat · 25.12.2015, 17:18

Ну, не хочу спорить, поскольку определения сильно забыл. Как по мне, разница не больше, чем между явным и неявным заданием функции в матанализе: в принципе, с явным работать удобнее, однако ж неявность никого особо не смущает.

@mmeexx 0 / 0 / 3 Регистрация: 09.10.2013 Сообщений: 189
		1
	Выразить на языке алгебры предикатов, используя S и П, утверждение x<0 22.12.2015, 23:41. Показов 1918. Ответов 6 Метки нет (Все метки) На множестве целых чисел Z определены предикаты П(x,y,z)=1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow$ x·y=z и S(x,y,z)=1 $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow$ x+y=z .Выразить на языке алгебры предикатов , используя S и П, утверждение x<0. Не получается у меня почему-то. Заранее спасибо! 0

@painzcupcake 12 / 12 / 5 Регистрация: 11.07.2015 Сообщений: 46
	24.12.2015, 16:15	2
	Сообщение от mmeexx почему-то Нам даны предикаты $https://www.cyberforum.ru/cgi-bin/latex.cgi?\pi (x, y, z) =1\,\Leftrightarrow \,x\cdot y = z$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta(x, y, z) =1\,\Leftrightarrow \,x+ y = z$ Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x)\, \Leftrightarrow \,x=0$ . Это легко: $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x) \, \Leftrightarrow \, \forall y \, \pi(x, y, x)$ (произведение 0 с любым числом дает 0) Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?E(x, y) \, \Leftrightarrow \, x = y$ следующим образом: $https://www.cyberforum.ru/cgi-bin/latex.cgi?E(x, y) \, \Leftrightarrow \, \exists x^{\prime} \exists z \, \theta(x, x^{\prime}, z) \wedge \theta(y, x^{\prime}, z) \wedge P_0(z)$ (грубо говоря, x = y, если существует число x', такое, что x + x' есть ноль и y + x' есть ноль) Выразим предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?M (x) \, \Leftrightarrow \, x \geq 0$ . Воспользуемся теоремой Лагранжа о сумме четырех квадратов и скажем тогда, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?M (x) \, \Leftrightarrow \, \exists a \exists b \exists c \exists d \, \exists p_1 \exists p_2 \exists p_3 \exists p_4 \, \exists S_1 \exists S_2 \exists S \, :$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\pi(a, a, p_1) \wedge \pi(b, b, p_2) \wedge \pi(c, c, p_3) \wedge \pi(d, d, p_4) \wedge \theta(p_1, p_2, S_1) \wedge \theta(S_1, p_3, S_2) \wedge \theta(S_2, p_4, S) \wedge E(x, S)$ (это значит, что существуют 4 числа a, b, c, d, такие, что a² + b² + c² + d² = x; a, b, c, d, x - целые числа. Тогда очевидно, искомый предикат $https://www.cyberforum.ru/cgi-bin/latex.cgi?L(x) \, \Leftrightarrow \, x < 0$ получается как $https://www.cyberforum.ru/cgi-bin/latex.cgi?L(x) \, \Leftrightarrow \, \neg M(x)$ (x меньше 0, если он не больше нуля и не равен нулю) Добавлено через 9 минут ЗЫ. название темы очень плохое. ИМХО, лучше "Выразить предикат "x < 0" на множестве целых чисел 2

iifat 2717 / 1771 / 187 Регистрация: 05.06.2011 Сообщений: 5,129
	24.12.2015, 16:46	3
	(Восхищённо чеша затылок) Не, конструкция, несомненно, совершенно правильная, но привлекать такую мощную штуку как теорему о четырёх квадратах к определению положительности числа — перебор, как по мне. В любом случае, как вариант: определяем $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_0(x)$ предложенным способом, потом $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_1(x)$ аналогичным, а потом $https://www.cyberforum.ru/cgi-bin/latex.cgi?P_+(x)\Leftrightarrow\exists y\forall z\forall t \theta(y,t,x)\wedge P_1(t)\wedge (P_0(y)\vee P_+(y))$ (Положительное число — число, которое получается прибавлением единицы к положительному числу либо нулю). Можно, впрочем, обойтись и без нуля: положительное число — это единица либо положительное плюс единица. Добавлено через 1 минуту Ах да, требовалось же определить отрицательные числа; впрочем, думаю, способ понятен. 1

@painzcupcake 12 / 12 / 5 Регистрация: 11.07.2015 Сообщений: 46
	24.12.2015, 17:01	4
	iifat, согласен, получилось... не самым простым способом %] Но у вас в каком-то смысле рекурсия - предикат выражается через самого себя, и "длина" формулы растет с ростом модуля x 0

iifat 2717 / 1771 / 187 Регистрация: 05.06.2011 Сообщений: 5,129
	24.12.2015, 17:08	5
	Не «в каком-то смысле», а вполне себе рекурсия, да. И, согласен, это — при прочих равных — недостаток. Но вы недооцениваете сложность простенького выражения «положительное число — число, которое можно представить в виде суммы четырёх квадратов» 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	25.12.2015, 10:59	6
	И всё же, iifat, Ваше P₊ Вами не задано явно как формула логики предикатов. В отличие от решения с четырьмя квадратами, где можно подставить все формулы и получить одну длинющую формулу со свободной буквой x, эквивалентную x<0, в Вашем решении это сделать принципиально невозможно без введения комбинатора неподвижной точки или чего-то аналогичного, ибо рекурсия. Иное дело, если бы к теории, содержащей сложение и умножение, нужно было бы добавить предикат x<0, тогда Ваше выражение можно было бы добавить к аксиомам и радоваться. Исходная задача, как я понял, не в этом состоит. 1

iifat 2717 / 1771 / 187 Регистрация: 05.06.2011 Сообщений: 5,129
	25.12.2015, 17:18	7
	Ну, не хочу спорить, поскольку определения сильно забыл. Как по мне, разница не больше, чем между явным и неявным заданием функции в матанализе: в принципе, с явным работать удобнее, однако ж неявность никого особо не смущает. 0

Опции темы