> See also: > - [[Truth Tables]] > - [[Set Theory]] > - [[Number Theory]] # Fundamentals of Logic > This note primarily focuses on mathematical logic. > [!question]+ **Vocabulary** > A **statement/proposition** is a sentence that is either true or false (but not both) > - These are referred to as **boolean variables** (often denoted by $p$, $q$, or $r$) > --- > - A **conjecture** is a guess/prediction that has yet to be proven true or false. > - A **theorem** is a statement that has been *proven true* > - A **corollary** is a *proposition* that *follows* from a theorem > - A **axiom** is a statement or proposition that is *taken to be true* without the need for a proof > - "Using the definition of..." ### Nested Quantifiers ![[Pasted image 20230502021022.png|400]] ### Logical Connectives There are several **logical connectives** that can be used to link statements together and form **compound statements**: | Name | Behavior | Symbol | |:---:|:---:|:---:| | Negation | NOT | $\neg$ | | Conjunction | AND | $\land$ | | Disjunction | OR | $\lor$ | | Implication | IF/THEN | $\implies$ or $\rightarrow$ | | Biconditional | IF & ONLY IF | $\iff$ | | Exclusive OR | If only one is true | $\oplus$ | > [!faq] Logical Connective Truth Tables > > Contents ### Laws of Logic > [!abstract]+ **Quick Reference Sheet** > > ![[Laws of Logic and Rules of Inference.pdf]] The subset symbol ($\subseteq$) returns a truth value while other set operators return a set - The law of distributivity can be used on any pair of logical connectives - modus tollens is also called “the rule of denial” > [!info]- Laws of Logic > > Contents > > > [!info]+ Commutativity > > Logic: > > $p \lor q \iff q \lor p$ > > Contents ### Rules of Inference https://calcworkshop.com/logic/rules-inference/ > [!info]- Rules of Inference > > Contents > > > [!info]+ Commutativity > > aaa > > Contents - **Disjunctive Amplification:** Because we know that one premise (p) is true, the statement “p or q” is always going to be true regardless of what q is (it can even be “p or not q”, which may be essential for using de morgans afterwards) - disjunctive amplification allows us to bring in variables that may not exist in the given premises - Goal to use implication identity in laws of logic problems to remove the “implies” symbols - You don’t want to get rid of implication arrows as often in rules of inference problems - You rarely have to reuse premises - Its **very powerful to get simple true statements** (independent variables) - Conjunctive simplification is key here - “conjunction” by itself can then be used to relink separate premises together (conjunction = “and”) - - Try to exhaust the possible rules of inference before moving on to trying the laws of logic ![[Screenshot 2023-09-08 092725.png]] ### Universal Generation We can make the statement “for some arbitrary value x” and if we can prove that a conclusion can be reached for ANY value of x then we would have proved that a premise → conclusion (implication) is true for all universal members of the set ## Proof Techniques The **rule of conjunction** states that if we can show that two statements are true, then we may build a compound statement expressing this fact, and be certain that this is also true. When writing out proofs (especially mathematical proofs), you will often use the [[Fundamentals of Logic|rules of inference]] to justify the steps/logic being used, almost always without stating the rules outright. - There is not a strict format to formal proofs so long as the steps being taken are valid There are several general methods of forming proofs: The statement that you are trying to prove is known as the **conclusion**. When proving the equality of sets, you must prove both sides of the equation ### Direct Proofs In a direct proof, the goal is to start with a premise(s) and logically derive the conclusion through a series of steps. In this process we assume that the premises are true to start off, and in the process we form a logical connection between the premise(s) and the conclusion: 1. Clearly **write out the conclusion** to be proven 2. List the premises that are being used to prove the statement 3. Start with the given premises and use logical reasoning and mathematical rules to reach the conclusion - "Proof by cases" ### Proof by Contrapositive ### Proof by Contradiction ### Proof by Induction