In this problem, we will give another proof that the set of connectives {-, A, V}...

 

Transcribed Image Text:

In this problem, we will give another proof that the set of connectives {-, A, V} is adequate for propositional (Boolean logic.) To do this, we will show that every n-ary Boolean operator (n > 1) F(p1,..., Pn) is induced by a propositional formula which uses the connectives , A, and V only. The proof is by induction on n, with the case n = 1 being easy. To prove the claim for n+1 assuming that every n-ary Boolean operator is express- ible in terms of ¬, A and V, proceed as follows: suppose F(p1,..., Pn, Pn+1) is an (n + 1)-ary Boolean operator. Consider the following two n-ary Boolean operators F1(P1, ... , Pn) = F(p1;...,Pn, T) F2(P1, ..., Pn) = F(p1,..., Pn, F) obtained from F by fixing the value of the (n+ 1)-th variable pn+1 to be T and F, respectively. Apply the inductive hypothesis on F1 and F2, to get the formulas A1 and A2, and consider the formula (A1 ^ Pn+1) V (A2 A-Pn+1). Remark: One can refine the result of this problem even further. Namely, for a formula obtained in this way, using tivity and De Morgan's laws repeatedly, one can show that the formula is equivalent to a disjunction of conjunctions of literals. So, every Boolean operator is induced by a formula (DNF.) This fact was stated, without proof, in MTH110. -, A, and V only, using distribu- S. hich in a disjunctive normal form In this problem, we will give another proof that the set of connectives {-, A, V} is adequate for propositional (Boolean logic.) To do this, we will show that every n-ary Boolean operator (n > 1) F(p1,..., Pn) is induced by a propositional formula which uses the connectives , A, and V only. The proof is by induction on n, with the case n = 1 being easy. To prove the claim for n+1 assuming that every n-ary Boolean operator is express- ible in terms of ¬, A and V, proceed as follows: suppose F(p1,..., Pn, Pn+1) is an (n + 1)-ary Boolean operator. Consider the following two n-ary Boolean operators F1(P1, ... , Pn) = F(p1;...,Pn, T) F2(P1, ..., Pn) = F(p1,..., Pn, F) obtained from F by fixing the value of the (n+ 1)-th variable pn+1 to be T and F, respectively. Apply the inductive hypothesis on F1 and F2, to get the formulas A1 and A2, and consider the formula (A1 ^ Pn+1) V (A2 A-Pn+1). Remark: One can refine the result of this problem even further. Namely, for a formula obtained in this way, using tivity and De Morgan's laws repeatedly, one can show that the formula is equivalent to a disjunction of conjunctions of literals. So, every Boolean operator is induced by a formula (DNF.) This fact was stated, without proof, in MTH110. -, A, and V only, using distribu- S. hich in a disjunctive normal form

Answer rating: 100% (QA)

When n1 then we have a unary operator and it can be represented usin... View the full answer