Propositional Logic: Proofs

Propositional Logic: Proofs - Review

• Propositional formulas are built from variables $p, q, r, \dots$ and constants $T$ and $F$.
• The connectives used are $\land, \lor, \neg, \rightarrow, \leftrightarrow$.
• Meaning is assigned via a truth assignment $\mathcal{A}$, mapping each propositional variable to a truth value ($\mathbf{T}$ or $\mathbf{F}$).
• Formula truth values are recursively determined by subformula values and connective truth tables.
• $\Gamma$ entails $\varphi$ ($\Gamma \vDash \varphi$) if, for every truth assignment $\mathcal{A}$, if $\mathcal{A} \vDash \psi$ for every $\psi \in \Gamma$, then $\mathcal{A} \vDash \varphi$.
• Two formulas $\varphi$ and $\psi$ are equivalent ($\varphi \equiv \psi$) if $\varphi \vDash \psi$ and $\psi \vDash \varphi$.

Proofs

• A proof establishes entailment algorithmically.
• A proof system includes axioms (assumed true) and inference rules (derive new formulas).
• A proof is a sequence of formulas, each an axiom or derived via an inference rule.
• The notation $\Gamma \vdash \varphi$ means there is a proof of $\varphi$ from $\Gamma$.

Natural Deduction - Inference Rules

Conjunction

• Introduction: $\frac{\varphi \quad \psi}{\varphi \land \psi} \land i$
• Elimination:
  • $\frac{\varphi \land \psi}{\varphi} \land e_{1}$
  • $\frac{\varphi \land \psi}{\psi} \land e_{2}$

Disjunction

• Introduction:
  • $\frac{\varphi}{\varphi \lor \psi} \lor i_{1}$
  • $\frac{\psi}{\varphi \lor \psi} \lor i_{2}$
• Elimination:
  • $\begin{array}{ccc} & [\varphi] & [\psi] \ \varphi \lor \psi & \vdots & \vdots \ & \chi & \chi \ \hline \chi \end{array} \lor e$

Negation

• Introduction:
  • $\begin{array}{c} [\varphi] \ \vdots \ \frac{\bot}{\neg \varphi} \end{array} \neg i$
• Elimination:
  • $\frac{\varphi \quad \neg \varphi}{\bot} \neg e$

Implication

• Introduction:
  • $\begin{array}{c} [\varphi] \ \vdots \ \frac{\psi}{\varphi \rightarrow \psi} \end{array} \rightarrow i$
• Elimination:
  • $\frac{\varphi \quad \varphi \rightarrow \psi}{\psi} \rightarrow e \text{ (Modus Ponens)}$

Falsity

• Elimination:
  • $\frac{\bot}{\varphi} \bot e$

Double Negation

• Introduction:
  • $\frac{\varphi}{\neg \neg \varphi} \neg \neg i$
• Elimination:
  • $\frac{\neg \neg \varphi}{\varphi} \neg \neg e$

Example Proof - $(p \land q) \rightarrow (q \land p)$

1. $p \land q$ Assumption
2. $p \qquad \land e_{1} 1$
3. $q \qquad \land e_{2} 1$
4. $q \land p \qquad \land i 3, 2$
5. $(p \land q) \rightarrow (q \land p) \qquad \rightarrow i 1-4$

• $\land e_{1} 1$ applies the rule $\land e_{1}$ to line 1.
• $\rightarrow i 1-4$ applies the rule $\rightarrow i$ to the subproof from line 1 to line 4.

Soundness and Completeness

• A proof system is sound if $\Gamma \vdash \varphi$ implies $\Gamma \vDash \varphi$.
• A proof system is complete if $\Gamma \vDash \varphi$ implies $\Gamma \vdash \varphi$.
• Natural deduction is both sound and complete for propositional logic.

Data Structures and Algorithms – Assignment 2

Instructions

• Submit a zip file including:
  • A PDF document with answers to all questions, including time complexity analysis.
  • A folder with code for exercise 3 and a README file with instructions on how to run the code.
• Discussing with other students is allowed, but writing your own code and answers is a must.
• Deadline: November 15, 2023 at 23:59.

Questions

• Briefly describe:
  • Data structure
  • Abstract data type
  • Algorithm
  • Time complexity
  • Asymptotic analysis
• Answer the following:
  • What is the difference between an array and a linked list?
  • What is the difference between a stack and a queue?
  • What is the difference between a binary tree and a binary search tree?
  • What is the difference between Dijkstra’s algorithm and Bellman-Ford algorithm?
  • What is the difference between a depth-first search (DFS) and a breadth-first search (BFS)?
• Implement the following in Python:
  • Given a graph $G = (V, E)$, implement the depth-first search (DFS) algorithm to find all connected components in the graph.
  • Given a graph $G = (V, E)$, implement Dijkstra’s algorithm to find the shortest path from a source vertex to all other vertices in the graph.
  • Given a graph $G = (V, E)$, implement the Floyd-Warshall algorithm to find the shortest path between all pairs of vertices in the graph. The implementation should be able to detect negative cycles.
  • Give a brief explanation of the algorithm and its time complexity for each implementation.
  • Provide a simple interface (command line) for the user to input the graph and the source vertex (for Dijkstra’s algorithm).
  • Test the implementation on several graphs of different sizes and densities and compare the performance of the algorithms on these graphs.