2.1 Statements

Symbolic logic involves the use of symbols and formal systems to represent logical statements and their relationships. This approach provides a clear and precise way to analyze logical expressions and arguments. Here’s a summary of key concepts and symbols used in symbolic logic:

1. Basic Logical Connectives

1. Conjunction (AND)
   • Symbol: $\wedge$
   • Definition: The statement $P\wedge Q$ is true if both $P$ and $Q$ are true.
   • Truth Table:
     

     $P$	$Q$	$P\wedge Q$
     T	T	T
     T	F	F
     F	T	F
     F	F	F

2. Disjunction (OR)
   • Symbol: $\vee$
   • Definition: The statement $P\vee Q$ is true if at least one of $P$ or $Q$ is true.
   • Truth Table:
     

     $P$	$Q$	$P\vee Q$
     T	T	T
     T	F	T
     F	T	T
     F	F	F

3. Negation (NOT)
   • Symbol: $\neg$ or $\sim$
   • Definition: The statement $\neg P$ is true if $P$ is false, and vice versa.
   • Truth Table:
     

     $P$	$\neg P$
     T	F
     F	T

4. Implication (IF… THEN…)
   • Symbol: $\to$
   • Definition: The statement $P\to Q$ (if $P$ then $Q$) is true if $P$ is false or $Q$ is true (or both).
   • Truth Table:
     

     $P$	$Q$	$P\to Q$
     T	T	T
     T	F	F
     F	T	T
     F	F	T

5. Biconditional (IF AND ONLY IF)
   • Symbol: $\leftrightarrow$
   • Definition: The statement $P\leftrightarrow Q$ is true if $P$ and $Q$ have the same truth value (both true or both false).
   • Truth Table:
     

     $P$	$Q$	$P\leftrightarrow Q$
     T	T	T
     T	F	F
     F	T	F
     F	F	T

2. Quantifiers

1. Universal Quantifier
   • Symbol: $\forall$
   • Definition: Indicates that a statement is true for all elements in a domain.
   • Example: $\forall x(P(x))$ means “For all $x$, $P(x)$ is true.”
2. Existential Quantifier
   • Symbol: $\exists$
   • Definition: Indicates that there exists at least one element in a domain for which the statement is true.
   • Example: $\exists x(P(x))$ means “There exists an $x$ such that $P(x)$ is true.”

3. Logical Equivalence

• Definition: Two statements are logically equivalent if they have the same truth value in all possible scenarios.
• Symbol: $\equiv$
• Example: $P\to Q\equiv \neg P\vee Q$

4. De Morgan’s Laws

• Definition: Provide rules for transforming negations of conjunctions and disjunctions.
• Laws:
  • Negation of Conjunction: $\neg (P\wedge Q)\equiv \neg P\vee \neg Q$
  • Negation of Disjunction: $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$

2.2 Compound statements and their truth values

Compound statements in logic are formed by combining simpler statements using logical connectives such as AND ($\wedge$), OR ($\vee$), NOT ($\neg$), IMPLIES ($\to$), and IF AND ONLY IF ($\leftrightarrow$). The truth value of a compound statement depends on the truth values of its component statements and the logical connectives used.

1. Truth Tables for Compound Statements

To determine the truth value of a compound statement, we use truth tables. A truth table lists all possible truth values for the component statements and calculates the truth value of the compound statement for each combination.

Example of Compound Statements

1. Conjunction (AND)
   • Statement: $P\wedge Q$
   • Truth Table:
     

     $P$	$Q$	$P\wedge Q$
     T	T	T
     T	F	F
     F	T	F
     F	F	F

   Explanation: $P\wedge Q$ is true only when both $P$ and $Q$ are true.

2. Disjunction (OR)
   • Statement: $P\vee Q$
   • Truth Table:
     

     $P$	$Q$	$P\vee Q$
     T	T	T
     T	F	T
     F	T	T
     F	F	F

   Explanation: $P\vee Q$ is true if at least one of $P$ or $Q$ is true.

3. Negation (NOT)
   • Statement: $\neg P$
   • Truth Table:
     

     $P$	$\neg P$
     T	F
     F	T

   Explanation: $\neg P$ is true when $P$ is false, and false when $P$ is true.

