Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 11 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 06 янв 2021, 18:09 
Не в сети
Начинающий
Зарегистрирован:
06 янв 2021, 17:58
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Для функций f(x,y,z) и g(x,y,z) выяснить вопрос об их принадлежности к классам T0,T1,L,S,M.
В случае, если некоторая функция представляет из себя функционально полный класс, выразить из неё с помощью суперпозиций константы 0,1, отрицание и конъюнкцию xy.
В случае, если некоторая функция представляет из себя функционально полный в слабом смысле класс, выразить из неё с помощью суперпозиций и фиксирования переменных отрицание и конъюнкцию xy.
Полученные результаты проверить с помощью построения таблиц.
f: 1111 0111
g: 1011 1100

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 06 янв 2021, 20:18 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Невежливо просить других сделать то, что вы вполне можете сделать сами.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Fa4stik
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 03 фев 2021, 10:47 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Все свойства, кроме линейности, можно определить, имея в распоряжении только вектор значений булевой функции. Насколько я понимаю, проверить на линейность таким образом нельзя - придётся записать функцию в виде формулы (в данном случае - в виде полинома Жегалкина).

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Ellipsoid "Спасибо" сказали:
Fa4stik
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 10:49 
Не в сети
Начинающий
Зарегистрирован:
18 июн 2021, 07:58
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
000 1
001 1
010 0
011 0
100 0
101 1
110 1
111 1
Функция f=(11000111) [math]\notin[/math] T0 [math]\in[/math] T1 [math]\notin[/math] M [math]\notin[/math] S [math]\notin[/math] L
1 [math]\otimes[/math] x [math]\oplus[/math] y [math]\oplus[/math] xz [math]\oplus[/math]xyz
p(x) =f(0,x,1), p(x) =¬x - отрицание.
f(1,x,y)=xy+y+1 - конъюнкции.

В последнем пункте не пойму, как таблицы строить.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 11:29 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Hailmary писал(а):
1 [math]\otimes[/math] x [math]\oplus[/math] y [math]\oplus[/math] xz [math]\oplus[/math]xyz
Никогда не разбивайте одну формулу по разным тегам math. Почему первая связка — это [math]\otimes[/math], а остальные — [math]\oplus[/math]?

Hailmary писал(а):
f(1,x,y)=xy+y+1 - конъюнкции.
Нет, [math]f(1,x,y)=x\oplus y\oplus xy=x\lor y[/math], а [math]1\oplus y\oplus xy=y\to x[/math].

Hailmary писал(а):
В последнем пункте не пойму, как таблицы строить.
По-видимому, нужно построить таблицы истинности для [math]f(0,x,1)[/math] и для второй функции, выражающей конъюнкцию.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 12:04 
Не в сети
Начинающий
Зарегистрирован:
18 июн 2021, 07:58
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer писал(а):
Hailmary писал(а):
1 [math]\otimes[/math] x [math]\oplus[/math] y [math]\oplus[/math] xz [math]\oplus[/math]xyz
Никогда не разбивайте одну формулу по разным тегам math. Почему первая связка — это [math]\otimes[/math], а остальные — [math]\oplus[/math]?

Перепутал значки.
3D Homer писал(а):
Hailmary писал(а):
f(1,x,y)=xy+y+1 - конъюнкции.
Нет, [math]f(1,x,y)=x\oplus y\oplus xy=x\lor y[/math], а [math]1\oplus y\oplus xy=y\to x[/math]

Почему? f(1,x,y) =1*xy+1*x+y+x+1=xy+y+1 Где ошибка?
3D Homer писал(а):
Hailmary писал(а):
В последнем пункте не пойму, как таблицы строить.
По-видимому, нужно построить таблицы истинности для [math]f(0,x,1)[/math] и для второй функции, выражающей конъюнкцию.

Есть пример для функции 00101000, как строить таблицы.
Введём функцию h(x, y) =f(1,y+ [math]\alpha, x+ \beta) + \alpha \beta + \gamma =f(1,¬y,¬x)=f(1,f(0,1)y),f0,1x))[/math]
Только я не пойму, откуда эти формулы взялись?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 12:27 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
[math]f(x,y,z)=1\oplus x\oplus y\oplus xz\oplus xyz[/math].

Hailmary писал(а):
f(1,x,y) =1*xy+1*x+y+x+1=xy+y+1 Где ошибка?

Когда вы пишете 1 в качестве первого аргумента, вы подставляете его вместо [math]x[/math].

