Set Operation Exclusion Constraint for Multiple Tables All at Once

In multiple of my tables, I have a deleted column for tracking things which have been deleted, instead of directly deleting them from the database. As such, I would like to create a constraint for disallowing the *undeletion* of things, preferably all at once. Is that even possible? To exemplify things:

CREATE TABLE IF NOT EXISTS users (
    id UUID DEFAULT uuid_generate_v4 ()
        CONSTRAINT users_pk PRIMARY KEY,
    deleted BOOLEAN NOT NULL DEFAULT FALSE
);

CREATE TABLE IF NOT EXISTS votes (
    id UUID DEFAULT uuid_generate_v4 ()
        CONSTRAINT votes_pk PRIMARY KEY,
    deleted BOOLEAN NOT NULL DEFAULT FALSE
);

In those tables, the constraint should disallow operations which turn deleted from TRUE to FALSE.