4. Implication (IF… THEN…)
   • Statement: $P\to Q$
   • Truth Table:
     

     $P$	$Q$	$P\to Q$
     T	T	T
     T	F	F
     F	T	T
     F	F	T

   Explanation: $P\to Q$ is false only when $P$ is true and $Q$ is false.

5. Biconditional (IF AND ONLY IF)
   • Statement: $P\leftrightarrow Q$
   • Truth Table:
     

     $P$	$Q$	$P\leftrightarrow Q$
     T	T	T
     T	F	F
     F	T	F
     F	F	T

   Explanation: $P\leftrightarrow Q$ is true if $P$ and $Q$ have the same truth value.

2. Combining Compound Statements

When dealing with compound statements involving multiple connectives, you evaluate them based on the order of operations, which typically follows these rules:

1. Negations are evaluated first.
2. Conjunctions and Disjunctions are evaluated next, with conjunctions ($\wedge$) being evaluated before disjunctions ($\vee$).
3. Implications and Biconditionals are evaluated last.

Example of a Compound Statement

Statement: $(P\wedge Q)\to (R\vee \neg S)$

Truth Table:

2.3 Logical connectives

Logical connectives (also known as logical operators) are symbols used to connect statements or propositions in logic. They help in forming compound statements and determining their truth values based on the truth values of the individual components. Here’s an overview of the primary logical connectives:

1. Conjunction (AND)

• Symbol: $\wedge$
• Definition: The conjunction of two statements $P$ and $Q$, written as $P\wedge Q$, is true if and only if both $P$ and $Q$ are true.
• Truth Table:
  

  $P$	$Q$	$P\wedge Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	F

2. Disjunction (OR)

• Symbol: $\vee$
• Definition: The disjunction of two statements $P$ and $Q$, written as $P\vee Q$, is true if at least one of $P$ or $Q$ is true.
• Truth Table:
  

  $P$	$Q$	$P\vee Q$
  T	T	T
  T	F	T
  F	T	T
  F	F	F

3. Negation (NOT)

• Symbol: $\neg$ or $\sim$
• Definition: The negation of a statement $P$, written as $\neg P$, is true if $P$ is false, and false if $P$ is true.
• Truth Table:
  

  $P$	$\neg P$
  T	F
  F	T

4. Implication (IF… THEN…)

• Symbol: $\to$
• Definition: The implication $P\to Q$ means “if $P$ then $Q$“. It is false only when $P$ is true and $Q$ is false; otherwise, it is true.
• Truth Table:
  

  $P$	$Q$	$P\to Q$
  T	T	T
  T	F	F
  F	T	T
  F	F	T

5. Biconditional (IF AND ONLY IF)

• Symbol: $\leftrightarrow$
• Definition: The biconditional $P\leftrightarrow Q$ means ” $P$ if and only if $Q$“. It is true if $P$ and $Q$ have the same truth value (both true or both false).
• Truth Table:
  

  $P$	$Q$	$P\leftrightarrow Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	T

6. Exclusive OR (XOR)

• Symbol: $\oplus$
• Definition: The exclusive OR (XOR) of two statements $P$ and $Q$, written as $P\oplus Q$, is true if exactly one of $P$ or $Q$ is true.
• Truth Table:
  

  $P$	$Q$	$P\oplus Q$
  T	T	F
  T	F	T
  F	T	T
  F	F	F

2.4. Algebra of statements

The algebra of statements (also known as Boolean algebra) deals with the manipulation and simplification of logical statements using algebraic methods. It provides a set of rules and operations for combining and transforming logical expressions. Here’s an overview of the key concepts and properties involved:

1. Basic Operations and Laws

1.1 Conjunction (AND)

• Symbol: $\wedge$
• Definition: Combines two statements; true if both are true.

1.2 Disjunction (OR)

• Symbol: $\vee$
• Definition: Combines two statements; true if at least one is true.

1.3 Negation (NOT)

• Symbol: $\neg$ or $\sim$
• Definition: Inverts the truth value of a statement.

1.4 Implication (IF… THEN…)

• Symbol: $\to$
• Definition: The statement $P\to Q$ is false only when $P$ is true and $Q$ is false.

1.5 Biconditional (IF AND ONLY IF)

