Connectives

Logic Level 2

In propositional-logic , we have five connectives:

Negation
Conjunction
Disjunction
Conditional
Biconditional

Billy argues that this is too many and that any logical proposition that can be constructed with these five connectives can be constructed with fewer.

What is the fewest number of connectives necessary (including only those listed here) in order to be able to construct any logical proposition that can be constructed with these five?

1 2 3 4 5 This is an unsolved problem

2 solutions

Geoff Pilling
Jan 30, 2017

It suffices to show that all of the above functionality can be represented by only two of the connectives. So, we can show that it can be done with just these two:

Negation
Conjunction

$(A \vee B) \leftrightarrow \neg((\neg A) \wedge (\neg B))$

$(A \to B) \leftrightarrow \neg(A \wedge (\neg B))$

$(A \leftrightarrow B) \leftrightarrow (\neg ((\neg A) \wedge B)) \wedge (\neg (A \wedge (\neg B)))$

Therefore, all of the propositional logic that can be constructed with the five main connectives, can be constructed with only $\boxed2$ of the five connectives.

In fact, if there was a connective with the logical NAND function, you could do it with just one since a NAND can be made into an inverter by tying both inputs together, and a NAND and an inverter can be made into an AND gate.

The question asked for the fewest number of connectives necessary. How do you know that "1" cannot be the answer?

Pi Han Goh - 4 years, 4 months ago

Good question... Lemme think about that one...

Geoff Pilling - 4 years, 4 months ago

Sir, Did you find proof that 1 cannot be the answer? I have also read that every single combination of connective can be constructed out of NAND but never saw a proof for it.

Puneet Pinku - 1 year, 9 months ago

Answer is 1. All you need is a conditional.

Ajinkya Shivashankar - 4 years, 4 months ago

What about the negation of a conditional. A conditional $A \supset B \equiv ~A\lor B$ , but the negation becomes $\sim \left(A\supset B\right) \equiv A \ \&\sim B$ . How would you express that?

Kishore S. Shenoy - 2 years, 2 months ago

Ajinkya Shivashankar
Jan 31, 2017

Answer is 1

All we need is a conditional.

$A \to A$ Is always true.

$T \to A$ Is Negation where T is always true.

$(\neg A) \to B$ is disjunction where negation is created by using the above.

Rest can be in turn shown to be represented by negation and disjuction.

But $A \to T$ is not Negation. Since it is always true.

Geoff Pilling - 4 years, 4 months ago

Made the necessary modification. Btw your line on NAND gate left me thinking and gave me this answer.

Ajinkya Shivashankar - 4 years, 4 months ago

But $T \to A,$ is not negation unless A is false,.

Geoff Pilling - 4 years, 4 months ago

A->T = T T->A = A

Hasmik Garyaka - 2 years, 4 months ago

Conditional is not only function that we need. We need a function which will return false on true argument. (There is a theorem). Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

The monotonic connectives; changing the truth value of any connected variables from F to T without changing any from T to F never makes these connectives change their return value from T to F, e.g. {\displaystyle \vee ,\wedge ,\top ,\bot } {\displaystyle \vee ,\wedge ,\top ,\bot }. The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g. {\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow } {\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }. The self-dual connectives, which are equal to their own de Morgan dual; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g. {\displaystyle \neg } \neg , MAJ(p,q,r). The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables, e.g. {\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow } {\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }. The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g. {\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow } {\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }. In fact, Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called Post's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal clones.

Hasmik Garyaka - 2 years, 4 months ago

Connectives

2 solutions

0 pending reports