Как решать задачу на булеву логику?

Question

[Xiran]

Известно, что:
(НЕ(a) ИЛИ НЕ(b) ИЛИ НЕ(c) ИЛИ A(d,e,f)) ИЛИ ((d) ИЛИ (e) ИЛИ (f) ИЛИ B(a,b,c))=1, где
A(d,e,f) и B(a,b,c) – логические функции от трех переменных, связанные между собой следующим условием:

НЕ (A(x,y,z)) ИЛИ (B(x,y,z))=1

Сколько существует пар функций
A и B, чтобы выполнялось указанное тождество? Пара – упорядоченный набор из двух функций, функции в паре могут повторяться. В ответ запишите количество таких пар или 0, если их не существует.

Comments

[Alexandroppolus]

Из первого равенства следует, что должно быть либо A(0, 0, 0)=1, либо B(1, 1, 1)=1, иными словами, нельзя одновременно A(0, 0, 0)=0 и B(1, 1, 1)=0

По второму всё сложно, там точно подходят все варианты А = В, кроме A(x,y,z) = B(x,y,z) = 0, исключаемого первым равенством. Но дополнительно ещё найдется куча вариантов, где A != B, при этом оба равенства соблюдены, например
A(x, y, z) = x & y & z
B(x, y, z) = x | y | z
и вот эти доп. пары непонятно как "классифицировать" и считать.

Можно, разумеется, выписать на бумаге все возможные пары функций, проверить их на соответствие равенствам и посчитать, но это уныние и отчаяние...

Answer 1

[Rsa97]

С помощью тождеств
not(A and B) = not A or not B
not(A or B) = not A and not B

Answer 2

[Xiran]

Написал код

Код

#include <cassert>
#include <iostream>

constexpr std::uint8_t THREE_BITS_MAX = 7, THREE_ARY_BOOL_FN_MAX = 255;

inline bool get_nth_bit(int reg, int x) {
    return (reg >> x) & 1;
}

template<std::size_t M>
class iteratable {
public:
    inline void next() {
        if (raw_ == M) {
            is_end_ = true;
            return;
        }

        raw_++;
    }

    inline bool is_end() const {
        return is_end_;
    }
protected:
    std::uint8_t raw_ { 0 };
    bool is_end_ { 0 };
};

class three_bits_pack : public iteratable<THREE_BITS_MAX> {
public:
    inline bool operator[](std::size_t index) const {
        assert(index <= 3);

        return get_nth_bit(raw_, index);
    }

    inline auto raw() const {
        return raw_;
    }
};


class three_ary_bool_fn : public iteratable<THREE_ARY_BOOL_FN_MAX> {
public:
    inline bool operator()(const three_bits_pack &pack) const {
        return get_nth_bit(raw_, pack.raw());
    }
};

int main() {
    int counter = 0;

    for (three_ary_bool_fn a_fn; !a_fn.is_end(); a_fn.next()) {
        for (three_ary_bool_fn b_fn; !b_fn.is_end(); b_fn.next()) {
            for (three_bits_pack abc; !abc.is_end(); abc.next()) {
                if (a_fn(abc) && !b_fn(abc))
                    goto next;

                for (three_bits_pack def; !def.is_end(); def.next()) {
                    if (!(!abc[0] || !abc[1] || !abc[2] || a_fn(def)))
                        goto next;

                    if (!(def[0] || def[1] || def[2] || b_fn(abc)))
                        goto next;
                }
            }
            counter++;
next:;
        }
    }

    std::cout << counter;
}

"Трюк" основан на том, что любую логическую 3-арную функцию можно представить как 8 битов, где номер каждого бита равен комбинации битов, которые от этой функции дают этот самый бит.
Только вот ничего не работает как надо. Выдает 1 и все, а должно 5103.