MUN Computer Science 1002 - Lab 1

Introduction to propositional logic

Review:

Vocabulary

 

Individual work

Solve each of the following exercises.

  1. Let k be some specific number. Let A = "k is even", B = "k > 7", C = "k is prime".
    1. Write the following sentences about k as logical formulas using A, B, C:
      1. Number k is either even or greater than 7.
      2. If k is both even and prime, then in particular it is even.
      3. Either k is even, or k is prime, and not both.
    2. Now, for the same A, B, C as above, write the following formulas in English.
      1. $ C \wedge B \to \neg A$
      2. $ \neg C \wedge A \wedge C$
      3. $ (A \wedge B) \to (A \wedge B)$
    3. For each of the six formulas above, say if it is a tautology, a contradiction, or neither.
    4. For each of the six formulas above which are neither tautology nor contradiction, give one satisfying assignment and one falsifying assignment to variables A, B, C.
  2. Let F be a formula $A \vee (\neg B) \vee A \wedge C \to (A \wedge \neg D)$ and G be a formula $(C \to D) \vee (\neg D \wedge \neg C) \to A$
    1. How many rows are in a truth table for F? And how many in the truth table for G?
    2. What are the values of F and G when A=True, B=False, C=True and D=True?
      • Remember the order of precedence: $A \to B \vee C \wedge \neg D$ is parenthesized $A \to (B \vee (C \wedge (\neg D)))$.
    3. What are the values of F and G when A=False, B=False, C=True and D=False?
    4. Are F and G equivalent?

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Topic 1: Truth tables

First draw parse trees for the formulas below. Then write a truth table for each of these two formulas. Include intermediate subformulas (nodes from your parse tree) as columns.

Topic 2: Negations

First draw parse trees for the formulas below. Use the parse trees to parenthesize the formulas fully. Then, negate the resulting formulas (using the parse trees as a hint) by applying double negation and De Morgan's laws, until all negations are on the variables. You will also find it useful to remember that $\neg (F \to G) \equiv (F \wedge \neg G)$.

Topic 3: Simplifications

First draw parse trees for the formulas below. Use the parse trees to parenthesize the formulas fully. Then, use the parse trees and the equivalences from the table below to simplify the resulting formulas as much as you can. It might be also helpful to remember that $F \to G \equiv (\neg F \vee G)$. You might find it useful to note which equivalences you use as you are writing your simplifications; do not bother memorizing the names.

Name $\wedge$-version $\vee$-version
Double negation $\neg \neg p \equiv p$
DeMorgan's laws $\neg (p \wedge q) \equiv (\neg p \vee \neg q)$ $\neg (p \vee q) \equiv (\neg p \wedge \neg q)$
Commutativity $( p \wedge q ) \equiv (q \wedge p)$ $( p \vee q ) \equiv (q \vee p)$
Associativity $(p \wedge (q \wedge r)) \equiv ((p \wedge q) \wedge r)$ $(p \vee (q \vee r)) \equiv ((p \vee q) \vee r)$
Distributivity $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
Identity $p \wedge TRUE \equiv p$ $p \vee FALSE \equiv p$
$p \wedge FALSE \equiv FALSE$ $p \vee TRUE \equiv TRUE$
Idempotence $p \wedge p \equiv p $ $p \vee p \equiv p$
Absorption $p \wedge (p \vee q) \equiv p$ $p \vee (p \wedge q) \equiv p$

Here, $p, q, r$ are propositional variables. TRUE and FALSE are formulas that are always true and always false, respectively. In particular, $TRUE = (A \vee \neg A)$ and $FALSE = (A \wedge \neg A)$ for some (any) formula $A$.

Review after the group exercises

Take a formula $(\neg B \vee A) \to (\neg A \wedge \neg B)$. Now, do all of the following tasks on this formula:

  1. Draw a parse tree for this formula.
  2. Parenthesize it fully.
  3. Write a truth table for it, noting all intermediate subformulas.
  4. Negate this formula, using double negation and De Morgan's laws, together with $\neg (F \to G) \equiv (F \wedge \neg G)$ equivalence, to bring all negations down to variables.
  5. Simplify the initial (not negated) formula as much as you can. Use the table of equivalences above.