• Symbol: $\leftrightarrow$
• Definition: True if both statements have the same truth value.

1.6 Exclusive OR (XOR)

• Symbol: $\oplus$
• Definition: True if exactly one of the statements is true.

2. Laws of Boolean Algebra

2.1 Identity Laws

• Conjunction: $P\wedge \text{True}=P$
• Disjunction: $P\vee \text{False}=P$

2.2 Null Laws

• Conjunction: $P\wedge \text{False}=\text{False}$
• Disjunction: $P\vee \text{True}=\text{True}$

2.3 Domination Laws

• Conjunction: $P\wedge \text{True}=P$
• Disjunction: $P\vee \text{False}=P$

2.4 Idempotent Laws

• Conjunction: $P\wedge P=P$
• Disjunction: $P\vee P=P$

2.5 Complement Laws

• Conjunction: $P\wedge \neg P=\text{False}$
• Disjunction: $P\vee \neg P=\text{True}$

2.6 Double Negation

• Definition: $\neg (\neg P)=P$

2.7 Distributive Laws

• Conjunction over Disjunction: $P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)$
• Disjunction over Conjunction: $P\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)$

2.8 De Morgan’s Laws

• First Law: $\neg (P\wedge Q)=\neg P\vee \neg Q$
• Second Law: $\neg (P\vee Q)=\neg P\wedge \neg Q$

2.9 Absorption Laws

• First Law: $P\vee (P\wedge Q)=P$
• Second Law: $P\wedge (P\vee Q)=P$

3. Examples and Applications

Simplification Example Simplify the expression $(P\vee Q)\wedge (\neg P\vee R)$:

1. Apply Distributive Law: $$(P\vee Q)\wedge (\neg P\vee R)=[(P\wedge \neg P)\vee (P\wedge R)]\vee [(Q\wedge \neg P)\vee (Q\wedge R)]$$
2. Apply Complement Law $P\wedge \neg P=\text{False}$: $$(P\wedge R)\vee [(Q\wedge \neg P)\vee (Q\wedge R)]$$
3. Combine like terms: $$(P\wedge R)\vee (Q\wedge \neg P)\vee (Q\wedge R)$$
4. Combine terms using Absorption Law: $$(P\wedge R)\vee (Q\wedge \neg P)\vee (Q\wedge R)=(P\wedge R)\vee (Q\wedge \neg P)\vee (Q\wedge R)=(P\vee Q)\wedge (R\vee \neg P)$$

4. Applications

• Digital Circuit Design: Boolean algebra is fundamental in designing and simplifying digital circuits.
• Search Algorithms: Used in query processing and database search operations.
• Error Detection and Correction: Boolean logic is used in coding theory to detect and correct errors in data transmission.
• Logical Reasoning: Helps in formalizing and solving problems in logic, mathematics, and computer science.

2.5 Equivalent statements

Equivalent statements are logical statements or propositions that have the same truth value in every possible scenario. In other words, two statements are considered equivalent if they are true or false under the same conditions. Logical equivalence is a fundamental concept in logic and Boolean algebra.

1. Definition of Logical Equivalence

Two statements $P$ and $Q$ are logically equivalent if $P\leftrightarrow Q$ (P if and only if Q) is always true, meaning $P$ and $Q$ have the same truth value in all possible scenarios.

2. Examples of Equivalent Statements

1. De Morgan’s Laws
   • First Law: $\neg (P\wedge Q)\equiv \neg P\vee \neg Q$
   • Second Law: $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$

   Explanation: These laws show how negations distribute over conjunctions and disjunctions, respectively.

2. Distributive Laws
   • Conjunction over Disjunction: $P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)$
   • Disjunction over Conjunction: $P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee R)$

   Explanation: These laws express how conjunction and disjunction distribute over each other.

3. Absorption Laws
   • First Law: $P\vee (P\wedge Q)\equiv P$
   • Second Law: $P\wedge (P\vee Q)\equiv P$

   Explanation: These laws show that certain expressions can be simplified by absorbing redundant terms.

4. Double Negation
   • Law: $\neg (\neg P)\equiv P$

   Explanation: This law states that negating a negated statement returns the original statement.

