Объяснить принцип решения задачи.

[ogcjm]

Задание: построить множество всех булевых функций, зависящих от переменных x1 и x2 и принадлежащих замыканию множества б.ф. P:

$ 1. P = {x1^x2} 2.P = {~x1 || x2} $

Например, для 1 случая ответ будет таким {x1, x2, x1^x2}
Честно говоря, не совсем понятно как строить это множество?
Как x1 ^ x2 в ответе получается это понятно. Но как получить просто x1 или x2? У нас же в функции должны быть обязательно переменные x1 и x2?

Объясните пожалуйста принцип решения.

-- 15.10.2012, 21:10 --

Простите за опечатку:
в 1 случае P = x1 ^ x2, а во втором P = {~x1 or x2}

[Xaositect]

${x_1}^{x_2}$, $~x_1 \par x_2$, $\neg x_1 \vee x_2$

${x_1}^{x_2}$, $\mathord{\sim} x_1 \parallel x_2$,$\neg x_1 \vee x_2$

Напишите определение замыкания.

[ogcjm]

Вот:
Замыканием множества булевых функций M называется множество всех булевых функций представимых в виде формул над M.

-- 15.10.2012, 21:40 --

Что сделать на следующем шаге?

-- 15.10.2012, 21:42 --

Хотелось бы понять как решать эти задачи, желательно не перебирая всевозможные комбинации формул над некоторым множеством.

-- 15.10.2012, 21:47 --

Скажите, пожалуйста, вот, если у нас есть множество:
P = {x1^x2 or x2^x2 or x1 ^ x3}
То формула x1^x1 or x1^x1 or x1^x1 является формулой над P или нет?

[Toucan]

ogcjm, у Вас есть еще примерно 20 минут, чтобы исправить $\TeX$ в стартовом сообщении. Если Вы этого не сделаете, тема уедет в Карантин.

-- Пн 15.10.12 21:49:42 --

Кстати, не только в стартовом.

[Xaositect]

Угу.
Следующим шагом обычно бывает описание некоторой канонической формы, к которой приводится любая формула над нашим множеством.

Например, если система $M$ состоит только из отрицания, то любая формула имеет вид $\neg \neg\dots \neg x$, а, поскольку $\neg \neg z = z$, любая формула реализует такую же функцию, как и формула с двумя отрицаниями меньше, в итоге приходим к $\neg x$ и $x$.

Вот, я тут когда-то это уже писал: post223131.html#p223131

А кстати, что это за функция ${x_1}^{x_2}$?

-- Пн окт 15, 2012 21:52:37 --

ogcjm в сообщении #631376 писал(а):

То формула x1^x1 or x1^x1 or x1^x1 является формулой над P или нет?

А это Вы скажите, определение формулы Вы должны знать.

[ogcjm]

Если вы это увидели в моём тексте, то это опечатка.
А вообще

$ x1 ^ {x2} = 1 <=> x1 = x2 $

-- 15.10.2012, 21:57 --

Вы могли бы ещё подсказать:
если

$ P = {x1^{x2}} $

То может ли формула над P не содержать x1 или x2 или константы?

-- 15.10.2012, 21:58 --

Опять извиняюся P = {x1 ^ x2}

[Toucan]

Видимо, сигнал не дошел; тема переезжает в Карантин.

Исправьте формулы во всех своих сообщениях и напишите об этом в теме Сообщение в карантине исправлено.