Logical Deduction

Videos (~45 mins)

Reading (~15 mins)

No formal reading for today, but these slides from Prof. Xin He at the University of Buffalo provide a good written overview of logical inference rules, as well as several additional worked examples.

Warmup (~50 mins)

Problem 1

Consider the following rule of logical deduction:

\[ \begin{array}{lll} \mathrm{(P1)}:& p \lor q \\ \mathrm{(P2)}:& \lnot q \\ \hline \therefore & p \end{array} \]

Please write a careful proof of this deduction using known rules. Please number each line of your derivation. For each step, please state which rule of logical deduction or logical equivalence you are using, as well as the previous line(s) to which you are applying the equivalence.

Problem 2

Below are two logical deductions. For each of the two, determine whether the deduction is valid.

  • If the deduction is valid, write a proof of the deduction using rules of logical deduction (such as modus ponens, modus tollens, and logical equivalence rules). Please number each line of your derivation. For each step, please state which rule of logical deduction or logical equivalence you are using, as well as the previous line(s) to which you are applying the equivalence.
  • If the deduction is invalid, determine a set of truth values for each of the variables such that all the premises are true but the conclusion is false.

Deduction 1

\[ \begin{array}{lll} \mathrm{(P1)}:& p \rightarrow q \\ \mathrm{(P2)}:& q \rightarrow r \\ \mathrm{(P3)}:& q \\ \hline \therefore & r \land p \end{array} \]

Deduction 2

\[ \begin{array}{lll} \mathrm{(P1)}: & p \rightarrow q \\ \mathrm{(P2)}:& \lnot q \lor \lnot r \\ \mathrm{(P3)}:& r \\ \hline \therefore & \lnot p \end{array} \]

Problem 3

Write a complete derivation justifying the following logical deduction. You will likely need to use the rules of universal and existential instantiation covered in the lecture video. Please number each line of your derivation. For each step, please state which rule of logical deduction or logical equivalence you are using, as well as the previous line(s) to which you are applying the equivalence.

\[ \begin{array}{lll} \mathrm{(P1)}:& \forall x \in S, (\lnot R(x) \lor \lnot Q(x)) \\ \mathrm{(P2)}:& \exists x \in S: R(x) \\ \hline \therefore & \exists x \in S: \lnot Q(x) \end{array} \]

Hint: This one is pretty complex! I wrote a total of 7 lines, and used the following rules (some more than once):

  • Double negation
  • Implication equivalence
  • Conjunction deduction
  • Existential instantiation
  • Existential generalization: if I have an element \(x\in S\) such that \(P(x)\) is true, then I can deduce \(\exists x \in S: P(x)\).
  • Universal instantiation
  • Modus tollens



© Phil Chodrow, 2024