Is there a general form of a logical formula with N variables?

58 Views Asked by At

Let N = 2. Then there are 16 possible non-equivalent N variable logical formulas, listed below.

False, A ∧ B, ¬(A → B), A, ¬(B → A), B, A ⊕ B, A v B, ¬(A v B), ¬(A ⊕ B), ¬B, B → A, ¬A, A → B, ¬(A ∧ B), True.

A possible general form for N = 2 could be: (A v B) ∧ (A v B).

Each of the above formulas can be represented with the general form by simply switching logical operators. Potential derived forms are below, in order.

(A ∧ ¬A) ∧ (A ∧ A), (A ∧ B) v (A ∧ ¬A), (A ∧ ¬B) v (A ∧ ¬A), (A v A) v (A v A), (¬A ∧ B) v (A ∧ ¬A), (B v B) v (B v B), (¬A ∧ B) v (A ∧ ¬B), (A v B) v (A v B), (¬A v ¬B) v (¬A v ¬B), (A v ¬B) ∧ (¬A v B), (¬B ∧ ¬B) ∧ (¬B ∧ ¬B), (A v ¬B) v (A v ¬B), (¬A ∧ ¬A) ∧ (¬A ∧ ¬A), (¬A v B) v (¬A v B), (¬A v ¬B) v (¬A v ¬B), (A v ¬A) ∧ (B v ¬B).

Is there a form like this for every N? If so, what is the smallest?