1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 2Milos [email protected] Sennott SquarePropositional logicM. HauskrechtCS 441 Discrete mathematics for CSCourse administrationHomework 1 • First homework assignment is out today will be posted on the course web page• Due next week on ThurdayRecitations:• today at 4:00pm SENSQ 5313• tomorrow at 11:00 SENSQ 5313Course web page:http://www.cs.pitt.edu/~milos/courses/cs441/2M. HauskrechtCS 441 Discrete mathematics for CSPropositional logic: review• Propositional logic: a formal language for representing knowledge and for making logical inferences• A proposition is a statement that is either true or false.• A compound proposition can be created from other propositions using logical connectives • The truth of a compound proposition is defined by truth values of elementary propositions and the meaning of connectives.• The truth table for a compound proposition: table with entries (rows) for all possible combinations of truth values of elementary propositions.M. HauskrechtCS 441 Discrete mathematics for CSCompound propositions• Let p: 2 is a prime ….. Tq: 6 is a prime ….. F• Determine the truth value of the following statements:¬ p: Fp  q : Fp  ¬q: Tp  q : Tp  q: Tp  q: Fq  p: T3M. HauskrechtCS 441 Discrete mathematics for CSConstructing the truth table • Example: Construct the truth table for (p  q)  (¬p  q)M. HauskrechtCS 441 Discrete mathematics for CSConstructing the truth table • Example: Construct the truth table for (p  q)  (¬p  q)pq¬pp  q¬p  q(pq)(¬pq)TTTFFTFFRows: all possible combinations of values for elementary propositions:2nvalues4M. HauskrechtCS 441 Discrete mathematics for CSConstructing the truth table • Example: Construct the truth table for (p  q)  (¬p  q)pq¬pp  q¬p  q(pq)(¬pq)TTTFFTFFTypically the target (unknown) compound proposition and its valuesAuxiliary compound propositions and their valuesM. HauskrechtCS 441 Discrete mathematics for CSConstructing the truth table • Examples: Construct a truth table for (p  q)  (¬p  q)pq¬pp  q¬p  q(pq)(¬pq)TTFTFFTFFFTFFTTTTTFFTTFF5M. HauskrechtCS 441 Discrete mathematics for CSComputer representation of True and False We need to encode two values True and False: • Computers represents data and programs using 0s and 1s • Logical truth values – True and False • A bit is sufficient to represent two possible values:– 0 (False) or 1(True)• A variable that takes on values 0 or 1 is called a Boolean variable.• Definition: A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.M. HauskrechtCS 441 Discrete mathematics for CSBitwise operations • T and F replaced with 1 and 0pqp  qp  q1111101001100000p¬p10016M. HauskrechtCS 441 Discrete mathematics for CSBitwise operations • Examples:1011 0011 1011 0011 1011 0011 0110 1010  0110 1010  0110 10101111 1011 0010 0010 1101 1001M. HauskrechtApplications of propositional logic• Translation of English sentences• Inference and reasoning:– new true propositions are inferred from existing ones– Used in Artificial Intelligence:• Rule based (expert) systems• Automatic theorem provers• Design of logic circuitCS 441 Discrete mathematics for CS7M. HauskrechtCS 441 Discrete mathematics for CSTranslationAssume a sentence:If you are older than 13 or you are with your parents then you can attend a PG-13 movie.Parse:• If ( you are older than 13 or you are with your parents )then( you can attend a PG-13 movie)Atomic (elementary) propositions: – A= you are older than 13– B= you are with your parents– C=you can attend a PG-13 movie• Translation: A  B  CM. HauskrechtCS 441 Discrete mathematics for CSTranslation • General rule for translation. • Look for patterns corresponding to logical connectives in the sentence and use them to define elementary propositions. • Example:You can have free coffee if you are senior citizen and it is a TuesdayStep 1 find logical connectives8M. HauskrechtCS 441 Discrete mathematics for CSTranslation • General rule for translation. • Look for patterns corresponding to logical connectives in the sentence and use them to define elementary propositions. • Example:You can have free coffee if you are senior citizen and it is a TuesdayStep 1 find logical connectivesM. HauskrechtCS 441 Discrete mathematics for CSTranslation • General rule for translation. • Look for patterns corresponding to logical connectives in the sentence and use them to define elementary propositions. • Example:You can have free coffee if you are senior citizen and it is a TuesdayStep 2 break the sentence into elementary propositions9M. HauskrechtCS 441 Discrete mathematics for CSTranslation • General rule for translation. • Look for patterns corresponding to logical connectives in the sentence and use them to define elementary propositions. • Example:You can have free coffee if you are senior citizen and it is a TuesdayStep 2 break the sentence into elementary propositionsabcM. HauskrechtCS 441 Discrete mathematics for CSTranslation • General rule for translation . • Look for patterns corresponding to logical connectives in the sentence and use them to define elementary propositions. • Example:You can have free coffee if you are senior citizen and it is a TuesdayStep 3 rewrite the sentence in propositional logicabcb  c  a10M. HauskrechtCS 441 Discrete mathematics for CSTranslation • Assume two elementary statements:– p: you drive over 65 mph ; q: you get a speeding ticket• Translate each of these sentences to logic– you do not drive over 65 mph. (¬p)– you drive over 65 mph, but you don't get a speeding ticket. (p  ¬q)– you will get a speeding ticket if you drive over 65 mph.(p  q)– if you do not drive over 65 mph then you will not get a speeding ticket.(¬p  ¬q)– driving over 65 mph is sufficient for getting a speeding ticket. (p  q)– you get a speeding ticket, but you do not drive over 65 mph. (q  ¬p)M. HauskrechtCS 441 Discrete mathematics for CSApplication: inference Assume we know the following sentences are true:If you are older than 13 or you are with your parents then you can attend a PG-13 movie. You are older than 13. Translation:• If