Problem 1.

(15 points) Let $P, Q, R$ denote distinct propositional variables.
(a) Write the formula which $((P \wedge Q) \vee \neg R)$ abbreviates.
(b) Is $((\neg P \leftrightarrow Q) \vee(P \leftrightarrow Q))$ a tautology? Justify.
(c) Are $((R \rightarrow Q) \leftrightarrow P)$ and $(P \vee(\neg R \wedge \neg Q))$ truth equivalent? Justify.

Problem 2.

(15 points) For any formula $\varphi$, let $V(\varphi)$ be the number of propositional variables occurring in $\varphi$ including repeats, and let $S(\varphi)$ be the number of brackets $(,$, and connectives $\neg, \rightarrow$ in $\varphi$. For example,
$$\psi=\left(\left(P_{1} \rightarrow P_{2}\right) \rightarrow \neg P_{1}\right)$$
has $V(\psi)=3$ and $S(\psi)=7$.
Prove that, for all formulas $\varphi, \varphi$ is not a propositional variable if and only if $V(\varphi) \leq S(\varphi)$.

Problem 3.

(10 points) Let $P, Q, R$ be distinct propositional variables. Find the disjunctive normal form (DNF) of $((P \rightarrow(Q \wedge R)) \vee(\neg Q \wedge R))$.

Problem 4.

(10 points) Decide whether the following argument is valid by first converting to a question of satisfiability of clauses, and then using the Davis Putnam Procedure (DPP).
$$(P \wedge \neg R),(P \vee \neg Q),(P \rightarrow(Q \vee R)) \text {, therefore } Q$$

Problem 5.

(10 points) Determine whether the following set of Horn clauses is satifiable.
$${{P},{P, \neg R},{R, \neg W, \neg S},{Q},{\neg P, S},{\neg Q, W},{\neg P, \neg Q, \neg R},{\neg W, S}}$$

Problem 6.

(10 points) Let $P, Q, R, S, T$ be distinct propositional variables. Find an instance of 3 -SAT which is satisfiably equivalent to
$${{P},{P, Q, \neg R, S, \neg T},{\neg Q, \neg S}} .$$

Problem 7.

(20 points) Determine if the following proof system for propositional logic is sound and/or complete. Justify your answer for both.
Axioms: All tautologies.
Rules: If $\psi$ is a subformula of $\varphi$, then we can infer $\psi$ from $\varphi$.

Problem 8.

(10 points) Let $\varphi$ be a propositional formula. By the completeness theorem, notice that ${\neg \neg \varphi} \vdash \varphi$. Write down a derivation of $\varphi$ from ${\neg \neg \varphi}$.

Problem 9.

(25 points) Consider the first order language $\mathcal{L}=(R, g, f, c)$, where $R$ is a binary relation, $f$ is a binary function, $g$ is a 3 -nary function, and $c$ is a constant.
(a) Consider the interpretation $\mathcal{I}=(\mathcal{A}, \beta)$ of $\mathcal{L}$ with domain $A=\mathbb{R}, c^{\mathcal{A}}=-2, f^{\mathcal{A}}(x, y)=$ $x-y, g^{\mathcal{A}}(x, y, z)=x^{2}+y^{2}-z^{2}$, and $\beta\left(x_{i}\right)=-i$. Compute $\mathcal{I}\left(f g f x_{1} c c x_{2} x_{5}\right)$.
(b) Find an interpretation $\mathcal{I}$ such that $\mathcal{I} \neq \forall x_{3} R f x_{1} \operatorname{cg} x_{1} c x_{3}$.
(c) Find an interpretation $\mathcal{I}$ such that $\mathcal{I} \models \forall x_{3} R f_{1} \operatorname{cg} x_{1} c x_{3}$.

Consider the language of arithmetic $\mathcal{L}{\text {ar }}$. (a) (5 points) Translate the following English sentence into a statement in $\mathcal{L}{\text {ar }}$ “The only integer divisible by zero is itself.” You may not use the notation | to denote “divides”.
(b) (5 points) Translate the following formula into an English statement about the natural numbers.
$$(\forall x(\exists y x \cdot y \approx x+1 \vee x \approx 1)$$
(c) (10 points) For $\varphi=\forall a a<a+1$ and
$$\Gamma={0<1, \forall x \forall y \forall z((x<y \wedge 0<z) \rightarrow z+x<z+y)}$$
prove $\Gamma \models \varphi$.

Consider the language of graphs $\mathcal{L}={E}$, where $E$ is a binary relation. For all natural numbers $n$, we define the formula
$$\begin{gathered} \psi_{n}=\exists x \exists y \neg \exists v_{1} \cdots \exists v_{n-1}\left(\left(E x v_{1} \vee x \approx v_{1}\right) \wedge\left(E v_{1} v_{2} \vee v_{1} \approx v_{2}\right) \wedge\right. \ \left.\cdots \wedge\left(E v_{n-1} v_{n} \vee v_{n-1} \approx v_{n}\right) \wedge\left(E v_{n} y \vee v_{n} \approx y\right)\right) . \end{gathered}$$
We then make the following definition: we say that an interpretation $\mathcal{G}$ of $\mathcal{L}$ has finite

BS equation代写

# MA 38500, Fall 2021Introduction To Logic

Credit Hours: 3.00. Propositional calculus and predicate calculus with applications to mathematical proofs, valid arguments, switching theory, and formal languages. Typically offered Spring.