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

[Коляныч]

Пожалуйста, помогите решить следующие задачи. Даже если просто подскажете идею решения, то тоже буду очень благодарен.

1. Две формулы, содержащие только связки "и", "или" и "не", эквивалентны. Докажите, что они останутся эквивалентными, если всюду заменить "и" на "или" и наоборот.

2. Построить формулу от трех переменных, которая принимате то же значение, что и большинство ее переменных.

3. Докажите, что любую самодвойственную функцию можно выразить через "не" и функцию h(x, y, z) = xy + yz + xz

Заранее большое спасибо!

[AD]

Коляныч в сообщении #160788 писал(а):

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

Ну выписываем табличку значений, и скатываем с неё СДНФ, потом при желании упрощаем.

Добавлено спустя 4 минуты 16 секунд:

Коляныч в сообщении #160788 писал(а):

Докажите, что любую самодвойственную функцию можно выразить через "не" и функцию h(x, y, z) = xy + yz + xz

Насколько я помню, в S есть базис из одной-единственной функции со столбцом значений (10001110) (идея - в том, что в верхней половине сидит штрих Шеффера, а нижняя половина получается из верхней известным способом). Так что, в качестве плана - доказать, что указанная функция порождает S, а потом выразить ее через отрицание и эту вашу h. Не знаю, наверное, можно и проще.