Discrete Structures 1

• Proposition


  A declarative statement that has a truth value (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
• Simple statement


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


  • Polytechnic University of the Philippines is in Sta. Mesa, Manila
  • Noynoy Aquino was succeeded as President of the Philippines by Rodrigo Duterte
• Complex sentence


  Has at least one sentence and has one or more logical connectives as a component
• Types of complex sentences in propositional logic

  • Negations
  • Conjunctions
  • Disjunctions
  • Conditionals
  • Biconditional
• Negation


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


  • Polytechnic University of the Philippines is not in Sta. Mesa, Manila
• Conjunction


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


  • It is raining today and my sunroof is open
• Disjunction


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


  • I will go to the movies this weekend or I will stay home and grade critical thinking homework
• Conditional


  Becomes false if its hypothesis is true but the conclusion is false
• Conditional


  • If you will study tonight, then you will get a high score in our quiz tomorrow
  • You will pass Discrete Mathematics, provided you study
• Inverse


  Negates the hypothesis and conclusion
• Converse


  Changes the position of hypothesis and conclusion
• Contrapositive


  Negates the converse form of the given conditional statement
• Necessary condition


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


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


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


  • Completing all your requirements is both sufficient and necessary to earn a degree
• Syntax


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


  The content, or meaning of expressions
• Any capital letter by itself is a Well-Formed Formula
• Any WFF can be prefixed with "~"
• Any two WFFs can be put together with "•", "∨", "⊃", or "≡" between them
• Syntax


  The rules in generating complex claims from simple ones using logical connectives and operators
• Symbols used in propositional logic


  • P, Q, R, ... X, Y, Z
• Unary propositional operator


  • ~ or ¬
• Binary propositional connectives


  • ∧ or •, V, ⇒, ⇔
• Grouping symbols


  • ( ), [ ]
• Negation


  ~ or ¬
• Conjunction


  ∧ or •
• Determining if a propositional logic is in its well-formed formula (WFF)


  1. Any capital letter by itself is a WFF

  2. Any WFF can be prefixed with "~"

  3. Any two WFFs can be put together with "•", "∨", "⊃", or "≡" between them, enclosing the result in parentheses
• Parentheses are very important. For instance, ~(P ∧ Q) is different from ~P ∧ Q.
• Semantics


  Semantic rules of propositional logic tell us how the meaning of its constituent parts, and their mode of combination, determine the meaning of a compound statement. This meaning represents its truth value.
• Logical operators


  Determine what the truth-values of compound statements are depending on the truth-values of the formulae in the compound
• Meaning of "A ∧ B"

  • This is only true if both A and B are true
• Logical connectives


  • NOT ¬, AND ∧, OR ∨, IMPLICATION ⇒, BICONDITIONAL ⇔