πŸͺ΄ Notes

Logical Operations

2 min read

Course: CSCI 1900

Propositions

  • A declarative statement that can either be true or false
    • β€œEarth is flat” β†’ T
    • β€œTen is less than seven” β†’ F

Boolean Algebra

Conditional Statements

  • Negation (Β¬) β†’ not
  • Conjunction (∧) β†’ and
  • Disjunction (∨) β†’ or
  • Exclusive Or (βŠ•) β†’ xor

Variations

  • Implication (π‘β†’π‘ž) β†’ if 𝑝 then π‘ž
    • 𝐹→𝑇=𝑇 β†’ vacuous truth
  • Converse (q β†’ p)
    • If you failed the course, then you did poorly on an exam
  • Inverse (Β¬π‘β†’Β¬π‘ž)
    • You did not do poorly on an exam, you will not fail the course
  • Contrapositive (Β¬π‘žβ†’Β¬π‘β‰‘π‘žβ†’π‘)
    • If you didn’t fail, you didn’t do poorly on a test
  • Biconditional (π‘β†”π‘ž) β†’ β€œif and only if”
    • π‘β†’π‘žβˆ§π‘žβ†’π‘

Vacuous Truth

  • If 𝑝 is false, π‘β†’π‘ž is always true.

Predicates + Quantifiers

  • Predicate β†’ a function that returns a boolean value based on input
    • 𝑃(π‘₯)=π‘₯βˆˆβ„€βˆ§π‘₯<10
  • Universal Quantifier β†’ for all π‘₯, 𝑃(π‘₯) must be true
    • βˆ€π‘₯(π‘₯2β‰₯0)
  • Existential Quantifier β†’ there exists and π‘₯ where 𝑃(π‘₯) is true
    • βˆƒπ‘₯(π‘₯βˆˆβ„€)

Terms

  • Tautology β†’ a statement that is always true
    • π‘βˆ¨Β¬π‘
  • Contradiction β†’ a statement that is always false
    • π‘βˆ§Β¬π‘

Logical Properties

  • Commutative β†’ π‘βˆ§π‘ž=π‘žβˆ§π‘
  • Associative β†’ (π‘βˆ§π‘ž)βˆ¨π‘Ÿ=π‘βˆ§(π‘žβˆ¨π‘Ÿ)
  • Distributive β†’ π‘βˆ§(π‘žβˆ¨π‘Ÿ)=(π‘βˆ§π‘ž)∨(π‘žβˆ§π‘Ÿ)

Graph View