7.5.2. Tautology Implication

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 that any logical statement (or compound proposition) can be built using only these operators. For example, with the operators AND, OR, and NOT, we can express any logical statement without any other operators. This property is fundamental in logic as it ensures we can represent complex logical expressions in their simplest forms.

Think of functional completeness like basic ingredients to a recipe. If you have flour, sugar, and eggs, you can make a cake. These ingredients are sufficient to create the cake, just like the logical operators are enough to form 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.

If we encounter an implication in a logical statement, we can replace it with a different expression. The implication 'p → q' can be expressed as 'not p or q' (¬p ∨ q). This means that we can rewrite any logical expression involving implications entirely in terms of AND, OR, and NOT, which helps in simplifying or analyzing the logic.

Imagine you're making a decision: 'If it rains (p), then I will take an umbrella (q).' If it doesn't rain (¬p), you indeed don't need an umbrella. So, the statement can also be viewed as: 'It's either not raining or I have my umbrella.' This shows how one statement leads to another logically.

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 'p ↔ q' means that p is true if and only if q is true. This can be expressed as two separate implications: 'p → q' and 'q → p'. Hence, we combine these implications using AND (conjunction) to yield 'p and q' or their negations. This transformation allows us to express the bi-implication using only the logical operators we have.

Consider a situation where you only go to a concert if you have a ticket, and you can only get a ticket if you're going to the concert. This means both events are dependent on each other, reflecting the nature of a bi-implication.

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.

To express a conjunction (like 'p and q') solely in terms of disjunction and negation, we can use De Morgan's Laws. Specifically, 'p and q' can be rewritten as 'not (not p or not q)'. Therefore, even though 'and' is not directly used, we can still express it by manipulating the structure of the formula using the allowed operators.

Imagine you need to pass two exams to graduate. Instead of saying, 'I passed both exams,' we might say, 'It is not the case that I did not pass exam 1 or I did not pass exam 2.' This reflects a conjunction, but framed in a negative context.

So that shows that just your negation operator and disjunction operator are functionally complete.

This demonstrates that with just two logical operators, negation (NOT) and disjunction (OR), we can represent any logical expression, even those involving conjunctions. This concept of functional completeness is crucial since it simplifies calculations and expressions in logical systems.

Think of this like a flashlight and a color filter. Even with just these two items, you can create a variety of light effects to convey different environments or moods. Similarly, with negation and disjunction, we can represent any logical scenario.

--