Hailmary писал(а):
Есть пример для функции 00101000, как строить таблицы.
Я не знаю, что вы имеете в виду под таблицами, но в булевой алгебре под ними обычно имеются в виду таблицы истинности. Эта формула взялась из доказательства леммы о нелинейной функции.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 12:53 
Не в сети
Начинающий
Зарегистрирован:
18 июн 2021, 07:58
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Тогда как правильно конъюнкцию расписать?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 18 июн 2021, 12:58 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Для функций f и g выяснить их принадлежность к классам T0,T1
СообщениеДобавлено: 23 июн 2021, 09:20 
Не в сети
Начинающий
Зарегистрирован:
18 июн 2021, 07:58
Сообщений: 5
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
x y z f g
000 1 1
001 1 0
010 1 1
011 1 1
100 0 1
101 1 1
110 1 0
111 1 0
Исследуем f(x, y, z). f(0,0,0)=1 значит f [math]\notin[/math] To, f(1,1,1)=1, f [math]\in[/math] T1, f [math]\notin[/math] S [math]\notin[/math] M [math]\notin[/math] L
Полином Жегалкина [math]\sum[/math](x+¬a) (y+¬b) (z+¬c) = xyz+xy+xz+x+1.
Найдём отрицание: f(0,0,0)=1, f(1,0,0)=0 значит f(x, 0,0)=¬x.
Найдём конъюнкцию: для её нахождения зафиксируем одну переменную и переобозначим оставшиеся переменные так, чтобы полином принял вид xy+ax+by+c.
x=1, y=x, z=y, xy+x+y, a=b=1, c=0.
Введём функцию h(x, y) =f(1,x+a, y+b) + ab + c = f(1,¬x,¬y)+1 = ¬f(1,¬x,¬y)=f(1,x,y)=f(1,¬f(x,0,0),y), x [math]\lor[/math] y = ¬(¬x¬y) = f(1,x,y), xy = ¬(¬x [math]\lor[/math] y) = ¬f(1,¬x,¬y)
Проверим с помощью таблицы

h(x, y) 1, ¬x, ¬y, f, ¬f
00 1 1 1 1 0
01 1 1 0 1 0
10 1 0 1 1 0
11 1 0 0 0 1

Исследуем g(x, y, z). Она не принадлежит к классам. Полином Жегалкина xyz+xy+xz+yz+z+1. g(0,0,0)=1, g(1,1,1)=0, значит g(x, x, x) = ¬x. g(0,0,1)=g(1,1,0)=0, 0(x)=g(¬x,¬x,x). 1(x)=¬0(x)=g(g(x,x,g(x,x,x)),g(x,x,g(x,x,x)),g(x,x,g(x,x,x)))=1.
f(x, y, 0)=xy+1= ¬(xy), xy = ¬f(x, y, 0) =¬f(x, y, g(x, x, g(x, x, x)))
Таблица
h(x, y) x y 0 ¬f
00 0 0 0 1 0
01 0 1 0 1 0
10 1 0 0 1 0
11 1 1 0 0 1

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 11 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Определить принадлежность функции 5 замкнутым классам

в форуме Дискретная математика, Теория множеств и Логика

progrart

0

670

19 дек 2015, 22:12

Двум классам было дано задание собрать по 100кг крыжовника.

в форуме Алгебра

tanyhaftv

9

191

21 июл 2023, 11:02

Проверить на принадлежность множеству

в форуме Дискретная математика, Теория множеств и Логика

MaxK

0

291

03 июн 2015, 00:59

Как определить принадлежность точки

в форуме Аналитическая геометрия и Векторная алгебра

M4383

1

576

22 мар 2016, 12:32

Принадлежность координат к шаровому сегменту

в форуме Аналитическая геометрия и Векторная алгебра

dmake

6

295

12 ноя 2017, 18:27

По графику определить принадлежность к теории

в форуме Теория вероятностей

Abraziv

0

218

17 июл 2016, 04:47

Принадлежность точек одной плоскости

в форуме Геометрия

kvadratisharic

6

613

02 дек 2017, 17:37

Принадлежность отрезка многоугольнику любого вида

в форуме Геометрия

Amplifier

11

382

17 май 2020, 20:54

Выяснить сходимость ряда

в форуме Ряды

a_zajtcev

4

571

19 июн 2014, 12:18

Выяснить,образует ли базис

в форуме Линейная и Абстрактная алгебра

rozali

4

449

25 апр 2021, 19:01


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 27


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved