\documentclass[12pt]{article}
\usepackage{hyperref}

\begin{document}

\centerline{\bf Homework 2, MORALLY Due Feb 12}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}


\begin{enumerate}

\item 
(28 points-7 points each) 
\begin{enumerate} 
\item 
Consider the formula

$$
(x_{11}\vee x_{12}) \wedge (x_{21} \vee x_{22})\wedge (x_{31} \vee x_{32}) \wedge (x_{41} \vee x_{42}).$$

How many satisfying assignments does this formula have? Justify!


\item
Let $n\in\N$ with $n\ge 3$.  Consider the formula

$$(x_{11} \vee  x_{12}) \wedge (x_{21} \vee x_{22}) \wedge \cdots \wedge (x_{n1} \vee x_{n2}).$$

How many satisfying assignments does this formula have? Justify!
(Note that it may be a function of $n$.) 


\item
Consider the formula

$$(x_1 \vee \neg x_2) \wedge (x_2 \vee  \neg x_3) \wedge (x_3 \vee \neg x_4) \wedge (x_4\vee \neg x_1).$$

How many satisfying assignments does this formula have? Justify!
(Do not use a truth table.) 


\item
Give an example of a 2CNF formula which uses 4 variables and is NOT satisfiable. 


\end{enumerate}

\newpage

\item
(20 points)
Let $n\in\N$. 
Two formulas $\phi_1$ and $\phi_2$ are {\it $n$-Equiv}
if their truth tables DIFFER on exactly $n$ rows. 
Note that logical equivalence is 0-Equiv. 

\begin{enumerate}
\item
(10 points) 
Give an example of two formulas $\phi_1,\phi_2$, each on 3 variables,  that are 1-Equiv. 
(Hint: This is easier if you make them in DNF form.) 


\item
(10 points) 
Give an example of three formulas $\phi_1,\phi_2,\phi_3$, each on 3 variables,
such that the following hold:
\begin{enumerate}
\item
$\phi_1$ and $\phi_2$ are 1-Equiv.
\item
$\phi_2$ and $\phi_3$ are 1-Equiv.
\item
$\phi_1$ and $\phi_3$ are 2-Equiv.
\end{enumerate} 


\end{enumerate} 


\newpage

\item
(20 points -- 5 points each)
For each of the following statements write the negation without using any negations signs.
\begin{enumerate}
\item
$x\ne 4$


\item
$(x_1 \le x_2)\wedge (x_1 \le x_3)$ 


\item
$(x\le 5) \vee (x\ge 15)$


\item
$x< y< z$

\end{enumerate}

\newpage

\item
(32 points-8 points each)
You are designing an algorithm for CNFSAT. 
I will incompletely describe some short cuts you can take.
Fill in the BLANK

The input is of the form 

$C_1 \wedge \cdots \wedge C_m$

where each $C_i$ is an OR of literals (a literal is a var or its negation).

\begin{enumerate}
\item
If $C_1= (x_3)$ then you can do $BLANK_1$.

\item 
If $x_4$ appears in the formula but $\neg x_4$ never appears then you can do $BLANK_2$. 

\item
If $C_2 = (x_8)$ and $C_3 = (x_9)$ and $C_4=(\neg x_8 \vee \neg x_9)$ then you can do $BLANK_3$. 


\item
If $C_4 = (x_{10} \vee\neg  x_{11} \vee x_{12} \vee \neg x_{12})$ then you can do $BLANK_4$. 

\end{enumerate} 

\newpage 

\item
(0 point- For FUN and just EMAIL Bill your answer)
Contradiction in real life: There are songs where what people
{\it think} the song is about is in contradiction to what
the song is really about if you listen to they lyrics carefully.
Bill had a blog post on this (Bill has been a blogger on complexity theory
since 2008 or so) 
\href{https://blog.computationalcomplexity.org/2023/09/the-contradiction-of-margaritaville-and.html}{here}) 

READ the blog post.

EMAIL Bill your thoughts on the post- which song you particular liked, something you learned,
some other song that has that property, whatever you want. 


\end{enumerate} 

\end{document}