Today’s topicsBits and Bit OperationsBit StringsCounting in BinaryBitwise OperationsEnd of §1.1Propositional Equivalence (§1.2)Tautologies and ContradictionsLogical EquivalenceProving Equivalence via Truth TablesEquivalence LawsEquivalence Laws - ExamplesMore Equivalence LawsDefining Operators via EquivalencesAn Example ProblemExample Continued...End of Long ExampleReview: Propositional Logic (§§1.1-1.2)Predicate Logic (§1.3)Applications of Predicate LogicOther ApplicationsPractical Applications of Predicate LogicSubjects and PredicatesMore About PredicatesPropositional FunctionsUniverses of Discourse (U.D.s)Quantifier ExpressionsThe Universal Quantifier The Existential Quantifier Free and Bound VariablesExample of BindingNesting of QuantifiersReview: Predicate Logic (§1.3)Quantifier ExerciseNatural language is ambiguous!Game Theoretic SemanticsLet’s Play, “Verify or Falsify!”Still More ConventionsMore to Know About BindingQuantifier Equivalence LawsSlide 41Slide 42More Notational ConventionsDefining New QuantifiersSome Number Theory ExamplesGoldbach’s Conjecture (unproven)Calculus ExampleDeduction ExampleDeduction Example ContinuedAnother ExampleThe DerivationEnd of §1.3-1.4, Predicate LogicCompSci 102 © Michael Frank 1.1Today’s topics•Boolean algebra previewBoolean algebra preview•Propositional equivalencesPropositional equivalences•Predicate logicPredicate logic•Reading: Sections 1.2-1.4Reading: Sections 1.2-1.4CompSci 102 © Michael Frank 1.2Bits and Bit Operations•A A bitbit is a is a bibinary (base 2) dignary (base 2) digitit: 0 or 1.: 0 or 1.•Bits may be used to represent truth values.Bits may be used to represent truth values.•By convention: By convention: 0 represents “false”; 1 represents “true”. 0 represents “false”; 1 represents “true”.•Boolean algebraBoolean algebra is like ordinary algebra is like ordinary algebra except that variables stand for bits, + means except that variables stand for bits, + means “or”, and multiplication means “and”.“or”, and multiplication means “and”.–See module 23 (chapter 10) for more details.See module 23 (chapter 10) for more details.Topic #2 – BitsJohn Tukey(1915-2000)CompSci 102 © Michael Frank 1.3Bit Strings•AA Bit string Bit string of of length n length n is an ordered sequence is an ordered sequence (series, tuple) of (series, tuple) of nn0 bits.0 bits.–More on sequences in More on sequences in §3.2.§3.2.•By convention, bit strings are (sometimes) written By convention, bit strings are (sometimes) written left to right: left to right: –e.g.e.g. the “first” bit of the bit string “1001101010” is 1. the “first” bit of the bit string “1001101010” is 1.–Watch out!Watch out! Another common convention is that the Another common convention is that the rightmost bit is bit #0, the 2rightmost bit is bit #0, the 2ndnd-rightmost is bit #1, etc.-rightmost is bit #1, etc.•When a bit string represents a base-2 number, by When a bit string represents a base-2 number, by convention, the first (leftmost) bit is the convention, the first (leftmost) bit is the most most significantsignificant bit. bit. Ex. Ex. 1101110122=8+4+1=13.=8+4+1=13.Topic #2 – BitsCompSci 102 © Michael Frank 1.4Counting in Binary•Did you know that you can count Did you know that you can count to 1,023 just using two hands?to 1,023 just using two hands?–How? Count in binary!How? Count in binary!•Each finger (up/down) represents 1 bit.Each finger (up/down) represents 1 bit.•To increment: Flip the rightmost (low-order) bit.To increment: Flip the rightmost (low-order) bit.–If it changes 1If it changes 1→0, then also flip the next bit to the left,→0, then also flip the next bit to the left,•If that bit changes 1→0, then flip the next one, If that bit changes 1→0, then flip the next one, etc.etc.•0000000000, 0000000001, 0000000010, …0000000000, 0000000001, 0000000010, ……, 1111111101, 1111111110, 1111111111 …, 1111111101, 1111111110, 1111111111 Topic #2 – BitsCompSci 102 © Michael Frank 1.5Bitwise Operations•Boolean operations can be extended to Boolean operations can be extended to operate on bit strings as well as single bits.operate on bit strings as well as single bits.•E.g.:E.g.:01 1011 011001 1011 011011 0001 110111 0001 110111 1011 1111 Bit-wise OR Bit-wise OR01 0001 0100 Bit-wise ANDBit-wise AND10 1010 1011 Bit-wise XORBit-wise XORTopic #2 – BitsCompSci 102 © Michael Frank 1.6End of §1.1You have learned about:You have learned about:•Propositions: What Propositions: What they are.they are.•Propositional logic Propositional logic operators’operators’–Symbolic notations.Symbolic notations.–English equivalents.English equivalents.–Logical meaning.Logical meaning.–Truth tables.Truth tables.•Atomic vs. compound Atomic vs. compound propositions.propositions.•Alternative notations.Alternative notations.•Bits and bit-strings.Bits and bit-strings.•Next section: §1.2Next section: §1.2–Propositional Propositional equivalences.equivalences.–How to prove them.How to prove them.CompSci 102 © Michael Frank 1.7Propositional Equivalence (§1.2)Two Two syntacticallysyntactically ( (i.e., i.e., textually) different textually) different compound propositions may be the compound propositions may be the semantically semantically identical (identical (i.e., i.e., have the same have the same meaning). We call them meaning). We call them equivalentequivalent. Learn:. Learn:•Various Various equivalence rules equivalence rules oror laws laws..•How to How to proveprove equivalences using equivalences using symbolic symbolic derivationsderivations..Topic #1.1 – Propositional Logic: EquivalencesCompSci 102 © Michael Frank 1.8Tautologies and ContradictionsA A tautologytautology is a compound proposition that is is a compound proposition that is truetrue no matter whatno matter what the truth values of its the truth values of its atomic propositions are!atomic propositions are!Ex.Ex. p p pp [What is its truth table?][What is its truth table?]A A contradiction contradiction is a compound proposition is a compound proposition that is that is falsefalse no matter what! no matter what! Ex.Ex. p p p p [Truth table?][Truth table?]Other compound props. are Other compound props. are contingenciescontingencies..Topic #1.1 – Propositional Logic:
View Full Document
Unlocking...