Задача по математической логике

[Olegator]

И.Л. Никольская. "Математическая логика" упр. 21, стр. 34.
Упростите следующую, инструкцию: "Подчеркивайте числа, которые одновременно кратны трем, оканчиваются нулем и имеют
сумму цифр, большую 37. Подчеркивайте также те числа, которые
не делятся на 3, оканчиваются нулем н имеют сумму цифр, не превосходящую 37. Кроме того, подчеркивайте числа, которые оканчиваются нулем, делятся на 3 и сумма цифр которых не более 37, а также числа, оканчивающиеся нулем, с суммой цифр, большей 37, и не кратные трем. И наконец, подчеркивайте числа, кратные трем, не оканчивающиеся нулем и имеющие сумму цифр, превосходящую 37".

Если обозначить:
Х1-кратны трём
Х2-оканчивается нулём
Х3-сумма цифр > 37

то получится следующая формула:
(X1^X2^X3)v(notX1^X2^notX3)v(X1^X2^notX3)v(notX1^X2^X3)v(X1^notX2^X3)
Решение:
1. Сначала по закону идемпотентности (ХvX=X) делаем так:
(X1^X2^X3)v (X1^X2^X3)v (X1^X2^X3)v (notX1^X2^notX3)v(X1^X2^notX3)v(notX1^X2^X3)v(X1^notX2^X3)
2. Затем по закону склеивания (X^Y)v(notX^Y)=Y получаем:
 (X1^X2)v(X1^X3)v(X2^X3)v(notX1^X2^notX3)
До этого момента вроде всё верно. И может быть это уже ответ. Но я продолжил дальше:
3. По закону дистрибутивности (X^Y)v(X^Z)=X(YvZ):
(X1^X2)v(X2^X3)=X2^(X1vX3)
4. По закону де Моргана (notX^notY)=not(XvY):
(notX1^X2^notX3)=X2^(not(X1vX3))
5. Получается так:
(X1^X3)v(X2^(X1vX3))v(X2^(not(X1vX3)))
6. По закону склеивания:
(X1^X3)vX2
И тут у меня сомнения. Может где-то с 3 по 6 пункт я допустил ошибку.

[RXL]

Olegator, если с точки зрения программирования, то можно удобоваримее сделать:
У тебя даны 5 вариантов комбинаций трех параметров (по два варианта на параметер). Всего комбинаций может быть 2^3 = 8. Если разбить по битам (так просто будет удобнее нумеровать варианты), то заданы: 7, 2, 3, 6 и 5. Нужно провести для каждого числа три теста и по результату определить номер, а по номеру решить - подчеркивать или нет.
Замечу так же, что если число оканчивается на 0, то по условиям его всегда нужно подчеркивать.

[Sla]

Olegator, выдели общее из первых четырех, а потом и упрощать ничего не надо должно получиться (X1^X3^notX2)vX2

[Sands]

Sla, по-моему, (X1^X3^notX2)vX2 еквивалентно (X1^X3)vX2

[Olegator]

Sla, по-моему, (X1^X3^notX2)vX2 еквивалентно (X1^X3)vX2

Верно. Значит я не ошибся.

[Olegator]

Ещё одна задача из того же источника:

Докажите, что число попарно неравносильных формул с переменными Х₁, Х₂,...,Х_n равно 2⁽²ⁿ⁾

1. И тут не понятно, что значит число попарно неравносильных формул.
Т.е. допустим "F1 не равносильно F2" и "F3 не равносильно F4". Сколько тут попарно неравносильных формул? 2 или 4?

2. Как я понял при составлении всего множества формул, когда мы получаем дизъюнкцию конъюнкций, количество конъюнкций получается равным (2ⁿ). Как это доказывается, пока не знаю.

И теперь что значит 2⁽²ⁿ⁾

[Dimka]

Попарно неравносильные означают, что для любой формулы во множестве формул на общем множестве переменных нет равносильной ей. Любые две формулы достаточно свести к их полным дизъюнктивной или конъюнктивной нормальным формам (ДНФ, КНФ), чтобы установить их равносильность или неравносильность. Можно и по таблицам истинности проверять.

Попытаюсь объяснить наглядно. В случае N переменных имеется 2^N различных наборов значений этих переменных: если выписать в таблице по столбцам переменые X1...XN, то их значения, состоящие из 1 и 0 займут 2^N различных строк. В этой же таблице можно ввести колонку результата F, имеющую 2^N значений. Так как неравносильные формулы дают различный результат, получаем, что каждая формула даёт набор из M=2^N значений. Количество таких наборов 2^M. Таким образом, имеем количество неравносильных формул 2^(2^N).

Пример для N=2.

Имеем 2^N наборов значений переменных (в данном случае 4).

Код:

X1 X2  F
 0  0
 0  1
 1  0
 1  1

В этом случае F может принимать следующие возможные значения:

Код:

F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1