ICS 6B Sections 1.12, 1.13, and all of 2

• 1.12: Rules of inference with propositions
• 1.13: Rules of inference with quantifiers
• 2.1: Mathematical definitions
• 2.2: Introduction to proofs
• 2.3: Best practices and common errors in proofs
• 2.4: Writing direct proofs
• 2.5: Proof by contrapositive
• 2.6: Proof by contradiction
• 2.7: Proof by cases

1.12: Rules of inference with propositions

• There are rules of inference that can be generally applied to arguments to know if they are valid
  • List of rules:
• Proving the validity of an argument using the rules of inference and laws of propositions is called a logical proof
  • Each step has different justifications; providing a hypothesis is calleda “hypothesis”, and you must state the law/rule if not
  • Example of a logical proof:

STUDY THIS SECTION, Challenge Activity 1.12.1 part 4 is good

1.13: Rules of inference with quantifiers

• To apply a rule of inference to a quantified statement, you must use an element in the domain of the statement
  • Elements can be defined in the hypotheses, example below:
  • Can use one of two elements in a logical proof
    • Arbitrary elements have no special properties other than the fact that they are in the domain
    • Particular elements can have properties that aren’t shared by others in the domain
  • An element defined in a hypothesis is particular by default and must be labeled as “Hypothesis”, while an element defined in the proof is labeled “Element definition”

• Table of rules of inference for quantified statements:

• A common error is defining the same variable for two different instances of existential instantiation; make sure to mark one variable as C and one as D

STUDY THIS SECTION, Challenge Activity is good

2.1: Mathematical definitions

• Even integers can be written as 2k; odd ones are written as 2k + 1 (also known as parity)
• Same parity is if two numbers are both odd or even; if not, they are of opposite parity
• Rational numbers are ones where there exists integers x, where y!= 0 and r = x/y
• A number (x) that divides another number (y) is one where y % x == 0
  • Denoted as x|y (x divides y); x is a multiple of y if it divides it
  • Numbers that don’t divide are denoted as so:
  • A number that divides another is called a multiple
• Prime numbers and composite numbers (if you don’t know this shit ur dumb)
• Inequalities: <, >, =, etc.

2.2: Introduction to proofs

• Theorem: A statement that can be proven to be true via a proof
  • Proofs might use axioms which are statements assumed to be true
• Theorems are often rewritten as universally or existentially quantified statements
• Proof of exhaustion: A proof that is done by examining every element in a domain
• Proofs involving universal generalizations uses a statement to define an arbitrary element
• Counterexample: definition of one element in a domain that makes the statement false
• Existence proofs show that existential statements are true
  • Constructive proofs of existence are the most common, and they provide a specific example in the domain that satisfies the statement
  • Nonconstructive proofs of existence provide an example with certain properties that satisfies the statement
  • Disproving existential statements requies DeMorgan’s Law and a proof that a negated statement is true
    • Example:

2.3: Best practices and common errors in proofs

Section includes various important factoids to know

2.4: Writing direct proofs

• Direct proofs: A hypothesis, p, is assumed to be true and the conclusion, c, is proven due to that assumption (p -> c)

2.5: Proof by contrapositive

• Proof by contrapositive: A proof of a conditional theorem of the form (p -> c) by proving (!c -> !p)
  • Example of what to do with multiple hypotheses:

2.6: Proof by contradiction

• Proof by contradiction assumes that the theorem is false and shows a logical inconsistency with such assumption; also called an indirect proof
  • Example:

2.7: Proof by cases

• Proof by cases: Separates the domain into separate classes (cases) and proves that each class is true
  • Example:
• Without loss of generality is written to show that one case can apply to all cases
  • Example: