证明满足f(T,T,…,T)=T的真值函数可由{∧,∨,→}表示

Alright, let's work through this proof step by step. Here's how to show that any n-ary truth function ( f ) with ( f(T, T, …, T) = T ) can be expressed using only the connective set ( {\land, \lor, \rightarrow} ):

Step 1: Start with a CNF representation #

First, recall that every truth function can be written in Conjunctive Normal Form (CNF) using the connectives ( {\neg, \land, \lor} ). Let’s call this CNF formula ( \varphi ) for our function ( f ).

CNF means ( \varphi = D_1 \land D_2 \land ... \land D_m ), where each ( D_i ) is a clause (a disjunction of literals; a literal is either a variable ( p_j ) or its negation ( \neg p_j )).

Step 2: Leverage the given property ( f(T,T,...,T)=T ) #

Since ( f(T,T,...,T)=T ), substituting all ( p_j = T ) into ( \varphi ) must result in ( T ). For a CNF formula to evaluate to ( T ), every clause ( D_i ) must evaluate to ( T ) when all variables are ( T ).

The only clause that would evaluate to ( F ) in this scenario is a disjunction of nothing but negated variables: ( \neg p_1 \lor \neg p_2 \lor ... \lor \neg p_n ). Substituting ( T ) for each ( p_j ) turns every ( \neg p_j ) into ( F ), making the whole clause ( F ).

But since our ( \varphi ) evaluates to ( T ) here, none of the clauses ( D_i ) can be this all-negated clause. Every clause ( D_i ) must contain at least one positive literal (a variable without a negation).

Step 3: Eliminate negations using logical equivalences #

Take any clause ( D_i ) in our CNF. It will look like this:
( \neg q_1 \lor \neg q_2 \lor ... \lor \neg q_k \lor r_1 \lor r_2 \lor ... \lor r_t )
where ( t \geq 1 ) (from Step 2: there’s at least one positive literal present).

We use the logical equivalence provided in the hint:

( \neg \theta \lor \psi \equiv \theta \rightarrow \psi )

Combined with De Morgan’s law (( \neg(q_1 \land q_2 \land ... \land q_k) \equiv \neg q_1 \lor \neg q_2 \lor ... \lor \neg q_k )), we can rewrite the entire clause as:
( (q_1 \land q_2 \land ... \land q_k) \rightarrow (r_1 \lor r_2 \lor ... \lor r_t) )

This expression uses only ( \land ), ( \lor ), and ( \rightarrow )—no negations at all!

Step 4: Combine all rewritten clauses #

Since every clause ( D_i ) in our CNF can be rewritten without negations using ( {\land, \lor, \rightarrow} ), the entire formula ( \varphi ) (which is the conjunction of these clauses) can also be expressed using only these three connectives.

That’s it—we’ve proven that ( f ) can be represented with the connective set ( {\land, \lor, \rightarrow} )!

内容的提问来源于stack exchange，提问作者Constantly confused