\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Predicate definition}


{\bf  Definition}: A  {\bf predicate}  is  a function from a given set (domain) to $\{T,F\}$.

A predicate can be applied, or {\bf evaluated} at, an element of the domain.

Usually, a predicate {\it describes a  property} that domain elements may or may not have.

Two predicates over the same domain are {\bf equivalent} means they evaluate to
the same truth values for all possible assignments of domain elements to the
input. In other words, they are equivalent means that they are equal as functions.

To define a predicate, we must specify its domain and its value at each domain element.
The rule assigning truth values to domain elements can be specified using a formula, 
English description, in a table (if the domain is finite), or recursively (if the domain is recursively
defined).

Note: Since logical operations are functions, they can be part of the definitions of predicates. \vfill
\section*{Predicate examples finite domain}


\begin{center}
    \begin{tabular}{c||c|c|c}
    Input & \multicolumn{3}{c}{Output} \\
    &$V(x)$ & $N(x)$ & $Mystery(x)$\\
    $x$ & $[x]_{2c,3} > 0$ & $[x]_{2c,3} < 0$& \\
    \hline
    $000$  & $F$ & & $T$\\
    $001$  & $T$ & & $T$\\
    $010$  & $T$ & & $T$\\
    $011$  & $T$ & & $F$\\
    $100$  & $F$ & & $F$\\
    $101$  & $F$ & & $T$\\
    $110$  & $F$ & & $F$\\
    $111$  & $F$ & & $T$\\
    \end{tabular}
    \end{center}
    
    The domain for each of the predicates $V(x)$, $N(x)$, $Mystery(x)$ is
    \underline{\phantom{$\{ b_1b_2b_3 ~\mid~ b_i \in \{0,1\} \textrm{ for each } i, 1 \leq i \leq 3 \}$}}.

    Fill in the table of values for the predicate $N(x)$ based on the formula given. \vfill
\section*{Predicate truth set definition}


{\bf Definition}: The {\bf truth  set} of a  predicate is the collection of all elements in its
domain where the predicate evaluates to $T$.

Notice that specifying the domain and the truth set is sufficient for defining
a predicate. \vfill
\section*{Predicate truth set example}


The truth set for the predicate $V(x)$ is $\underline{\phantom{\{ x ~\mid~ V(x) = T\} = \{ 001, 010, 011 \}}}$.

The truth set for the predicate $N(x)$ is $\underline{\phantom{\{ x ~\mid~ N(x) = T\} = \{ 101, 111 \}}}$.

The truth set for the predicate $Mystery(x)$ is $\underline{\phantom{\{ x ~\mid~ Mystery(x) = T\} = \{ 000, 001, 010, 101, 111 \}}}$.


\vfill \vfill
\section*{Predicate rna example}


{\bf Example predicates on $S$, the set of RNA strands (an infinite set)}


$L_{\A}: S \to \{T, F\}$  defined recursively by: 

~~Basis step: $L_{\A}(\A) = T$, $L_{\A}(\C) = L_{\A}(\G) = L_{\A}(\U) = F$

~~Recursive step: If $s \in S$ and $b \in B$, then $L_{\A}(sb) = L_{\A}(s)$.

Example where $L_{\A}$ evaluates to $T$ is \underline{\phantom{$\A\C\G$~\hspace{1in}}}

\vfill

Example where $L_{\A}$ evaluates to $F$ is \underline{\phantom{$\U\A\C\U$\hspace{1in}}}

\vfill


$H: S \to \{T, F\}$ where $H(s) = T$ for all $s$.

Truth set of $H$ is \underline{\phantom{$S$\hspace{1in}}}

\vfill
 \vfill
\end{document}