Shawn Zhong

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Math 240

Home / Mathematics / Notes / Math 240 / Page 9

1.1 Propositional Logic

  • Jan 30, 2018
  • Shawn
  • Math 240
  • No comments yet
Propositions • Definition ○ A proposition is a declarative sentence that is either true or false. • Examples of propositions ○ The Moon is made of green cheese. ○ Paris is the capital of Europe. ○ Toronto is the capital of Canada. ○ 1 + 0 = 1 ○ 0 + 0 = 2 • Examples that are not propositions ○ Sit down! ○ What time is it? ○ x+1=2 ○ x+y=z Constructing Propositions • Propositional Variables: p, q, r, s, … • The proposition that is always true is denoted by T • The proposition that is always false is denoted by F. Compound Propositions • Definition ○ Propositions constructed from logical connectives and other propositions • Negation ¬ ○ The negation of a proposition p is denoted by ¬p ○ Truth table p ¬p T F F T ○ Example § If p denotes “The earth is round.” § Then ¬p denotes “It is not the case that the earth is round,” § Or more simply “The earth is not round.” • Conjunction ∧ ○ The conjunction of propositions p and q is denoted by p∧q ○ Truth Table p q p∧q T T T T F F F T F F F F ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p∧q denotes “I am at home and it is raining.” • Disjunction ∨ ○ The disjunction of propositions p and q is denoted by p∨q ○ Truth Table p q p∨q T T T T F T F T T F F F ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p∨q denotes “I am at home or it is raining.” • Inclusive Or vs Exclusive Or ○ “Inclusive Or” § In the sentence “Students who have taken CS202 or Math120 may take this class,” we assume that students need to have taken one of the prerequisites, but may have taken both. § This is the meaning of disjunction. § For p ∨ q to be true, either one or both of p and q must be true. ○ “Exclusive Or” § When reading the sentence “Soup or salad comes with this entrée,” we do not expect to be able to get both soup and salad. § This is the meaning of Exclusive Or (XOR). § In p⊕q , one of p and q must be true, but not both. § The truth table for ⊕ is: p q p⊕q T T F T F T F T T F F F • Implication → ○ If p and q are propositions, then p→q is a conditional statement or implication which is read as “if p, then q ” ○ Truth Table p q p→q T T T T F F F T T F F T ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p→q denotes “If I am at home then it is raining.” ○ In p→q, p is the hypothesis (antecedent or premise) and q is the conclusion (or consequence). • Biconditional ↔ ○ If p and q are propositions, then we can form the biconditional proposition p↔q , read as “p if and only if q.” ○ Truth Table p q p↔q T T T T F F F T F F F T ○ If p denotes “I am at home.” and q denotes “It is raining.” then p↔q denotes “I am at home if and only if it is raining.” • Example p q (¬p)∧(¬q) (¬p)∨(¬q) T T F F T F F T F T F T F F T T Converse, Contrapositive, and Inverse • From p→q we can form new conditional statements . ○ q→p is the converse of p→q ○ ¬q→¬p is the contrapositive of p→q ○ ¬p→¬q is the inverse of p→q • Example ○ "If it is raining, then I will not go to town." ○ p: "It is raining" ○ q: "I am going to town" ○ Sufficient Condition § It raining is a sufficient condition for my not going to town. ○ Necessary Condition § My not going to town is a necessary condition for it raining. ○ Converse § If I do not go to town, then it is raining. ○ Inverse § If it is not raining, then I will go to town. ○ Contrapositive § If I go to town, then it is not raining. • Truth Table p q p→q q→p ¬q→¬p ¬p→¬q ¬(p→q) T T T T T T F T F F T F T T F T T F T F F F F T T T T F Truth Table for Compound Propositions • Construction of a truth table: ○ Rows § Need a row for every possible combination of values for the atomic propositions. ○ Columns § Need a column for the compound proposition (usually at far right) § Need a column for the truth value of each expression that occurs in the compound proposition as it is built up. § This includes the atomic propositions • Precedence of Logical Operators Operator Precedence ¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5 • Example: p∨q→¬r p q r p∨q ¬r p∨q→¬r T T T T F F T F T T F F F T T T F F F F T F F T T T F T T T T F F T T T F T F T T T F F F F T T
Read More >>

0. Introductory Lecture

  • Jan 30, 2018
  • Shawn
  • Math 240
  • No comments yet
What is Discrete Mathematics? • Study of discrete (as opposed to continuous) objects • Calculus is continuous • Example of discrete objects ○ Integers ○ Steps taken by a computer program ○ Distinct paths to travel from point A to point B on a map along a road network ○ Ways to pick a wining set of numbers in a lottery Kinds of Problems Solved Using Discrete Mathematics • Number of valid passwords • Number of valid websites • Probability of winning a lottery • Link between two computers in a network • Identify spam e-mails • Shortest path • Prove there are infinitely many prime numbers • Numbers of steps need to do a sorting • Prove the correctness of algorithms Goals of a Course in Discrete Mathematics • Mathematical Reasoning • Combinatorial Analysis • Discrete Structures
Read More >>
  • 1
  • …
  • 7
  • 8
  • 9

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 - Discrete Math
    • Math 375 - Linear Algebra
    • Math 431 - Intro to Probability
    • Math 514 - Numerical Analysis
    • Math 521 - Analysis I
    • Math 541 - Abstract Algebra
    • Math 632 - Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 - Intro to Computer Engr.
    • CS/ECE 352 - Digital System Fund.
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E＆M
    • AP Physics C: Mechanics
    • CLEP Psychology

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E＆M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (4)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP