Introduction to propositional logic

- Lectures 1-4.

- Proposition, propositional variable, propositional formula,
- Logic connectives: AND ($\wedge$, conjunction), OR ($\vee$, disjunction), NOT ($\neg$, negation), IF .. THEN ($\to$, implication)
- Truth assignment, satisfying assignment, falsifying assignment, tautology, contradiction.
- Truth table, de Morgan's laws, double negation.
- Negation and simplification. Definition of $\to$ in terms of $\neg, \vee$.

Solve each of the following exercises.

- Let k be some specific number. Let A = "k is even", B = "k > 7", C = "k is prime".
- Write the following sentences about k as logical formulas using A, B, C:
- Number k is either even or greater than 7.
- If k is both even and prime, then in particular it is even.
- Either k is even, or k is prime, and not both.

- Now, for the same A, B, C as above, write the following formulas in English.
- $ C \wedge B \to \neg A$
- $ \neg C \wedge A \wedge C$
- $ (A \wedge B) \to (A \wedge B)$

- For each of the six formulas above, say if it is a tautology, a contradiction, or neither.
- 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.

- Write the following sentences about k as logical formulas using A, B, C:
- 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$
- How many rows are in a truth table for F? And how many in the truth table for G?
- 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)))$.

- What are the values of F and G when A=False, B=False, C=True and D=False?
- Are F and G equivalent?

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.

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.

- $(A \wedge \neg B) \to (A \vee B \to \neg B)$
- $(\neg B \to A) \wedge (\neg A \to B) \vee (\neg C \to B) $

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

- $(A \wedge \neg B) \to (A \vee B \to \neg B)$
- $(\neg B \to A) \wedge (\neg A \to B) \vee (\neg C \to B) $

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.

- $(A \wedge \neg B) \to (A \vee B \to \neg B)$
- $(\neg B \to A) \wedge (\neg A \to B) \vee (\neg C \to B) $

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

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

- Draw a parse tree for this formula.
- Parenthesize it fully.
- Write a truth table for it, noting all intermediate subformulas.
- 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.
- Simplify the initial (not negated) formula as much as you can. Use the table of equivalences above.