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

Write a truth table for the following formulas. Include intermediate subformulas as columns.

Topic 2: Negations

Negate the following formulas. Apply 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

Simplify the following formulas as much as you can. In addition to $F \to G \equiv (\neg F \vee G)$, you can use equivalences from the table below the formulas. 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 three tasks on this formula:

  1. Write a truth table for this formula
  2. Negate this formula, and use 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.
  3. Simplify the initial (not negated) formula as much as you can. Use the table of equivalences above.