This is a query regarding the definition of Circuit Family and Language (in the same Context). The textbook definitions of each are:
Language: A function whose inputs and outputs are a finite bit of boolean strings (i.e. members of $\{0,1\}^*$) is a Boolean Function. A Boolean Function f whose output is a single bit is identified as follows: $L_f=\{x:f(x)=1\}⊆ \{0,1\}^*$. We call such sets ($L_f$) Languages or Decision Problems.
An alternative definition of Language (What is the difference between an algorithm, a language and a problem?): A language is simply a set of strings. If you have an alphabet, such as $Σ$, then $Σ^∗$ is the set of all words containing only the symbols in $Σ$. For example, $\{0,1\}^∗$ is the set of all binary sequences of any length. An alphabet doesn't need to be binary, though. It can be unary, ternary, etc. A language over an alphabet $Σ$ is any subset of $Σ^∗$.
Circuit Family: Let $T∶N→N$ be a function. A $T(n)$-size circuit family is a sequence $\{C_n \}_{(n∈N)}$ of Boolean circuits, where $C_n$ has $n$ inputs and a single output, and its size $|C_n |≤T(n)$ for every $n$. We say that a language L is in $SIZE(T(n))$ if there exists a $T(n)$-size circuit family $\{C_n\}_{(n∈N)}$ such that for every $x∈\{0,1\}^n,x∈L⇔C_n (x)=1$.
Query 1: Do the above definition mean: Any completely unrelated and arbitrary set of circuits such that the first circuit has 1 input, the second circuit has 2 inputs, third circuit has 3 inputs and so on (each circuit having exactly 1 output) qualify as a 'Circuit Family'? And do all the inputs that give output 1 form a 'Language' (as a set)?
The idea i am struggling with is the definition seems to imply there need not be any overarching logical relation between the circuits of various sizes to constitute a Circuit Family and a Language as long as they satisfy this simple input output size criteria? Is that correct or i am missing something?
Query 2: Given two circuit families $C_a$ and $C_b$. Lets us create a new circuit family $C_r$ as follows:
- For each input size $(n, n∈N)$ toss a random coin.
- If 0 $C_a(n)∈C_r$.
- If 1 $C_b(n)∈C_r$ where $C_a(n)$ and $C_b(n)$ represents circuits for input size $n$.
Does $C_r$ and the set of strings accepted by it represent a valid Circuit Family and Language respectively?