7.8.1. Verification of Valid Argument

So here we want to prove that the set of these three operators is functionally complete. That means any compound proposition you can represent just by using these three operators.

In logic, certain sets of operators can be combined to create any statement (compound proposition) you need. To show that a set of operators is complete, you must demonstrate that you can construct any logical expression using only those operators. Here, we consider three operators: conjunction (AND), disjunction (OR), and negation (NOT). If we can express all possible logical expressions with just these, the set is deemed functionally complete.

Think of it like using a basic toolset to build anything you want. Just as a hammer, screwdriver, and wrench can accomplish a wide variety of tasks if used creatively, these three logical operators can create any logical statement.

If I am given a proposition which indeed involves only these three operators, I do not have to do anything. But 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.

In logic, the implication (p → q) can be transformed into an expression involving disjunction and negation. Specifically, it can be rewritten as ‘not p or q’ (¬p ∨ q). This transformation allows us to eliminate any instance of implication by substituting it with this equivalent form, thus relying solely on our original three operators.

Imagine if someone said, 'If it rains, then the ground will be wet.' You can rephrase this as 'Either it doesn’t rain, or the ground is wet.' This is like changing how you deliver news but maintaining the same meaning.

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 biconditional statement (p ↔ q) can also be expressed using combinations of other logical operators. Specifically, it can be reformed into two implications: (p → q) AND (q → p). Thus, we can replace biconditional expressions with a combination of conjunctions and implications, which we already know how to convert into our basic set of operators.

Consider 'You can pass this test if and only if you study.' This can be broken down into two statements: 'If you study, then you’ll pass,' and 'If you pass, then you must have studied.' Just like recounting a story in different ways while keeping the plot intact.

What I have to do now is how do I represent even a conjunction, namely a proposition where conjunction is involved by an equivalent proposition where I have just occurrences of disjunction and negation.

To represent a conjunction (AND operation) using only disjunction (OR) and negation (NOT), you can apply De Morgan's laws. For example, the conjunction p AND q can be rewritten as 'not (not p or not q)'. This allows us to express all conjunctions while remaining within the constraints of using only disjunction and negation.

It's like saying, 'You can’t be both happy and sad at the same time' can be transformed into 'It is not the case that you are either not happy or not sad.' This keeps the core meaning while using different structural elements.

So that shows that if you have these two operators namely disjunction and negation, you can represent any statement, any compound proposition and hence this is a functionally complete set of logical operators.

By proving that both conjunction and negation can be represented solely with disjunction and negation, we see that this combination is also functionally complete. Therefore, having just these two operators is sufficient to express any logical statement, which emphasizes their functional depth and versatility.

Think of it as having just a saw and a hammer — with enough creativity, you can build any wood structure without needing a full toolbox. Just like in logic, even a couple of operators can cover a vast scope of logical expressions.

The third part now says that you have to show that only the negation operator and the conjunction operator are functionally complete.

To prove that just negation and conjunction can be functional complete, we show how we can produce a disjunction (OR) with these operators. For instance, p OR q can be rewritten using negation and conjunction. Following similar transformation rules will conclude that all expressions can be achieved with only these two operators.

Imagine needing to get coffee. You can get coffee if it’s hot, and if it’s not, you make an espresso instead. This illustrates how two tools (hot coffee or espresso) are enough to achieve your goal of having coffee.

--