Discrete Math

• Proposition


  A declarative statement (either true or false)
• Propositional logic


  Studies the relationship between two or more propositions regardless of its content

  
• Propositions


  • "If the moon is made of cheese then basketballs are round"
  • "If spiders have eight legs then Anne walks with a limp"
• Atomic statement


  A simple, indivisible statement
• Simple statement


  Contains no other statement as a part or has no addition of another proposition
• Complex statement


  Has at least one sentence and has one or more logical connectives as a component
• Logical connectives


  • Negations
  • Conjunctions
  • Disjunctions
  • Conditional
  • Biconditional
• Negation


  Asserts that something is not the case or simply reverses a statement
• Negation


  • "Zuko is NOT a firebender"
• Conjunction


  Puts two sentences together and claims that they are both true
• Conjunction


  • "Katara is a waterbender, AND Sokka is a warrior"
• Disjunction


  Claims that at least one of two sentences are true
• Disjunction


  • "Toph will teach Aang earthbending, OR Aang will learn on his own"
• Conditional


  Statement becomes false if its hypothesis is true but the conclusion is false
• Conditional


  • "If Aang masters all four elements, THEN he can defeat the Fire Lord"
• Forms of conditional statement

  • Inverse
  • Converse
  • Contrapositive
• Sufficient condition


  Something that is enough to guarantee the truth of something else
• Necessary condition


  Something that must be true in order for something else to be true
• Biconditional


  When something is both a necessary and a sufficient condition for something else
• Biconditional


  • "Zuko is the Fire Lord if and only if he rules the Fire Nation"
• Syntax


  The "form" of the expressions such as words, sentences, and the like
• Semantics


  The content, or meaning of expressions
• Syntax of propositional logic


  • Unary Propositional Operator: ~ or ¬
  • Binary Propositional Connectives: ∧ or • , V, ⇒ ,⇔
  • Grouping Symbols: ( ) , [ ]
• Rules to determine whether a Propositional Logic is in its Wellformed Formula (WFF) or not

  
• Tautology


  A proposition that is always true for all possible truth values of its propositional variables
• Contradiction


  A proposition that is always false for all possible truth values of its propositional variables
• Contingency


  A proposition that is neither a tautology nor a contradiction
• Logical equivalence


  Compound propositions that have the same truth values in all possible cases
• Propositional equivalences


  The replacement of a statement with another statement with the same truth value
• Propositional equivalences


  • Used to simplify and validate mathematical statement

  
• Tautology


  A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it
• Contradiction


  A compound proposition that is always false
• Contingency


  A compound proposition that is neither a tautology nor a contradiction
• Logical equivalences


  Compound propositions that have the same truth values in all possible cases
• Logical equivalence (p ≡ q)


  The compound propositions p and q are logically equivalent if p ↔ q is a tautology
• De Morgan's laws


  Tell us how to negate conjunctions and how to negate disjunctions
• Negating conjunctions using De Morgan's first law


  ¬(p ∧ q) ≡ ¬p ∨ ¬q

  
• Negating disjunctions using De Morgan's second law


  ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Idempotence


  The property of certain operations whereby they can be applied multiple times without changing the result beyond the initial application
• Idempotence


  • p ∨ p ≡ p
  • p ∧ p ≡ p