MA0301/exercise2/main.tex

\documentclass[12pt]{article}
\usepackage{ntnu}
\usepackage{ntnu-math}

\author{Øystein Tveit}
\title{MA0301 Exercise 2}

\begin{document}
  \ntnuTitle{}
  \break{}
  
  \begin{excs}
    \exc{}

   \begin{truthtable}
     {e|c|c|e}
     {$p$ & $q$ & $p \wedge q$ & $p \vee (p \wedge q)$}
     \T & \T & \T & \T \\
     \T & \F & \F & \T \\
     \F & \T & \F & \F \\
     \F & \F & \F & \F \\
   \end{truthtable} 

   
    \exc{}
    (DL1)
   \begin{truthtable}
     {c|c|c|c|e|c|c|e}
     {$\alpha$ & $\beta$ & $\gamma$ & $(\beta \wedge \gamma)$ & $\alpha \vee (\beta \wedge \gamma)$ & $\alpha \vee \beta$ & $\alpha \vee \gamma$ & $(\alpha \vee \gamma) \wedge (\alpha \vee \gamma)$}
     \T & \T & \T & \T & \T & \T & \T & \T \\
     \T & \T & \F & \F & \T & \T & \T & \T \\
     \T & \F & \T & \F & \T & \T & \T & \T \\
     \T & \F & \F & \F & \T & \T & \T & \T \\
     \F & \T & \T & \T & \T & \T & \T & \T \\
     \F & \T & \F & \F & \F & \T & \F & \F \\
     \F & \F & \T & \F & \F & \F & \T & \F \\
     \F & \F & \F & \F & \F & \F & \F & \F \\
   \end{truthtable} 
 
    (DL2)
   \begin{truthtable}
     {c|c|c|c|e|c|c|e}
     {$\alpha$ & $\beta$ & $\gamma$ & $(\beta \vee \gamma)$ & $\alpha \wedge (\beta \vee \gamma)$ & $\alpha \wedge \beta$ & $\alpha \wedge \gamma$ & $(\alpha \wedge \gamma) \vee (\alpha \wedge \gamma)$}
     \T & \T & \T & \T & \T & \T & \T & \T \\
     \T & \T & \F & \T & \T & \T & \F & \T \\
     \T & \F & \T & \T & \T & \F & \T & \T \\
     \T & \F & \F & \F & \F & \F & \F & \F \\
     \F & \T & \T & \T & \F & \F & \F & \F \\
     \F & \T & \F & \T & \F & \F & \F & \F \\
     \F & \F & \T & \T & \F & \F & \F & \F \\
     \F & \F & \F & \F & \F & \F & \F & \F \\
   \end{truthtable}

   \exc{}
   \begin{align*}
     p \Rightarrow (q \vee r) &\equiv (p \wedge \neg q) \Rightarrow r \\
                 &\equiv \neg (p \wedge \neg q) \vee r \\
                 &\equiv (\neg p \vee \neg\neg q) \vee r \\
                 &\equiv (\neg p \vee q) \vee r \\
                 &\equiv \neg p \vee (q \vee r) \\
                 &\equiv p \Rightarrow (q \vee r)
   \end{align*}
 
   \exc{}
   \begin{align*}
     [(q \wedge p) \vee q] \wedge \neg(\neg q \vee p) &\equiv q \wedge \neg p \\
                        q \wedge \neg p &\equiv [(q \wedge p) \vee q] \wedge \neg(\neg q \vee p) \\
                                &\equiv [q] \wedge (\neg\neg q \wedge \neg p) \\
                                &\equiv q \wedge (q \wedge \neg p) \\
                                &\equiv (q \wedge q) \wedge \neg p \\
                                &\equiv q \wedge \neg p
   \end{align*}

   \exc{}
   \begin{subexcs}
     \subexc{}
     $\forall S(x)[H(x)]$
     \subexc{}
     $\exists S(x)[\neg H(x)]$
     \subexc{}
     $\forall S(x)[\neg H(x)]$
     \subexc{} 
     $\forall \neg H(x) \exists S(x)$

   \end{subexcs} 

   
   \exc{}
   \begin{subexcs}
     \subexc{}
     The formula is true because of the case where $x < z < y$ which would mean that $x < y \wedge z < y \wedge x < z \wedge \neg (z < x)$
     \subexc{}
     The formula is false because $p(z, y)$ and $\neg p(z, x)$ cannot be fulfilled at the same time. $z \geq 0 \wedge \neg (z \geq 0) \equiv F$

     \setsubexc{4}
     \subexc{}
     \fbox{see comment in ovsys}

   \end{subexcs} 


   \exc{}
   \begin{align*}
     \neg (\forall x [p(x) \wedge q(x)]) &\equiv \exists x [\neg(p(x) \wedge q(x))] \\
                           &\equiv \exists x [\neg p(x) \vee \neg q(x)]
   \end{align*}

   \exc{}
   \begin{align*}
     \neg (\exists x \forall y [p(y) \vee \neg q(x,y)]) &\equiv \forall x \neg(\forall y [p(y) \vee \neg q(x,y)]) \\
                                   &\equiv \forall x \exists y \neg[p(y) \vee \neg q(x,y)] \\
                                   &\equiv \forall x \exists y [\neg p(y) \wedge \neg\neg q(x,y)] \\
                                   &\equiv \forall x \exists y [\neg p(y) \wedge q(x,y)]
   \end{align*} 

  \end{excs}
  

\end{document}