Home MATH 318 HTSEFP: Propositional logic

HTSEFP: Propositional logic CC-BY-NC

Maintainer: admin

Part one of the "How to solve every problem" series for MATH 318.

1Truth tables

Given a propositional formula, write out its truth table and determine whether or not it is a tautology.

1.1General solution

A truth table for a formula of $n$ variables will need $2^n$ lines. Just write out every possible valuation based on the combinations of the values of the variables. The formula is a tautology if and only if every single line in the truth table comes out $\top$.

1.2Examples

2Determining validity for propositional arguments

Given an argument, translate the statements into propositional formulas and determine whether or not the argument is valid.

2.1General solution

Translating should be easy, just put a $\vdash$ before the final statement. To determine validity, simply try to invalidate it: look for a valuation that makes the conclusion come out $\bot$ and the premises come out $\top$. If this is impossible, then it's valid, and explain why (due to the connectives etc).

2.2Examples

3Determining the consistency of statements

Given a set of a sentences, translate the statements into propositional formulas and determine whether or not the set is consistent.

3.1General solution

Try to make them all come out $\top$. If this is impossible, then it's inconsistent.

3.2Examples

4Representative sets

Give a representative set of propositional formulas in $n$ variables (where $n$ is a natural number). Alternatively: same as before, but use only the connectives given.

4.1General solution

A representative set of propositional formulas in $n$ variables will have $2^{2^n}$ formulas. Finding the formulas is just a matter of identifying the possible truth tables and creating a formula for each. For example, for $n=1$, there are two truth tables: either the formula comes out $\top$, or the formula comes out $\bot$. For the former, the formula $p_1$ would do it; for the latter, $\neg p_1$. For $n = 2$, there are 16 truth tables. One truth table consists of $\top$ in every situation (i.e. for all four combinations of the values of $p_1$ and $p_2$), another consists of $\bot$ in every situation, another consists of $\top$ only when $V(p_1) = V(p_2) = \top$, etc.

For each truth table, just find a corresponding formula. For example, for the truth table that comes out $\bot$ only when $V(p_1) = V(p_2)$, we could use the formula $\neg (p_1 \iff p_2)$, which would give the required truth table. It's mostly a matter of trial and error, and possibly identifying patterns.

If the connectives used in the propositional formulas must come from a supplied set, then just use those connectives to generate each formula. This should be fairly straightforward.

4.2Examples

  • Assignment 1, question 4 (for the general case)
  • Assignment 2, question 2, part b (part of the proof; also includes the "alternative" part)

5Truth tables and normal forms

Given the truth table for some unknown connective, find an equivalent formula in disjunctive normal form and one in conjunctive normal form.

5.1General solution

Disjunctive normal form
Identify the rows that come out $\top$, and find an equivalent conjunctive clause (e.g. $p \land q \land \neg r$) for each. Then join them together with $\lor$s. Simplify if possible - $(p \land q \land \neg r) \lor (p \land \neg q \land \neg r)$ can be simplified to $p \land \neg r$, for example.
Conjunctive normal form
The easiest way is probably to take the simplified formula in d.n.f. (obtained above) and use the distributive law to turn it into c.n.f. See the example in the lecture notes below for the procedure.

5.2Examples

6Functionally complete sets

Given a set of $n$ connectives, determine whether or not that set is functionally complete. Justify your answer. Alternatively: show that a set of connectives is functionally complete.

6.1General solution

Pretty simple. If it's functionally complete, you can generate every possible truth table (so $2^{2^n}$ different ones). If it's not, you can't. See the example in the assignment.

6.2Examples

  • Assignment 2, question 2