Mathematics Foundations/2.1 Propositional Logic

2.1 Propositional Logic Introduction Propositional logic (also called propositional calculus or sentential logic) is the branch of logic that studies ways of combining propositions to form more complex propositions, as well as analyzing their logical relationships and properties. A proposition is a declarative statement that is either true or false, but not both. Basic Components Propositions A proposition is a declarative statement that has a truth value (either true or false). Examples of propositions: "The sky is blue." "Paris is the capital of France." "2 + 2 = 5." Non-examples (not propositions): "Is it raining?" (interrogative) "Close the door!" (imperative) "x + 3 = 7" (contains a variable, truth depends on the value of x) Propositional Variables We typically denote simple propositions with lowercase letters such as p, q, r, etc. These are called propositional variables or atomic propositions. Logical Operators Propositional logic uses several logical operators (also called logical connectives) to form compound propositions: Negation (NOT) The negation of a proposition p is denoted by or , and is read as "not p." The truth value of is the opposite of the truth value of p. Truth Table for Negation: + Negation p T F F T Conjunction (AND) The conjunction of propositions p and q is denoted by , and is read as "p and q." The conjunction is true only when both p and q are true. Truth Table for Conjunction: + Conjunction p q T T T T F F F T F F F F Disjunction (OR) The disjunction of propositions p and q is denoted by , and is read as "p or q." The disjunction is true when at least one of p or q is true. Truth Table for Disjunction: + Disjunction p q T T T T F T F T T F F F Conditional (Implication) The conditional statement "if p then q" is denoted by , and is read as "p implies q" or "if p then q." It is false only when p is true and q is false. Truth Table for Conditional: + Conditional p q T T T T F F F T T F F T Biconditional (Equivalence) The biconditional statement is denoted by , and is read as "p if and only if q." It is true when p and q have the same truth value. Truth Table for Biconditional: + Biconditional p q T T T T F F F T F F F T Compound Propositions By combining propositional variables with logical operators, we can create compound propositions. For example: Precedence of Logical Operators When multiple logical operators appear in a compound proposition, the order of operations is: Negation () Conjunction () and Disjunction () Conditional () and Biconditional () Parentheses can be used to override this precedence. Truth Tables A truth table is a systematic way to determine the truth value of a compound proposition for all possible combinations of truth values of its component propositions. Example: Construct a truth table for + Truth table for p q r T T T T F F T T F T T T T F T F F T T F F F T T F T T F F T F T F F T T F F T F F T F F F F T T Logical Equivalence Two compound propositions are logically equivalent if they have the same truth value for all possible combinations of truth values of their component propositions. We denote logical equivalence by . Important Logical Equivalences Double Negation: De Morgan's Laws: Conditional Equivalences: (Contrapositive) Biconditional Equivalence: Distributive Laws: Tautologies, Contradictions, and Contingencies Tautology A tautology is a compound proposition that is always true, regardless of the truth values of its component propositions. Examples: (Law of Excluded Middle) Contradiction A contradiction is a compound proposition that is always false, regardless of the truth values of its component propositions. Examples: (Law of Non-Contradiction) Contingency A contingency is a compound proposition that is neither a tautology nor a contradiction; its truth value depends on the truth values of its component propositions. Examples: Applications in Mathematics Propositional logic forms the foundation for mathematical reasoning and proof techniques. It provides the basic framework for: Constructing valid arguments Analyzing the logical structure of mathematical statements Developing formal proof systems Understanding necessary and sufficient conditions Exercises 1. Construct truth tables for the following compound propositions: a) b) c) 2. Determine which of the following are tautologies, contradictions, or contingencies: a) b) c) 3. Prove the following logical equivalences using truth tables: a) b) c) 4. Express the statement "If it's not raining, then I will go for a walk or visit a museum" using propositional logic. 5. Use logical equivalences to simplify the following compound proposition: