7.2.4. Negation and Disjunction Functionality

So we will start with question 8, in question 8 we are defining a functionally complete set of logical operators, if you are given a set of logical operators, we say it is functionally complete, if every compound proposition can be converted into a logically equivalent proposition involving only the logical operators, that is given in your collection.

A functionally complete set of logical operators means we can express any logical statement (compound proposition) using just a designated set of operators. If we can take any complex logical statement and rewrite it entirely using only the operators from this set, then this set is considered functionally complete. This is crucial in logic and computer science since it tells us how much expressive power a set of operators possesses.

Think of building a structure using Lego blocks. If you have a complete set of blocks, you can recreate any custom design. Similarly, having a complete set of logical operators allows you to create any logical statement.

What about a compound proposition where I have an occurrence of implication? In that case what I can do is I can use this logical identity that p → q is logically equivalent to negation of p disjunction q and I can substitute p → q by this RHS expression.

When we encounter an implication in a logical statement, we can simplify it using a specific identity: p → q can be rephrased as ¬p ∨ q (not p or q). This means anytime there's a statement that says 'If p then q', we can represent it in a way that avoids using the 'if...then...' structure, thus simplifying our logical expression into a form that's easier to work with using conjunctions, disjunctions, and negations.

Imagine a traffic light system where 'if the light is green, cars can go'. Instead of saying that, we can express it as 'either the light is not green, or cars can go'. This makes the rules clearer and more manageable.

What if my expression has bi implication (↔) symbol? I do not have to worry, what I have to do is I can use the identity that the bi implication is nothing but the conjunction of two individual implications.

A bi-implication like p ↔ q can be represented as (p → q) ∧ (q → p). This means that p is true if and only if q is also true, implying both implications must be satisfied. By breaking it down into conjunctions of simpler implications, we can apply the same rules of simplification we used for simple implications.

Think of a cooperative game where two players win only if both agree to play together. The statement 'Player A wins if and only if Player B plays' can be seen as two conditional agreements rather than one complex rule, making it easier to understand and negotiate.

This is how we can prove that imagine you have an expression of the form conjunction of p and q. This is logically equivalent to negation of negation of p, conjunction negation of negation of q and then by De Morgan's law, this is nothing but equivalent to negation of this entire expression, namely disjunction of ¬ p and ¬ q.

We can express a logical conjunction (p ∧ q) using just negation and disjunction. By applying double negation and De Morgan's laws, we find that p ∧ q can be rewritten as ¬(¬p ∨ ¬q). This shows that even when we have an 'and' operation, we can convert it into an expression that uses only 'or' and 'not', demonstrating that disjunction and negation alone can describe conjunction.

Think of preparing a dish. If the recipe states you can only use certain ingredients, you can creatively combine them (negation and disjunction) to create a flavorful dish (joining different components) while ensuring it adheres to the original requirements (conjunction).

The third part now says that you have to show that only the negation operator and the conjunction operator are functionally complete and here we have to show how we can represent a disjunction in terms of conjunction and negation.

We can show that using only conjunction and negation, we can express disjunction. The identity used here would be that p ∨ q can be rewritten using De Morgan's laws as ¬(¬p ∧ ¬q). This suggests that not only disjunction and negation but also conjunction and negation are sufficient to constitute a functionally complete set of operators.

Imagine you want to confirm if a light is on or off (a disjunction). You can instead check whether it is NOT both off and NOT off (conjunction and negation). This shows that while it may sound complex, you can arrive at the same conclusion using fewer ingredients.

--