Discrete Mathematics Study Center

Home Course Notes Exercises Mock Exam About

Logic

• Logic gives precise meaning to statements
  • tells us precisely what statements mean
  • allows computers to reason without the baggage of language
• the building block of logic is the proposition
  • a declarative sentence that is either true or false
    • "Carleton University is located in Ottawa"
    • "$1+1=2$"
    • "$1+1=3$"
• sentences that are not declarative are not propositions:
  • "How are you feeling today?"
  • "Pay attention!"
• sentences that are neither true nor false are not propositions:
  • "$x+y=z$"
  • "This sentence is false."
• we can assign propositions names like $a,b,c,\ldots$ for short
• the truth value of a proposition is either $T$ (true) or $F$ (false)
• a single proposition should express a single fact:
  • "It is Monday and I am in class" is better expressed as two propositions: "It is Monday", "I am in class"

Connectives

How do we assert two propositions are true (or otherwise related) at once?

• use connectives to create compound propositions
• negation: if $p$ is a propostion, then "it is not the case that $p$ is true" is a compound proposition called the negation of $p$, written $\neg p$
  • The negation of "The network is functioning normally" is "It is not the case that the network is functioning normally" (or just "The network is not functioning normally")
  • as a general rule, the original propositions you define should not contain a negation
  • the truth value of a negation can be determined using a truth table: \begin{array}{c|c} p & \neg p \\\hline T & F \\ F & T \\ \end{array}
• conjunction ("and"): if $p$ and $q$ are propositions, then "$p$ and $q$" is a compound proposition called the conjunction of $p$ and $q$, written $p \wedge q$
  • "The program is fast and the program is accurate" (or just, "The program is fast and accurate")
  • conjunction has the following truth table: \begin{array}{cc|c} p & q & p \wedge q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F\\ \end{array}
  • there are many ways to express conjunction: "and", "but", "so", "also", ...
• disjunction ("or"): if $p$ and $q$ are propositions, then "$p$ or $q$" is a compound proposition called the disjunction of $p$ and $q$, written $p \vee q$
  • "I work hard or I fail"
  • disjunction has the following truth table: \begin{array}{cc|c} p & q & p \vee q \\\hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \end{array}
  • disjunction in logic differs a bit from casual language
  • there are two kinds of "or": inclusive and exclusive
    • inclusive: "Students must have taken computer science or calculus to enroll in this course"
    • exclusive: "The meal comes with a soup or salad"
  • we will always assume inclusive or when we use the $\vee$ symbol
  • for exclusive or, we write $\oplus$ and use the following truth table: \begin{array}{cc|c} p & q & p \oplus q \\\hline T & T & F \\ T & F & T \\ F & T & T \\ F & F & F \\ \end{array}
• implication ("if...then"): if $p$ and $q$ are propositions, then the implication "if $p$ then $q$" is a compound propositon, written $p \rightarrow q$
  • "If the website is down, then the technical support person must fix it"
  • We call $p$ the hypothesis and $q$ the conclusion
  • implication has the following truth table: \begin{array}{cc|c} p & q & p \rightarrow q \\\hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array}
  • there are many ways to write $p \rightarrow q$ in English:
    • if $p$ then $q$
    • $p$ implies $q$
    • if $p$, $q$
    • $p$ only if $q$
    • $p$ is sufficient for $q$
    • a sufficient condition for $q$ is $p$
    • $q$ if $p$
    • $q$ whenever $p$
    • $q$ when $p$
    • $q$ is necessary for $p$
    • $q$ follows from $p$
    • a necessary condition for $p$ is $q$
  • when $p$ is false, $p \rightarrow q$ is true regardless of the truth value of $q$
  • given $p \rightarrow q$, we can define a few special propositions:
    • $q \rightarrow p$ is the converse
    • $\neg q \rightarrow \neg p$ is the contrapositive
    • $\neg p \rightarrow \neg q$ is the inverse
• biconditional ("if and only if"): if $p$ and $q$ are propositions, then the biconditional "$p$ if and only if $q$" is a compound propositon, written $p \leftrightarrow q$
  • "You will pass this course if and only if you study"
  • The biconditional has the following truth table: \begin{array}{cc|c} p & q & p \leftrightarrow q \\\hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \end{array}
  • "if and only if" is often abbreviated to "iff"
  • we say "$p$ is necessary and sufficient for $q$", "if $p$ then $q$, and conversely", or "$p$ iff $q$"

A quick note on precedence:

• we will use brackets as much as possible to make precedence clear
• as a general rule, negation applies to whatever is directly after only
  • $\neg p \vee q$ is $(\neg p) \vee (q)$
• use brackets for everything else so there is no ambiguity

Translating Sentences

• Let $a$ be the proposition "the computer lab uses Linux", $b$ be the proposition "a hacker breaks into the computer" and $c$ be the proposition "the data on the computer is lost."
  • $(a \rightarrow \neg b) \wedge (\neg b \rightarrow \neg c)$ means "If the computer in the lab uses Linux then a hacker will not break into the computer, and if a hacker does not break into the computer then the data on the computer will not be lost."
  • $\neg(a \vee \neg b)$ means "It is not the case that either the computer in the lab uses Linux or a hacker will break into the computer." (This is a bit awkward. We will learn how to phrase this better later.)
  • $c \leftrightarrow (\neg a \wedge b)$ means "The data on the computer is lost if and only if the computer in the lab does not use Linux and a hacker breaks into the computer."
• How could we translate "If the hard drive crashes then the data is lost"?
  • Let $h$ be the proposition "the hard drive crashes" and $d$ be the proposition "the data is lost." The sentence translates to $h \rightarrow d$.
• How could we translate "The infrared scanner detects motion only if the intruder is in the room or the scanner is defective"?
  • Let $m$ be the proposition "the infrared scanner detects motion", $i$ be the proposition "the intruder is in the room" and $d$ be the proposition "the scanner is defective." The sentence translates to $m \rightarrow (i \vee d)$.
• How could we translate "If the server is down and the network connection is lost, then email is not available but I can still play games" into propositional logic?
  • Let $s$ be the proposition "the server is down", $n$ be the proposition "the network connection is lost", $e$ be the proposition "email is available" and $g$ be the proposition "I can play games." The sentence translates to $(s \wedge n) \rightarrow (\neg e \wedge g)$.