➕Logic and Formal Reasoning Unit 4 – Propositional Logic: Equivalence & Validity

Key Concepts

• Propositional logic deals with propositions and their relationships using logical connectives
• Propositions are declarative sentences that can be either true or false, but not both simultaneously
• Logical connectives (operators) join propositions to create compound propositions
  • Common connectives include negation (not), conjunction (and), disjunction (or), implication (if-then), and biconditional (if and only if)
• Truth tables display all possible truth value combinations for a given set of propositions
  • Used to determine the truth value of compound propositions based on the truth values of their component propositions
• Logical equivalence occurs when two propositions have the same truth value for all possible truth value assignments of their component propositions
• Validity in propositional logic refers to the relationship between the premises and the conclusion of an argument
  • An argument is valid if and only if it is impossible for the premises to be true and the conclusion false
• Proof techniques, such as truth tables and logical equivalences, are used to establish the validity of arguments and the equivalence of propositions

Propositional Logic Basics

• Propositional logic is a branch of logic that studies the relationships between propositions using logical connectives
• Propositions are statements that can be either true (T) or false (F), but not both at the same time
  • Examples of propositions: "The sky is blue," "2 + 2 = 5"
• Propositional variables (usually represented by lowercase letters like p, q, r) are used to represent propositions
• Compound propositions are formed by combining propositions using logical connectives
  • Example: If p represents "It is raining" and q represents "I have an umbrella," then the compound proposition "If it is raining, then I have an umbrella" can be represented as $p \rightarrow q$
• The truth value of a compound proposition depends on the truth values of its component propositions and the logical connectives used

Logical Connectives

• Logical connectives are symbols used to join propositions to create compound propositions
• Negation (not): represented by $\neg$ or ~, it reverses the truth value of a proposition
  • Example: If p is true, then $\neg p$ is false
• Conjunction (and): represented by $\land$, it is true only when both propositions are true
  • Example: $p \land q$ is true only if both p and q are true
• Disjunction (or): represented by $\lor$, it is false only when both propositions are false
  • Example: $p \lor q$ is false only if both p and q are false
• Implication (if-then): represented by $\rightarrow$, it is false only when the antecedent (hypothesis) is true and the consequent (conclusion) is false
  • Example: $p \rightarrow q$ is false only if p is true and q is false
• Biconditional (if and only if): represented by $\leftrightarrow$, it is true when both propositions have the same truth value
  • Example: $p \leftrightarrow q$ is true if p and q are both true or both false

Truth Tables

• Truth tables are a systematic way to represent all possible truth value combinations for a given set of propositions
• Each row in a truth table represents a unique combination of truth values for the propositions involved
• The number of rows in a truth table is determined by $2^n$, where n is the number of distinct propositions
  • Example: A truth table for two propositions (p and q) will have $2^2 = 4$ rows
• Truth tables are used to determine the truth value of a compound proposition based on the truth values of its component propositions
  • Example: The truth table for $p \land q$ will have the value T only in the row where both p and q are T
• Constructing truth tables is a crucial skill in propositional logic, as they help in understanding the behavior of logical connectives and in determining logical equivalence and validity

Logical Equivalence

• Two propositions are logically equivalent if they have the same truth value for all possible truth value assignments of their component propositions
• Logical equivalence is denoted by the symbol $\equiv$
  • Example: $p \land q \equiv q \land p$ (commutativity of conjunction)
• Logical equivalences can be used to simplify complex propositions and to prove the validity of arguments
• Some common logical equivalences include:
  • De Morgan's Laws: $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$
  • Double Negation: $\neg(\neg p) \equiv p$
  • Conditional: $p \rightarrow q \equiv \neg p \lor q$
  • Biconditional: $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$
• Logical equivalences can be proven using truth tables by showing that the truth values of the propositions are the same for all possible truth value assignments

Validity in Propositional Logic

• An argument in propositional logic consists of a set of premises and a conclusion
• An argument is valid if and only if it is impossible for the premises to be true and the conclusion false
  • In other words, if the premises are true, the conclusion must also be true
• Validity is concerned with the structure of the argument, not the actual truth values of the propositions involved
  • Example: The argument "If it is raining, then the ground is wet. It is raining. Therefore, the ground is wet." is valid, regardless of whether it is actually raining or not
• Validity can be proven using truth tables by showing that there is no row in the truth table where the premises are true and the conclusion is false
• Validity is an essential concept in propositional logic, as it allows us to determine whether an argument is logically sound

Proof Techniques

• Proof techniques are methods used to establish the validity of arguments and the equivalence of propositions in propositional logic
• Truth tables are a common proof technique, where the truth values of the premises and conclusion are evaluated for all possible truth value assignments
  • If there is no row in the truth table where the premises are true and the conclusion is false, the argument is valid
• Logical equivalences can be used to prove the equivalence of propositions by transforming one proposition into another using known equivalences
  • Example: To prove $\neg(p \land q) \equiv \neg p \lor \neg q$, we can use De Morgan's Law
• Indirect proof (proof by contradiction) is a technique where we assume the negation of the conclusion and show that it leads to a contradiction with the premises
  • If a contradiction is found, the original conclusion must be true
• Proof by cases is a technique where we break down a proposition into different cases and prove each case separately
  • Example: To prove $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$, we can consider the cases where p is true and where p is false
• Mastering proof techniques is crucial for solving complex problems in propositional logic and for constructing valid arguments

Applications and Examples

• Propositional logic has numerous applications in various fields, such as computer science, mathematics, and philosophy
• In computer science, propositional logic is used in Boolean algebra, which is the foundation for digital circuit design
  • Example: The logical expression $(A \land B) \lor (\neg A \land C)$ can represent a digital circuit with three inputs (A, B, C) and one output
• Propositional logic is used in artificial intelligence and machine learning for knowledge representation and reasoning
  • Example: A simple expert system can use propositional logic to represent rules like "If the patient has a fever and a rash, then they have measles"
• In mathematics, propositional logic is used as a foundation for more advanced logical systems, such as first-order logic and modal logic
  • Example: The principle of mathematical induction can be formalized using propositional logic
• Philosophers use propositional logic to analyze and evaluate arguments in various domains, such as ethics, epistemology, and metaphysics
  • Example: The argument "If determinism is true, then there is no free will. Determinism is true. Therefore, there is no free will." can be evaluated using the tools of propositional logic
• Everyday reasoning can often be modeled using propositional logic, helping to clarify arguments and expose logical fallacies
  • Example: The argument "If you study hard, you will get good grades. You did not get good grades. Therefore, you did not study hard." is an example of the fallacy of denying the antecedent, which can be exposed using propositional logic