CS245 course notes: https://www.student.cs.uwaterloo.ca/~cs245/CS245-Lecture-Notes.pdf

Table of Contents

• lec 1. 9.10
• lec 3.
• tut 2. 9.13
• lec 4. 9.17
• lec 5. 9.19
• tut 3. 9.20
• lec 6. 9.24
• lec 7. 9.26
• tut 3. 9.27
• lec 8. 10.1
• lec 9. 10.3
• tut 4. 10.4
• lec 10. 10.8
• lec 11. 10.10
• tut 5. 10.11
• lec 12. 10.22
• lec 13. 10.24
• tut 6. 10.25
• lec 14. 10.29
• lec 15. 10.31
• tut 7. 11.1
• lec 16. 11.05
• lec 17. 11.07 (Colin)
• lec 18. 11.12
• lec 19. 11.14
• tut 8. 11.15
• lec 20. 11.19
• lec 21. 11.21

lec 1. 9.10

definition. a proposition is a statement that is either true or false.

definition. a compound proposition is formed by means of logical connectives.

definition.

unary connective

• negation

  A	not A
  1	0
  0	1

binary connectives

• conjunction

  A	B	A and B	B and A
  1	1	1	1
  1	0	0	0
  0	1	0	0
  0	0	0	0

• inclusive disjunction

  A	B	A or B	B or A
  1	1	1	1
  1	0	1	1
  0	1	1	1
  0	0	0	0

• implication

  A	B	if A then B
  1	1	1
  1	0	0
  0	1	1	vacuously true when A=0;
  0	0	1	not symmetric

• equivalence

  A	B	A iff B	B iff A
  1	1	1	1
  1	0	0	0
  0	1	0	0
  0	0	1	1

definition. propositional language $L^p$

• symbols

  • propositional symbols: $p,q,r,...$
  • connectives: $\lnot, \land, \lor, \rightarrow, \iff$
  • punctuation: $(, )$

• expressions are finite strings of symbols. two expressions are equal if symbols and lengths are same

• empty expression $\lambda$: expression of length 0

• $uv$ denotes the result of concatenating two expressions $u, v$ in this order.

  • $\lambda u=u \lambda=u$

• $v$ is a segment of $v=w_1vw_2$.

  • $v$ is a proper segment of $u$ if $v$ is non-empty and $v\neq u$.

• if $v=vw$ then $v$ is initial segment(suffix) of $u$

definition. $\textrm{atom}(L^p)$ is the set of expressions of $L^p$ consisting of a proposition symbol only.

definition.(well-formed propositional formula) an expression of $L^p$ is a member of $\textrm{form}(L^p)$ iff:

• $\textrm{atom}(L^p) \subseteq \textrm{form}(L^p)$
• $A\in \textrm{form}(L^p) \longrightarrow (\lnot A) \in \textrm{form}(L^p)$
• $A,B\in \textrm{form}(L^p) \longrightarrow (A*B)\in \textrm{form}(L^p)$ where $*$ is one of the four connectives.

