【DiscreteStructuresClassNotes · Ⅰ】Logic and Proofs

由 MisakaStone 发布

Chapter Summary

  • Propositional Logic

    • The Language of Propositions
    • Applications
    • Logical Equivalences
  • Predicate Logic

    • The Language of Quantifiers

Propositional Logic


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

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.

      • Negation ¬
      • Conjunction ∧
      • Disjunction ∨
      • Implication →
      • Biconditional ↔

Compound Proposition


The negation of a proposition p is denoted by ¬p and has this truth table :



The conjunction of propositions p and q is denoted by p ∧ q and has this truth table :

pqp ∧ q


The disjunction of propositions p and q is denoted by p ∨ q and has this truth table :

pqp ∨ q

The Connective Or in English

In English “or” has two distinct meanings.

  • Inclusive Or

    • For p ∨ q to be true, either one or both of p and q must be true.
  • Exclusive Or (Xor)

    • In p ⊕ q , one of p and q must be true, but not both.
    • The truth table for ⊕ is :
pqp ⊕ q


If p and q are propositions, then p → q is a conditional statement or implication which is read as “if p, then q” and has this truth table :

pqp → q

In p → q , p is the hypothesis (antecedent or premise) and q is the conclusion (or consequence).

Understanding Implication

In p → q there does not need to be any connection between the antecedent or the consequent. The “meaning” of p →q depends only on the truth values of p and q.

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.”

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
  • 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 (SWAP)
  • ¬q → ¬p is the contrapositive of p → q (SWAP + NEGATE)
  • ¬p → ¬q is the inverse of p → q (NEGATE)

Example: Find the converse, inverse, and contrapositive of “It’s raining is a sufficient condition for my not going to town.” This is equivalent to “If It’s raining, then I am not going to town.”


converse: If I do not go to town, then it is raining.

inverse: If it is not raining, then I will go to town.

contrapositive: If I go to town, then it is not raining.


If p and q are propositions, then we can form the biconditional proposition p ↔ q , read as “p if and only if q.” The biconditional p ↔ q denotes the proposition with this truth table :

pqp ↔ q

The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

If p denotes “I am at home.” and q denotes “It is raining.”, then p ↔ q denotes “I am at home if and only if it is raining.”

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


Truth Tables For Compound Propositions

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

Solution: Each propositional variable’s value can be T or F, therefore, there are $ 2^{n} $ rows in a truth table with n variables.

Note that this means that with n propositional variables, we can construct $ 2^{n} $ distinct (not equivalent) propositions.

How to fill up the rows – the combinations of values for the atomic propositions.


  • Start in the left-most column, divide it evenly, fill the first half with T’s and the second half with F’s.
  • Then move right to the next column, repeat the previous step in the first half of the column and the second half of the column. Repeat until the last column is filled with alternating T's and F's.
  • The first row will be all T's.
  • The last row will be all F's.

Equivalent Propositions

Two propositions are equivalent if they always have the same truth value.

Example: Show using a truth table that the conditional is equivalent to the contrapositive.


pq¬p¬qp → q¬q → ¬p

Logic and Bit Operations

Computers represent information using bits.

A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one).

A bit can be used to represent a truth value, because there are two truth values, namely, true and false.

Truth ValuesBit

Customarily, we will use a 1 bit to represent true and a 0 bit to represent false. That is, 1 represents T (true), 0 represents F (false).

A variable is called a Boolean variable if its value is either true or false. Consequently, a Boolean variable can be represented using a bit.

Computer bit operations correspond to the logical connectives.

  • Bitwise OR (∨, Disjunction, Inclusive OR)
  • Bitwise AND (∧, Conjunction)
  • Bitwise XOR (⊕, Disjunction, Exclusive OR)

A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.

Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101.

Bitwise Calculations

Applications of Propositional Logic

Boolean Searches

Logical connectives are used extensively in searches of large collections of information, such as indexes of Web pages. In Boolean searches,

Andmatch records that contain both of two search terms
Ormatch one or both of two search terms
Notexclude a particular search term. (sometimes written as AND NOT )

Web Page Searching Most Web search engines support Boolean searching techniques, which usually can help find Web pages about particular subjects.

Logic Circuits

Electronic circuits: each input/output signal can be viewed as a 0 or 1.

  • 0 represents False
  • 1 represents True

Complicated circuits are constructed from three basic circuits called gates.

Basic Ciruits

We will study logic circuits in great details in Boolean Algebra.

Propositional Equivalences

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
  • A contingency is a proposition which is neither a tautology nor a contradiction, such as p
