The Logic of Compound Statements

Logical Form and Logical Equivalence Lecture 2 Section 1.1 Fri, Jan 19, 2007 Statements A statement is a sentence that is either true or false, but not both. These are statements: It is Wednesday. Discrete Math meets today. These are not statements:

Hello. Are you there? Go away! Logical Operators Binary operators Conjunction and. Disjunction or. Unary operator Negation

not. Other operators XOR exclusive or NAND not both NOR neither Logical Symbols Statements are represented by letters: p, q, r, etc. means and. means or. means not. Examples Basic statements

p = It is Wednesday. q = Discrete Math meets today. Compound statements p q = It is Wednesday and Discrete Math meets today. p q = It is Wednesday or Discrete Math meets today. p = It is not Wednesday . False Negations Statement Everyone

False negation Everyone likes me. does not like me. True negation Someone does not like me. False Negations Statement Someone

False negation Someone likes me. does not like me. True negation No one likes me. Truth Table of an Expression Make a column for every variable. List every possible combination of truth values of the variables. Make one more column for the expression.

Write the truth value of the expression for each combination of truth values of the variables. Truth Table for and p q is true if p is true and q is true. p q is false if p is false or q is false. p q pq T T T

T F F F T F F F F Truth Table for or p q is true if p is true or q is true.

p q is false if p is false and q is false. p q pq T T T T F T

F T T F F F Truth Table for not p is true if p is false. p is false if p is true. p p

T F F T Example: Truth Table Truth table for the statement (p) (q r). p q r (p) (q r ) T

T T T T T F F T F T

F T F F F F T T T F T

F T F F T T F F F T

Logical Equivalence Two statements are logically equivalent if they have the same truth values for all combinations of truth values of their variables. Example: Logical Equivalence (p q) (p q) (p q) (p q) p T q T (p q) (p q) T

(p q) (p q) T T F F F F T F F F

F T T DeMorgans Laws DeMorgans Laws: (p q) (p) (q) (p q) (p) (q) If it is not true that i < size && value != array[i] then it is true that DeMorgans Laws DeMorgans Laws: (p q) (p) (q)

(p q) (p) (q) If it is not true that i < size && value != array[i] then it is true that i >= size || value == array[i] DeMorgans Laws If it is not true that x 5 or x 10, then it is true that DeMorgans Laws If it is not true that x 5 or x 10,

then it is true that x > 5 and x < 10. Tautologies and Contradictions A tautology is a statement that is logically equivalent to T. It is a logical form that is true for all logical values of its variables. A contradiction is a statement that is logically equivalent to F. It is a logical form that is false for all logical

values of its variables. Tautologies and Contradictions Some tautologies: p p p q (p q) Some contradictions: p p p q (p q)

Recently Viewed Presentations

  • Abstract: Foreign accent syndrome is a rare phenomenon

    Abstract: Foreign accent syndrome is a rare phenomenon

    In addition, although the extent of vowel distortion could not be evaluated in this case study because the speech was mostly unintelligible, observations on the formant frequencies of identifiable corner vowels revealed a tendency for lower than normal tongue positioning...
  • Adapted Physical Education - Rowan University

    Adapted Physical Education - Rowan University

    Replaced the term handicapped with disability. Defined 13 categories of disabilities. Physical Education is defined to include; physical and motor fitness, fundamental motor skills and patterns and skills in aquatics, dance, and individual and group games and sports (intramural and...
  • Lesson Twelve Integrated Concepts  Language Arts: descriptive language,

    Lesson Twelve Integrated Concepts Language Arts: descriptive language,

    PowerPoint Presentation Last modified by: BRI Created Date: 1/1/1601 12:00:00 AM Document presentation format: On-screen Show (4:3) Other titles: Arial Calibri Times New Roman Default Design Slide 1 Lesson Twelve Slide 3 Slide 4 Slide 5 Slide 6 Slide 7...
  • The First Americans

    The First Americans

    Life in Mayan Cities. One way to please the gods was through human sacrifice. Mayans wanted captives more than land when they fought wars. Offered captives to Chac, god of rain and sunlight during droughts
  • Differentiated Instruction Elementary Math

    Differentiated Instruction Elementary Math

    Differentiated instruction can be defined as a way for teachers to focus on the student and be responsive to individual differences via a process of adapting and modifying teaching, learning activities, and what students are required to do and produce...
  • Wednesday, 9/4/13

    Wednesday, 9/4/13

    Jean-Paul Sartre, existentialist philosopher and writer, Existentialism is a Humanism, 1946 The development described in the passage best reflects a movement away from which of the following? The objectivity of science and rational thought. Faith based spiritual beliefs and practices....
  • PowerPoint bemutató

    PowerPoint bemutató

    FEJLŐDÖTT A PAJZSMIRIGY GYÓGYÁSZAT AZ ELMÚLT 50 ÉVBEN? Dr. Földes János Szt. János Kórház
  • River Valley Civilizations

    River Valley Civilizations

    Ancient China - Huang He (Yellow) River. PP Design of T. Loessin; Akins H.S. ... it is the best preserved legal document reflecting the social structure of Babylon during Hammurabi's rule. ... "The Four Early River Valley Civilizations" ...