Skip to main content

Subsection 3.3.7 Computation

Once we’ve proved all of these identities, we can use them to transform and simplify logical expressions. If necessary, we can apply several of them, one step at a time.

As we do that, we may find that we want to compute logical values. Appealing to our analogy with algebra, we have that:

\(x + 5 – 5 \) can be simplified to: \(x\)

\(5 + 7 \) can be simplified to: \(12 \)

In logic, we compute with the truth values T and F . It is straightforward to prove all of these equivalences with truth tables:

  • p ∨ ¬ p ≡ T ¬ p ∨ p ≡ T

  • p ∧ ¬ p ≡ F ¬ p ∧ p ≡ F

  • p ∨ T ≡ T T ∨ p ≡ T

  • p ∨ F ≡ p F ∨ p ≡ p

  • p ∧ T ≡ p T ∧ p ≡ p

  • p ∧ F ≡ F F ∧ p ≡ F

When we use one of these facts, we’ll label that step with the justification Computation .

Suppose that we are presented with the following logical expression (maybe as the solution to some circuit design problem):

\(p \wedge \neg ( \neg s \vee p) \)

We want to try to simplify it before we use it for something else. We’ll show here a set of steps that do that. On each line (except the first), we’ll indicate the identity that we used in moving to it from the equivalent logical expression above it. We’ll also underline the part of the input expression to which the identity applied.

    Exercises Exercises

    The problems in this section are simple and give you a chance to practice working with individual identities.

    1.

    1. Given the statement: ¬( p ∧ ¬ q ) ∨ r

    Which of the following alternative statements is equivalent to the one we’ve been given:

    I. (¬ p ∨ q ) ∨ r

    II. ( p ∨ ¬ q ) ∨ r

    III. (¬ p ∨ q ) ∨ ¬ r

    1. Just I.

    2. Just II.

    3. Just III.

    4. Just I and II.

    5. Just II and III.

    Answer.
    Correct answer is A.
    Solution.
    Explanation: We get I by applying De Morgan and then Double Negation once to rewrite r to r. The other two aren’t equivalent.

    2.

    2. Given the statement: p → ( q ∨ r )

    Which of the following alternative statements is equivalent to the one we’ve been given:

    I. (¬ p ∨ q ) ∨ r

    II. ( q ∨ r ) → p

    III. ( p → q ) ∨ r

    1. Just I.

    2. Just II.

    3. Just III.

    4. Just I and II.

    5. Just I and III.

    Answer.
    Correct answer is E.
    Solution.
    Explanation: We get I by applying Conditional Disjunction and then Associativity. We get III by applying Conditional Disjunction, then Associativity, and then Conditional Disjunction again.

    Exercise Group.

    3. Prove that implies isn’t associative. To do this, you need to show that:

    ( p → q ) → r

    is not logically equivalent to:

    p → ( q → r )

    Use a truth table to show that this claim is not a tautology:

    (( p → q ) → r ) ≡ ( p → ( q → r ))

    Use the truth table app. Click here to begin.

    www.truthtables.org/#/true/((p->q)->r)=(p->(q->r)) 1 

    3.
    (Part 1) When you’ve finished the table, enter the value for the ((p  q)  r) column here. Enter a sequence of t’s and f’s, separated by a single space
    Answer.
    Box to enter value. Correct answer is: t f t t t f t f
    4.
    (Part 2) Enter the value for the (p  (q  r)) column as a single string of T’s and F’s.
    Answer.
    Box to enter value. Correct answer is: t f t t t t t t
    truthtables.org