7.1. Discrete Mathematics

We 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. So the first part of question 8 asks you the following. 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, so how do we prove this? Well if I am given a proposition which indeed involves only these three operators, I do not have to do anything.

This chunk explains the concept of functional completeness in logical operators. A set of operators is considered functionally complete if any logical expression can be formed using just those operators. To illustrate, if we are only using conjunction (AND), disjunction (OR), and negation (NOT), we can create any other logical expressions, including implications and biconditionals. This is vital for defining logical systems where we want to build complex statements from basic building blocks.

Imagine you're trying to construct a house. The three logical operators (AND, OR, NOT) are like your basic building materials — bricks, wood, and nails. Just as you can use these materials to build any kind of house (a simple one or a complex mansion), you can use these logical operators to create any logical statement. If you need to create a new room (logical statement), you know that with these materials, you can achieve whatever you want.

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 and I can substitute p → q by this RHS expression. And by applying this rule repeatedly wherever I have an occurrence of implication I can remove those implications and I will now have an equivalent formula where everything is represented only in terms of conjunction, disjunction and negation.

This chunk dives into how to handle implications in logical expressions. An implication like 'if p then q' (p → q) can be rewritten in terms of disjunctions and negations. Specifically, it's equivalent to saying 'not p or q' (¬p ∨ q). This substitution allows us to express any logical statement using only conjunctions, disjunctions, and negations, reinforcing the functional completeness of our initial operators.

Think of this process as translating a sentence from one language to another. For example, the implication 'If it rains (p), then the ground will be wet (q)' can be translated to 'Either it does not rain (¬p) or the ground is wet (q)'. Just as a translator can convey the same meaning using different phrases, we can express logical relationships in various ways using fundamental operators.

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 and I know that each individual implication can be replaced by these two sub expressions.

Here, the chunk explains how to handle biconditional statements, often represented by the symbol '↔'. A biconditional like 'p if and only if q' (p ↔ q) can be broken down into two implications: 'p → q' and 'q → p'. By converting each of these implications into disjunctions of negations, we maintain the essential logical relationships while sticking to our base operators.

Consider a two-way street where cars can go both directions: if car A goes to point B, it means car B is coming from B to A. The biconditional (if and only if) captures this mutual relationship. By understanding each direction separately, we can still demonstrate the same route, much like decomposing the biconditional into separate implications.

So what I have to do is from the first part of the question, I know that if you have an occurrence of implication you can represent them by just using negation and disjunction, this is what we have shown. What we have to now worry about 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.

This segment addresses how to express conjunctions using only disjunction and negation. It highlights that conjunctions can also be represented through these operators. For example, 'p AND q' can be reshaped into 'NOT (p is not true OR q is not true)', which precisely retains the original logical meaning. This confirms that even with limited operators (just negation and disjunction), we can build any required logical expression.

Imagine organizing a party. You can say 'We will only have the party if it is not raining and the invitations are sent out'. This means both conditions must be met together, which can be expressed in another way: 'It is not true that either it is raining or the invitations are not sent out'. This highlights how we can shift the perspective of logical conditions while maintaining the same meaning.

So now you can see that my original expression is converted into an expression where every operator is either conjunction, disjunction and negation. So that shows that if you have these three operators namely a conjunction, disjunction and negation, you can represent any statement, any compound proposition and hence this is a functionally complete set of logical operators.

In conclusion, this chunk summarizes the findings regarding the functionally complete set of operators. It asserts that any compound proposition can be constructed using just conjunction, disjunction, and negation. This proves their completeness as logical operators in formal logic, capable of expressing all necessary logical relationships.

Think of a powerful toolbox — if you have a hammer, screwdriver, and wrench, you can perform nearly any repair around the house. Similarly, having conjunction, disjunction, and negation means we have all the essential tools to construct any logical statement in discrete mathematics.

--