Question

Give a simplified form of each of the following expressions (using T to stand for a statement that is always true and F to stand for a statement that is always false). \({ }^{4}\) a. \(s \vee s\) b. \(s \wedge s\) c. \(s \vee \neg s\) d. \(s \wedge \neg s\)

Short answer

a. \(s\), b. \(s\), c. \(T\), d. \(F\)

Step-by-step solution

Simplifying a Logical OR with Itself

The expression given is \( s \vee s \). According to the idempotent law in logical expressions, any proposition OR-ed with itself simplifies to just that proposition. Therefore, \( s \vee s = s \).

Simplifying a Logical AND with Itself

The expression given is \( s \wedge s \). Using the idempotent law, any proposition AND-ed with itself simplifies to that proposition. Hence, \( s \wedge s = s \).

Identifying a Tautology

The expression is \( s \vee eg s \). This represents a tautology because either \( s \) is true or \( eg s \) (not \( s \)) is true, covering all possible cases. Thus, \( s \vee eg s = T \).

Identifying a Contradiction

The expression is \( s \wedge eg s \). This is a contradiction because \( s \) and \( eg s \) cannot be true at the same time. Hence, \( s \wedge eg s = F \).

Key concepts

Idempotent Law

The Idempotent Law is a principle in logic and mathematics that simplifies expressions involving repeated terms. In logical expressions, this law states that any statement OR-ed or AND-ed with itself results in the statement itself. Let's explore the implications of this simple yet powerful law.
For any statement or proposition \(s\):

• The expression \(s \vee s\) simplifies to \(s\). Here, using OR with itself does not change the statement.
• Similarly, the expression \(s \wedge s\) also simplifies to \(s\). When AND-ed with itself, the statement remains unchanged.

This law helps in reducing the complexity of logical expressions by removing redundancy, making them easier to handle and understand.

Tautology

In logic, a tautology is a statement that is always true, no matter what the truth values of its components are. Tautologies are crucial in validating arguments because they represent universally true statements.
You can identify a tautology through logical expressions where the outcome is always true.
For example:

• The statement \(s \vee eg s\) is a classical tautology. This says either \(s\) is true or its negation \(eg s\) is true.
• Thus, no matter the truth value of \(s\), the expression results in a true statement.

Tautologies simplify the evaluation of logical structures by providing certainty in truth, essential for constructing logical proof frameworks.

Contradiction

Contradictions in logical terms refer to statements that are always false, regardless of the truth values of their constituent parts. Identifying contradictions is important in logic as they signal inconsistency and the impossibility of certain conditions being true simultaneously.
Consider the logical expression:

• \(s \wedge eg s\), which is a contradiction.
• Here, \(s\) and its negation \(eg s\) cannot both be true at the same time.

This results in the entire expression being false. In logical reasoning, detecting contradictions helps ensure the consistency and validity of arguments.

Discrete Mathematics

Discrete Mathematics is a field of mathematics dealing with distinct and separate values. Unlike continuous mathematics which involves calculus and real numbers, discrete mathematics encompasses topics such as graph theory, combinatorics, and logic.
Logical expressions, including concepts like idempotent law, tautologies, and contradictions, play a pivotal role in discrete mathematics.
The study of these concepts offers:

• Tools to simplify complex logical expressions, enhancing computational efficiency.
• A foundation for reasoning in computer science, including algorithm design and data structures.

Furthermore, discrete mathematics forms the backbone of disciplines like cryptography, network modeling, and decision algorithms, making it an invaluable area of study.