eg. $p$ is a prop. variable, then which of $p, (, \neg$ can appear in a well-formed formula?

• $p, ($

lec 3.

definition. given a set $Y\subseteq X$ and set $P$ of operations (functions from $X^{n\geq1}\rightarrow X$), $Y$ is closed under $P$ if for every $f\in P$, say $f$ is an $n$-ary function and every $y_1,...,y_n\in Y$ we have $f(y_1,...,y_n)\in Y$.

definition. $Y$ is a minimal set with respect to a property $R$ if $Y$ satisfies $R$, and for every set $Y_0$ that satisfies $R,Y\subseteq Y_0$.

definition. $I(X,A,P)$ is the minimal subset of $X$ that contains $A$ and is closed under the operations in $P$.

• universe of all elements denote to be $X$
• core set denote to be $A$
• a set of operations $B$

eg. the natural numbers.

$X=\{\mathbb{R}\}^* \,, A=\{0\} \\ P=\{f(x)=x+1\} \\ \mathbb{N} = \{X,A,P\}$

definition. Given $X,A,P$ and an element $x\in X$, a generation sequence from $x$ is $\alpha_1,\alpha_2,...\alpha_m$ from $X$ such that $\alpha_n=x$ and for every $i\leq m$ $\alpha_i$ is either in $A$ or is the result of applying some $f\in P$ to some $\alpha_j,\alpha_{j'}$ such that $j,j' < i$.

eg. let $X=\{a,b\}^*,A=\{aa,aba\},P=\{\frac{x}{xx}, \frac{x,y}{xy}\}$. we have $\alpha_1=aa,\alpha_2=aba$ and then $\alpha_3=aaaba$ (applied from $\alpha_1,\alpha_2$), $...$

technique. to show a property $R$ holds for every element of a set inductively defined:

• show $R$ holds for minimal subset of $X$ (which is $A$)
• show for every $n$-ary $f\in P, R(f(y_1,...,y_n))$ holds whenever $f(y_1),...,f(y_n)$ hold.

propositions

$X=\{\textrm{finite sequences of symbols}\}^* \\ A=\{\textrm{English letters}\} \\ P=\{\neg,\land,\lor\implies\}$

claim.(1) $pp$ is not a legal proposition.
interpret. we have property $R$ and propositions are $I=(X,A,P)$.
proof. base: show the property holds for for all members of $A$. This is clear since every member of $A$ is a single letter.
inductive step: for every operation $f\in \mathcal{P}$ and every $x,y\in X$, if $R$ holds for $X$ and $y$ then $R$ holds for $f(x,y)$. Here $P=\{\frac{x}{(\neg x)},\frac{x,y}{(x\land y)},\frac{x,y}{x\lor y},\frac{x,y}{(x\rightarrow y)}\}$ we have no repeating two letters. $\square$

property.(2) every proposition is either an atomic proposition or it starts with "$($" or ends with "$)$".
proof. trivial structural induction $\square$

property.(3) the number of left brackets in a proposition is always equal to the number of right brackets in the proposition.
proof. base: if $x\in A$, then $\mathrm{op}(x)=0,\mathrm{cl}(x)=0$ hence equal.
inductive: Assume $x,y$ satisfy this property. Want to show so do they for four operations.
Then $\mathrm{op}((\neg x))=\mathrm{op}(x)+1,\mathrm{cl}((\neg x))=\mathrm{cl}(x)+1$, given that $\mathrm{op}(x)=\mathrm{cl}(x)$ by inductive hypothesis we have equality. For $\mathrm{op}((x\rightarrow y))=\mathrm{op}(x)+\mathrm{op}(y)+1$ and $\mathrm{cl}((x\rightarrow y))=\mathrm{cl}(x)+\mathrm{cl}(y)+1$. Invoke inductive hypothesis for $\mathrm{op}(x)=\mathrm{cl}(x),\mathrm{op}(y)=\mathrm{cl}(y)$ we have equality. Same argument applies to other two. $\square$

definition. given any sequence $x=\alpha_1\alpha_2...\alpha_n$ a proper initial segment of $x$ is any sequence $\alpha_1...\alpha_k$ for $k<n$.
property.(4) every non empty proper initial segment of a proposition has more left bracket than right brackets.
proof. base: there is no proper initial segments hence the property holds vacuously.
inductive: Assume the property holds for $x$ we want to show it holds for four operations. do permutations. $\square$

tut 2. 9.13

eg. let $\varphi$ be a well-formed formula of propositional logic. let $m_\varphi$ be the number of propositional variables in $\varphi$. let $n_\varphi$ be the number of occurrences of binary connections in $\varphi$ (which are $\land,\lor,\rightarrow,\iff$), show that $m_\varphi=n_\varphi+1$.
proof. we define this property as $R(\varphi)$.
base: let $\varphi=p$ for some propositional variable $p$, hence $m_\varphi=1$ and $n_\varphi=0$. Hence $R(\varphi)$ holds.
inductive: assume we have $m_\alpha=n_\alpha+1$ (a) let $\varphi=(\neg \alpha)$ for some well-formed formula $\alpha$. Then $m_\varphi=m_\alpha=n_\alpha+1=n_\varphi+1$. (b) let $\varphi=\alpha * \beta$ for some well-formed formulas $\alpha,\beta$ and a binary connective $*$. Then $m_\varphi=m_\alpha+m_\beta=(n_\alpha+1)+(n_\beta+1)=(n_\alpha+1+n_\beta)+1=n_\varphi+1$. By the principle of structural induction we showed that $R(\varphi)$ holds for all well-formed propositional formula. $\square$

lec 4. 9.17

theorem.(unique readability) for every proposition $\alpha$ exactly one of the following holds:

1. $\alpha$ is a propositional variable.
2. $\alpha$ is $(\neg \beta)$ for some proposition $\beta$.
3. $\alpha$ is $\beta * \gamma$ for some propositions $\beta,\gamma$ where $*$ is one of $\lor,\land,\rightarrow$.

Furthermore, these $\beta,\gamma$ are uniquely determined.

proof. by counting brackets in $\alpha$.
if there are no brackets, then it falls in option 1 and $\alpha$ is a propositional variable.
If $\alpha$ starts with a left bracket: If this next symbol is $\neg$ then $\alpha=(\neg \beta)$ and the rest of $\alpha$ is $\beta)$
otherwise starting counting r and l brackets from left to right and stop when the counts are equal for the first time. by property 3 at this point we finished scanning $\beta$ and the next symbol should be a connective followed by $\gamma$. eg.

$\sout{(}p\rightarrow (q\land r))$

here stop at $p$ as this time we have zero left/right brackets, and followed with a binary connective then followed by another proposition. $\square$

eg. parse $((p\rightarrow(\neg q))\lor((\neg a)\land(b\rightarrow c)))$

eg. draw a parse tree of $((p\lor q)\rightarrow ((\neg p)\iff(q\land r)))$ using def'n of well-formed prop. formulas.

eg. draw a tree for $(((\neg p)\lor q)\rightarrow(p\land (q \lor (\neg r)))$

definition. a parse tree for a formula $\alpha$ is a finite tree with formulas written on its nodes. $\alpha$ is its root and the formula $\beta_i$ at every leaf is a propositional formula.

remark. the unique readability theorem tells the parse tree is unique.

theorem. a sequence of symbols in X has a parse tree iff it is a proposition.
proof. if $\alpha$ is a proposition then it has a parse tree by definition. if $\alpha$ is a parse tree then by definition $\alpha$ is a member of $I(X,A,P)$ since going from the leaves to the root every formula is either a prop. variable or generated by applying operations in $P$ to its children that are propositions. $\square$

remark. we define an order of precedence among $\neg,\land,\lor\rightarrow,\iff$ and use brackets only if we want to violate this order.

definition. precedence rules:

• left precedences right: $\neg, \land, \lor , \implies, \iff$

eg.

• $\neg p \lor q = ((\neg p) \lor q)$
• $p \land q \lor r = ((p \land q) \lor r)$
• $\neg a \rightarrow a\lor b \land \neg c=(\neg a) \rightarrow (a\lor (b \land (\neg c)))$

lec 5. 9.19

definition. a truth valuation $t$ is a function from propositional variables to $\{0,1\}$:

$t:P\rightarrow\{0,1\}$

where $P$ denotes the set of available prop. variables.

definition. $p^t$ denotes the value of $p$ under $t$.

• $p^t=t(p)$ if $p$ is a prop. variable under the definition of $t$.
• $(\neg p)^t=\begin{cases} 1 & \text{ if } p^t=0 \\ 0 & \text{ if } p^t=1 \end{cases}$
• $(p\land q)^t=\begin{cases} 1 & \text{ if } p^t=q^t=1\\ 0 & \text{ else } \end{cases}$
• $(p\lor q)^t=...$
• $(p \rightarrow q)^t=\begin{cases} 1 & \text{ if } p^t=0\text{ or }q^t=1\\ 0 & \text{ else } \end{cases}$
• $(p\iff q)^t=\begin{cases} 1 & \text{ if } p^t=q^t\\ 0 & \text{ else } \end{cases}$

remark. $p\rightarrow q\equiv\neg p \lor q$

theorem. the truth value $A^t$ for a given well-formed formula under truth valuation $t$ is uniquely determined.
proof. let $t$ be any truth valuation and $A$ any well-formed formula.
base: let $A$ be atomic, then $A^t=t(A)$. as $t(A)$ is uniquely determined, so is $A^t$.
step: let $A$ be some well-formed non-atomic formula. by uniquely readability theorem, we have that the precedences of $A$ and the connectives are uniquely determined. hence we have only one of the following situations:

1. $A=(\neg B)$ for some uniquely determined well-formed formula $B$. invoking inductive hypothesis we have the truth value of $B$ is uniquely determined. but $A^t$ is given by $A^t=1\text{ if } B^t=0\text{ else } 0$ so the truth value $A^t$ is uniquely determined.
2. $A=(B*C)$ for some uniquely determined well-formed formula $B,C$ and a binary connective $*\in \{\land,\lor,\rightarrow,\iff\}$. Invoking IH we have $B^t,C^t$ are uniquely determined in their truth values. but as $*$ is uniquely determined (...) and so the truth value of $(B*C)^t$ is uniquely determined.

by induction, all $A^t$ is uniquely determined. $\square$

eg. evaluate $((A\lor B)\rightarrow(A\land(\neg B)))^t$ under:

$t:\{A,B\}\rightarrow\{0,1\}$

$t(A)=1,t(B)=0$

then $(A\lor B)=1$, $(\neg B)=1$, $(A\land(\neg B))=1$, original=$1$.

definition. a formula $A$ is satisfiable if there exists a truth valuation $t$ such that $t(A)=1$.

definition. a formula $A$ is tautology (valid formula) if for all truth valuations $t$ we have $t(A)=1$.

definition. a formula $A$ is unsatisfiable (contradiction) if for all truth valuations $t$ we have $t(A)=0$.

eg. $(A\rightarrow B)\lor(B\rightarrow A)$ is tautology.

eg. $A$ is a contradiction iff $\neg A$ is a tautology.
proof. let $t$ be a truth valuation. (1) let $A$ be a contradiction, we know that $A^t=0$ so $(\neg A)^t=1$ by definition. hence $(\neg A)^t=1$ holds for all truth variables so $\neg A$ is a tautology. (2) let $\neg A$ be a tautology. we know that $(\neg A)^t=1$ then by definition we have $A^t=0$ for all truth variables and so $A$ is a contradiction. $\square$

remark.

1. satisfiable is the negation of contradiction.
2. tautology is not the negation of contradiction.
3. every tautology is satisfiable.

tut 3. 9.20

eg. show $A=(p\rightarrow q)\lor((p\rightarrow r)\lor(r\rightarrow p))$ is a tautology. (method 2)
proof.

• case 1: let $t$ be a truth valuation with $p^t=1$, therefore $(r\rightarrow p)^t=1$ hence $A^t=1$.
• case 2: let $t$ be a truth valuation with $p^t=0$, therefore $(p\rightarrow q)^t=1$ hence $A^t=1$. $\square$

lec 6. 9.24

remark. $A$ is a tautology iff $\neg A$ is a contradiction.
remark. $A$ is satisfiable iff $A$ is not a contradiction iff $\neg A$ is not a tautology.

eg. application
code for chip design -> a propositional formula $A$ specifications -> a propositional formula $B_3$. is $A\land \neg B_3$ satisfiable?
is there an 'efficient' algorithm for checking satisfiability?

tautological consequences

definition. we write $A$ tautologically implies $B$, $A\models B$, if for every truth assignment $t$ we have $A^t=1\rightarrow B^t=1$.
eg.

• $(p\land q)\models (p\lor q)$
• $(p\lor q)\nvDash(p\land q)$

claim & exer.

1. $A\models B$ iff $A\rightarrow B$ is a tautology.
2. $A\nvDash B$ iff $A\land \neg B$ is satisfiable.
3. if $A,B$ are tautologies, then $A\land B$ is a tautology.
4. if $A,B$ are satisfiable, then $A\land B$ is satisfiable?
   • false. eg. $A=p,B=\neg p$
5. if $A\land B$ is a tautology, then $A$ is a tautology?
   • false. eg. $p\land \neg p$ is a tautology while $p$ is not

definition. let $\Sigma$ denote a set of propositions. $\Sigma \models A$ if every truth assignment $t$ for which $B^t=1$ for all $B\in\Sigma$, it also gives $A^t=1$ (if $t$ makes members of $\Sigma$ be 1, then it also makes $A$ 1).

eg. $\Sigma=\{p_1\rightarrow p_2,p_2\rightarrow p_3,...,p_m\rightarrow p_{m+1},...:m\in \mathbb{N}\}$, does $\Sigma\models(p_4\rightarrow p_{24})$?
note $(p_4\rightarrow p_{24})^t=0$ iff $p_4^t=1,p_{24}^t=0$. if for every $p_m\in\Sigma$, $p_m^t=1$, then
$(p_4\rightarrow p_5)^t=1$ so $p_5^t=1$
$(p_5\rightarrow p_6)^t=1$ so $p_6^t=1$
$(p_{23}\rightarrow p_{24})^t=1$ so $p_{24}^t=1$
a contradiction, so this is true.

definition. $\Sigma$ is satisfiable if there exists $t$ such that for all $B\in\Sigma$ we have $B^t=1$.

eg. is $\Sigma=\{p_1\leftrightarrow\neg p_2,p_2\leftrightarrow\neg p_3,...,p_m\leftrightarrow\neg p_{m+1},...:m\in \mathbb{N}\}$ satisfiable?
no.

definition. $\Sigma_1\models\Sigma_2$ if whenever $t$ is such that every $A\in\Sigma_1,A^t=1$, then for every $B\in\Sigma_2,B^t=1$ (ie every $t$ that satisfies members of $\Sigma_1$ also satisfies members of $\Sigma_2$).

eg. $\Sigma_1=\{p_1,p_1\rightarrow p_2\}$, $\Sigma_2=\{p_2\}$
see first row

lec 7. 9.26

eg. is $\Sigma=\{p_1\rightarrow\neg p_2,p_2\rightarrow\neg p_3,p_3\rightarrow\neg p_4\}$ satisfiable?
yes. put $p_1^t=p_2^t=p_3^t=0$ or $p_1^t=p_3^t=1,p_2^t=p_4^t=0$.

eg. is $\Sigma=\{p_1,\neg p_2,p_1\rightarrow p_2\}$ satisfiable?
no. can't find a row with all 1's for these three:

claim.

1. if $\Sigma$ ia not satisfiable then for every proposition formula $A$ we have $\Sigma\models A$ vacuously.
2. $\Sigma$ is satisfied by every truth assignment, let $A$ be a propositional formula, then $\Sigma\models A$ iff $A$ is a tautology.

claim.

1. if $\Sigma_2\subseteq\Sigma_1$, then $\Sigma_1\models\Sigma_2$.
2. if $\Sigma_1\models\Sigma_2$ then, for every $A$, if $\Sigma_2\models A$ then $\Sigma_1\models A$.

eg. let $\Sigma_1=\{p_1\rightarrow p_2\}$, and $\{A:\Sigma_1\models A\}=\{p_1\rightarrow p_2,p_1\rightarrow p_2\land p_2,p_1\rightarrow p_1,...\}$

eg. assume $\Sigma_1\models\Sigma_2$, which is true?

1. if $\Sigma_1$ satisfiable then so is $\Sigma_2$. (true, by definition)
2. if $\Sigma_1$ satisfiable then so is $\Sigma_2$. (false)
   • $\Sigma_1=\{p_1,\neg p_2\},\Sigma_2=\{p_1\}$

corollary.(monotonicity of logic) let $\Sigma_1\subseteq\Sigma_2$, if $\Sigma_1\models A$ then $\Sigma_2\models A$.

eg. for any $w\in\mathbb{W}$ and $s\in\mathbb{S}$ pick a propositional variable $p_{ws}$. given a truth assignment $t$

give a map $f(w)=s$ iff $p_{ws}^t=1$, else nothing. find functions $\Sigma$ satisfying $f$'s requirements

$\Sigma_{\text{funcs}}=\{p_{w,s_1}\rightarrow p_{w,s_2}:s_1,s_2\in\mathbb{S},w\in\mathbb{W}\}$ $\Sigma_{\text{bijections}}=\{p_{w_1,s}\rightarrow \neg p_{w_2,s}:w_1,w_2\in\mathbb{W},s\in\mathbb{S}\}$
take $\Sigma_{\text{funcs}}\cup\Sigma_{\text{bijections}}$.

propositional logic only cares about the truth value of the assignment.
on the positive side, and connective whose truth is fully determined by the truth values of its components can be expressed in propositional logic.

tut 3. 9.27

eg. let $P=\{p_n:n\in\mathbb{N}\}$ be a finite set of prop. variables. are they satisfiable?

1. $\Sigma_0=\{p_n\rightarrow p_{n+1}:n\in\mathbb{N}\}$
2. $\Sigma_1=\{p_n\rightarrow\neg p_{n+1}:n\in\mathbb{N}\}$
3. $\Sigma_2=\Sigma_0\cup\Sigma_1$
4. $\Sigma_3=P$
5. $\Sigma_4=\Sigma_1\cup\Sigma_3$

Ans:

1. true. let $t_0:P\rightarrow\{0,1\}$ with $t_0(p_n)=0\,\forall n\in\mathbb{N}$, then $\Sigma_0^t=1$ since every element in $\Sigma_0$ has the form $p_n\rightarrow p_{n+1}$ while $p_n^t=0$.
2. true. use the above $t_0$.
3. true. still use the same $t_0$.
4. true. let $t_3:P\rightarrow\{0,1\}$ with $t_3(p_n)=1\,\forall n\in\mathbb{N}$
5. false. assume $\Sigma_4$ is satisfiable, then we must have $\Sigma_3^t=1$ and then $p_n=1\,\forall n\in\mathbb{N}$. now consider $p_n\rightarrow\neg p_{n+1}\in\Sigma_1$ then this cannot be true.

eg. prove or disprove the tautological consequence.

1. $\{A\rightarrow B,B\rightarrow C\}\models A\rightarrow C$
2. $\{(A\rightarrow\neg B)\lor C,B\land\neg C,A\leftrightarrow C\}\models \neg A\land(B\rightarrow C)$

Ans:

1. true. let $t$ be any truth valuation such that $\{A\rightarrow B,B\rightarrow C\}^t=1$.
   case 1. $t(A)=1$: since $(A\rightarrow B)^t=1$ we know $B^t=1$. since $(B\rightarrow C)^t=1$ we know $C^t=1$ and so $(A\rightarrow C)^t=1$.
   case 2. $t(A)=0$: then $(A\rightarrow C)^t=1$ by the definition of $\rightarrow$.
2. false. first look at $B\land\neg C$ to decide $B^t,C^t$, we can then decide $A^t$ from iff.
   let $A^t=C^t=0,B^t=1$.

lec 8. 10.1

proofs: verify the validity of arguments

definition. proofs satisfy

1. soundness: if $A$ has a proof, then $A$ is a "true statement", $\Sigma\vdash A\rightarrow\Sigma\models A$.
2. given an object that claims to be a proof, one can verify it.
3. completeness: if $A$ is a true statement, then $A$ can be proved. $\Sigma\models A\rightarrow\Sigma\vdash A$.

eg. propositional proof for propositional logic:
A proof of a proposition $A$ will be a truth table for $A$ that has 1 in every row.

definition. proof system for propositional logic: let

1. core set (axioms)
2. operation (deduction rules)

then $\vdash A$ iff $A\in I(\text{propositions, axioms, rules})=I(X,A,P)$.

a formal proof of $A$ will be a sequence of propositions $B_1,B_2,...B_n$ for every $i\leq m$, $B_i$ is either in $A$ or the result of applying operations from $P$ to previous $B_1,...,B_{i-1}$.

axioms. axioms of proof system for propositional logic

rule. (modus ponens) $P=\{\frac{A,A\rightarrow B}{B}\}$ (if we have $A$ true, $A\rightarrow B$ true, then $B$ true)

eg. $\vdash(A\rightarrow A)$
proof.

definition. (proof from assumptions) $\Sigma\vdash A$ if $A\in I(\text{axioms }\cup A,M,P)$

eg. $\{\neg\neg A\}\vdash A$
proof.

theorem. (deduction) for every $\Sigma$ and every $A,B$, we have $\Sigma\vdash(A\rightarrow B)$ iff $\Sigma\cup \{A\}\vdash B$.
proof. forward:

backward: pass

eg. to show $\{A\rightarrow B,B\rightarrow C\}\vdash(A\rightarrow C)$, it suffices to show $\{A\rightarrow B,B\rightarrow C,A\}\vdash C$.
proof.

eg. show $\vdash(\neg A\rightarrow\neg B)\rightarrow(B\rightarrow A)$.
proof. by the deduction, it suffices to show $\{\neg A\rightarrow\neg B,B\}\vdash A$.

lec 9. 10.3

eg. is $[(p\rightarrow\neg q)\rightarrow((\neg p\rightarrow q)\rightarrow p)]$ an axiom?
no. comparing with Ax3 the parse trees are different (not symbol-by-symbol).

remark $\vdash$ is formal proof (syntax), $\models$ is tautologically implies (semantics).

theorem. (soundness) for every proposition $A$ and every set of propositions $\Sigma$, if $\Sigma\vdash A$ then $\Sigma\models A$.
remark. same as $A\in I(\text{axioms}\cup\Sigma,\{\text{MP}\})\rightarrow \Sigma\models A$.
proof.
base: (i) $A$ is an axiom. check that every axiom is a tautology, so every $\Sigma$ implies every tautology:

1. by contradiction, if $A\rightarrow(B\rightarrow A)$ gives $0$, then $A$ gives $1$, $B\rightarrow A$ gives $0$. now $B$ must be $1$ and $A$ must be $0$.
2. by contradiction, if $[A\rightarrow(B\rightarrow C)]\rightarrow [(A\rightarrow B)\rightarrow(A\rightarrow C)]$ gives $0$, then $A\rightarrow(B\rightarrow C)$ gives $1$ and $(A\rightarrow B)\rightarrow(A\rightarrow C)$ gives $0$. then $A\rightarrow B$ gives $1$ and $A\rightarrow C$ gives $0$. then $A$ gives $1$, $C$ gives $0$. substitute $B$ by either $1$ or $0$ to axiom we get contradiction.
3. ...

(ii) if $A\in\Sigma$. by the definition of $\Sigma\models A$, every $t$ satisfying $\Sigma$ should satisfy $A$ since $A\in\Sigma$.

inductive: (under MP) we assume $\Sigma\models A$ and $\Sigma\models(A\rightarrow B)$, we want to show $\Sigma\models B$. let $t$ satisfy $\Sigma$, need to show $B^t=1$. by IH, $A^t=1, (A\rightarrow B)^t=1$, then by truth table $B^t=1$. $\square$

corollary. for every prop. variable $p$, $\nvdash p$ ($p$ can't be proved).
proof. assume that $\vdash p$, then by soundness, $\models p$. but prop. variable can't be tautology since it can be either $1$ or $0$. $\square$

prop. $\Sigma:=\{p_1\rightarrow p_2,p_2\rightarrow p_3,...,p_m\rightarrow p_{m+1},...:m\in\mathbb{N}\}\nvdash p_3$.
proof. assume $\Sigma\vdash p_3$ then by soundness $\Sigma\models p_3$. counter example: all $p_n$ has $(p_n)^t=0$. $\square$

remark.

prop. for every satisfiable $\Sigma$ there exists a proposition $A$ such that $\Sigma\nvdash A$.
proof. let $t$ be a truth valuation that satisfies $\Sigma$. consider $p_1^t$ such that if $p_1^t=1$ then $\Sigma\nvdash\neg p_1$ and if $p_1^t=0$ then $\Sigma\nvdash p_1$. by soundness $\Sigma\vdash\neg p_1$ implies $(\neg p_1)^t=1$, $\Sigma\vdash p_1$ implies $p^t=1$. a contradiction.
alternate proof. consider a contradiction $A$, since $\Sigma$ is satisfiable, we have $\Sigma\nvDash A$, by soundness $\Sigma\nvdash A$. $\square$