Logic and Proofs

• Propositional Logic
  • The Language of Propositions
  • Applications
  • Logical Equivalences
• Predicate Logic
  • The Language of Quantifiers
  • Logical Equivalences
  • Multiple Quantifiers
• Proofs
  • Rules of Inference

• The Language of Propositions
  • Connectives
  • Truth Values
  • Truth Tables
• Applications
  • Translating English Sentences
  • System Specifications
  • Logic Puzzles
  • Logic Circuits
• Logical Equivalences
  • Important Equivalences
  • Showing Equivalence
  • Satisfiability

Propositional Logic S E C T I O N 1. 1

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

• Logic is the study of consequence.
  • Given a few mathematical statements or facts, we would like to be able to draw some conclusions.
• Logic aims to determine in which cases a conclusion is, or is not, a consequence of a set of premises.
• Example:
  • Premise/Fact #1: If Sara eats her vegetables, then she can have a cookie.
  • Premise/Fact #2: Sara eats her vegetables.
  • Conclusion: Sara gets a cookie.

• A proposition is a declarative sentence that is either true or false.
• Examples of propositions: a) The Moon is made of green cheese. b) Cairo is the capital of Egypt. c) Toronto is the capital of Canada. + = 1 d) 1 0 e) 0 + 0 = 2
• Examples that are not propositions. a) Sit down! b) What time is it? c) x + 1 = 2 d) x + y = z

• 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 is true and p is false. q

In q

there does not need to be any connection

• p between the antecedent or the consequent. The depends only on the truth values → p q of and. p q
• “meaning” of → These implications are perfectly fine, but would not be used in ordinary English.
• “If the moon is made of green cheese, then I have more money than Bill Gates. ”
• “If the moon is made of green cheese then I’m on welfare.”
• “If 1 + 1 = 3, then your grandma wears combat boots.”

• Implication ‘If...then...’ Symbol: → Terminology
• • p = premise, hypothesis, antecedent
• • q = conclusion, consequence

p if and only if q ” is expressed in English:

• Some alternative ways “
  • p is necessary and sufficient for q
  • if p then q, and conversely
  • p iff q (abbreviation of if and only if)

• Construction of a truth table:
• Rows
  • Need a row for every possible combination of values for the atomic propositions.
• Columns
  • Need a column for the compound proposition (usually at far right)
  • Need a column for the truth value of each expression that occurs in the compound proposition as it is built up.
    • This includes the atomic propositions

• Construct a truth table for

• Construct the truth table of the compound proposition: p  q p q → ∨ ∧

• How many rows are there in a truth table with n propositional variables?

Solution: n We will see how to do this in Chapter 6.

• Note that this means that with n propositional variables, we can construct 2 n distinct (i.e., not equivalent) propositions.

Applications of Propositional Logic S E C T I O N 1. 2

• Translating English to Propositional Logic
• System Specifications
• Logic Puzzles
• Logic Circuits

Problem: Translate the following sentence into propositional logic:

if you are a computer science major or you are not a freshman, You can

“

access the Internet from campus.”

Solution:

Let a

: “You can access the internet from campus,”

c

: “You are a computer science major,” f: “You are a freshman.”

)

f