P¬pp ∨ ¬pp ∧ ¬p

Logically Equivalent

Two compound propositions p and q are logically equivalent if p ↔ q is a tautology.

We write this as p ⇔ q or 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 that ¬p ∨ q is equivalent to p → q.

pq¬p¬p ∨ qp → q

De Morgan’s Laws

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

Key Logical Equivalences

  • Identity Laws

    • p ∧ T ≡ p
    • p ∨ F ≡ p
  • Domination Laws

    • p ∨ T ≡ T
    • p ∧ F ≡ F
  • Idempotent laws

    • p ∨ p ≡ p
    • p ∧ p ≡ p
  • Double Negation Law

    • ¬(¬p) ≡ p
  • Negation Laws

    • p ∨ ¬p ≡ T
    • p ∧ ¬p ≡ F
  • Commutative Laws

    • p ∨ q ≡ q ∨ p
    • p ∧ q ≡ q ∧ q
  • Associative Laws

    • (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
    • (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
  • Distributive Laws

    • p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
    • p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
  • Absorption Laws

    • p ∨ (p ∧ q) ≡ p
    • p ∧ (p ∨ q) ≡ p

More Logical Equivalences

  • Logical Equivalences Involving Conditional Statements

    • p → q ≡ ¬p ∨ q
    • p → q ≡ ¬q → ¬p
    • p ∨ q ≡ ¬p → q
    • p ∧ q ≡ ¬(p → ¬q)
    • ¬(p → q) ≡ p ∧ ¬q
    • (p → q) ∧ (p → r) ≡ p → (q ∧ r)
    • (p → r) ∧ (q → r) ≡ (p ∨ q) → r
    • (p → q) ∨ (p → r) ≡ p → (q ∨ r)
    • (p → r) ∨ (q → r) ≡ (p ∧ q) → r
  • Logical Equivalencecs Involving Biconditional Statements

    • p ↔ q ≡ (p → q) ∧ (q → p)
    • p ↔ q ≡ ¬p ↔ ¬q
    • p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
    • ¬(p ↔ q) ≡ p ↔ ¬q

Predicates and Quantifiers

Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language.

Need a language, predicate logic, that talks about objects, their properties, and their relations.

Predicate logic can be used to express the meaning of a wide range of statements in mathematics and computer science in ways that permit us to reason and explore relationships between objects.

Introducing Predicate Logic

Predicate logic uses the following new features :

  • Variables: x, y, z
  • Predicates: P(x), M(x)
  • Quantifiers

Propositional functions are a generalization of propositions.

  • They contain variables and a predicate, e.g., P(x)
  • Variables can be replaced by elements from their domain.

We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable.

The statement P(x) is also said to be the value of the propositional function P at x.

Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.

Propositional Functions

For example, let P(x) denote “x > 0” and the domain be the integers.

  • P(-3) is false.
  • P(0) is false.
  • P(3) is true.

Often the domain is denoted by U. So in this example U is the integers.

In general, a statement involving the n variables $ x_{1} , x_{2}, ... , x_{n} $ can be denoted by

$$ P(x_{1} , x_{2}, ... , x_{n}) $$

A statement of the form $ P(x_{1} , x_{2}, ... , x_{n}) $ is the value of the propositional function P at the n-tuple ($ x_{1} , x_{2}, ... , x_{n} $), and P is also called an n-place predicate or a n-ary predicate.


Quantification expresses the extent to which a predicate is true over a range of elements.

We need quantifiers to express the meaning of English words including all and some :

  • “All men are Mortal."
  • “Some cats do not have fur.”

The area of logic that deals with predicates and quantifiers is called the predicate calculus.

Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain.

The two most important quantifiers are :

  • Universal Quantifier, “For all,” symbol: ∀
  • Existential Quantifier, “There exists,” symbol: ∃

∀x P(x) asserts P(x) is true for every x in the domain.

∃x P(x) asserts P(x) is true for some x in the domain.

Universal Quantifier

∀x P(x) is read as “For all x, P(x)” or “For every x, P(x).”

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).”

Precedence of Quantifiers

The quantifiers ∀ and ∃ have higher precedence than all the logical operators.

De Morgan’s Laws for Quantifiers

The rules for negating quantifiers are :

De Morgan’s Laws

Logic Programming

Prolog (from Programming in Logic) is a programming language developed in the 1970s by researchers in artificial intelligence (AI).

Prolog programs include Prolog facts and Prolog rules.

There is much more at Learn Prolog Now! to Prolog and to the entire field of logic programming.

Thanks for the learning resource provided by Qi Wang from University at Albany!