5. Contrapositive
   • Law: $P\to Q\equiv \neg Q\to \neg P$

   Explanation: The contrapositive of an implication is logically equivalent to the original implication.

6. Material Implication
   • Law: $P\to Q\equiv \neg P\vee Q$

   Explanation: An implication can be expressed as a disjunction where the antecedent is negated.

3. Proof of Equivalence

To prove that two statements are equivalent, you can use truth tables, logical laws, or algebraic manipulation.

Example: Prove that $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$ using a truth table.

Truth Table:

The columns for $\neg (P\vee Q)$ and $\neg P\wedge \neg Q$ are identical, demonstrating that the two statements are logically equivalent.

2.6 Conditional and bi-conditional statements

Conditional and bi-conditional statements are fundamental concepts in logic, used to express relationships between statements and their truth values.

1. Conditional Statements

Conditional Statement (also known as an implication) expresses a relationship where one statement implies another. It has the general form:

$P\to Q$

where $P$ is the antecedent (or hypothesis) and $Q$ is the consequent (or conclusion).

Truth Table for Conditional Statements

The truth value of $P\to Q$ (if $P$ then $Q$) can be summarized as follows:

Explanation:

• $P\to Q$ is false only when $P$ is true and $Q$ is false.
• In all other cases (when $P$ is false or $Q$ is true), the implication is true.

Examples

1. Example: “If it rains (P), then the ground will be wet (Q).”
   • Conditional Statement: $P\to Q$
   • If it rains and the ground is wet, the statement is true.
   • If it rains but the ground is not wet, the statement is false.
   • If it does not rain, the statement is true regardless of the ground’s condition.

2. Bi-Conditional Statements

Bi-Conditional Statement (also known as equivalence) asserts that two statements are logically equivalent; both are true or both are false. It has the general form:

$P\leftrightarrow Q$

This is read as “P if and only if Q” (often abbreviated as “P iff Q”).

Truth Table for Bi-Conditional Statements

The truth value of $P\leftrightarrow Q$ can be summarized as follows:

Explanation:

• $P\leftrightarrow Q$ is true if both $P$ and $Q$ have the same truth value (both true or both false).
• It is false if $P$ and $Q$ have different truth values.

Examples

1. Example: “The light is on (P) if and only if the switch is up (Q).”
   • Bi-Conditional Statement: $P\leftrightarrow Q$
   • The light being on and the switch being up means the statement is true.
   • The light being off and the switch being down also makes the statement true.
   • Any mismatch between the light and the switch position means the statement is false.

3. Comparison Between Conditional and Bi-Conditional Statements

• Conditional Statement ($P\to Q$):
  • Expresses a one-way implication.
  • True unless the antecedent is true and the consequent is false.
• Bi-Conditional Statement ($P\leftrightarrow Q$):
  • Expresses mutual implication.
  • True only if both statements share the same truth value.

4. Applications

• Proofs and Reasoning: Conditional and bi-conditional statements are used to construct logical arguments and proofs.
• Computer Science: Conditional statements are fundamental in programming for control flow (e.g., if-else statements).
• Mathematics: Used to define equivalences and implications in mathematical theorems and definitions.

2.7 Tautology and contradictions

Tautologies and contradictions are key concepts in logic that describe the nature of statements based on their truth values.

1. Tautology

A tautology is a logical statement or proposition that is true in every possible scenario, regardless of the truth values of its components. In other words, a tautology is always true.

Examples of Tautologies

1. Simple Example:
   • Statement: $P\vee \neg P$
   • Explanation: This is the law of excluded middle. It states that either a proposition $P$ is true, or its negation $\neg P$ is true. Thus, $P\vee \neg P$ is always true.
2. Complex Example:
   • Statement: $(P\to Q)\vee (Q\to P)$
   • Truth Table:
     

     $P$	$Q$	$P\to Q$	$Q\to P$	$(P\to Q)\vee (Q\to P)$
     T	T	T	T	T
     T	F	F	T	T
     F	T	T	F	T
     F	F	T	T	T

   • Explanation: In every possible combination of $P$ and $Q$, the statement $(P\to Q)\vee (Q\to P)$ is true, hence it is a tautology.

2. Contradiction

