Understanding Propositional Logic and Truth Tables

Chapter 2.1 2.4 Topics Covered

Section Summary Propositions Connectives Negation Conjunction Disjunction Implication; contrapositive, inverse, converse Biconditional Truth Tables

Propositions A proposition is a declarative sentence that is either true or false.

Propositions A proposition is a declarative sentence that is either true or false. Examples of propositions: a) The Moon is made of green cheese. b) Trenton is the capital of New Jersey. c) Toronto is the capital of Canada. d) 1 + 0 = 1 e) 0 + 0 = 2

Propositional Logic Constructing Propositions Propositional Variables: p, q, r, s, The proposition that is always true is denoted by T and the proposition that is always false is denoted by F. Compound Propositions: constructed from logical connectives and other propositions (other symbols are sometimes used) Negation Conjunction Disjunction (inclusive-or) Exclusive-or Implication Biconditional

Truth Tables Logical operators/connectives are defined by truth tables: Negation truth table (unary): p T F p F T Binary truth tables: p q p q T F F F p q p q p q p q T T T F F T T F F T F T F F T T T F T T T F F T

Understanding Implication One way to view the logical conditional is to think of an obligation or contract. If I am elected, then I will lower taxes. If you get 100% on the final, then you will get an A. If the politician is elected and does not lower taxes, then the voters can say that he or she has broken the campaign pledge. Something similar holds for the professor. This corresponds to the case where p is true and q is false.

Different Ways of Expressing p q if p, then q if p, q q unless p q if p q when p q whenever p q follows from p p implies q p only if q q when p p is sufficient for q q is necessary for p a necessary condition for p is q a sufficient condition for q is p

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

Expressing the Biconditional Some alternative ways p if and only if q is expressed in English: p is necessary and sufficient for q if p then q , and conversely p iff q

