2. Discrete Mathematics

Hello everyone. Welcome to this lecture on logical equivalence. So, just a quick recap. In the last lecture we discussed about propositional logic, various logical operators. In this lecture, we will discuss about logical equivalence and logical identities.

This chunk serves as an introduction to the topic of logical equivalence, which is a fundamental concept in discrete mathematics. It connects to the previous lecture on propositional logic, where the basic logical operators were discussed. Logical equivalence deals with the relationship between two statements; if both statements yield the same truth value in every possible scenario, they are considered logically equivalent.

Think of logical equivalence like two different routes to the same destination. No matter which route you take, you will end up at the same place. Similarly, two logically equivalent statements lead to the same truth regardless of how you approach them.

So, remember if p then q is represented by p → q and truth table of p → q is this... The inverse of p → q is denoted by ¬ p → ¬ q and its truth table will be like this and the contrapositive which is very important for p → q will be the statement ¬ q → ¬ p.

In this chunk, we explore different forms of implications in logic. The implication 'if p then q' is denoted as p → q. The converse of this implication is q → p, while the inverse is ¬p → ¬q, and the contrapositive is ¬q → ¬p. Understanding these relationships is crucial because it highlights how the truth values interact among these forms, particularly that an implication and its contrapositive are logically equivalent.

Imagine a classroom scenario: 'If it is raining (p), then the ground is wet (q).' The contrapositive states, 'If the ground is not wet (¬q), then it is not raining (¬p).' Both statements convey the same truth, akin to how knowing someone is not at a party also suggests they did not receive an invitation.

Let me first define a bi conditional operator or a bi conditional statement which for which we use this notation ↔ that means an arrowhead which has an arrowhead at both ends. This bi conditional statement is used to represent statements of the form p if and only if q.

This chunk presents the bi-conditional operator, denoted as 'p if and only if q' or 'p ↔ q'. This statement holds true only when both p and q are either true or false simultaneously. The bi-conditional operator is essential for establishing conditions that are necessary and sufficient, indicating both sides of the statement support each other’s truth.

Consider a job requirement: 'You will get the job if and only if you pass the interview.' This means passing the interview is both necessary and sufficient to get the job. If you don’t pass, you won’t get the job, and if you do, you certainly will.

Now let us next define tautology, contradiction and contingency... whereas a contingency is a proposition, which is neither a tautology nor a contradiction that means it can be sometimes true it can be sometimes false.

In this chunk, we define three key concepts: tautology, contradiction, and contingency. A tautology is a statement that is always true, like 'p or not p.' A contradiction is always false, like 'p and not p.' A contingency can be true or false depending on the truth values of its components, like 'p and q,' which can vary based on the truth of p and q.

Imagine a light switch: if it’s always on regardless of anything else, that’s like a tautology. If it’s never on, that’s a contradiction. But if it can be either on or off, it’s akin to a contingency.

Now, we want to define what we call as logically equivalent statement... more formally X is logically equivalent to Y provided the X bi-implication Y is a tautology.

This chunk provides a formal definition of logical equivalence between two statements X and Y. If their bi-implication (X ↔ Y) is a tautology, they are considered logically equivalent. This means they will both yield the same truth value in all scenarios.

Think of two different recipes for the same dish. If both recipes result in the same cuisine with identical taste, they are equivalent in outcome, even if the ingredients differ. Similarly, logically equivalent statements yield the same truth value.

There are various standard logical equivalent statements which are available... Well, we can verify using the truth table method namely we can draw, we can construct a truth table of the left hand side of the expression.

In this chunk, several standard logical identities are introduced. These identities, such as De Morgan's laws and distribution laws, allow us to simplify logical expressions. While truth tables can validate these identities for smaller cases, larger expressions require using these established identities for practical verification.

Consider using mathematical identities to simplify an algebraic expression. Just as you would apply the distributive property or combine like terms to make calculations easier, logical identities streamline the verification of complex logical statements.

So now let us do an example here... So that brings me to the end of this lecture.

In this chunk, an example is presented demonstrating how to prove that two expressions are logically equivalent without using a truth table. By applying various logical identities step by step, the conversion from expression X to expression Y illustrates the process significantly and showcases the application of the logical identities discussed earlier.

Imagine a puzzle where you need to rearrange pieces to form a complete picture. Each logical identity serves as a guideline on how to reposition those pieces (or logical statements) until the image (or conclusion) is complete.

--