A contradiction is a logical statement or proposition that is false in every possible scenario, regardless of the truth values of its components. In other words, a contradiction is always false.

Examples of Contradictions

1. Simple Example:
   • Statement: $P\wedge \neg P$
   • Explanation: This is a direct application of the law of non-contradiction. A statement and its negation cannot both be true simultaneously. Thus, $P\wedge \neg P$ is always false.
2. Complex Example:
   • Statement: $(P\wedge Q)\wedge \neg (P\wedge Q)$
   • Truth Table:
     

     $P$	$Q$	$P\wedge Q$	$\neg (P\wedge Q)$	$(P\wedge Q)\wedge \neg (P\wedge Q)$
     T	T	T	F	F
     T	F	F	T	F
     F	T	F	T	F
     F	F	F	T	F

   • Explanation: In every possible combination of $P$ and $Q$, the statement $(P\wedge Q)\wedge \neg (P\wedge Q)$ is false, hence it is a contradiction.

3. Application and Importance

• Tautologies:
  • Used to validate logical arguments or proofs. If a statement is a tautology, it is always valid.
  • In circuit design, tautologies ensure that certain conditions are always met.
• Contradictions:
  • Used to identify logical inconsistencies. If a system leads to a contradiction, it means that there is an error or inconsistency in the system.
  • In proofs, deriving a contradiction from assumptions can be used to demonstrate that the assumptions are false (proof by contradiction).

2.8 Arguments and the test of their validity

Arguments in logic involve a set of statements where one or more statements (premises) are used to support another statement (conclusion). The validity of an argument depends on the logical structure of the premises and conclusion: an argument is valid if the conclusion logically follows from the premises.

1. Structure of an Argument

An argument typically consists of:

• Premises: Statements or propositions that provide support or evidence for the conclusion.
• Conclusion: The statement that is being supported or proven based on the premises.

2. Validity of an Argument

An argument is considered valid if and only if, assuming the premises are true, the conclusion must also be true. Validity concerns the logical structure of the argument rather than the actual truth of the premises.

Forms of Valid Arguments

1. Deductive Arguments
   • Definition: An argument where the truth of the premises guarantees the truth of the conclusion.
   • Example:
     • Premise 1: All humans are mortal.
     • Premise 2: Socrates is a human.
     • Conclusion: Socrates is mortal.
   • Explanation: If the premises are true, the conclusion must also be true. This is a valid deductive argument.
2. Inductive Arguments
   • Definition: An argument where the premises provide some level of support for the conclusion but do not guarantee it. Inductive arguments can be strong or weak.
   • Example:
     • Premise: Every swan I have seen is white.
     • Conclusion: All swans are white.
   • Explanation: The conclusion is not guaranteed by the premises but is supported by them. This argument is inductively strong if it is based on a large sample size.

3. Testing the Validity of Arguments

1. Truth Tables:

• Description: Used to evaluate the validity of logical arguments by listing all possible truth values of the premises and checking whether the conclusion follows logically.
• Example: To test the validity of $P\to Q$ and $P$, therefore $Q$:
  • Construct a truth table with $P$, $Q$, $P\to Q$, and $Q$.
  • Verify that whenever $P\to Q$ and $P$ are true, $Q$ must also be true.

2. Formal Proofs:

• Description: Use formal systems or rules of inference (e.g., modus ponens, modus tollens) to derive the conclusion from the premises.
• Example: Using modus ponens:
  • Premise 1: If $P$, then $Q$ ($P\to Q$).
  • Premise 2: $P$.
  • Conclusion: $Q$.

3. Venn Diagrams:

• Description: Used to visualize logical relationships and determine the validity of arguments involving categorical statements.
• Example: To test the validity of arguments involving categories like “All A are B,” “No A are C,” etc.

4. Counterexamples:

• Description: Find a counterexample where the premises are true but the conclusion is false. If such a counterexample exists, the argument is invalid.
• Example: To show an argument is invalid, provide a situation where the premises are true but the conclusion does not follow.

4. Validity vs. Soundness

• Validity: Refers to the logical structure of the argument. A valid argument is one where, if the premises are true, the conclusion must be true.
• Soundness: Refers to both validity and the actual truth of the premises. A sound argument is a valid argument with true premises, which ensures the conclusion is also true.