Precedence of Logical Operators Operator Precedence 1 2 3 4 5 p q If the intended meaning is p ( (q then parentheses must be used. r is equivalent to (p q) r r )

Equivalent Propositions Two propositions are equivalentif they always have the same truth value. Example: Show using a truth table that the conditional is equivalent to the contrapositive. Solution: p p q q p p q q p p q q q q p p T T F F T T T F F T F F F T T F T T F F T T T T

Translating English Sentences Steps to convert an English sentence to a statement in propositional logic Identify atomic propositions and represent using propositional variables. Determine appropriate logical connectives If I go to Harry s or to the country, I will not go shopping. p: I go to Harry s q: I go to the country. r: I will go shopping. If p or q then not r.

Tautologies, Contradictions, and Contingencies A tautology is a proposition which is always true. Example: p p A contradiction is a proposition which is always false. Example: p p P P p p p p p p p p p p T F T F F T T F

Logically Equivalent Two compound propositions p and q are logically equivalent if p tautology. We write this as p q where p and q are compound propositions. Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree. This truth table shows p q is equivalent to p q. q is a p p q q p p p p q q p p q q T T F T T T F F F F F T T T T F F T T T

Laws of Logic DeMorgan s laws

Algebraic Laws of logic

`Logic Laws of logic

Equivalence Proofs Example: Show that is logically equivalent to Solution:

Propositional Functions Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the universe. The statement P(x) is said to be the value of the propositional function P at x. For example, let P(x)denote x > 0 and the universe of x be the integers. Then: P(-3) is false. P(0) is false. P(3) is true. Often the universe is denoted by U. So in this example U is the integers.

Example of Propositional Functions Let x + y = z be denoted by R(x, y, z)and U (for all three variables) be the integers. Find these truth values: R(2,-1,5) Solution: R(3,4,7) Solution: R(x, 3, z) Solution:

Example of Propositional Functions Let x + y = z be denoted by R(x, y, z)and U (for all three variables) be the integers. Find these truth values: R(2,-1,5) Solution: F R(3,4,7) Solution: T R(x, 3, z) Solution: Not a Proposition

Quantifiers The two most important quantifiers are: Universal Quantifier, For all, symbol: Existential Quantifier, There exists, symbol: We write as in x P(x) and x P(x). x P(x) asserts P(x) is true for every x in the universe. x P(x) asserts P(x) is true for some x in the universe. The quantifiers are said to bind the variable x in these expressions.

Universal Quantifier x P(x)is read as For all x, P(x) or For every x, P(x) Examples: 1) If P(x)denotes x > 0 and U is the integers, then x P(x) is false. 2) If P(x)denotes x > 0 and U is the positive integers, then x P(x) is true. 3) If P(x)denotes x is even and U is the integers, then x P(x) is false.

Existential Quantifier x P(x) is read as For some x, P(x) , or as There is an x such that P(x), or For at least one x, P(x). Examples: 1. If P(x)denotes x > 0 and U is the integers, then x P(x) is true. It is also true if U is the positive integers. 2. If P(x)denotes x < 0 and U is the positive integers, then x P(x) is false. 3. If P(x)denotes x is even and U is the integers, then x P(x) is true.

Properties of Quantifiers The truth value of x P(x) and x P(x) depend on both the propositional function P(x) and on the domain U. Examples Examples: 1. If U is the positive integers and P(x) is the statement x < 2 , then x P(x) is true, but x P(x) is false. 2. If U is the negative integers and P(x) is the statement x < 2 , then both x P(x) and x P(x) are true. 3. If U consists of 3, 4, and 5, and P(x) is the statement x > 2 , then both x P(x) and x P(x) are true. But if P(x) is the statement x < 2 , then both x P(x) and x P(x) are false.

Precedence of Quantifiers The quantifiers and have higher precedence than all the logical operators. For example, x P(x) Q(x) means ( x P(x)) Q(x) x (P(x) Q(x)) means something different. Unfortunately, often people write x P(x) Q(x) when they mean x (P(x) Q(x)).

Negating Quantified Expressions Consider x J(x) Every student in cs1820 has taken a course in Java. Here J(x)is x has taken a course in Java and the domain is students in cs1820. Negating the original statement gives It is not the case that every student in cs1820 has taken Java. This implies that There is a student in cs1820 who has not taken Java. Symbolically x J(x) and x J(x) are equivalent

De Morgans Laws for Quantifiers The rules for negating quantifiers are: The reasoning in the table shows that:

Translation from English to Logic Examples: 1. Some student in this class has visited Mexico. Solution: Let M(x) denote xhas visited Mexico and S(x) denote xis a student in this class, and U be all people. x (S(x) M(x)) 2. Every student in this class has visited Cuba or Mexico. Solution: Add C(x) denoting xhas visited Cuba. x (S(x) (M(x) C(x)))

Nested Quantifiers Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics. Example: Every real number has an inverse is x y(x + y = 0) where the domains of x and y are the real numbers.

Questions on Order of Quantifiers Example 1 1: Let U be the real numbers, Define P(x,y) : x y = 0 What is the truth value of the following: 1. x yP(x,y) Answer: False 2. x yP(x,y) Answer: True 3. x y P(x,y) Answer: True 4. x y P(x,y) Answer: True

Translating Mathematical Statements into Predicate Logic Example :Translate The sum of two positive integers is always positive into a logical expression. Solution: 1. Rewrite the statement to make the implied quantifiers and domains explicit: For every two integers, if these integers are both positive, then the sum of these integers is positive. 2. Introduce the variables x and y, and specify the domain: For all positive integers x and y, x+ yis positive. 3. The result is: x y ((x> 0) (y > 0) (x + y > 0)) where the domain of both variables consists of all integers

Arguments in Propositional Logic A argument in propositional logic is a sequence of propositions. If the premises are p1 ,p2, ,pnand the conclusion is q then (p1 p2 pn ) q is a tautology.

Rules of Inference

Arguments in Propositional Logic A argument in propositional logic is a sequence of propositions. If the premises are p1 ,p2, ,pnand the conclusion is q then (p1 p2 pn ) q is a tautology.

Using the Rules of Inference to Build Valid Arguments A valid argument is a sequence of statements. Each statement is either a premise or follows from previous statements by rules of inference. The last statement is called conclusion. A valid argument takes the following form: S1 S2 . . . Sn C

Example:

Example: