How to find the general form for a family of tautologies?

37 Views Asked by At

I was given the following family of tautologies:

$H_1 = p \lor \neg p$

$H_2 = (p \land q) \lor (\neg p \land q) \lor (p \land \neg q) \lor (\neg p \land \neg q)$

$H_3 = (p \land q \land r) \lor (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (\neg p \land \neg q \land r) \lor (p \land q \land \neg r) \lor (\neg p \land q \land \neg r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land \neg q \land \neg r)$

I have to find the general form for the tautology $H_n$. $n$ is the number of atoms.

I have found the following:

Let $p_i$ be atoms of the propositional logic:

$H_n = (p_1 \lor \neg p_1)_1 \land \ldots (p_n \lor \neg p_n)_n$ is a reduced general form for the intended general expression. In other words, the expansion of it probably is the one I'm asked for but I can't see a good way to make it general,

This way, for example:

$H_n = (p_1 \land \ldots p_n)_1 \lor \ldots (p_1 \land \ldots p_n)_{2^n}$

does not show how the negations inside the parenthesis must be distributed.

Note also that this form has $2^n$ expressions inside parenthesis, that's because it is covering every possible valuation that could falsify it and using the negation to always be satisfiable.

1

There are 1 best solutions below

0
On

I would have written something like: $$\bigvee_{j=1}^{n}\bigvee_{k_j \in \{∅,¬\}}\bigwedge_{p=1}^{n}k_j a_p$$ where the $a_p$ are the atoms, but hard to be sure without the exact formulation of the question.