Теорема Поста

@Angellok · Регистрация: 15.11.2012

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

Как проверить систему функций М на полноту
М={0,1} ?

Добавлено через 1 час 37 минут
как расчитать Т0,Т1,S,M,L?

vetvet · 18.12.2012, 19:14

Для каждой функции отдельно. Очевидно, что функция 0 принадлежит классу T₀, а функция 1 - классу T₁ и обе они монотонны.

@Angellok · 19.12.2012, 16:00 **[ТС]**

А как это для них доказать? ведь функции нету для них?

vetvet · 19.12.2012, 16:48

Ну можете для собственного удобства представить их как
f(x₁, x₂, ... , x_n)=1
и
f(x₁, x₂, ... , x_n)=0
Хотя и не уверена, что так пишут.
Вообще, у меня получилось так:

\	T₀	T₁	S	M	L
1	-	+	-	+	+
0	+	-	-	+	+

Т.о., данная система полной не является.

@Angellok · 19.12.2012, 21:53 **[ТС]**

Я поняла как доводить T0 и Т1. А вот самодвойственность, монотонность, линейность как доводить?Ведь эти функции не имеют переменной x. Или просто надо выучить эту таблицу и всё?

vetvet · 20.12.2012, 02:24

Монотонность очевидна: это же постоянные функции.
Самодвойственными они обе быть не могут, так как для самодвойственности должно выполняться [latex]\overline{f(\bar{x},\bar{y},...)=f(x,y,...)
Эти функции от переменных (а следовательно и их отрицаний не зависят), а
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{1}=0\ne 1,\bar{0}=1\ne 0$
С линейными тоже всё просто. Функция линейна, если её можно представить многочленом Жегалкина, а многочлен Жегалкина строится при помощи операции $https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus$ , переменных и констант 0,1. Т.е. эти константы для себя многочленом Жегалкина и являются.

@Angellok · 21.12.2012, 17:48 **[ТС]**

Коректировка по самодвойственности: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline{f(\bar{x},\bar{y},...)=f(x,y,...)$
Огромное спасибо.

vetvet · 21.12.2012, 18:00

Не так: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline{f(\bar{x},\bar{y},...)}=f(x,y,...)$

Добавлено через 1 минуту
Здесь можно было и не проверять все свойства. Сразу видно, что обе функции монотонны, а для полноты системы должна быть одна немонотонная.

@Angellok · 21.12.2012, 23:17 **[ТС]**

Для первокурсника заочника это очень важно, а то еще прицепятся на сессии что и как

@Angellok 1 / 1 / 0 Регистрация: 15.11.2012 Сообщений: 94
		1
	Теорема Поста 18.12.2012, 18:14. Показов 3184. Ответов 8 Метки нет (Все метки) Как проверить систему функций М на полноту М={0,1} ? Добавлено через 1 час 37 минут как расчитать Т0,Т1,S,M,L? 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	18.12.2012, 19:14	2
	Для каждой функции отдельно. Очевидно, что функция 0 принадлежит классу T₀, а функция 1 - классу T₁ и обе они монотонны. 0

@Angellok 1 / 1 / 0 Регистрация: 15.11.2012 Сообщений: 94
	19.12.2012, 16:00 [ТС]	3
	А как это для них доказать? ведь функции нету для них? 0

@Angellok 1 / 1 / 0 Регистрация: 15.11.2012 Сообщений: 94
	19.12.2012, 21:53 [ТС]	5
	Я поняла как доводить T0 и Т1. А вот самодвойственность, монотонность, линейность как доводить?Ведь эти функции не имеют переменной x. Или просто надо выучить эту таблицу и всё? 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	20.12.2012, 02:24	6
	Монотонность очевидна: это же постоянные функции. Самодвойственными они обе быть не могут, так как для самодвойственности должно выполняться [latex]\overline{f(\bar{x},\bar{y},...)=f(x,y,...) Эти функции от переменных (а следовательно и их отрицаний не зависят), а $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{1}=0\ne 1,\bar{0}=1\ne 0$ С линейными тоже всё просто. Функция линейна, если её можно представить многочленом Жегалкина, а многочлен Жегалкина строится при помощи операции $https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus$ , переменных и констант 0,1. Т.е. эти константы для себя многочленом Жегалкина и являются. 1

@Angellok 1 / 1 / 0 Регистрация: 15.11.2012 Сообщений: 94
	21.12.2012, 17:48 [ТС]	7
	Коректировка по самодвойственности: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline{f(\bar{x},\bar{y},...)=f(x,y,...)$ Огромное спасибо. 0

vetvet Змеюка одышечная 9864 / 4595 / 178 Регистрация: 04.01.2011 Сообщений: 8,556
	21.12.2012, 18:00	8
	Не так: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\overline{f(\bar{x},\bar{y},...)}=f(x,y,...)$ Добавлено через 1 минуту Здесь можно было и не проверять все свойства. Сразу видно, что обе функции монотонны, а для полноты системы должна быть одна немонотонная. 0

@Angellok 1 / 1 / 0 Регистрация: 15.11.2012 Сообщений: 94
	21.12.2012, 23:17 [ТС]	9
	Для первокурсника заочника это очень важно, а то еще прицепятся на сессии что и как 0