(c ∨ ¬ → a

• System and Software engineers take requirements in English and express them in a precise specification language based on logic.

Example: Express in propositional logic:

when the file system is full”

“The automated reply cannot be sent

Solution: One possible solution:

Let q denote “The automated reply

can be sent”

and p denote “The file system is full.”

q

p→ ¬

Definition: A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true.

Exercise: Are these specifications consistent?

• “The diagnostic message is stored in the buffer or it is retransmitted.”
• “The diagnostic message is not stored in the buffer.”
• “If the diagnostic message is stored in the buffer, then it is retransmitted.”

Solution:

• Let p denote “The diagnostic message is stored in the buffer.”
• Let q denote “The diagnostic message is retransmitted”
• The specification can be written as: q, p, ¬ .
• When p is false and q is true all three statements are true. (see TT next) p ∨ p→ q

So the specification is consistent.

• Consider the following set of propositions. Do they form a consistent or inconsistent set? (1) John is at the store. (2) Corinne plays guitar. (3) Mike cheats on his taxes. (4) John is a fire-fighter.

Solution:

• Consistent. Notice that nothing in the logical form of (1)-(4) prevents all of the propositions from being true.

Propositional Equivalences S E C T I O N 1. 3

• Tautologies, Contradictions, and Contingencies.
• Logical Equivalence
  • Important Logical Equivalences
  • Showing Logical Equivalence
• Propositional Satisfiability
  • Sudoku Example

q are logically equivalent

• Show that p → q and ¬p ∨

• Identity Laws: ,
• Domination Laws: ,
• Idempotent laws: ,
• Double Negation Law:
• Negation Laws: ,

• We can show that two expressions are logically equivalent by developing a series of logically equivalent statements.
• To prove that we produce a series of equivalences beginning with A and ending with B.
• Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition.

• When a compound proposition involves many atomic components, the size of the truth table for the compound proposition becomes large
• Q1: How many rows are required to construct the truth-table of: q ( (¬(s r) ¬ t) ) → (q→r ¬ ) ?  p→r
• Q2: How many rows are required to construct the truth-table of a ∧ ∧ ∨ proposition involving n atomic components?
• A1: 32 rows, each additional variable doubles the number of rows
• A2: In general, n rows 2
• Therefore, as compound propositions grow in complexity, truth tables become more and more unwieldy.
• In such cases, it is better to use derivational proof techniques

• A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, the compound proposition is unsatisfiable.
• A compound proposition is unsatisfiable if and only if its negation is a tautology.

Predicates and Quantifiers S E C T I O N 1. 4

• Predicates
• Variables
• Quantifiers
  • Universal Quantifier
  • Existential Quantifier
• Negating Quantifiers
  • De Morgan’s Laws for Quantifiers
• Translating English to Logic

• If we have: “All men are mortal.” “Socrates is a man.”
• Does it follow that “Socrates is mortal?”
• Can’t be represented in propositional logic. Need a language that talks about objects, their properties, and their relations.

• A generalization of propositions - propositional functions or predicates: propositions which contain variables
• Predicates become propositions once every variable is bound- by:
  • Assigning it a value from the Universe of Discourse U or
  • Quantifying it

• Connectives from propositional logic carry over to predicate logic.
• If P(x) denotes “ x > find these truth values: P(3) -1) Solution: T 0,” P() -1) Solution: F 3 ∨ P( P() -1) Solution: F 3 ∧ P(
• → P( Expressions with variables are not propositions and therefore do not have truth values. For example, P() y 3 ) P() y x )
• ∧ P( When used with quantifiers (to be introduced next), these expressions → P( (propositional functions) become propositions.

•  x P (x) is read as For all x, P(x )” or “ For every x, P(x )” “ Examples:

1. If P(x) denotes “ x > U is the integers, then  x P (x) is false.
2. If P(x) denotes “ x U is the positive integers, then  x P (x) is true.
   • 0” and
3. If P(x) denotes “ x is even U is the integers, then  x P (x) is false. 0” and ” and

• 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:

1. If U is the positive integers and P(x) is the statement x < then  2 ”, 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 < then both  2 x P(x) x P(x) and  are false.

Example: Translate the following sentence into predicate logic:

“Every student in this class has taken a course in Java.” Solution:

First decide on the domain U.

Solution: If U is all students in this class,

• define a propositional function J(x) denoting “x has taken a course in Java” and
• translate as  x J(x).

Solution: But if U is all people, also

• define a propositional function S(x) denoting “x is a student in this class” and
• translate as  . x (S(x)→ J(x))

Example 2: Translate the following sentence into predicate logic:

“Some student in this class has taken a course in Java.” Solution:

First decide on the domain U.

Solution: If U is all students in this class, translate as



x J(x)

Solution: But if U is all people, then translate as

 x (S(x) ∧ J(x))

• Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value
  • for every predicate substituted into these statements and
  • for every domain of discourse used for the variables in the expressions.
• The notation S T indicates that S T and are logically equivalent.
• Example:  x S(x)  x S(x) ¬¬ ≡ ≡

• Consider  x J(x) “Every student in your class has taken a course in Java.” Here J(x) is the statement “x has taken a course in ” and Java the domain is students in your class.
• Negating the original statement gives “It is not the case that every student in your class has taken Java.” This is equivalent to “There is a student in your class who has not taken Java.” Symbolically ¬ x J(x)   and x ¬J(x) are equivalent

• Now Consider  x J(x) “There is a student in this class who has taken a course in Java.” Where J(x) is “x has taken a course in Java.”
• Negating the original statement gives “It is not the case that there is a This is equivalent to Every student in this class who has taken Java.” “ student in this class has not taken Java” Symbolically ¬ x J(x)   and x ¬J(x) are equivalent

Examples:

1. “Some student in this class has visited Mexico.” Solution: Let M (x) denote “ has visited Mexico” and) denote “ x S (x x is a student in this class,” and U be all people.  x (S(x) M(x))
2. “Every student in this class has visited Canada or Mexico.” ∧ Solution: Add C (x) denoting “ has visited Canada.” x  x (S(x)→ (M(x)∨C(x)))

• U = {fleegles, snurds, thingamabobs} F(x) : x is a fleegle S(x) : x is a snurd T(x) : x is a thingamabob Translate “Everything is a fleegle”

Solution: 

x F(x)

• U = {fleegles, snurds, thingamabobs} F(x) : x is a fleegle S(x) : x is a snurd T(x) : x is a thingamabob “Nothing is a snurd.”

Solution: ¬  x S(x)

What is this equivalent to?

Solution:  x S(x)

¬

• U = {fleegles, snurds, thingamabobs} F(x) : x is a fleegle S(x) : x is a snurd T(x) : x is a thingamabob “All fleegles are snurds.”

Solution: 

x (F(x)→ S(x))

• U = {fleegles, snurds, thingamabobs} F(x) : x is a fleegle S(x) : x is a snurd T(x) : x is a thingamabob “Some fleegles are thingamabobs.”

Solution:  x (F(x) T(x))

∧

• U = {fleegles, snurds, thingamabobs } F(x) : x is a fleegle S(x) : x is a snurd T(x) : x is a thingamabob “No snurd is a thingamabob.”

Solution: ¬  x (S(x) T(x)) What is this equivalent to?

∧

Solution:  x (

¬

¬ T(x))

S(x) ∨

Consider these statements, of which the first three are premises and the fourth is a valid conclusion.

• “All hummingbirds are richly colored .”
• “ No large birds live on honey.” dull in color .”
• “Birds that do not live on honey are
• “Hummingbirds are small.”

Let:

P(x) , be the statements “ is a hummingbird,”

x

• Q(x) , be the statements “ is large,” x R(x) , be the statements “ lives on honey,” x
• S(x) be the statements “ x is richly colored ,”
• Assuming that the domain consists of all birds, express the statements in the argument using quantifiers and P(x) , Q(x) , R(x) , and S(x) .

We can express the statements in the argument as

• x(P(x) S(x)). →
• ¬ x(Q(x) R(x)). ∀
• ¬ R(x) S(x)). x( ¬ → ∃ ∧
• x(P(x) → ¬ Q(x)). ∀ ∀

Rules of Inference

R O S E N 1. 6

• Let p to represent = you have my password, q= you can log on to my email
• Fact 1:
  • "If you have my password, then you can log on to my email",
  • p→q = T
• Fact 2:
  • "You cannot log on to my email",
  • ¬q = T
• What can we conclude from these two facts??
• ¬p = T You do not have a password!!!!



3 

2 

2   (2)  

• A valid argument can lead to an incorrect



2 

conclusion, if one of its premises is

wrong/false!

2 

3 



 2   



2 

p: 2 

The argument is valid as it is constructed using modus

ponens.

3 



But one of the premises is false (q is false)

q: 2   

2 



So, we cannot derive the conclusion is true. Also note that the conclusion q of this statement is false

p  q

Show that the premises: It is not sunny this afternoon and it is colder than yesterday.

If we go swimming it is sunny this afternoon.

If we do not go swimming then we will take a canoe trip.

If we take a canoe trip then we will be home by sunset.

lead to the conclusion: We will be home by sunset

1. Anna is skiing or it is not snowing.
2. It is snowing or Bart is playing hockey.
3. Consequently Anna is skiing or Bart is playing hockey. We want to show that (3) follows from (1) and (2)

You might think of this as some sort of game.

You are given some statement, and you want to see if it is a valid argument and true You translate the statement into argument form using propositional variables, and make sure you have the premises right, and clear what is the conclusion You then want to get from premises/hypotheses (A) to the conclusion (B) using the rules of inference.

So, get from A to B using as “moves” the rules of inference